Solve Karush–Kuhn–Tucker conditions

Question

solving a constrained optimizing problem with equality constraints can be done with the lagrangian multiplier. (http://en.wikipedia.org/wiki/Lagrange_multiplier) This approach leads to a system of equations which can then be solved with for example newton-method.

if you have a problem with inequality constraints. The lagrange multiplier can be generalized to the Karush–Kuhn–Tucker conditions (http://en.wikipedia.org/wiki/Karush–Kuhn–Tucker_conditions#Necessary_conditions) This lead to solving a system of equations, but also inequalities. What method can be used to solve the inequalities? (Does also newton-method work somehow)?

Answer 1

A problem could be

$\texttt{max} \ f(x,y)=-(x-1)^2-(y-1)^2$ under the constraints $x+y\leq 1$ and $x,y\geq 0.$

The lagrange function then is:

$L(x,y,\lambda )=-(x-1)^2-(y-1)^2+\lambda (1-x-y)$

The expression in the brackets of $\lambda ()$ has to be greater or equal to zero.

The KKT conditions are:

$\frac{\partial L}{\partial x}=-2(x-1)-\lambda\leq 0 \quad (1), \quad \frac{\partial L}{\partial y}=-2(y-1)-\lambda \leq 0 \quad (2)$

$\frac{\partial L}{\partial \lambda}=1-x-y\leq 0\quad (3), \quad x\cdot \frac{\partial L}{\partial x}=-x\left( 2(x-1)+\lambda\right)= 0\quad (4)$

$y\cdot \frac{\partial L}{\partial y}=-y(2(y-1)+\lambda) = 0 \quad (5), \quad \lambda\cdot \frac{\partial L}{\partial \lambda}=\lambda(1-x-y)=0 \quad (6), \quad x,y,\lambda \geq 0 \quad (7)$

Now you check the two cases $\lambda=0$ and $\lambda \neq 0 $

• Case 1: $\lambda=0$

For (4) and (5) you would have 4 possible solutions $(x,y,\lambda)$:$(0,0,0),(1,0,0),(0,1,0),(1,1,0) $

None of these solutions satisfies the conditions (1),(2) and (3) simultaneously.

• Case 2: $\lambda\neq 0$

Because of (6) we have $1-x-y=0$

If $x=0$, then $y=1$. Inserting the values in (5): $-1(0-\lambda)=\lambda=0$ Because of $\lambda \neq 0$ (case 2) we have a contradiction.

If $x=1$, then $y=0$. Inserting the values in (4): $-1(0-\lambda)=\lambda=0$ Because of $\lambda \neq 0$ (case 2) we have a contradiction.

We can conclude, that $x,y \neq 0$. Because of (4) and (5) we have the two equations.

$2x-2-\lambda=0$

$2y-2-\lambda=0$

Substracting the second equation by the first equation.

$2x-2y=0 \Rightarrow 2x=2y \Rightarrow x=y$

With (6) and $\lambda\neq 0$ we get $1-x-x=0 \Rightarrow 1=2x \Rightarrow x=\frac{1}{2}$ and $y=\frac{1}{2}$ By using (5) we can calculate $\lambda$.

$2\cdot \left(\frac{1}{2}-1\right)+\lambda=0\Rightarrow \lambda=1$