KKT conditions

Second-order conditions

Example 1

A simple example, adapted from http://www.math.ubc.ca/~israel/m340/

Consider the problem \begin{align*} \max\ & f(x, y) = xy \\ \mbox{s.t. } & x + y^2 \leq 2 \\ & x, y \geq 0 \end{align*}

Note that the feasible region is bounded, and $f(x,y)$ is continuous, so a global maximum exists. Rewrite the problem as \begin{align*} \min\ & -xy \\ \mbox{s.t. } & x + y^2 -2 \leq 0 \\ & -x \leq 0\\ & -y \leq 0 \end{align*}

The KKT conditions can be written as \begin{align*} -y + \lambda_1 - \lambda_2 &= 0 \\ -x + 2\lambda_1y - \lambda_3 &= 0 \\ x + y^2 -2 &\leq 0 \\ -x &\leq 0\\ -y &\leq 0 \\ \lambda_1(x + y^2 -2) &= 0 \\ \lambda_2(-x) &= 0\\ \lambda_3(-y) &= 0 \\ \lambda_i &\geq 0,\ i = 1,2,3 \end{align*}

or \begin{align*} -y + \lambda_1 - \lambda_2 &= 0 \\ -x + 2\lambda_1y - \lambda_3 &= 0 \\ x + y^2 -2 &\leq 0 \\ \lambda_1(x + y^2 -2) &= 0 \\ \lambda_2x &= 0\\ \lambda_3y &= 0 \\ \lambda_i &\geq 0,\ i = 1,2,3 \\ x, y &\geq 0\\ \end{align*}

Suppose $\lambda_1 = 0$. Then \begin{align*} \lambda_2 &= -y \\ \lambda_3 &= -x \end{align*} As $x, y, \lambda_2, \lambda_3 \geq 0$, this implies $x = y = \lambda_1 = \lambda_2 = \lambda_3 = 0$.

But $f(0,0) = 0$, and it is clearly not a minimum as for instance $f(1,1) = -1$, and $(1,1)$ is feasible.

Take $\lambda_1 \ne 0$. Then, we must have $x + y^2 - 2 = 0$, and therefore $x$ or $y$ is strictly positive.

Suppose $x > 0$. Then $\lambda_2 = 0$ and $\lambda_1 = y$. Since $\lambda_1 \ne 0$, $\lambda_3 = 0$, and $x = 2\lambda_1y = 2y^2$. Thus $$ 0 = x + y^2 - 2 = x + \frac{x}{2} - 2 = \frac{3x}{2} - 2 $$ and $$ x = \frac{4}{3},\ y = \sqrt{\frac{2}{3}} $$

Suppose $x = 0$, $y > 0$. Thus, $y = \sqrt{2}$ and $\lambda_3 = 0$. But this also implies $\lambda_1 = 0$, while we have assumed $\lambda_1 \ne 0$. Therefore, this case cannot happen.

Therefore, we have two KKT points: $\left( \frac{4}{3}, \sqrt{\frac{2}{3}} \right)$ and $(0, 0)$. $\left( \frac{4}{3}, \sqrt{\frac{2}{3}} \right)$ is the minimizer of the function.

Can we verify it using second-order optimality conditions? First, express $\nabla^2_{xx} L(x, \lambda)$. We have $$ \nabla^2_{xx} L(x, \lambda) = \begin{pmatrix} 0 & -1 \\ -1 & 2\lambda_1 \end{pmatrix} $$ Since the first principal minor is 0, the matrix cannot be positive definite.

For $(0, 0)$, we have two active constraints: \begin{align*} -x &= 0 \\ -y &= 0 \end{align*} The Jacobian associated to these constraints is $$ J = \begin{pmatrix} -1 & 0 \\ 0 & -1 \\ \end{pmatrix} $$ and the LICQ is obviously verified. We can also check it by computing the rank of $J$:

In [1]:
using LinearAlgebra

J = [-1 0; 0 -1]
rank(J)
Out[1]:
2
In [3]:
J = [-1 1+1e-12; 1 -1]
rank(J,1e-8), rank(J)
Out[3]:
(1, 2)
In [6]:
J = [-1 1+1e-12; 1-1e-8 -1]
rank(J,1e-8), rank(J)
Out[6]:
(1, 2)
In [7]:
eigen(J)
Out[7]:
Eigen{Float64,Float64,Array{Float64,2},Array{Float64,1}}
eigenvalues:
2-element Array{Float64,1}:
 -1.9999999950005      
 -4.9995000361846564e-9
eigenvectors:
2×2 Array{Float64,2}:
 -0.707107  0.707107
  0.707107  0.707107

The second-order conditions involve the computation of $d^T \nabla^2_{xx} L(x^*, \lambda^*)d$ for all $d \in N^+$, where $$ N^+ = \left\lbrace d \ne 0 \,\bigg|\, \begin{matrix} d^T \nabla g_i(x^*) = 0, & i \in \mathcal{E} \\ d^T \nabla g_i(x^*) \leq 0, & i \in \mathcal{A}(x^*) \cap \mathcal{I} \end{matrix} \right\rbrace $$ Unfortunately as we have also $\lambda^* = 0$ while $\mathcal{A}(x^*) \ne \emptyset$, the strict complementarity condition does not hold. It is then not trivial to characterize $N^+$.

