# Problem with finding Karush-Kuhn-Tucker points and checking for global or local minima.

I need to solve the following optimization problem

\begin{align*} & \mathrm{Min}:\quad f(x_1,x_2)=x_1-10x_2\\ & \mathrm{subject \ to}: \quad x_1^2 -x_2 \geq 0\\ & \qquad \qquad \qquad x_1^2x_2^2 \leq 1 \end{align*}

So first I tried to find all Karush-Kuhn-Tucker points. To do that, I wrote

$$\nabla f + u_1\nabla g_1 + u_2\nabla g_2$$ where $g_1= -x_1^2 +x_2$ and $g_2=x_1^2x_2^2-1$ ($u_i \geq 0$ for the minimization problem, and $u_i \leq 0$ for the maximization problem), and the ortogonality conditions

$$u_ig_i =0$$ for $i=1,2$. Now, assume that $u_1 \neq 0$. Then $g_1 =0$. If $u_2=0$, then

$$\nabla f + u_1 \nabla g_1=0$$ that is,

\begin{align*} 1-2u_1x_1 &=0 &-10 +u_1& =0 \end{align*} So $u_1 =10$ and I get the potin $P_1=(1/20,1/400)$. Continuing the process and assuming now that $u_2 \neq 0$ I get the points $P_2=(-1,1)$ and $P_3=(1,1)$.

Now I should consider the case where $u_1=0$ and $u_2 \neq 0$, but I'm having troubles in finding any points, so any help with that would be appreciate.

Leaving that question apart, now I need to check wether one of this points is a global minimum or not. Using the Hessian test, $f$ and $g_1$ are convex at $P_1, P_2$ and $P_3$, so $f$ is pseudo convex and $g_1$ is cuasiconvex, but $g_2$ is not convex at $P_2$ and $P_3$ since it has negative eigenvalues.

The question now is how should I conclude the question? From the fact that $g_2$ is not convex I can't say anything about the cuasiconvexity of $g_2$ at any point. Furtheremore, WolframAlpha says that $P_2$ and $P_3$ are local minima, and says nothing about $P_1$. Why is that?

Any help with thus would be highly appreciate. Thanks in advance!

Edit: I think I managed to find a feaseble point when $u_1 = 0$ and $u_2 \neq 0$, which is $P_4 = (-10/ \sqrt{10}, 1/ \sqrt{10})$, but the problem then is to check wether this points are global minima,local minima, etc. For the points $P_2$ and $P_3$ the Hessian matrix of both $g_1$ and $g_2$ is positive semidefinite and hence, $g_1$ and $g_2$ are convex at $P_1, P_2$. Since convexity implies quasiconvexity, $g_1$ and $g_2$ are quasiconvex at $P_1, P_2$.

Now, for $P_1$ and $P_4$, the Hessian matrix of $g_2$ is indefinite, so $g_2$ is not convex at this points. Can I say something about quasiconvexity?

Finally, I have fhe following theorem in my notes:

Let $x$ be a Karush-Kuhn-Tucker point, $f$ pseudoconvex at $x$ and $\{g_i\}$ quasiconvex at $x$. Then $x$ is a global minimun. ($g_i$ diferentiable)

But according to this theorem, shouldn't be both $P_2$ and $P_3$ global minimun? (Which can't be true since $f(P_2) \lt f(P_1)$) This confuses me even more...

• This problem is not, in fact, convex. In particular neither of the constraints are convex. I've edited the question and the tags to reflect that. – Michael Grant May 27 '16 at 12:49
• @MichaelGrant Thanks for the edit! I'm new at this and I didn't even know there was a KKT tag. So any idea to aproqch the problem? That is, what should I test to see if a given KKT point is a local minimun, global minimum, etc? – user313212 May 28 '16 at 15:30

The answer is $-\infty$. To see that, see the soln, $x_1 = -N$ and $x_2 = -1/N$. Then, both the constraints are satisfied for any $N>0$. Now, the objective function at this choice is $-N+10/N$. Since this can be achieved for any $N>0$, taking limit as $N\to \infty$ gives the objective as $-\infty$.

Even $(-N,0)$ satisfies the constraints with the objective value of $-N$. So, taking $N\to\infty$ achieves the objective of $-\infty$.

• Thanks for the answer! So the value of the objective finction $z$ is not bounded and therefore, there isn't a global minimum. However, there still might be local minima (which I belive are the points $(-1,)$ and $(1,1)$. Any idea of how to prove or disprove the local minimality of those points? – user313212 Jun 2 '16 at 10:29
• Consider $(-1,1)$ - Consider any point around it $(-1+\epsilon, 1-\delta)$ for $\delta>0$ (Any feasible point in local neighborhood will have lower $x_2$). $x_1^2-x_2^2 \approx \delta-2\epsilon\ge 0$ and $(1-\epsilon-\delta)<1$ and thus $\epsilon+\delta>0$. Thus, $\delta>0$ and $-\delta\le \epsilon\le \delta/2$. Difference of objective at new point compares to old point is $\epsilon + 10\delta\ge 9\delta\ge 0$ and thus any local point around has higher objective. Thus, it is local minima. – Vaneet Jun 2 '16 at 14:19
• Now consider $(1,1)$. Consider any point around it $(1-\epsilon, 1-\delta)$ for $\delta>0$ (Any feasible point in local neighborhood will have lower $x_2$). $x_1^2-x_2 \approx \delta-2\epsilon\ge 0$ and $(1-\epsilon-\delta)<1$ and thus $\epsilon+\delta>0$. Thus, $\delta>0$ and $-\delta\le \epsilon\le \delta/2$. Difference of objective at new point compares to old point is $-\epsilon + 10\delta\ge 9.5 \delta\ge 0$ and thus any local point around has higher objective. Thus, it is local minima. – Vaneet Jun 2 '16 at 14:24
• Excellent! Exactly what I was looking for! Thank you very much! – user313212 Jun 2 '16 at 15:34

Let $x_1\to x$ and $x_2\to y$ be interpreted as Cartesian coordinates of the plane, then: \begin{align*} & \mathrm{Min}:\quad f(x,y)=x-10\, y\\ & \mathrm{subject \ to}: \quad x^2 - y \geq 0\\ & \qquad \qquad \qquad x^2y^2 \leq 1 \end{align*} And we can visualize the problem as follows: The viewport employed is given by:

  xmin := -4; xmax := 4;
ymin := -5; ymax := 3;

The coordinate axes are in yellow. The area of interest is in $\color{green}{\mbox{green}}$: it is delimited by the parabola $y=x^2$ and the branches of two hyperbolas $xy = \pm 1$. Contour lines ($y=x/10 +\,$ constant) of the (linear) function $f(x,y)$ are displayed in grey, the darker these isolines, the lower the function values are.
For me, as an absolute non-expert in optimization, it is sufficiently clear now that the minimum must be at the intersection point of the hyperbola $xy=-1$ and the parabola $y=x^2$, which is $(x,y)=(-1,+1)$ : $\color{red}{\mbox{red arrow}}$.
Substituting this into $f(x,y)$ gives the minimum: $f(-1,+1)=-11$.

• But, in view of the answer given by Vaneet, $-11$ must be considered as a local minimum. As I've said: I'm not at all an expert in optimization and I don't know what the usual requirements are: e.g. is the answer supposed to be finite? – Han de Bruijn Jun 2 '16 at 10:04
• Thank you! I think your answer also shows that the value of the function is not bounded, since the region isn't bounded as well. – user313212 Jun 2 '16 at 10:32
• Also, shouldn't we consider the other point of the intersection between the hyperbola and the parabola? That is the point $(1,1)$? It gives the value $-9$, which is greater than $-11$, but in view of the other answer, shouldn't it be a local minimum as well? – user313212 Jun 2 '16 at 10:35
• You're quite right. That shows my inexperience :-( – Han de Bruijn Jun 2 '16 at 10:48