# Optimisation problem and KKT conditions (unsatisfied?)

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

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

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!

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.

• Thank you for this! Apr 8 at 18:21