Strong Duality & Slater's Condition

Weak duality is free; closing the gap costs one strictly feasible point.

The idea

Definition (Strong duality).

A problem has strong duality when $d^{\star} = p^{\star}$: the best dual bound equals the primal optimal value.

Weak duality, from The Lagrange Dual, guarantees $d^{\star} \le p^{\star}$ for every problem; when equality holds, solving the dual solves the primal, which is worth having because the dual is a concave maximization whatever the primal was, and is often the easier problem.

Strong duality is not automatic, and convexity alone does not guarantee it. What does is a constraint qualification: an extra condition on the problem beyond convexity. The standard one is Slater's.

Theorem (Slater's condition).

Suppose the problem is convex, meaning every $f_{i}$ is convex and every equality constraint is affine. If some point of the domain is strictly feasible — it satisfies $f_{i}(x) < 0$ for every inequality constraint, together with the equalities — then strong duality holds and the dual optimum is attained.

Strict feasibility rules out the geometry in which gaps arise: plain feasibility permits a feasible set consisting of a single point or a lower-dimensional slice. One refinement: a constraint that is itself affine needs only $f_{i}(x) \le 0$ rather than strict inequality, so for a linear program Slater's condition asks for nothing beyond a feasible point.

Ways to work on it

• Walkthrough. When the primal and dual optima coincide, and the strict-feasibility condition that guarantees it.
• Proof. Prove strong duality with a separating-hyperplane argument.
• Practice. Decide whether strong duality holds across linear and convex examples.
• Hardest. A fully convex problem with a positive duality gap, and the geometry behind it.

Not sure where to start? Take the ten-question placement test.