# Solve Karush–Kuhn–Tucker conditions

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)?

• I would look at the Simplex or Ellipsoid algorithms for solving LPs. – ml0105 Dec 22 '14 at 1:19
• yes but this does not work for NLPs, and the conditions hold sometimes even for non-convex functions. – user3613886 Dec 22 '14 at 1:39
• @user3613886 What problems do you have with the Karush-Kuhn-Tucker conditions ? – callculus Dec 22 '14 at 3:21
• It depends on the problem. There is no exist a general method. If your problem is LP (Simplex, Ellipsoids algorithms), SDP (Interior points, proximal methods), non-convex (relaxations), ... – Alex Silva Dec 22 '14 at 10:14
• @calculus the question is how to solve the system of equations and inequations from the KKT conditions? – user3613886 Dec 22 '14 at 11:20

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$

• thank you for your effort, but this is not the answer i was intending. I was asking how they can be solved by computers without enumerating all cases – user3613886 Dec 25 '14 at 4:19
• @user3613886 Then I misunderstood you. But if you solve it by a computer, why you don´t want to enumerate all cases. ? How do you want to influence what the computer is calculating ? In general: If you are lucky, then you have to enumerate only one case. – callculus Dec 25 '14 at 15:55
• where did you see this KKT conditions? In which book? – user441848 Jun 16 '18 at 20:56
• @user441848 You can read it on this site. Although it is in german the KKT-condition in the box should be clear. – callculus Jun 17 '18 at 3:26
• oh ok thank you, I'll try to understand. – user441848 Jun 17 '18 at 3:31