2
$\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
    Commented Dec 22, 2014 at 1:19
  • $\begingroup$ yes but this does not work for NLPs, and the conditions hold sometimes even for non-convex functions. $\endgroup$ Commented Dec 22, 2014 at 1:39
  • $\begingroup$ @user3613886 What problems do you have with the Karush-Kuhn-Tucker conditions ? $\endgroup$ Commented Dec 22, 2014 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
    Commented Dec 22, 2014 at 10:14
  • $\begingroup$ @calculus the question is how to solve the system of equations and inequations from the KKT conditions? $\endgroup$ Commented Dec 22, 2014 at 11:20

1 Answer 1

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$ Commented Dec 25, 2014 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$ Commented Dec 25, 2014 at 15:55
  • $\begingroup$ where did you see this KKT conditions? In which book? $\endgroup$
    – user441848
    Commented Jun 16, 2018 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$ Commented Jun 17, 2018 at 3:26
  • 1
    $\begingroup$ oh ok thank you, I'll try to understand. $\endgroup$
    – user441848
    Commented Jun 17, 2018 at 3:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .