Welcome to our community

Be a part of something great, join today!

Find the solution using the KKT conditions.

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,120
Hi!!! :eek:

Given then following problem:
$$ \min [-x_1 - (x_2 -9)^2]$$
subject to $$4x_1^2+x_2^2 \leq 400$$
I have to find the solution using the KKT conditions.

I have found that the solution is $(0,9)$. Is my result correct?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,866
Hi!!! :eek:

Given then following problem:
$$ \min [-x_1 - (x_2 -9)^2]$$
subject to $$4x_1^2+x_2^2 \leq 400$$
I have to find the solution using the KKT conditions.

I have found that the solution is $(0,9)$. Is my result correct?
Hey!! :eek:

I don't understand?? :confused:

How about for instance $(0,-9)$?
Doesn't it have a lower minimum while still satisfying the condition?
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,120
Hey!! :eek:

I don't understand?? :confused:

How about for instance $(0,-9)$?
Doesn't it have a lower minimum while still satisfying the condition?
Having the nonlinear problem:
$ \max f(x)$
$ g_i (x) \leq 0$
$x \geq 0$

the KKT conditions are:
$$μ_i \geq 0$$
$$\frac{\partial f}{\partial x_j}(x^*)-\sum_{i=1}^{p}μ_i \frac{\partial g_i}{\partial x_j}(x^*) \leq 0$$
$$x_j^*(\frac{\partial f}{\partial x_j}(x^*)-\sum_{i=1}^{p}μ_i \frac{\partial g_i}{\partial x_j}(x^*))=0$$
$$g_i(x^*) \leq 0$$
$$μ_i g_i (x^*) =0$$
$$x_j^* \geq 0$$

So the solution cannot have negative values.
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,866
Having the nonlinear problem:
$ \max f(x)$
$ g_i (x) \leq 0$
$x \geq 0$

the KKT conditions are:
$$μ_i \geq 0$$
$$\frac{\partial f}{\partial x_j}(x^*)-\sum_{i=1}^{p}μ_i \frac{\partial g_i}{\partial x_j}(x^*) \leq 0$$
$$x_j^*(\frac{\partial f}{\partial x_j}(x^*)-\sum_{i=1}^{p}μ_i \frac{\partial g_i}{\partial x_j}(x^*))=0$$
$$g_i(x^*) \leq 0$$
$$μ_i g_i (x^*) =0$$
$$x_j^* \geq 0$$

So the solution cannot have negative values.
Okay... how about (10, 0) then?
Better or worse?
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,120
Okay... how about (10, 0) then?
Better or worse?
(Thinking)
Since the objective function at the point (10,0) is -91, and with (0,9) it's 0, I assume that yours is better..

I did the following:
The KKT conditions for this proble are:
KKT1: $μ_1 \geq 0$
KKT2: $-1-μ_1 8x_1 \leq 0$
KKT3: $-2(x_2-9)-μ_1 2 x_2 \leq 0$
KKT4: $ x_1 (-1-μ_1 8x_1 )=0$
KKT5: $ x_2 (-2(x_2-9)-μ_1 2 x_2 )=0$
KKT6: $ 4x_1^2+x_2^2-400 \leq 0$
KKT7: $ μ_1 (4x_1^2+x_2^2-400 )=0$
KKT8: $ x_1 \geq 0$
KKT9: $ x_2 \geq 0$

Case1: $μ_1=0$
KKT4: $-x_1=0 \Rightarrow x_1=0$
KKT5: $-2x_2(x_2-9)=0 \Rightarrow x_2=0 \text{ or } x_2=9$
For $x_2=0$, at KKT3:$18 \leq 0$ that is not true, so $x_2 \neq 0$
Since, for $μ_1=0$, $x_1=0$ and $x_2=9$ all conditions are satisfied, $(0,9)$ is a solution. Then I showed that the function $f$ is concave, so this solution is unique.

Have I done something wrong? :confused:
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,725
(Thinking)
Since the objective function at the point (10,0) is -91, and with (0,9) it's 0, I assume that yours is better..

I did the following:
The KKT conditions for this proble are:
KKT1: $μ_1 \geq 0$
KKT2: $-1-μ_1 8x_1 \leq 0$
KKT3: $-2(x_2-9)-μ_1 2 x_2 \leq 0$
KKT4: $ x_1 (-1-μ_1 8x_1 )=0$
KKT5: $ x_2 (-2(x_2-9)-μ_1 2 x_2 )=0$
KKT6: $ 4x_1^2+x_2^2-400 \leq 0$
KKT7: $ μ_1 (4x_1^2+x_2^2-400 )=0$
KKT8: $ x_1 \geq 0$
KKT9: $ x_2 \geq 0$

Case1: $μ_1=0$
KKT4: $-x_1=0 \Rightarrow x_1=0$
KKT5: $-2x_2(x_2-9)=0 \Rightarrow x_2=0 \text{ or } x_2=9$
For $x_2=0$, at KKT3:$18 \leq 0$ that is not true, so $x_2 \neq 0$
Since, for $μ_1=0$, $x_1=0$ and $x_2=9$ all conditions are satisfied, $(0,9)$ is a solution. Then I showed that the function $f$ is concave, so this solution is unique.

Have I done something wrong? :confused:
You have found the unique point $(x_1,x_2) = (0,9)$ that maximises the objective function. But you want to minimise it. So it looks as though you need to consider Case2: $μ_1\ne0$.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,120
You have found the unique point $(x_1,x_2) = (0,9)$ that maximises the objective function. But you want to minimise it. So it looks as though you need to consider Case2: $μ_1\ne0$.
Ok...Thank you..!!! :eek: