<p>Indeed, I think the problem is that the Jacobian of the (active) constraints is not of maximal rank at <span class="math-container">$(0,0)$</span>.</p>
<p>One solution is to rephrase your set of constraints.
<span class="math-container">$$
\begin{align*}
&amp;x^3 \le - y\\
&amp;x^3 \le y\\
&amp;y \ge 0.
\end{align*}
$$</span>
Note that given the first and last constraint, your second constraint is redundant.</p>
<p>Next notice that <span class="math-container">$x^3 \le -y \le 0$</span> requires <span class="math-container">$x \le 0$</span>. So we can replace the set of constraints by the following:
<span class="math-container">$$
\begin{align*}
&amp;x \le 0,\\
&amp;- y \le 0,\\
&amp;x^3 + y \le 0.
\end{align*}
$$</span>
The jacobian of these are:
<span class="math-container">$$
\begin{bmatrix} 1 &amp; 0\\ 0 &amp; -1 \\ 2 x^2 &amp; 1\end{bmatrix}
$$</span>
which is of rank <span class="math-container">$2$</span>.</p>
<p>The Lagrangian is now:
<span class="math-container">$$
L = (x - 2)^2 + y - \theta x - \mu (-y) - \lambda(x^3 + y).
$$</span>
The first order and complementary slackness constraints are:
<span class="math-container">$$
\begin{align*}
&amp;2 (x - 2) - \theta - 3 \lambda x^2 = 0,\\
&amp;1 + \mu - \lambda = 0,\\
&amp;\theta x = 0,\\
&amp;\mu y = 0,\\
&amp;\lambda(x^3 + y) = 0,\\
&amp;\lambda, \mu, \theta \le 0
\end{align*}
$$</span></p>
<ul>
<li>The second constraint shows that <span class="math-container">$\mu= \lambda= 0$</span> is not possible.</li>
<li>If <span class="math-container">$\mu = 0$</span> then <span class="math-container">$\lambda = 1 &gt; 0$</span>, which violates the last condition for having a (local) minimum.</li>
<li>If <span class="math-container">$\lambda = 0$</span> and <span class="math-container">$\mu &lt; 0$</span> then <span class="math-container">$y = 0$</span> and <span class="math-container">$\mu = -1$</span>.
<ul>
<li>if <span class="math-container">$\theta &lt; 0$</span>, we get that also <span class="math-container">$x = 0$</span> and <span class="math-container">$\theta = -4$</span>. The constraint <span class="math-container">$x^3 \le -y$</span> is also satisfied, so this is a possible minimum.</li>
<li>if <span class="math-container">$\theta = 0$</span>, we get from the first constraint that <span class="math-container">$-4 = 0$</span>, a contradiction.</li>
</ul>
</li>
<li>If <span class="math-container">$\lambda &lt; 0$</span> and <span class="math-container">$\mu &lt; 0$</span> we get the constraint <span class="math-container">$\lambda - \mu = 1$</span>, <span class="math-container">$x^3 = -y$</span> and <span class="math-container">$y = 0$</span>. So <span class="math-container">$x = y = 0$</span>. Then the first constraint gives <span class="math-container">$\theta = -4$</span>. This is a kind of strange case all all three constraints are binding, while the rank of the Jacobian is of rank 2 at <span class="math-container">$(x,y) = (0,0)$</span>. This candidate should therefore not be considered.</li>
</ul>
<p>This gives 1 candidate <span class="math-container">$(x,y) = (0,0)$</span> with <span class="math-container">$\lambda = 0$</span>, <span class="math-container">$\mu = -1$</span> and <span class="math-container">$\theta = -4$</span>.</p>
<p>For the second order conditions, it suffices that the Lagrangian is convex in <span class="math-container">$x$</span> and <span class="math-container">$y$</span> for the ``optimal values'' of <span class="math-container">$\lambda, \mu$</span> and <span class="math-container">$\theta$</span>.</p>
<p>The Hessian of <span class="math-container">$L$</span> is given by:
<span class="math-container">$$
\begin{bmatrix} 2 - 6 \lambda x &amp; 0\\ 0 &amp; 0\end{bmatrix}
$$</span>
This reduces to <span class="math-container">$\begin{bmatrix} 2 &amp; 0 \\ 0 &amp; 0\end{bmatrix}$</span> for the candiate solution where <span class="math-container">$\lambda = 0$</span>. This matrix is positive semi-definite so the candiate <span class="math-container">$(0,0)$</span> is a global minimum.</p>

