Finding Local Minimizers using KKT points (in a degenerate case)

Question

Consider the problem $$ \begin{split} \min_{x\in \mathbb{R}^2}\ & x_1^4 -2x_2^2-x_2 \\ \text{subject to }\ & x_1^2+x_2^2+x_2\leq 0 \end{split} $$

I have found that the point $x$ with $x_1 = 0, x_2 = -0.25$ is a KKT point with corresponding Lagrange multiplier $\lambda = 0$. According lecture notes, a sufficient condition for $x$ to be a local minimizer is that $<s,\nabla^2 L(x,\lambda) s>$ is positive definite for all $s$ such that $<s,c_i(x)> = 0$ and $\lambda >0$ where $c_i(x)$ is the ith active inequality constraint (here $L$ is the Lagrangian function). In our case, there is no such $s$, since for e.g. $\lambda = 0$.

Does this mean that $x$ is a local minimizer?

Answer 1

Your sufficient KKT condition is not complete. It should be $$ \langle s,c_i(x)\rangle\ \#\ 0, \quad\forall c_i\text{ active} $$ where $\#$ is equality if $\lambda>0$ or inequaity if $\lambda=0$ (the inequality is used to be $\ge$ in the literature that uses constraints $c_i(x)\ge 0$).

Now in your case (if I am not miscalculating as I am doing it a bit quickly) we have $$ \nabla^2L=\begin{bmatrix}0 & 0\\0 & -4\end{bmatrix}\qquad\text{subject to } s_2\le 0. $$ Here $\langle s,\nabla^2L s\rangle\not>0$, hence, no, it cannot be confirmed to be a local minimum from this test.

P.S. I assume that the point and $\lambda=0$ are correct.

P.P.S. The second order sufficient KKT condition is vacuously true, that is if there is no such $s$ then the point is a (strict) local minimizer.

Answer 2

Interesting question. It indeed does not need Lagrange.

Convert the problem to the following.

$$\begin{split} \min_{x\in \mathbb{R}^2}\ & (x_1^2)^2 -2(x_2+\dfrac14)^2 + \dfrac18 \\ \text{subject to }\ & 0\le x_1^2 \le -x_2^2-x_2 \end{split}$$

It's obvious that letting $x_1=0$ doesn't affect the optimal solution, so the problem is again converted to the following.

$$\begin{split} \min_{x_2\in \mathbb{R}}\ & -2(x_2+\dfrac14)^2 + \dfrac18 \\ \text{subject to }\ & 0 \le -(x_2+\dfrac12)^2 + \dfrac14 \Longleftrightarrow -1\le x_2\le 0 \end{split}$$

Compare the endpoints to $-\dfrac14$ and we know $-1$ is farther, so the solution is $-1$ where $x = (0,-1)$.

Answer 3

Note that $x_1^2+x_2^2+x_2\leq 0$ can be written as $$ x_1^2+(x_2+\frac12)^2\le\frac14. $$ Hence $x_1\in[-\frac12,\frac12],x_2\in[-1,0]$. So \begin{eqnarray} x_1^4 -2x_2^2-x_2&=&x_1^4-2(x_2^2+\frac12x_2)\\ &=&x_1^4-2\bigg[(x_2+\frac14)^2-\frac1{16}\bigg]\\ &\ge&-2(x_2+\frac14)^2+\frac18. \end{eqnarray} Since $x_2\in[-1,0]$, one has $-\frac34\le x_1+\frac14\le\frac14$ and hence $$ (x_2+\frac14)^2\le (-\frac34+1)^2=\frac9{16}. $$ So \begin{eqnarray} x_1^4 -2x_2^2-x_2&=&x_1^4-2(x_2^2+\frac12x_2)\\ &=&x_1^4-2\bigg[(x_2+\frac14)^2-\frac1{16}\bigg]\\ &\ge&-2(x_2+\frac14)^2+\frac18\\ &\ge&-2\times\frac9{16}+\frac18\\ &=&-1 \end{eqnarray} and the equal sign holds if and only if $x_1=0$ and $x_2=-1$.

Answer 4

Hint.

According to the convention

$$ \max_x f(x)\ \ \ \text{s. t.}\ \ g(x) \ge 0 $$

our problem can be stated as

$$ \max_x -(x_2^2-x_2^2-x_2) \ \ \ \text{s. t.}\ \ \ -(x_1^2+x_2^2+x_2) \ge 0 $$

so according to this convention, at the relative solutions $x^*$ the vectors $\nabla g(x^*)$ and $\nabla f(x^*)$ should obey

$\nabla f(x^*) \ge \lambda \nabla g(x^*)$ for $\lambda > 0$

Attached a plot showing the level curves for $f(x)$ inside the feasible region. In red dots the stationary points $x^*$, in red vectors $\nabla g(x^*)$ and in black vectors $\nabla f(x^*)$ As we can see there are four stationary points at the boundary and one interior. There are also two candidates to the solution.