# Finding Fritz-John multipliers

We have the optimization problem:

Minimize $$f(x,y) = (x+1)^2 + y^2$$ subject to $$g(x,y) = -x^3 + y^2 \leq 0$$.

We would like to find multipliers $$\lambda_0, \lambda_1$$ satisfying the Fritz-John optimality conditions, and show that KKT fails here.

In regards to Fritz-John, we have the following system if I am not mistaken

$$\begin{cases}2\lambda_0 (x+1)-3\lambda_1x^2 = 0 \\ 2\lambda_0y+2\lambda_1y = 0\\ -x^3+y^2 \leq 0 \\ \lambda_1(-x^3+y^2) = 0\end{cases}$$

Option 1: Suppose that the feasability constraint $$-x^3 + y^2 \leq 0$$ is not binding, meaning $$-x^3 + y^2 < 0$$. Then $$\lambda_1 = 0$$ and our system reduces to $$\begin{cases}2\lambda_0 (x+1) = 0\\2\lambda_0y = 0\end{cases}$$

If $$\lambda_0 = 0$$ then all our lambdas are zero which violates the FJ conditions, so $$\lambda_0 \neq 0$$, and so $$x = -1$$ and $$y=0$$. Sadly $$(x,y) = (-1, 0)$$ is not a feasable point since it violates $$-x^3 + y^2 < 0$$

So all in all, option 1 is not relevant.

Option 2: the feasability constraint is binding, so $$-x^3 + y^2 = 0$$ or $$x = y^{\frac{2}{3}}$$. Now our system reduces to

$$\begin{cases}2\lambda_0 (y^{\frac{2}{3}}+ 1) - 3\lambda_1 y^{\frac{4}{3}} = 0 \\ 2\lambda_0 y + 2\lambda_1y = 0\end{cases}$$

I'm unsure what to do now. There's no way to find all three variables. I was specifically asked for the lambdas. If we assume that $$y = 0$$ then there's no way to find the lambdas, they could be anything.

If we assume that $$y \neq 0$$ then we have $$\lambda_1 = -\lambda_0$$ and our first equation becomes $$2\lambda_0(y^{\frac{2}{3}} + 1) +3\lambda_0 y^{\frac{4}{3}} = \lambda_0 (2(y^{\frac{2}{3}} + 1) + 3y^{\frac{4}{3}}) = 0$$.

Now again we must have $$\lambda_0 = 0$$ which means all lambdas are zero but FJ doesn't allow for that.

Help?

It is straightforward to show that a solution exists and the constraint must be active

The Fritz John conditions give $$\lambda_0 Df((x,y)) + \lambda_1 Dg((x,y)) = 0$$, with $$(\lambda_0,\lambda_1) \neq 0$$.

We get $$2(\lambda_0+\lambda_1)y = 0$$, so either $$y=0$$ or $$\lambda_0+\lambda_1 = 0$$.

If $$\lambda_0 + \lambda_1 = 0$$ then we obtain $$2(x+1)+3x^2 = 0$$ which has no (real) solution hence this is impossible.

Consequently $$y=0$$ from which we obtain $$x=0$$ (since $$y^2 = x^3$$) which gives a cost of $$1$$. Since $$2 \lambda_0 = 0$$ we see that $$\lambda_0 = 0$$ and so $$\lambda_1>0$$.

Hence any multiplier of the form $$(0,t)$$, with $$t>0$$ will do.

As an aside, the multipliers (which are non negative) are often normalised to lie on the simplex, so in this case, the solution would be $$\lambda=(0,1)$$.

Note that $$Dg((0,0)) = 0$$, so KKT does not apply (that is, it does not fail!).

• "Consequently $y=0$ from which we obtain $x=0$" is wrong. We know $-x^3 + y^2 \leq 0$, not that they are equal to zero. – Oria Gruber Dec 16 '19 at 20:25
• If the constraint is active (see first sentence) then we must have equality. How is that reasoning wrong? – copper.hat Dec 16 '19 at 20:30
• By active you mean strict? As in it's an equality constraint rather than inequality – Oria Gruber Dec 16 '19 at 20:54
• A constraint $g(x) \le 0$ is active at $x^*$ iff $g(x^*) = 0$. – copper.hat Dec 16 '19 at 21:17
• Note that I should have just dismissed the $\lambda_0+\lambda_1 = 0$ possibility immediately as we have $\lambda_k \ge 0$ and $(\lambda_0,\lambda_1) \neq 0$. – copper.hat Dec 17 '19 at 4:26