Convex programs, duality gap, and interior point methods
A convex program minimizes a convex objective over a convex feasible set. The defining property: any local minimum is automatically global. This makes convex optimization tractable — efficient algorithms with guaranteed convergence exist. Interior point methods, in particular, solve convex programs in polynomial time.
Toggle between convex and non-convex problems. In the convex case, there is a single minimum and any descent method finds it. In the non-convex case, local minima trap algorithms.
Convex feasible region with convex objective. The single optimum is both local and global.
Key insight: Recognizing convexity is the most important step in optimization. If your problem is convex, you are guaranteed efficient solutions. If not, you face fundamentally harder challenges.
The duality gap is the difference between primal and dual objective values. Weak duality guarantees the gap is non-negative. Strong duality, which holds for convex programs under mild conditions, says the gap closes to zero at optimality.
The primal objective decreases while the dual objective increases. The gap between them is always non-negative (weak duality) and converges to zero (strong duality).
Key insight: A zero duality gap provides a certificate of optimality: you know you have found the best possible solution without needing to search further.
Interior point methods traverse the interior of the feasible set along a smooth central path, unlike simplex which walks along edges. A barrier function keeps iterates away from the boundary; as the barrier parameter shrinks, the path converges to the optimum.
The interior point method (solid indigo) curves smoothly through the polytope interior as the barrier parameter decreases. The simplex method (dashed gray) walks along edges. Both converge to the same optimum.
Key insight: Interior point methods solve LPs and convex programs in polynomial time. They revolutionized optimization in the 1980s and are the algorithm of choice for large-scale problems.