Slater Condition for Strong Duality
Primal and dual problem
Strong duality
Slater’s theorem
Geometry
Primal and Dual Problems
We consider a convex constrained optimization problem in standard form:
where are convex functions, , define the affine inequality constraints.
To this problem we associate the Lagrangian, wich is the function with values
The corresponding dual function is the function with values
Recall that the function is concave, and that it can assume values. Its domain is
Finally, the dual problem reads
Note that the sign constraints are imposed only on the dual variables corresponding to inequality constraints. Note also that there are (possibly) implicit constraints in the above problem, since we must have .
Strong duality
The theory of weak duality seen here states that . This is true always, even if the original problem is not convex. We say that strong duality holds if .
Slater’s sufficient condition for strong duality
Slater’s theorem provides a sufficient condition for strong duality to hold. Namely, if
The primal problem is convex;
It is strictly feasible, that is, there exists such that
then, strong duality holds: , and the dual problem is attained. (Proof)
Example:
Geometry
The geometric interpretation of weak duality shows why strong duality holds for a convex, strictly feasible problem. For simplicity again, we consider the case with no equality constraints, and a single convex constraint.
Recall that we can express the primal problem with two new scalar variables , as follows:
where
Since the primal problem is convex, that is, and are convex functions, the above set is convex.
Strict primal feasibility means that the set cuts ‘‘inside’’ the right-half of the -plane. If that property holds, then we can attain the optimal point by a tangent with a finite strictly negative slope. One implication is that , that is, strong duality holds. This slope is precisely the optimal dual variable, ; thus the dual problm is attained.
|