Minimum of the quartic $(x^2-1)^2+y^2$ using KKT conditions

Question

Consider the following optimization problem.

$$\begin{array}{ll} \text{minimize} & (x^2-1)^2+y^2\\ \text{subject to} & x^2 - 4 \le 0\\ & x + y \le 0\end{array}$$

Using KKT conditions, find the optimal solution.

Solution: If one draw the region and the objective function then we clearly see that $\overline x=(\frac{1}{2},-\frac{1}{2})$ is the optimal solution.

And the rest it is just calculations and verifications of KKT conditions. So we can verify algebraically that $\overline x$ is the optimal solution.

Question:

Suppose we are not lucky enought to draw the region and objective function, so we are not able to find the solution geometrically.

What to do in this cases?

If you check KKT theorem (Confusion about definition of KKT conditions) , it does not explicitly says how to find the point that will be the optimal solution, it just states that if a point $x$ is fesible and f pseudoconvex at $x$ and there exists scalars such that ... then $x$ is optimal.

Answer 1

Although the question clearly asks one to use the Karush-Kuhn-Tucker (KKT) conditions, one can do without them. Note that the feasible region can be parameterized as follows

$$\begin{bmatrix} x\\y\end{bmatrix} = u \begin{bmatrix} 2\\-2\end{bmatrix} + v \begin{bmatrix} 0\\-1\end{bmatrix}, \qquad u \in [-1,1], v \geq 0$$

Since $u \in [-1,1]$, use $u = \sin (\theta)$. Since $v \geq 0$, use $v = t^2$. Let us use SymPy to do the substitutions and find where the gradient vanishes. The following Python script

from sympy import *

x, y, theta, t = symbols('x y theta t')

# objective function in terms of x and y
f = (x**2 - 1)**2 + y**2

# objective function in terms of theta and t
g = f.subs([(x,2*sin(theta)), (y,-2*sin(theta)-t**2)])

# find where the gradient of g vanishes
solutions = solve([diff(g,theta).expand(),diff(g,t).expand()],theta,t)

Extrema = FiniteSet(*[])
for (theta_opt, t_opt) in solutions:
    if theta_opt.is_real and t_opt.is_real:
        x_opt =  2 * sin(theta_opt)
        y_opt = -2 * sin(theta_opt) - t_opt**2
        Extrema = Extrema + FiniteSet((x_opt.evalf(),y_opt.evalf()))

print Extrema

produces the following set of $8$ candidate extremizers

{(-2.0, 0), (-2.0, 2.0), (-1.0, 0), (-1.0, 0.e-125), (-0.707106781186548, 0.707106781186548), (0, 0), (0.707106781186548, -0.707106781186548), (2.0, -2.0)}

Note that (-1.0, 0) and (-1.0, 0.e-125) are actually the same. Thus, we have $7$ candidates. Borrowing the pretty plot in Cesareo's answer, these $7$ candidates are plotted below.

Plotting the objective over the feasible region, we conclude that $(-1,0)$ is the global minimizer.

Answer 2

I think $$\min (x^2-1)^2+y^2=0,$$ when $x=-1,y=0$. Besides, the $x,y$ could satisfy the constraint conditions, since $$x+y=-1+0=-1 \leq 0,~~~~x^2-4=(-1)^2-4=-3 \leq 0.$$

Answer 3

Introducing some slack variables to cope with the inequalities we have the lagrangian

$$ L(x,y,\lambda,\epsilon) = (x^2-1)^2+y^2+\lambda_1(x+y+\epsilon_1^2)+\lambda_2(x^2-4+\epsilon_2^2) $$

The stationary points are calculated by solving

$$ \nabla L = \left\{ \begin{array}{rcl} 4 x^3+2 \lambda_2 x+\lambda_1=4 x \\ \lambda_1+2 y=0 \\ \lambda_1 \epsilon_1=0 \\ \lambda_2 \epsilon_2=0 \\ \epsilon_1^2+x+y=0 \\ \epsilon_2^2+x^2=4 \\ \end{array} \right. $$

giving

$$ \left[ \begin{array}{c|ccc} \text{label} & x & y & f(x,y)\\ \hline A & -2 & 2 & 13 \\ B & -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & \frac{3}{4} \\ C & 0 & 0 & 1 \\ D & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & \frac{3}{4} \\ E & 2 & -2 & 13 \\ F & -2 & 0 & 9 \\ G & -1 & 0 & 0 \\ \end{array} \right] $$

The minimum point is the interior point $G$

Attached a plot showing the stationary points found using the Lagrange multipliers technique.

NOTE

According to the KKT conditions the feasible points to consider are the labeled as $A,B,F, G$