## Optimality Conditions and SensitivityComplementary slackness KKT optimality conditions Primal solutions from dual variables Examples
## Complementary slacknessWe consider a primal convex optimization problem (without equality constraints for simplicity):
We assume that the duality gap is zero: , and that both primal and dual values are attained, by a primal-dual pair . (This is guaranteed for example if both the primal and dual are strictly feasible, in the weak sense of Slater’s.) We have
This implies that minimizes the function :
## KKT optimality conditionsAssume that the functions are differentiable. Consider the so-called KKT (The acronym comes from the names Karush, Kuhn and Tucker, researchers in optimization around 1940-1960) conditions on a primal-dual pair .
If, in addition the problem is convex, then the conditions are also ## Primal solutions from dual variablesAssume that the problem has a zero duality gap, with dual values attained. Now assume that is optimal for the dual problem, and assume that the minimization problem
This allows to compute the primal solution when a dual solution is known, by solving the above problem. ## ExamplesXXX |