1
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ I would look at the Simplex or Ellipsoid algorithms for solving LPs. $\endgroup$ – ml0105 Dec 22 '14 at 1:19
  • $\begingroup$ yes but this does not work for NLPs, and the conditions hold sometimes even for non-convex functions. $\endgroup$ – user3613886 Dec 22 '14 at 1:39
  • $\begingroup$ @user3613886 What problems do you have with the Karush-Kuhn-Tucker conditions ? $\endgroup$ – callculus Dec 22 '14 at 3:21
  • $\begingroup$ 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), ... $\endgroup$ – Alex Silva Dec 22 '14 at 10:14
  • $\begingroup$ @calculus the question is how to solve the system of equations and inequations from the KKT conditions? $\endgroup$ – user3613886 Dec 22 '14 at 11:20
4
$\begingroup$

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$

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$ – user3613886 Dec 25 '14 at 4:19
  • $\begingroup$ @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. $\endgroup$ – callculus Dec 25 '14 at 15:55
  • $\begingroup$ where did you see this KKT conditions? In which book? $\endgroup$ – user441848 Jun 16 '18 at 20:56
  • $\begingroup$ @user441848 You can read it on this site. Although it is in german the KKT-condition in the box should be clear. $\endgroup$ – callculus Jun 17 '18 at 3:26
  • $\begingroup$ oh ok thank you, I'll try to understand. $\endgroup$ – user441848 Jun 17 '18 at 3:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.