Strong Duality

Optimization · Axiom Academy

LESSON Strong Duality in Convex Optimization Understanding when and why the duality gap vanishes in convex optimization problems 1. Strong Duality: Closing the Gap In optimization, we often work with a primal problem and its corresponding dual problem . Strong duality occurs when the optimal values of these two problems are equal. Without strong duality, we have weak duality : d* ≤ p* (the dual optimal is always a lower bound on the primal optimal). Strong duality closes this gap completely. 2. Slater's Condition: The Key to Strong Duality For convex optimization problems, Slater's condition is a simple constraint qualification that guarantees strong duality. If the problem is convex and Slater's condition holds, then strong duality is guaranteed. This is why Slater's condition is so important in practice. 3. Geometric View of the Duality Gap The duality gap can be visualized as the vertical distance between the primal and dual objective functions. As we approach optimality, this gap closes. When strong duality holds, the primal and dual curves meet at the optimal point, with zero gap. This geometric picture helps us understand why strong duality is so powerful. 4. Complementary Slackness at Optimality When strong duality holds, the complementary slackness conditions characterize the relationship between primal and dual optimal solutions.

This is the written version of the interactive lesson above. See the full Optimization course.