2
$\begingroup$

find the KKT point of the following problem: $$\min\quad f(x_1,x_2)=(x_1-3)^{2}+(x_2-2)^{2}\\ subject\quad to\qquad \qquad \qquad \qquad \qquad\qquad\\ x_1^{2}+x_2^{2}\le5\\ x_1+2x_2=4\\ x_1\ge0,x_2\ge0$$

what I tried:

for the general problem: $$min\quad f(\textbf x)\\ s.t.\quad h_i(\textbf x)=0\quad (i=1,2,\dots ,m)\\ g_j(\textbf x)\ge0\quad (j=1,2,\dots,l)$$

where $\textbf x=(x_1,x_2,\dots,x_n)^{T}$

the KKT condition is

$$\nabla f(x^{*})-\sum_{j=1}^{l}\gamma_j^*\nabla g_j(x^*)-\sum_{i=1}^m\lambda_i^*\nabla h_i(x^*)=0\\ \gamma_j^*g_j(x^*)=0\quad (j=1,2,\dots,l)\\ \gamma_j^*\ge0\quad (j=1,2,\dots,l)$$ where $x^*=(x_1,x_2,\dots,x_n)^{T}$,$\gamma^*=(\gamma_1^*,\gamma_2^*,\dots,\gamma_l^*)^{T}$,$\lambda^*=(\lambda_1^*,\lambda_2^*,\dots,\lambda_m^*)^{T}$

$x^*$ is the KKT point if $x^*$ satisfies the KKT condition.

with this knowledge, for the specific problem above,

Let $$f(\textbf x)=(x_1-3)^{2}+(x_2-2)^{2}\\ g_1(\textbf x)=-x_1^2-x_2^2+5\\ g_2(\textbf x)=x_1\\ g_3(\textbf x)=x_2 h_1(x)=x_1+2x_2-4$$ (change $x_1^2+x_2^2\le5$ to the general form $-x_1^2-x_2^2+5\ge0$)

and $x^*=(x_1,x_2)^{T}$ is the KKT point,then we have: $$\nabla f(x^*)= \begin{bmatrix} 2(x_1-3)\\ 2(x_2-2)\\ \end{bmatrix}$$ $$\nabla g_1(x^*)= \begin{bmatrix} -2x_1\\ -2x_2\\ \end{bmatrix}$$ $$\nabla g_2(x^*)= \begin{bmatrix} 1\\ 0\\ \end{bmatrix}$$ $$\nabla g_2(x^*)= \begin{bmatrix} 0\\ 1\\ \end{bmatrix}$$ $$\nabla h_1(x^*)= \begin{bmatrix} 1\\ 2\\ \end{bmatrix}$$

the KKT condition is: $$\begin{bmatrix} 2(x_1-3)\\ 2(x_2-2)\\ \end{bmatrix}-\gamma_1\begin{bmatrix} -2x_1\\ -2x_2\\ \end{bmatrix}-\gamma_2\begin{bmatrix} 1\\ 0\\ \end{bmatrix}-\gamma_3\begin{bmatrix} 0\\ 1\\ \end{bmatrix}-\lambda_1\begin{bmatrix} 1\\ 2\\ \end{bmatrix}=0$$ $$\gamma_1(-x_1^2-x_2^2+5)=0$$ $$\gamma_2 x_1=0$$ $$\gamma_3 x_2=0$$ $$\gamma_1,\gamma_2,\gamma_3\ge0$$

we should get the KKT point $x^*$ by solving the equation set above.

For me, the problem here is that the equation set seems not solvable, so how to solve the equation, or I did it completely the wrong way?

$\endgroup$
  • $\begingroup$ What is a KKT point? $\endgroup$ – Dr. Sonnhard Graubner Dec 30 '18 at 10:01
  • $\begingroup$ I suppose a KKT point is a point which satisfies the KKT condition $\endgroup$ – burg1ar Dec 30 '18 at 10:10
  • 1
    $\begingroup$ You need to add more context to the question and your own thoughts as well. The easiest solution: the problem is convex, hence, any KKT point is the global minimizer. There is only one minimizer here, it is $(2,1)$, hence, it is the only KKT point. $\endgroup$ – A.Γ. Dec 30 '18 at 11:58
  • $\begingroup$ Another relatively easy way here is to find the KKT point graphically. $\endgroup$ – A.Γ. Dec 30 '18 at 12:07
  • $\begingroup$ @A.Γ. Thank you for pointing it out, I've updated the question. $\endgroup$ – burg1ar Dec 30 '18 at 13:19
1
$\begingroup$

Note that the general form of KKT you wrote is $$ \nabla f(x^{*})-\sum_{j=1}^{l}\gamma_j^*\nabla g_j(x^*)-\color{red}{\sum_{i=1}^m\lambda_i^*\nabla h_i(x^*)}=0 $$ while for this problem you have got $$ \begin{bmatrix} 2(x_1-3)\\ 2(x_2-2)\\ \end{bmatrix}-\gamma_1\begin{bmatrix} -2x_1\\ -2x_2\\ \end{bmatrix}-\gamma_2\begin{bmatrix} 1\\ 0\\ \end{bmatrix}-\gamma_3\begin{bmatrix} 0\\ 1\\ \end{bmatrix}=0 $$ that is without the equlity part. The right equation is $$ \begin{bmatrix} 2(x_1-3)\\ 2(x_2-2)\\ \end{bmatrix}-\gamma_1\begin{bmatrix} -2x_1\\ -2x_2\\ \end{bmatrix}-\gamma_2\begin{bmatrix} 1\\ 0\\ \end{bmatrix}-\gamma_3\begin{bmatrix} 0\\ 1\\ \end{bmatrix}-\color{red}{\lambda\begin{bmatrix} 1\\ 2\\ \end{bmatrix}}=0 $$ together with $x_1+2x_2=4$.

Now $x_2=0$ gives $x_1=4$ which is infeasible point ($x_1^2+x_2^2>5$), hence $x_2>0$ and $\gamma_3=0$.

Similarly, $x_1=0$ gives $x_2=2$ (and $\gamma_3=0$), $x_1^2+x_2^2<5$ (and $\gamma_1=0$), which leads to $\lambda=0$ and $\gamma_2=-6$. It is impossible as $\gamma_2\ge 0$, hence, $x_1>0$ and $\gamma_2=0$.

Next step is to try $\gamma_1=0$, it will give after some algebra $\lambda=-6/5$ and an infeasible point ($x_1^2+x_2^2>5$), then $\gamma_1>0$ and $x_1^2+x_2^2=5$.

Solving two equations \begin{align} x_1+2x_2&=4,\\ x_1^2+x_2^2&=5 \end{align} gives only one feasible point $(2,1)$. Check that all KKT conditions are satisfied ($\gamma_1=1/3$, $\lambda=-2/3$), then it is a KKT point.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ sorry, I missed it, too much typing $\endgroup$ – burg1ar Dec 30 '18 at 13:37
  • $\begingroup$ @burg1ar ok, I've added possible solution steps. $\endgroup$ – A.Γ. Dec 30 '18 at 13:41
  • $\begingroup$ "some algebra lambda=6/5", you mean lambda=-6/5(negative),right? $\endgroup$ – burg1ar Dec 30 '18 at 14:15
  • $\begingroup$ your answer is right,thank you,I'll accept it $\endgroup$ – burg1ar Dec 30 '18 at 14:15
  • $\begingroup$ @burg1ar Oh, right, I have opposite sign for $\lambda$ in my KKT. Editing. $\endgroup$ – A.Γ. Dec 30 '18 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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