CC BY-SA 4.0
2024-04-21T08:35:46.480Z
Such a helpful solution! I am also facing a KKT problem would love your thoughts if you have time...it's much simpler: https://economics.stackexchange.com/questions/58179/missing-solutions-in-kkt-optimisation-problem
CormJack
CC BY-SA 4.0
2024-04-08T08:12:31.393Z
2024-04-08T08:12:31.393Z
tdm
<p>I have to understand a thing about this exercise: find the minimum of <span class="math-container">$f(x, y) = (x-2)^2 + y$</span> subject to <span class="math-container">$y-x^3 \geq 0$</span>, <span class="math-container">$y+x^3 \leq 0$</span> and <span class="math-container">$y \geq 0$</span>.</p>
<p>Now, I solved the problem quite easily in a sketching way: the level curves of <span class="math-container">$f(x, y)$</span> are concave parabolas (<span class="math-container">$y = k - (x-2)^2$</span>), and the feasible region is the upper left plane bounded by <span class="math-container">$x&lt;0$</span>-axis and under the curve <span class="math-container">$-x^3$</span>.
The candidate solution is <span class="math-container">$(0, 0)$</span> at which <span class="math-container">$f(x, y) = 4$</span>.</p>
<p>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:</p>
<p><span class="math-container">$$-\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}$$</span>
with KKT Lagrangian</p>
<p><span class="math-container">$$L = -(x-2)^2-y- \lambda(-y+x^3) - \mu(y+x^3) - \Theta(-y)$$</span></p>
<p>which leads to the optimal conditions
<span class="math-container">$$
\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}
$$</span>
From here I have to study <span class="math-container">$8$</span> cases. Here are some:</p>
<p><span class="math-container">$\bullet$</span> When <span class="math-container">$\lambda = \mu = \Theta = 0$</span> the system is impossible.</p>
<p><span class="math-container">$\bullet$</span> When <span class="math-container">$\lambda = \mu = 0$</span>, <span class="math-container">$\Theta \neq 0$</span> I obtain <span class="math-container">$(2, 0)$</span> which doesn't satisfy the constraints.</p>
<p><span class="math-container">$\bullet$</span> When <span class="math-container">$\lambda = 0$</span>, <span class="math-container">$\mu \neq 0, \Theta = 0$</span> I get <span class="math-container">$\mu = -1$</span> which is not admissible.</p>
<p><span class="math-container">$\bullet$</span> When <span class="math-container">$\lambda, \mu, \Theta \neq 0$</span> I eventually manage to get among the others
<span class="math-container">$$\begin{cases}
\Theta = \mu + 1 - \lambda \\
(\mu+1-\lambda)y = 0
\end{cases}
$$</span>
From which either <span class="math-container">$y =0$</span> or <span class="math-container">$\lambda = \mu +1$</span>.</p>
<p>For <span class="math-container">$\lambda = \mu +1$</span> using the first equation I get
<span class="math-container">$$\mu = \frac{4-2x-3x^2}{6x^2}$$</span>
from which
<span class="math-container">$$\lambda = \frac{4 - 2x + 3x^2}{6x^2}$$</span>
If <span class="math-container">$y = 0$</span> then from the complementarity equation <span class="math-container">$\mu(x^3-y) = 0$</span> I obtain <span class="math-container">$(4-2x-3x^2)x = 0$</span>, hence either <span class="math-container">$x = 0$</span> or <span class="math-container">$x = \frac{1}{3}(-1\pm \sqrt{13})$</span>, but those last ones don't satisfy all the constraints.</p>
<p>On the other side, <span class="math-container">$x = 0$</span> would be good if not for the fact that I cannot take it since it would make <span class="math-container">$\lambda, \mu$</span> nonsensical.</p>
<p>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!</p>
<p>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).</p>
<p><a href="https://i.sstatic.net/yVX5N.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/yVX5N.png" alt="enter image description here" /></a></p>
<pre><code>plot1 = RegionPlot[{y - x^3 &gt;= 0 &amp;&amp; y + x^3 &lt;= 0 &amp;&amp; y &gt;= 0}, {x,     -3, 
3}, {y, -3, 5}, Axes -&gt; True]
plot2 = Plot[{-(x - 2)^2, 4 - (x - 2)^2, 3 - (x - 2)^2}, {x, -3, 5}, 
PlotStyle -&gt; {Dashed, Dashed, Dashed}]
Show[plot1, plot2]
</code></pre>
<p><strong>Second Thought</strong></p>
<p>Or maybe I just could say that <span class="math-container">$y \leq -x^3$</span> is the same as <span class="math-container">$-y \geq x^3$</span> but this, with the other condition implies <span class="math-container">$\begin{cases} x^3 \leq -y \\ x^3 \leq y \end{cases}$</span> could just imply either <span class="math-container">$x = 0$</span> and then <span class="math-container">$y = 0$</span>, or <span class="math-container">$y = 0$</span> and <span class="math-container">$x$</span> must be negative, though in this last case we would keep increasing the value of <span class="math-container">$f$</span> rather than find the minimum.</p>
<p><strong>Third Thought</strong></p>
<p>I perhaps have forgotten about the regularity of the constraints. The Jacobian matrix indeed reads</p>
<p><span class="math-container">$$\mathsf{J} = \begin{pmatrix} 3x^2 &amp; -1 \\ 3x^2 &amp; 1 \\ 0&amp; -1 \end{pmatrix}$$</span></p>
<p>From which we observe that at <span class="math-container">$(0, 0)$</span> we lose the regularity of the constraitns, being <span class="math-container">$\mathsf{J}$</span> of randk <span class="math-container">$1$</span>.</p>
<p>Perhaps this is what makes KKT conditions to not being satisfied.</p>
<p>In any case, the problem with the solution <span class="math-container">$x = 0$</span> remains: it is not valid since it makes <span class="math-container">$\lambda, \mu$</span> nonsensical.</p>
<p><strong>Fourth Thought</strong></p>
<p>By analysing the cas in which only <span class="math-container">$\Theta = 0$</span> I may have gotten the solution <span class="math-container">$(0,0)$</span>, which now doesn't carry any weird behaviour for <span class="math-container">$\mu$</span> \nad <span class="math-container">$\lambda$</span>.</p>
<p>The question on the KKT conditions still remains, but perhaps it's indeed the non regularity of the constraints the answer, which accurs at <span class="math-container">$x = 0$</span> and <span class="math-container">$y =0$</span>.</p>
<p><strong>Fifth Thought</strong></p>
<p>I didn't notice before, but the solution <span class="math-container">$x = 0$</span>, <span class="math-container">$y =0$</span> makes the gradient system impossible: the first equation would read <span class="math-container">$4 = 0$</span>.</p>
<p>At this point I have no more ideas about this exercise...</p>
<p><strong>Sixth Thought</strong></p>
<p>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</p>
<p><span class="math-container">$$-2T(x-2)^2 + 3\lambda x^2 = 0$$</span></p>
<p>Which returns <span class="math-container">$T = 0$</span> (admissible, since we need <span class="math-container">$T\geq 0$</span>) when <span class="math-container">$x = 0$</span>. 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!</p>

<optimization><lagrangian><multiplier>
Optimisation problem and KKT conditions (unsatisfied?)
Henry
# Optimisation problem and KKT conditions (unsatisfied?)

(Asked by: username_0 on 2024-03-29)

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

**Tags:** optimization, lagrangian, multiplier

---

## 1 answers

### Answer by username_1 on 2024-04-08. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_2**: Such a helpful solution! I am also facing a KKT problem would love your thoughts if you have time...it's much simpler: https://economics.stackexchange.com/questions/58179/missing-solutions-in-kkt-optimisation-problem  

---

