Convex Optimization

Convex optimization is the study of minimizing convex functions over convex sets, a class of problems for which local optima are global and efficient algorithms exist.

Definition

A convex optimization problem minimizes a convex objective subject to convex inequality constraints and affine equality constraints; the feasible set is convex, which ensures that any local minimum is also a global minimum.

Scope

This topic covers convex sets and functions, recognition and modeling of convex problems, linear, quadratic, second-order cone, and semidefinite programs, Lagrangian duality and the Karush-Kuhn-Tucker conditions for convex problems, and interior-point and first-order algorithms with their complexity guarantees.

Core questions

• How can a problem be recognized or reformulated as convex?
• Why does convexity guarantee that local optima are global?
• What does duality reveal about a convex problem and its solution?
• Which algorithms solve convex problems efficiently and with what guarantees?

Key theories

Global optimality of convex problems

Because a convex function over a convex set has no spurious local minima, any locally optimal point is globally optimal, making convex problems reliably solvable.

Lagrangian duality and KKT conditions

Every convex problem has an associated dual problem providing optimality certificates, and under constraint qualifications the Karush-Kuhn-Tucker conditions are necessary and sufficient for optimality.

Interior-point methods

Interior-point methods follow a central path through the interior of the feasible region, solving convex problems including semidefinite programs in provably polynomial time.

Clinical relevance

Convex optimization is pervasive in machine learning, signal and image processing, control, finance, and engineering design, because many estimation and decision problems can be cast as convex programs and solved reliably at scale.

History

The field rests on the convex analysis systematized by Rockafellar around 1970. Karmarkar's 1984 interior-point method and the subsequent theory of Nesterov and Nemirovski showed that broad classes of convex problems are solvable in polynomial time, sparking the modern, modeling-driven approach to convex optimization.

Key figures

• R. Tyrrell Rockafellar
• Stephen Boyd
• Yurii Nesterov
• Narendra Karmarkar

Seminal works

• boyd2004
• rockafellar1970

Frequently asked questions

Why prefer convex models when possible?

Convex problems come with a guarantee that any solution found is globally optimal and with mature, efficient algorithms. Nonconvex models may trap solvers in inferior local optima, so a great deal of applied work goes into reformulating problems convexly.

Is linear programming a kind of convex optimization?

Yes. A linear program minimizes a linear objective over a polyhedron, and both linear functions and polyhedra are convex, so linear programming is a special, particularly well-understood case of convex optimization.