Find all the points satisfying the Fritz John conditions

Question

Consider the problem $$\min \>x^2+y^2 $$ $$s.t.\> x^2-(y-1)^3=0$$

1. Find all the points satisfying the Fritz John conditions

   Solution

The FJ conditions are $$2x+\mu_1 2x=0$$ $$2y-\mu_1 3(y-1)^2=0$$ But I am stuck from here

2. One may be tempted to solve the optimization problem by substituting $ x^ 2 = (y − 1) ^3$ in the objective, thereby reducing it to the un- constrained problem $\min \> y^ 2 + (y − 1)^ 3$ . But something is wrong with this approach. What is it and how can it be corrected?

Answer 1

Part 1:

The problem has the form $\min \{ f(x) | h(x) = 0 \}$. (I am using $x \in \mathbb{R}^2$ here.)

It helps to plot the set of $x$ satisfying $h(x) = 0$.

A look at the picture will convince you that the solution is $(0,1)$.

The Fritz John conditions are necessary conditions and always hold at an extremum. In this case, the Fritz John conditions give: $h(x) = 0$ and $\lambda_0 \nabla f(x) + \nu \nabla h(x) = 0$, with $\lambda_0 \ge 0$ and $(\lambda_0, \nu) \neq 0$. (Note the presence of the $\lambda_0$, which is different from the Lagrange conditions.)

The points that satisfy the Fritz John conditions are the $((x_1,x_2), \lambda_0, \nu)$ that satisfy the above conditions. \begin{eqnarray} x_1^2 - (x_2-1)^3 &=& 0 \\ \lambda_0 \binom{x_1}{x_2} + \nu \binom{2x_1}{-3(x_2-1)^2} &=& 0 \end{eqnarray} We solve this by case analysis.

Suppose $x_1 \neq 0$. Then the top line of the gradient equation gives $\lambda_0 = - 2 \nu$ and hence both are non zero. Substituting for $\lambda_0$ and dividing through by $-\nu$ gives $2 x_2 + 3(x_2-1)^2 = 0$. This quadratic has no real solutions.

Hence we must have $x_1=0$, then the constraint gives $x_2 = 1$, and the gradient condition gives $\lambda_0 = 0$, hence the Fritz John points are $((0,1),0, \nu)$, with $\nu \neq 0$.

Note that the multiplier on $\nabla f(x)$ is zero.

Part 2:

Note that if $h(x) = 0$, we must have $x_2 \ge 1$. This is a subtle implicit constraint that 'disappears' if we just substitute $(x_2-1)^3$, for $x_1^2$. If we eliminate $x_1$ by substituting $x_1^2 = (x_2-1)^3$, we must also ensure that $x_2 \ge 1$. If we do not add the latter constraint, then it should be clear that the cost $y^2+(y-1)^3$ is unbounded below.

As an aside, the 'problem' here is that the relation $x_1^2 = (x_2-1)^3$ is not a function, despite the suggestive form in which it is written. If the constraint was of the form $h(x) = x_1-g(x_2)$, then we could safely substitute $x_1$ by $g(x_2)$.