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

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

, the above is equivalent to the complementary slackness condition:
lambda_i^ast f_i(x^ast) = 0, ;; i=1,ldots,m.

KKT optimality conditions

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.

Optimality Conditions and Sensitivity

Complementary slackness

KKT optimality conditions

Primal solutions from dual variables

Examples