1
$\begingroup$

max: $10x_1-2x_1^2-x_1^3+8x_2-x_2^2$
s.t.
$x_1+x_2≤2$
$x_1≥0$
$x_2≥0$

I'm supposed to write down the KKT conditions, show that (-1,-1) is not optimal and to find the solution to this problem.

This is what I did so far:
$-x_1<0$
$-x_2<0$

Ignoring the $x_2$ constraint, since linear dependency is present. Hence I formulated these equations:

$L(x_1,x_2,μ_1,μ_2):10x_1-2x_1^2-x_1^3+8x_2-x_2^2-μ_1*(x_1+x_2-2)-μ_2*(-x_1)=0$

$L(\frac{δL}{δx_1})=10-4x_1-3x_1^2-μ_1+μ_2=0$
$L(\frac{δL}{δx_2})=8-2x_2-μ_1=0$

Complementary slackness conditions:

$μ_1*(x_1+x_2-2)=0$
$μ_2*(-x_1)=0$

This would lead to four different cases:

1st: $μ_1=0$ & $μ_2=0$
2nd: $μ_1=0$ & $(-x_1)=0$
3rd: $μ_2=0$ & $(x_1+x_2-2)=0$
4th: $(x_1+x_2-2)=0$ & $(-x_1)$

I spend so many hours try to figure it out. Is this so far correct? If not, could you point out what's wrong? Thanks in advance!

$\endgroup$
0

1 Answer 1

1
$\begingroup$

First of all, you're missing a $\mu_3$ as such \begin{equation} L(x_1,x_2,\mu)= - \Big( 10x_1 - 2x_1^2 - x_1^3 + 8x_2 - x_2^2 \Big) + \mu_1 (x_1 + x_2 - 2) - \mu_2 x_1 - \mu_3 x_2 \end{equation}

Take that $3^{rd}$ one over there. Let's try $$x_1 + x_2 = 2 \tag{0}$$ and see what happens. Also take $\mu_2 = \mu_3 = 0$. Redoing everything as you did, we get:

\begin{align} 10 -4x_1 - 3x_1^2 - \mu_1+\mu_2 &= 0\\ 8 - 2x_2 - \mu_1+\mu_3 &= 0\\ \mu_1 (x_1 + x_2 - 2) &= 0 \\ \mu_2x_1 = \mu_3x_2 &= 0 \end{align} Now let's pick $x_1+x_2 =2$ , which means $\mu_1$ is a free parameter, and also let's pick $\mu_2 = \mu_3= 0$, which leads us to \begin{align} 10 -4x_1 - 3x_1^2 - \mu_1 &= 0 \tag{1}\\ 8 - 2x_2 - \mu_1 &= 0 \tag{2}\\ x_1 + x_2 &= 2 \end{align} Thus equation (2) in KKT tells us that $$x_2 = \frac{8-\mu_1}{2}$$ Now for $x_1$, just solve the quadratic equation, you shall get $x_1 = \frac{-4 \pm \sqrt{136 - 12\mu_1}}{6}$. Choosing the positive one, because the optimization problem restricts us to positive $x_1$'s. Hence $$x_1 = \frac{-4 + \sqrt{136 - 12\mu_1}}{6}$$ Now, replace $x_1 + x_2 = 2$ and solve for $\mu_1$, \begin{equation} \frac{-4 + \sqrt{136 - 12\mu_1}}{6}+\frac{8-\mu_1}{2}=2 \end{equation} Solving the above for $\mu_1$ and picking the positive solution gives $\mu_1 = \frac{36 + \sqrt{3888}}{18}$. Replacing in $x_1,x_2$, we get \begin{equation} x_1 = \frac{-4 + \sqrt{136 - 12\frac{36 + \sqrt{3888}}{18}}}{6} > 0 \end{equation} and \begin{equation} x_2 = \frac{8-\mu_1}{2} = \frac{8 - \frac{36 \pm \sqrt{3888}}{18}}{2} > 0 \end{equation} So, both $x_1,x_2$ are positive and add up to $2$. This is then an optimal solution. Are there any others? Well if you pick $\mu_k = 0$ for all $k$, then it is clear we will get $x_2=4$, hence $x_1+x_2$ can not be less than $2$ if $x_1\geq 0$. In total you have $2^3 = 8$ cases to discuss. We've discussed two so far. You will see that $\mu_3 \neq 0$ and $\mu_1=\mu_2=0$ will give you the optimal one.

$\endgroup$
0

You must log in to answer this question.

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