3
$\begingroup$

I have to understand a thing about this exercise: find the minimum of $f(x, y) = (x-2)^2 + y$ subject to $y-x^3 \geq 0$, $y+x^3 \leq 0$ and $y \geq 0$.

Now, I solved the problem quite easily in a sketching way: the level curves of $f(x, y)$ are concave parabolas ($y = k - (x-2)^2$), and the feasible region is the upper left plane bounded by $x<0$-axis and under the curve $-x^3$. The candidate solution is $(0, 0)$ at which $f(x, y) = 4$.

On the other side, I wanted to solve it with Kuhn-Tucker multipliers, so I set the problem in the standard form for a minimum problem that is:

$$-\max -f(x, y) \qquad \text{s.t.} \qquad \begin{cases} -y+x^3 \leq 0 \\ y+x^3 \leq 0 \\ -y \leq 0 \end{cases}$$ with KKT Lagrangian

$$L = -(x-2)^2-y- \lambda(-y+x^3) - \mu(y+x^3) - \Theta(-y)$$

which leads to the optimal conditions $$ \begin{cases} -2(x-2) - 3\lambda x^2 - 3\mu x^2 = 0 \\ -1+\lambda - \mu + \Theta = 0 \\ -y + x^3 \leq 0 \quad ; \quad \lambda(-y+x^3) = 0 \\ y+x^3 \leq 0 \quad ; \quad \mu(y+x^3) = 0 \\ -y\leq 0 \quad ; \quad \Theta y = 0 \lambda, \mu, \Theta \geq 0 \end{cases} $$ From here I have to study $8$ cases. Here are some:

$\bullet$ When $\lambda = \mu = \Theta = 0$ the system is impossible.

$\bullet$ When $\lambda = \mu = 0$, $\Theta \neq 0$ I obtain $(2, 0)$ which doesn't satisfy the constraints.

$\bullet$ When $\lambda = 0$, $\mu \neq 0, \Theta = 0$ I get $\mu = -1$ which is not admissible.

$\bullet$ When $\lambda, \mu, \Theta \neq 0$ I eventually manage to get among the others $$\begin{cases} \Theta = \mu + 1 - \lambda \\ (\mu+1-\lambda)y = 0 \end{cases} $$ From which either $y =0$ or $\lambda = \mu +1$.

For $\lambda = \mu +1$ using the first equation I get $$\mu = \frac{4-2x-3x^2}{6x^2}$$ from which $$\lambda = \frac{4 - 2x + 3x^2}{6x^2}$$ If $y = 0$ then from the complementarity equation $\mu(x^3-y) = 0$ I obtain $(4-2x-3x^2)x = 0$, hence either $x = 0$ or $x = \frac{1}{3}(-1\pm \sqrt{13})$, but those last ones don't satisfy all the constraints.

On the other side, $x = 0$ would be good if not for the fact that I cannot take it since it would make $\lambda, \mu$ nonsensical.

So I ask you: how to deal with this problem analytically? It looks like KKT conditions might not be satisfied, but I am not sure of this. I would like other pairs of eyes/mind from you, thank you!

Here is the sketch too, with Mathematica code. It's not as good as I thought, since the feasible region should include a missing portion (the origin to the left and above).

enter image description here

plot1 = RegionPlot[{y - x^3 >= 0 && y + x^3 <= 0 && y >= 0}, {x,     -3, 
3}, {y, -3, 5}, Axes -> True]
plot2 = Plot[{-(x - 2)^2, 4 - (x - 2)^2, 3 - (x - 2)^2}, {x, -3, 5}, 
PlotStyle -> {Dashed, Dashed, Dashed}]
Show[plot1, plot2]

Second Thought

Or maybe I just could say that $y \leq -x^3$ is the same as $-y \geq x^3$ but this, with the other condition implies $\begin{cases} x^3 \leq -y \\ x^3 \leq y \end{cases}$ could just imply either $x = 0$ and then $y = 0$, or $y = 0$ and $x$ must be negative, though in this last case we would keep increasing the value of $f$ rather than find the minimum.

Third Thought

I perhaps have forgotten about the regularity of the constraints. The Jacobian matrix indeed reads

$$\mathsf{J} = \begin{pmatrix} 3x^2 & -1 \\ 3x^2 & 1 \\ 0& -1 \end{pmatrix}$$

