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

1,381

Solution 1

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

Solution 2

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$.
Share:
1,381

Related videos on Youtube

user313212
Author by

user313212

Updated on June 02, 2020

Comments

  • user313212
    user313212 over 3 years

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

    • Michael Grant
      Michael Grant over 7 years
      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.
    • user313212
      user313212 over 7 years
      @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?
  • Han de Bruijn
    Han de Bruijn over 7 years
    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?
  • user313212
    user313212 over 7 years
    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
    user313212 over 7 years
    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
    user313212 over 7 years
    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?
  • Han de Bruijn
    Han de Bruijn over 7 years
    You're quite right. That shows my inexperience :-(
  • Vaneet
    Vaneet over 7 years
    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
    Vaneet over 7 years
    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.
  • user313212
    user313212 over 7 years
    Excellent! Exactly what I was looking for! Thank you very much!