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