MHB Find the solution using the KKT conditions.

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Conditions
AI Thread Summary
The discussion revolves around solving a minimization problem using the KKT conditions. The initial proposed solution of (0,9) is confirmed as satisfying the KKT conditions, but it is pointed out that this point maximizes the objective function instead of minimizing it. Participants suggest exploring other potential solutions, such as (10,0) and (0,-9), to find a lower minimum while adhering to the constraints. Ultimately, it is noted that the unique solution found may not be the correct one for minimization, prompting a reconsideration of the KKT conditions under different scenarios. The conversation highlights the importance of correctly applying the KKT conditions to achieve the desired optimization outcome.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hi! :o

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?
 
Mathematics news on Phys.org
mathmari said:
Hi! :o

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! :o

I don't understand?? :confused:

How about for instance $(0,-9)$?
Doesn't it have a lower minimum while still satisfying the condition?
 
I like Serena said:
Hey! :o

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.
 
mathmari said:
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?
 
I like Serena said:
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:
 
mathmari said:
(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$.
 
Opalg said:
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..! :o
 
Back
Top