From which we observe that at $(0, 0)$ we lose the regularity of the constraitns, being $\mathsf{J}$ of randk $1$.

Perhaps this is what makes KKT conditions to not being satisfied.

In any case, the problem with the solution $x = 0$ remains: it is not valid since it makes $\lambda, \mu$ nonsensical.

Fourth Thought

By analysing the cas in which only $\Theta = 0$ I may have gotten the solution $(0,0)$, which now doesn't carry any weird behaviour for $\mu$ \nad $\lambda$.

The question on the KKT conditions still remains, but perhaps it's indeed the non regularity of the constraints the answer, which accurs at $x = 0$ and $y =0$.

Fifth Thought

I didn't notice before, but the solution $x = 0$, $y =0$ makes the gradient system impossible: the first equation would read $4 = 0$.

At this point I have no more ideas about this exercise...

Sixth Thought

I shall perhaps have to pass to Fritz John conditions, which with one more multiplier directly into the object function makes things meaningful. Indeed I would have

$$-2T(x-2)^2 + 3\lambda x^2 = 0$$

Which returns $T = 0$ (admissible, since we need $T\geq 0$) when $x = 0$. This would put a good stone of peace over this question, but I'm still open to possible answer (more rigorous ones), so feel free to comment!

$\endgroup$

1 Answer 1

1
$\begingroup$

Indeed, I think the problem is that the Jacobian of the (active) constraints is not of maximal rank at $(0,0)$.

One solution is to rephrase your set of constraints. $$ \begin{align*} &x^3 \le - y\\ &x^3 \le y\\ &y \ge 0. \end{align*} $$ Note that given the first and last constraint, your second constraint is redundant.

Next notice that $x^3 \le -y \le 0$ requires $x \le 0$. So we can replace the set of constraints by the following: $$ \begin{align*} &x \le 0,\\ &- y \le 0,\\ &x^3 + y \le 0. \end{align*} $$ The jacobian of these are: $$ \begin{bmatrix} 1 & 0\\ 0 & -1 \\ 2 x^2 & 1\end{bmatrix} $$ which is of rank $2$.

The Lagrangian is now: $$ L = (x - 2)^2 + y - \theta x - \mu (-y) - \lambda(x^3 + y). $$ The first order and complementary slackness constraints are: $$ \begin{align*} &2 (x - 2) - \theta - 3 \lambda x^2 = 0,\\ &1 + \mu - \lambda = 0,\\ &\theta x = 0,\\ &\mu y = 0,\\ &\lambda(x^3 + y) = 0,\\ &\lambda, \mu, \theta \le 0 \end{align*} $$

  • The second constraint shows that $\mu= \lambda= 0$ is not possible.
  • If $\mu = 0$ then $\lambda = 1 > 0$, which violates the last condition for having a (local) minimum.
  • If $\lambda = 0$ and $\mu < 0$ then $y = 0$ and $\mu = -1$.
    • if $\theta < 0$, we get that also $x = 0$ and $\theta = -4$. The constraint $x^3 \le -y$ is also satisfied, so this is a possible minimum.
    • if $\theta = 0$, we get from the first constraint that $-4 = 0$, a contradiction.
  • If $\lambda < 0$ and $\mu < 0$ we get the constraint $\lambda - \mu = 1$, $x^3 = -y$ and $y = 0$. So $x = y = 0$. Then the first constraint gives $\theta = -4$. This is a kind of strange case all all three constraints are binding, while the rank of the Jacobian is of rank 2 at $(x,y) = (0,0)$. This candidate should therefore not be considered.

This gives 1 candidate $(x,y) = (0,0)$ with $\lambda = 0$, $\mu = -1$ and $\theta = -4$.

For the second order conditions, it suffices that the Lagrangian is convex in $x$ and $y$ for the ``optimal values'' of $\lambda, \mu$ and $\theta$.

The Hessian of $L$ is given by: $$ \begin{bmatrix} 2 - 6 \lambda x & 0\\ 0 & 0\end{bmatrix} $$ This reduces to $\begin{bmatrix} 2 & 0 \\ 0 & 0\end{bmatrix}$ for the candiate solution where $\lambda = 0$. This matrix is positive semi-definite so the candiate $(0,0)$ is a global minimum.

$\endgroup$
1
  • $\begingroup$ Thank you for this! $\endgroup$
    – Henry
    Apr 8 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.