Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to find the minimum of $-x_1$ with restrictions $\bar g\leq\bar 0$ so that

$$\bar g=\begin{pmatrix} (x_1+2)^2+(x_2-4)^2-20\\ (x_1+2)^2+x_2^2-20\\ -x_1\end{pmatrix}\leq \begin{pmatrix}0\\0\\0\\\end{pmatrix}=\bar0$$

I used KKT conditions to solve this puzzle below so $x_1=\frac{4\mu_1+4\mu_2-1-\mu_3}{2(\mu_1+\mu_2)}$ and $x_2=\frac{4\mu_1}{\mu_1+\mu_2}$ where $\mu_i\in\mathbb R\forall i$. I know from the graphical plot that the solution is something like $(1.5,1.5)$ but I cannot see how I can get such a solution from the equations for $x_1$ and $x_2$.

I followed this part of Wikipedia here, source here, about necessary conditions but I am stack how to find the minimum now. How to find it now with the necessary equations for the optimal point $(x_1,x_2)$?

My calculations

here

Updates

  1. Wok suggested complementary slackness -assumption $\mu_i g_i(x^*)=0, i=1,2,3$ and dual -feasibility assumption $\mu_i\geq 0,i=1,2,3$. I cannot yet see what it helps here.

  2. I can solve the intersection point just by solving the equations, proof here, but I cannot see how the KKT -way really make a difference in comparison to solving in the easy way, really puzzled!

  3. KKT is some sort of generalization of Lagrangean, example here, trying to understand what is happening...

share|improve this question

2 Answers 2

Try to use primal and dual feasibility and complementary slackness, while assuming $\mu_1+\mu_2\neq 0$ (otherwise your computations of $x_1$ and $x_2$ do not stand). With dual feasibility, at least one of $\mu_1$ and $\mu_2$ are strictly greater than zero.

Finding the solution is a matter of enumerating active constraints.

First case

If $\mu_1=0$ and $\mu_2\neq0$, then $x_2=0$. If $\mu_1\neq0$ and $\mu_2=0$, then $x_2=4$. In both cases, $(x_1+2)^2\leq 4$ (primal feasibility).

Since $x_1\geq0$, $x$ lies on the vertical axis (primal feasibility).

Second case

If $\mu_1\neq0$ and $\mu_2\neq0$, then $x$ is one of the two points at the intersection of the two circles (complementary slackness).

Since $x_1\geq0$, $x$ is the point in the right quadrant. (primal feasibility)

Conclusion

The maximum of $x_1$ is attained in the second case, since $x_1=0$ in the first case.

The solution is $x=(2,2)$.

share|improve this answer
    
Did you mean $\mu_1+\mu_2+\mu_3\not =0$? There are three constaints $g_1, g_2$ and $g_3$. Could you recite a bit what you mean... –  hhh Oct 25 '12 at 14:57
    
You assume $\mu_1+\mu_2\neq 0$ in your expression of $x_1$ and $x_2$. –  Wok Oct 25 '12 at 14:58
    
Please consider accepting the answer after satisfaction is provided. –  Wok Oct 25 '12 at 15:30
1  
$x_2=\frac{4\mu_1}{\mu_1+\mu_2} = \frac{4 \times 0}{0 + \mu_2} = 0$ –  Wok Oct 25 '12 at 18:37
1  
Use Primal feasability. –  Wok Oct 25 '12 at 20:29

I have tried to cover each topic in specific threads below. The lecture slides are here

  1. Explain Complementary Slackness $\mu_i g_i(x^*)=0\forall i$

  2. KKT: Explain visually the optimality condition $F_0\cap G_0\cap H_0=\emptyset$

  3. Explain this statement $\bar 0 \in \partial f(x^*)$ where $\partial f(x^*)$ is subgradient

  4. Explain $x^*$ of subgradient in KKT -conditions: primal optima or dual optima?

share|improve this answer
    
Please consider accepting the answer after satisfaction is provided. –  Wok Oct 30 '12 at 14:51
    
@wok I need to arrange a meeting with my teacher bf I am qualified enough to accept, taking some time. –  hhh Oct 30 '12 at 19:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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