1
$\begingroup$

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...

2 Answers 2

1

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)$.

  • 0
    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...2012-10-25
  • 0
    You assume $\mu_1+\mu_2\neq 0$ in your expression of $x_1$ and $x_2$.2012-10-25
  • 0
    In fact, I also use Primal feasibility.2012-10-25
  • 1
    $x_2=\frac{4\mu_1}{\mu_1+\mu_2} = \frac{4 \times 0}{0 + \mu_2} = 0$2012-10-25
  • 0
    Can you clarify this point $(x_1+2)^2\leq 4$? I still get $(x_1+2)^2\leq 20$ because $\mu_1=0$ so $(x_1+2)^2+x_2^2=20$ where $x_2=0$ so $(x_1+2)^2\leq 20$.2012-10-25
  • 1
    Use Primal feasability.2012-10-25
  • 0
    Moreover, your inference is wrong since it should be based on $\mu_2\neq 0$ and not $\mu_1=0$. And your inference results in an equality, which is stronger than the inequality you finally infer. It could even be used in a reductio ad absurdum for the first case.2012-10-25
  • 0
    Sorry I am getting lost what you mean, perhaps some simpler demo? Now reading MIT courseware things [here](http://ocw.mit.edu/courses/mechanical-engineering/2-854-introduction-to-manufacturing-systems-fall-2010/lecture-notes/MIT2_854F10_kkt_ex.pdf) -- must see some easy working example, getting confused by this example.2012-10-25
  • 0
    Just use $\bar g\leq\bar 0$ with $x_2=0$.2012-10-25
  • 0
    Please consider not erasing your comments.2012-10-25
  • 0
    In second case, would you solve it like this [here](http://i.stack.imgur.com/vPw0m.jpg)? I actually use no KKT, I just solved it, algebraically.2012-10-25
  • 0
    +1 I need to go to sleep, taking more time than expected to read this answer. It is not evident for me yet how you use all of the special terms there, have to recall every definition one-by-one.2012-10-26
  • 0
    Yes, this is true.2012-10-26
0

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. https://math.stackexchange.com/questions/221454/explain-x-of-subgradient-in-kkt-conditions-primal-optima-or-dual-optima

  • 0
    @wok I need to arrange a meeting with my teacher bf I am qualified enough to accept, taking some time.2012-10-30