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$
5
  • $\begingroup$ What is a KKT point? $\endgroup$ Commented Dec 30, 2018 at 10:01
  • $\begingroup$ I suppose a KKT point is a point which satisfies the KKT condition $\endgroup$
    – burg1ar
    Commented Dec 30, 2018 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.Γ.
    Commented Dec 30, 2018 at 11:58
  • $\begingroup$ Another relatively easy way here is to find the KKT point graphically. $\endgroup$
    – A.Γ.
    Commented Dec 30, 2018 at 12:07
  • $\begingroup$ @A.Γ. Thank you for pointing it out, I've updated the question. $\endgroup$
    – burg1ar
    Commented Dec 30, 2018 at 13:19

1 Answer 1

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.

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

You must log in to answer this question.

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