14 Strong Duality
Strong Duality
We examine the concept of duality in the context of a convex optimization problem.
For any minimization problem, weak duality allows us to form a dual problem which provides a lower bound on the original problem. The dual problem is always convex (it is a concave maximization problem).
We say that strong duality holds if the primal and dual optimal values coincide. In general, strong duality does not hold. However, if a problem is convex, and strictly feasible, then the value of the primal is the same as that of the dual, and the dual problem is attained. This is in essence Slater’s theorem. If in addition the dual is strictly feasible, then both problems are attained.
For convex problems where strong duality holds, and both primal and dual optimal values are attained, we can proceed to derive necessary and sufficient conditions for optimality, which are more amenable to algorithms than the supporting hyperplane conditions given here. At optimum, the variables of the dual problem can be interpreted as sensitivities of the optimal value with respect to a class of perturbations. This is one important benefit of duality for engineering problems.
Strong duality for convex problems has a number of important applications, including for solving large-scale convex problems over a cluster of computers.
Outline