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

optimization

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?

Best Answer

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

Related Question