Optimization

Weak and Strong Duality

Weak duality always bounds the primal by the dual; strong duality closes the gap under convexity and a constraint qualification.

The duality gap

Every optimization problem has a dual whose optimum d* never exceeds the primal optimum p*. The difference p* - d* is the duality gap. Weak duality (d* <= p*) holds universally. Strong duality (d* = p*) holds under additional conditions and is what lets the dual solve the primal.

Weak duality

Weak duality follows directly from the definition of the dual function as an infimum of the Lagrangian. It requires no assumptions, so it applies to nonconvex, discrete, and otherwise hard problems. This makes it a general tool for producing lower bounds, for example in branch-and-bound where dual bounds prune the search tree.

When strong duality holds

Convex problems satisfying Slater's condition (a strictly feasible interior point exists) have zero gap.
All feasible, bounded linear programs have zero gap.
Certain nonconvex problems, such as the trust-region subproblem, also enjoy strong duality despite nonconvexity.

Slater's condition

For a convex problem, Slater's condition asks that there exist a point strictly satisfying all inequality constraints (with equality constraints met). When it holds, strong duality follows and optimal dual multipliers exist. It is a mild requirement met by most well-posed convex models.

Consequences of strong duality

With zero gap, a primal-dual pair certifies optimality: if you exhibit feasible x and feasible (mu, nu) with equal objective values, both are optimal. Strong duality also validates the KKT conditions as sufficient and underlies primal-dual algorithms that drive the gap to zero as a stopping test.

python

# Weak duality: d* <= p*  (always)
# Strong duality: d* == p*  (convex + Slater, or LP feasible & bounded)
# gap = p* - d* is the certificate of suboptimality

The duality gap gives a rigorous, provable measure of how far a computed solution can possibly be from the true optimum.