Karush-Kuhn-Tucker conditions - Mines Nancy

Motivation¶

In this section, we look for necessary and/or sufficient conditions for optimality of the constrained problem

\begin{split} \minimize&\quad f_0(x)\\ \text{subject to}&\quad f_i(x) \leq 0, \quad i = 1, \ldots, m\\ &\quad h_i(x) = 0, \quad i = 1, \ldots, p \end{split}

(1)

with Lagrange dual problem

\begin{split} \maximize&\quad g(\lambda, \nu) := \inf_{x\in \mathcal{D}} \left(f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p\nu_i h_i(x)\right)\\ \text{subject to}&\quad \lambda \geq 0 \end{split}

(2)

Recall that, for unconstrained problems, such necessary and / or sufficient conditions are discussed in Chapter 2.

Complementary Slackness¶

Let $x^\star$ and $(\lambda^\star, \nu^\star)$ be primal and dual optimal, respectively. Then

\begin{align*} f_0(x^\star) &= g(\lambda^\star, \nu^\star)&\text{(strong duality)}\\ &=\inf_{x} \left(f_0(x)+ \sum_{i=1}^m \lambda_i^\star f_i(x) + \sum_{i=1}^p \nu_i^\star h_i(x)\right)&\text{(def of $g$)}\\ &\leq f_0(x^\star)+ \sum_{i=1}^m \lambda_i^\star f_i(x^\star) + \sum_{i=1}^p \nu_i^\star h_i(x^\star)&\text{($\inf$ property)}\\ &\leq f_0(x^\star)&\text{($x^\star, \lambda^\star$ are feasible)} \end{align*}

(3)

Since by definition, $\sum_{i=1}^m \lambda_i^\star f_i(x^\star) \leq 0$ , we conclude that $\sum_{i=1}^m \lambda_i^\star f_i(x^\star) = 0$ and since each term in the sum is negative, one has the complementary slackness property

\lambda_i^\star f_i(x^\star) = 0, \quad i=1, \ldots, m

(4)

or in other terms,

\lambda_i^\star > 0 \Rightarrow f_i(x^\star) = 0 \Longleftrightarrow f_i(x^\star) < 0 \Rightarrow \lambda_i^\star = 0

(5)

This means that the $i$ -th optimal Lagrange multiplier $\lambda_i^\star$ is zero as long as the associated inequality constraint is inactive ( $f_i(x^\star) < 0$ ). Conversely, if $\lambda_i^\star > 0$ , this means the constraint is active ( $f_i(x^\star) = 0$ ).

KKT conditions¶

Under the assumptions above, we can formulate two KKT conditions for nonconvex and convex problems, respectively.

Theorem 1 (KKT conditions for nonconvex problems)

Let $x^\star$ and $(\lambda^\star, \nu^\star)$ be primal and dual optimal with zero duality gap. Then one has

Primal feasibility:
$\begin{align*} f_i(x^\star) \leq 0, &\quad i=1, \ldots, m \\ h_i(x^\star) = 0, &\quad i=1, \ldots, p \end{align*}$
(6)
Dual feasibility:
$\lambda_i^\star \geq 0, \quad i=1, \ldots, m$
(7)
Complementary slackness
$\lambda_i^\star f_i(x^\star) = 0, \quad i=1, \ldots, m$
(8)
Stationarity of the Lagrangian with respect to $x$
$\nabla_{x} L(x^\star, \lambda^\star, \nu^\star) = 0 \Longleftrightarrow \nabla f_0(x^\star) + \sum_{i=1}^m \lambda_i^\star \nabla f_i({x^\star}) +\sum_{i=1}^p \nu_i^\star \nabla h_i(x^\star) = 0$
(9)
These five conditions are known as Karush-Kuhn-Tucker conditions.

Hence, for any (differentiable) optimization problem where strong duality holds, KKT conditions are necessary conditions for optimality of the triplet $(x^\star, \lambda^\star, \nu^\star)$ .

For convex problems, the KKT conditions become sufficient. Recall that a general convex problem can be put into the form

\begin{split} \minimize&\quad f_0(x)\\ \text{subject to}&\quad f_i(x) \leq 0, \quad i = 1, \ldots, m\\ &\quad Ax = b \end{split}

(10)

Theorem 2 (KKT conditions for convex problems)

Consider the convex problem (10) and let $\tilde{x}$ and $(\tilde\lambda, \tilde\nu)$ satisfy the KKT conditions

Primal feasibility:
$\begin{align*} f_i(\tilde x) \leq 0, &\quad i=1, \ldots, m \\ A\tilde x = b \end{align*}$
(11)
Dual feasibility:
$\tilde\lambda_i \geq 0, \quad i=1, \ldots, m$
(12)
Complementary slackness
$\tilde\lambda_i f_i(\tilde x) = 0, \quad i=1, \ldots, m$
(13)
Stationarity of the Lagrangian with respect to $x$
$\nabla_{x} L(\tilde x, \tilde\lambda, \tilde\nu) = 0 \Longleftrightarrow \nabla f_0(\tilde x) + \sum_{i=1}^m \lambda_i \nabla f_i(\tilde{x}) + A^\top \tilde\nu = 0$
(14)
Then $\tilde x$ is primal optimal, $(\tilde \lambda, \tilde \nu)$ are dual optimal, with zero duality gap.

In other words, for a convex problem, if the triplet $(\tilde{x}, \tilde\lambda, \tilde\nu)$ satisfies KKT conditions then we have found optimal points and strong duality holds.

Understanding why KKT works:

the first two condition ensures that $\tilde{x}$ is primal feasible and $(\tilde{\lambda}, \tilde{\nu})$ are dual feasible
complementary slackness implies that $f_0(\tilde{x}) = L(\tilde{x}, \tilde{\lambda}, \tilde{\nu})$
stationarity of the Lagrangian with the fact that $L(\cdot, \tilde{\lambda}, \tilde{\nu})$ is convex show that $\tilde{x}$ minimizes the Lagrangian over $x$ . Thus by definition $g(\tilde{\lambda}, \tilde{\nu}) = L(\tilde{x},\tilde{\lambda}, \tilde{\nu})$ .
hence $f_0(\tilde{x}) = g(\tilde{\lambda}, \tilde{\nu})$ . Strong duality follows and $(\tilde{x}, \tilde{\lambda}, \tilde{\nu})$ are optimal.

In general, for convex problems KKT conditions are only sufficient. However, provided that strong duality holds, they become necessary and sufficient.

In particular, Slater’s condition implies strong duality and that the dual optimum is attained.

Proposition 1 generalizes the necessary and sufficient condition of unconstrained convex problems ( $\nabla f_0(x) = 0$ ) to the general constrained convex case.

Summary¶

Comments

strong duality (almost always) holds for convex problems
the dual problem may help to solve the primal problem very efficiently
duality and dual methods are abundant in optimization and play a very important role in modern optimization; this course is just a rough sketch of the tip of the iceberg!