Why this optimisation problem cannot be solved with "usual" KT conditions?

Question

I have this optimisation problem:

$$f(x, y, z) = 2xy + yz \qquad \text{subject to} \qquad \begin{cases} x+y+2z \leq 1 \\ x \geq 0, y \geq 0, z\geq 0 \end{cases}$$

I solved it with "a certain writing of KT conditions" but with "the usual KT" conditions I cannot solve it.

The point that gives the max is $(1/2, 1/2, 0)$.

What I mean is this: creating the Lagrangian:

$$L = 2xy + yz - \lambda(x+y+2z-1)$$

Usual KT conditions

$$\begin{cases} 2y - \lambda = 0 \\ 2x+z - \lambda = 0 \\ y - 2\lambda = 0 \\ x+y+2z = 1 \\ \lambda(x+y+2z-1) \leq 0 \end{cases} $$

If $\lambda = 0$ I get $(-1/3, 0, 2/3)$ not admissible. If $\lambda \neq 0$ I get $y = 0$ and I cannot solve for $x$ and $z$. In any case the solution is wrong.

Different KT conditions

Those are not really "different", but they come from the notes I found online. Basically they state that since $x, y, z \geq 0$ I have to add complementarity equations, that is:

$$\begin{cases} 2y - \lambda = 0 \quad ; \quad x(2y - \lambda) = 0\\ 2x+z - \lambda = 0 \quad ; \quad y(2x+z - \lambda) = 0\\ y - 2\lambda = 0 \quad ; \quad z(y - 2\lambda) = 0\\ x+y+2z = 1 \\ \lambda(x+y+2z-1) \leq 0 \end{cases} $$

From this, solving and paying attention, I can really find the desired solution.

Can someone please explain me better why I cannot solve the problem with "usual" KT conditions?

Answer 1

Actually you can use the normal KT condition. However, you need to explicitly add the non-negativity constraints $x, y, z \ge 0$ as additional inequality constraints when specifying the Lagrangian.

So the Lagrangian looks like this: $$ L = 2xy + yz - \lambda(x + y + 2z - 1) + \mu(x-0) + \delta(y - 0) + \eta(z - 0). $$ Here $\mu, \delta, \eta$ are the three Lagrange multipliers for the three non-negativity constraints $x \ge 0, y \ge 0$ and $z \ge 0$.

The KT first order conditions are: $$ \begin{align*} &2 y - \lambda + \mu = 0,\\ &2x + z - \lambda + \delta = 0,\\ &y - 2 \lambda + \eta = 0,\\ &\lambda(x + y + 2z - 1) = 0,\\ &\mu x = 0,\\ &\delta y = 0,\\ &\eta z = 0. \end{align*} $$ The 1st and 5th can be used to get rid of $\mu$. In particular, notice that (from the 5th condition) either $\mu = 0$ or $x = 0$. So, we get the condition: $$ x(2y - \lambda) = 0. $$ Indeed, if $x = 0$ then above condition is always satisfied. If $x > 0$ then $\mu = 0$, so by the 1st condition (setting $\mu = 0$) we get $2 y - \lambda = 0$.

Similarly, the 2nd and 6th condition can be combined to: $$ y(2 x + z - \lambda) = 0, $$ and the 3rd and 7th condition can be combined to: $$ z(y - 2 \lambda) = 0. $$

Answer 2

The generalized Lagrangian function is: $$L(x,y,\lambda) = 2xy+yz+\lambda (1-x-y-2z)$$ The Kuhn-Tucker conditions for maximum: $$\begin{cases} L_x=2y-\lambda \le0, \quad \quad \quad \quad x\ge 0, \quad xL_x=0\\ L_y=2x+z-\lambda \le 0 , \quad \ \quad y\ge 0, \quad yL_y=0\\ L_z=y-2\lambda\le0, \quad \ \quad \quad \ \ \ z\ge 0, \quad zL_z=0\\ L_\lambda = 1-x-y-2z\ge 0 , \ \ \lambda\ge 0, \quad \lambda L_\lambda=0 \end{cases}$$ Now you need to check 16 cases (each of $x,y,z,\lambda$ is zero or positive). However, you can take shortcuts.

If $\lambda=0$, then from the 1st and/or 3rd inequalities we get $y=0$.

1. $x=z=0$, so $\color{red}{f(0,0,0)=0}$
2. $x=0,z>0$ or $x>0,z=0$ or $x>0,z>0$ are impossible, because 2nd equation fails.

If $\lambda>0$, then:

1. $x,y,z=0$ is impossible, because $L_\lambda \ne 0$.
2. $x=y=0,z>0$ is impossible, because $L_z=0\Rightarrow \lambda=0$ (contradiction).
3. $x=0,y>0,z=0$ is impossible, because $L_y=0 \Rightarrow \lambda=0$ (contradiction).
4. $x>0,y=z=0$ is impossible, because $L_x=0 \Rightarrow \lambda=0$ (contradiction).
5. $x=0,y>0,z>0$, then $\begin{cases}L_y=0 \\ L_z=0 \\ L_\lambda =0\end{cases}\Rightarrow (y,z,\lambda)=(0.5,0.25,0.25)$ So, $\color{red}{f=0.125}$.
6. $x>0,y=0, z>0$ is impossible, because $L_z=0 \Rightarrow \lambda=0$ (contradiction).
7. $x>0,y>0,z=0$, then $\begin{cases}L_x=0 \\ L_y=0 \\ L_\lambda =0\end{cases}\Rightarrow (x,y,\lambda)=(0.5,0.5,1)$ So, $\color{red}{f=0.5 \text{ (max)}}$.
8. $x>0,y>0,z>0$ is impossible, because $\begin{cases}L_x=0 \\ L_z=0\end{cases}\Rightarrow \begin{cases}y=0.5\lambda \\ y=2\lambda\end{cases}$ (contradiction).