# KKT condition with equality and inequality constraints

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?

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

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.

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