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

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.

• sorry sorry it's $y^2$ not $y$ (it's very late here..) Commented Jul 3, 2018 at 4:03
• @RodrigodeAzevedo they are circles, why it's not convex? Commented Jul 3, 2018 at 17:14
• @RodrigodeAzevedo Isn't this the equation of circles $(x^2-1)^2+y^2?$. I don't know why the level curves are like that in Cesareo's answer Commented Jul 3, 2018 at 18:06
• @RodrigodeAzevedo but why $y=0?$ Isn't suppose to draw the level curves like $(x-1)^2 + y^2=i,i=0,1,\dots$ Commented Jul 3, 2018 at 19:15
• And then we'll see how the circles approach to the feasible region. Commented Jul 3, 2018 at 19:16

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$

• I took the liberty of using your plot in my answer. Credit was given. Please let me know if you disapprove of this. Commented Jul 5, 2018 at 10:44

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.

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

• Why did you equal to zero the objective function? Commented Jul 3, 2018 at 5:06
• @user441848 you don't mean to find the minimum value of $(x^2-1)^2+y^2$,where $x,y$ satisfy the two condtions? Commented Jul 3, 2018 at 5:42
• yes but why $\min (x^2-1)^2+y^2=0$, =0? Commented Jul 3, 2018 at 5:56
• @user441848 My dear friend, first, you must notice that $(x^2-1)^2+y^2 \geq 0$ for all $x,y.$ Second, you should show that $0$ could be reached under the constraint conditions. In fact, we have pointed that out. Commented Jul 3, 2018 at 6:37
• @user441848 In addtion, $\min (x^2-1)^2+y^2=0$ means that the minimum value of $(x^2-1)^2+y^2$ is $0$,where $x,y$ satisfy your constraint condtions. Commented Jul 3, 2018 at 6:41