Optimality Conditions and Sensitivity

  • Complementary slackness

  • KKT optimality conditions

  • Primal solutions from dual variables

  • Examples

Complementary slackness

We consider a primal convex optimization problem (without equality constraints for simplicity):
 p^ast := min_x : f_0(x) ~:~ f_i(x) le 0, ;; i=1,ldots,m,
and its dual
 p^ast ge d^ast := max_{lambda} : g(lambda),
where g is the dual function
 g(lambda) := min_x : {cal L}(x,lambda) left(:= f_0(x) + sum_{i=1}^m lambda_i f_i(x)right).

We assume that the duality gap is zero: p^ast = d^ast, and that both primal and dual values are attained, by a primal-dual pair (x^ast,lambda^ast). (This is guaranteed for example if both the primal and dual are strictly feasible, in the weak sense of Slater’s.) We have
 p^ast = f_0(x^ast) = d^ast = g(lambda^ast) = min_x : {cal L}(x,lambda^ast) le {cal L}(x^ast,lambda^ast) le f_0(x^ast) = p^ast.
Thus, equalities hold in the above.

This implies that x^ast minimizes the function {cal L}(cdot,lambda^ast):
 x^ast in arg min_x {cal L}(x,lambda^ast).
If the functions f_0,ldots,f_m are differentiable, the above implies
 left. nabla_x {cal L}(x,lambda^ast)right|_{x=x^ast} := nabla f_0(x^ast) + sum_{i=1}^m lambda_i^ast nabla f_i(x^ast) = 0.
In addition, the equalities in (ref{eq:root-KKT-conds-L15}) imply
 sum_{i=1}^m lambda_i^ast f_i(x^ast) = 0.
Since lambda^ast ge 0, f_i(x^ast) le 0, i=1,ldots,m, the above is equivalent to the complementary slackness condition:
 lambda_i^ast f_i(x^ast) = 0, ;; i=1,ldots,m.

KKT optimality conditions

Assume that the functions f_0,ldots,f_m 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 (x^ast,lambda^ast).
 begin{array}{cr} f_i(x^ast) le 0, ;; i=1,ldots,m & mbox{(primal feasibility),}  lambda^ast ge 0 & mbox{(dual feasibility),}  lambda_i^ast f_i(x^ast) = 0, ;; i=1,ldots,m & mbox{(complementary slackness),}  left. nabla_x {cal L}(x,lambda^ast)right|_{x=x^ast} = 0 & mbox{(Lagrangian stationarity).} end{array}
The above development shows that for any problem (convex or not) for which strong duality holds, and primal and dual values are attained, the KKT conditions are necessary for a primal-dual pair (x^ast,lambda^ast) to be optimal.

If, in addition the problem is convex, then the conditions are also sufficient. To see this, note that the first two conditions imply that x^ast,lambda^ast are feasible for the primal and dual problems, respectively. Since {cal L}(cdot,lambda^ast) is convex, the fourth condition (which we called Lagrangian stationarity) states that x^ast is a minimizer of {cal L}(cdot,lambda^ast), hence
 g(lambda^ast) = min_x : {cal L}(x,lambda^ast) = {cal L}(x^ast ,lambda^ast) = f_0(x^ast) ,
where we used the third condition (complementary slackness) for the last equality. The above proves that the primal-dual pair (x^ast,lambda^ast) is optimal, since the corresponding gap is zero.

Primal solutions from dual variables

Assume that the problem has a zero duality gap, with dual values attained. Now assume that lambda^ast is optimal for the dual problem, and assume that the minimization problem
 min_x : {cal L}(x,lambda^ast).
has a unique solution x(lambda^ast) that is feasible for the primal problem. Then, x(lambda^ast) is optimal. Indeed, the fourth KKT condition (Lagrange stationarity) states that any optimal primal point minimizes the partial Lagrangian {cal L}(cdot,lambda^ast), so it must be equal to the unique minimizer x(lambda^ast).

This allows to compute the primal solution when a dual solution is known, by solving the above problem.