| # Slater Condition for Strong Duality Strong Duality > Slater Condition | Optimality conditions | Sensitivity | Applications 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: Minimum distance to an affine subspace. Dual of LP. Dual of QP. ## 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.