Convex programs, duality gap, and interior point methods
When a problem is convex, any valley you find is the deepest one. That single fact makes convex problems the ones we can solve reliably and fast.
Toggle between Convex and Non-convex mode. Count the minima: one in the convex case, several traps in the non-convex one.
Convex feasible region with convex objective. The single optimum is both local and global.
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.
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.
Pick a convergence speed and press Play. The primal value falls, the dual value rises, and the gap between them shrinks to zero.
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).
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.
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.
Press Auto-Play or Next Step to watch both methods race on the same polytope: simplex hops along the edges while the interior point path curves through the middle.
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.
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.
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.
Spot a mistake or have an idea?