It is nevertheless easy to find a $d \in N^+$ such that the second-order conditions are violated.

Note that the Jacobian matrix is $$ J(x) = \begin{pmatrix} \nabla^T g_i(x^*), \text{ for } i \in \mathcal{A}(x^*) \end{pmatrix} $$

Take indeed $d = (1,1)$. Then $Jd$ gives

In [9]:
d = [1.0; 1.0]
J = [-1.0 0; 0 -1.0]
J*d
Out[9]:
2-element Array{Float64,1}:
 -1.0
 -1.0

If we compute $d^T\nabla^2_{xx} L(x,\lambda) d$, we obtain

In [10]:
D2L = [0 -1.0; -1.0 0]
d'*D2L*d
Out[10]:
-2.0

In others terms, (0,0) is not a second-order critical solution.

The Lagrange multipliers associated to $\left( \frac{4}{3}, \sqrt{\frac{2}{3}} \right)$ is $$ \lambda^* = \begin{pmatrix} \sqrt{\frac{2}{3}} \\ 0 \\ 0 \end{pmatrix} $$ and the active constraint is \begin{align*} x + y^2 - 2 &= 0 \end{align*} The Jacobian of the active set at $\left( \frac{4}{3}, \sqrt{\frac{2}{3}} \right)$ is $$ J = \begin{pmatrix} 1 & 2\sqrt{\frac{2}{3}} \\ \end{pmatrix} $$ and again, it is trivial to verify the LICQ.

But now, $$ \nabla^2_{xx} L(x^*, \lambda^*) = \begin{pmatrix} 0 & -1 \\ -1 & 2\sqrt{\frac{2}{3}} \end{pmatrix} $$

and the strict complementarity condition holds.

Thus, $$ N^+ = \left\{ d \ne 0 \,|\, Jd = 0 \right\}. $$

Therefore, we have to consider the vectors $d \in \mathbb{R}^n$ such that $$ d^T \begin{pmatrix} 1 \\ 2\sqrt{\frac{2}{3}} \end{pmatrix} = 0 $$ In other words, $d \in Null(J)$, $d \ne 0$, where $$ J = \begin{pmatrix} 1 & 2\sqrt{\frac{2}{3}} \end{pmatrix} $$

In [6]:
A = [1 2*sqrt(2/3) ]
w = nullspace(A)
Out[6]:
2×1 Array{Float64,2}:
 -0.8528028654224418
  0.5222329678670935

$w$ is a basis vector of $A$, of norm equal to 1:

In [7]:
norm(w)
Out[7]:
1.0

But

In [8]:
D2L[2,2] = 2*sqrt(2/3)
w'*D2L*w
Out[8]:
1×1 Array{Float64,2}:
 1.33608531424537

Let $d = \sum_i α_iw_i$, $d \ne 0$. Then $$ d^T \nabla^2_{xx} L(x,\lambda) d = \sum_i α_i^2w_i^T \nabla^2_{xx} L(x,\lambda) w_i > 0. $$

The necessary and sufficient second-order optimality conditions are then satisfied.

Example 2

Use the Karush-Kuhn-Tucker conditions to solve \begin{align*} \max\ & KL \\ \mbox{subject to } & 4K + L \leq 8 \\ & K, L \geq 0 \end{align*}

The KKT conditions are \begin{align*} L − 4\lambda_1 + \lambda_2 &= 0 \\ K − \lambda_1 + \lambda_3 &= 0 \\ \lambda_1(8 − 4K − L) &= 0 \\ \lambda_2K &= 0 \\ \lambda_3L &= 0 \\ 4K + L &\leq 8 \\ K,L, \lambda_1, \lambda_2, \lambda_3 &\geq 0 \end{align*}

Case 1.

If $\lambda_1 = 0$, the first KKT condition says $L + \lambda_2 = 0$, which implies $L = \lambda_2 = 0$, and the second says $K + \lambda_3 = 0$, which implies $K = \lambda_3 = 0$. The KKT conditions are indeed satisfied with $K = L = \lambda_1 = \lambda_2 = \lambda_3 = 0$, and the objective value at K = L = 0 is 0.

Case 2

If $\lambda_1 > 0$, $4K + L = 8$. Thus at least one of $K$ and $L$ is positive, implying that $\lambda_2$ or $\lambda_3$ is 0. If $\lambda_2 = 0$, $L = 4\lambda_1 > 0$, but that implies $\lambda_3 = 0$. Similarly, if $\lambda_3 = 0$, $K = \lambda_1 > 0$, but that implies $\lambda_2 = 0$. So we must have $\lambda_2 = \lambda_3 = 0$, $L = 4\lambda_1$ and $K = \lambda_1$. Then $4K + L = 8$, $K = \lambda_1$, $L = \lambda_1$, implying $4\lambda_1 + 4\lambda_1 = 8$, so $\lambda_1 = 1$, $K = 1$ and $L = 4$. The KKT conditions are satisfied with $K = 1$, $L = 4$, $\lambda_1 = 1$, $\lambda_2 = \lambda_3 = 0$, and the objective value is 4.

In [ ]: