0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Michael Grant May 27 '16 at 12:49
  • $\begingroup$ @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? $\endgroup$ – user313212 May 28 '16 at 15:30
1
+50
$\begingroup$

\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*}

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user313212 Jun 2 '16 at 10:29
  • $\begingroup$ 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. $\endgroup$ – Vaneet Jun 2 '16 at 14:19
  • $\begingroup$ 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. $\endgroup$ – Vaneet Jun 2 '16 at 14:24
  • $\begingroup$ Excellent! Exactly what I was looking for! Thank you very much! $\endgroup$ – user313212 Jun 2 '16 at 15:34
1
$\begingroup$

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:

enter image description here

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Han de Bruijn Jun 2 '16 at 10:04
  • $\begingroup$ 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. $\endgroup$ – user313212 Jun 2 '16 at 10:32
  • $\begingroup$ 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? $\endgroup$ – user313212 Jun 2 '16 at 10:35
  • $\begingroup$ You're quite right. That shows my inexperience :-( $\endgroup$ – Han de Bruijn Jun 2 '16 at 10:48

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.