0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ "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. $\endgroup$ – Oria Gruber Dec 16 '19 at 20:25
  • $\begingroup$ If the constraint is active (see first sentence) then we must have equality. How is that reasoning wrong? $\endgroup$ – copper.hat Dec 16 '19 at 20:30
  • $\begingroup$ By active you mean strict? As in it's an equality constraint rather than inequality $\endgroup$ – Oria Gruber Dec 16 '19 at 20:54
  • $\begingroup$ A constraint $g(x) \le 0$ is active at $x^*$ iff $g(x^*) = 0$. $\endgroup$ – copper.hat Dec 16 '19 at 21:17
  • $\begingroup$ 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$. $\endgroup$ – copper.hat Dec 17 '19 at 4:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.