Convex Optimization
When the objective and feasible set are convex, every local minimum is global and efficient solvers guarantee the optimum.
The central fact
A convex optimization problem minimizes a convex function over a convex set. Its defining virtue is that any local minimum is also a global minimum, and a point is optimal if and only if it satisfies simple stationarity conditions. This removes the central difficulty of general optimization, where local minima and saddle points trap solvers.
Standard form
minimize f0(x) subject to f_i(x) <= 0 for convex f_i and A x = b for affine equality constraints. The feasible set, an intersection of convex sublevel sets and an affine subspace, is convex. Linear programs, quadratic programs, second-order cone programs, and semidefinite programs are all special cases.
Optimality conditions
For an unconstrained differentiable convex f, x* is optimal exactly when grad f(x*) = 0. With constraints, the KKT conditions are both necessary and sufficient under mild constraint qualifications. This equivalence is what makes convex problems reliably solvable.
Why convexity is powerful
- Global optimality is certified, not just hoped for.
- Duality gives lower bounds and optimality certificates (see Lagrangian duality).
- Interior-point methods solve large instances in polynomial time to high accuracy.
Recognizing convexity
Convexity is preserved under nonnegative weighted sums, composition with affine maps, and pointwise maximum of convex functions. Recognizing that a problem is convex, or reformulating it to be, is often the hardest and most valuable modeling step. Disciplined convex programming frameworks check convexity automatically from a set of rules.
Convex subproblems appear throughout engineering design, control, and the surrogate-model fitting used to explore complex physical systems.