Why Lagrange Multiplier Doesn't Work?

Question

Question: Find maximum value $f(x,y,z) = xy + zy + xz - 4xyz$ subject to constraint $x + y + z = 1$ and $x,y,z \geq 0$. $$ g(x,y,z) = x + y + z - 1 $$ and $$ \nabla g(x,y,z) \neq 0, \qquad \nabla g(x,y,z) = \langle 1,1,1 \rangle. $$ When we apply Lagrange Multiplier Method, we find $f \bigl( \frac{1}{2}, \frac{1}{4}, \frac{1}{4} \bigr) = \frac{3}{16}$, the maximum value, but the answer is $f \bigl( 0, \frac{1}{2}, \frac{1}{2} \bigr) = \frac{1}{4}$.

Why does that happen? Lagrange Multiplier Method has a only $1$ rule: $\nabla g(x,y,z) \neq 0$, there is no rule break.

EDİT: I find f(0,1/2,1/2) with another method and f(1/2,1/4,1/4) is not both a global maxima and a global minima point but Lagrange Multiplier gives that result, and f(1/2,1/4,1/4) is not a local minimum f(0,0,1) is lower than that.

Answer 1

The Lagrange multipliers method to be applied, requires that the inequalities involved, be transformed into equivalent equations, as follows.

$$ L(x,y,z,\lambda_0,\lambda_1,\lambda_2,\lambda_3,s_1,s_2,s_3) = f(x,y,z) + \lambda_0 g(x,y,z) + \lambda_1(x-s_1^2)+\lambda_2(y-s_2^2)+\lambda_3(z-s_3^2) $$

and the stationary points are the solutions for

$$ \nabla L = 0 = \left\{ \begin{array}{l} \lambda_0+\lambda_1-4 y z+y+z \\ \lambda_0+\lambda_2-4 x z+x+z \\ \lambda_0+\lambda_3-4 x y+x+y \\ x+y+z-1 \\ x-s_1^2 \\ y-s_2^2 \\ z-s_3^2 \\ -2 \lambda_1 s_1 \\ -2 \lambda_2 s_2 \\ -2 \lambda_3 s_3 \\ \end{array} \right. $$

after solution we have

$$ \left( \begin{array}{ccccccccccc} f & x & y & z & \lambda_0 & \lambda_1 &\lambda_2 &\lambda_3 & s_1^2 & s_2^2 & s_3^2\\ 0 & 0 & 0 & 1 & 0 & -1 & -1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & -1 & 0 & -1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & -1 & -1 & 1 & 0 & 0 \\ \frac{5}{27} & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & -\frac{2}{9} & 0 & 0 & 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{3}{16} & \frac{1}{4} & \frac{1}{4} & \frac{1}{2} & -\frac{1}{4} & 0 & 0 & 0 & \frac{1}{4} & \frac{1}{4} & \frac{1}{2} \\ \frac{3}{16} & \frac{1}{4} & \frac{1}{2} & \frac{1}{4} & -\frac{1}{4} & 0 & 0 & 0 & \frac{1}{4} & \frac{1}{2} & \frac{1}{4} \\ \frac{3}{16} & \frac{1}{2} & \frac{1}{4} & \frac{1}{4} & -\frac{1}{4} & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{4} & \frac{1}{4} \\ \frac{1}{4} & 0 & \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{4} & \frac{1}{2} & 0 & \frac{1}{2} & -\frac{1}{2} & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ \frac{1}{4} & \frac{1}{2} & \frac{1}{2} & 0 & -\frac{1}{2} & 0 & 0 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 0 \\ \end{array} \right) $$

NOTE

The inequalities $x>0,y>0,z>0$ were handled as $x-s_1^2=0,y-s_2^2=0, z-s_3^2=0$ hence when in the solution $s_i=0$ then the $i$ restriction is actuating.

Answer 2

$ \def\d{\delta}\def\l{f}\def\s{\sigma} \def\o{{\tt1}}\def\p{\partial} \def\LR#1{\left(#1\right)} \def\BR#1{\Big(#1\Big)} \def\diag#1{\operatorname{diag}\LR{#1}} \def\Diag#1{\operatorname{Diag}\LR{#1}} \def\trace#1{\operatorname{Tr}\LR{#1}} \def\qiq{\quad\implies\quad} \def\grad#1#2{\frac{\p #1}{\p #2}} \def\c#1{\color{red}{#1}} \def\CLR#1{\c{\LR{#1}}} \def\gradLR#1#2{\LR{\grad{#1}{#2}}} \def\m#1{\left[\begin{array}{r}#1\end{array}\right]} $Introduce an unconstrained vector $w$ and the all-ones vector $\o$, and use them to construct an $x$ vector having the desired properties by utilizing an element-wise softmax function
$$\eqalign{ w &= \m{u\\v\\w} \qquad x = \m{x\\y\\z}= \frac{e^w}{\o^Te^w} \\ }$$ Note that the components of $x$ are all positive and sum to one.

The differential of the softmax is well known $$\eqalign{ dx = \LR{X-xx^T}dw, \qquad\quad X = \Diag x,\;\;\d=\det(X) \\ }$$ Notice that $\;\LR{X-xx^T}\o = 0$

The objective function can be written in matrix form and differentiated. $$\eqalign{ \l &= \tfrac 12(J-I):xx^T - 4\d \\ d\l &= (J-I)x:dx - 4\d X^{-1}:dX \\ &= (\o-x):dx - 4\d X^{-1}\o:dx \\ &= \LR{X-xx^T}\LR{(\o-x) - 4\d X^{-1}\o}:dw \\ &= \LR{(x:x)x - Xx - 4\d\LR{I-x\o^T}\o}:dw \\ &= \LR{(X:X)X\o - X^2\o + 4\d\LR{nx-\o}}:dw \\ \grad{\l}{w} &= {(X:X)X\o - X^2\o + 4\d\LR{nX\o-\o}} \\ }$$ where $J=\o\o^T$ is the all-ones matrix, $I$ is the identity matrix, and colons denote the inner product $$A:B=\trace{A^TB}$$ Setting this unconstrained gradient to zero yields $$\eqalign{ X^2\o &= (X:X)X\o + 4\d\LR{nX\o-\o} \\ }$$ Expand $\,X = x\LR{e_1e_1^T} + y\LR{e_2e_2^T} + z\LR{e_3e_3^T} \;$ and evaluate terms $$\eqalign{ n &= 3 \\ \d &= xyz \\ X:X &= x^2+y^2+z^2 \\ X\o &= xe_1 + ye_2 + ze_3 \\ X^2\o &= x^2e_1 + y^2e_2 + z^2e_3 \\ }$$ Now consider the $e_3$-component of the zero-gradient condition and assume $z\ne 0$ $$\eqalign{ z^2 &= (x^2+y^2+z^2)\c{z} + 4xy\c{z}\LR{nz-\o} \\ z &= (x^2+y^2+z^2) + 4xy\LR{nz-\o} \\ }$$ The other two components are similarly obtained as $$\eqalign{ x &= (x^2+y^2+z^2) + 4yz\LR{nx-\o} \\ y &= (x^2+y^2+z^2) + 4xz\LR{ny-\o} \\ }$$ and their difference is $$\eqalign{ \LR{x-y} &= 4z\LR{nxy-y -nxy+x} \;=\; 4z\LR{x-y} \\ }$$ If $\,x\ne y\,$ then dividing by $\LR{x-y}\,$ yields $\,z=\frac 14.\;$ Furthermore
if $\,x\ne z\,$ then $\,y=\frac 14,\;$ and the constraint yields last component as $$\quad x=\LR{\o-\frac 14-\frac 14}= \frac 12$$ Since $(x,y,z)$ are indistinguishable, we have found 3 solutions $$\eqalign{ \LR{x,y,z} &= \LR{\frac 12,\frac 14,\frac 14}, \quad \LR{\frac 14,\frac 12,\frac 14}, \quad \LR{\frac 14,\frac 14,\frac 12} \\ }$$ Now consider the case where $\,z=0,\,$ which reduces the remaining component equations to $$\eqalign{ x &= (x^2+y^2) \\ y &= (x^2+y^2) \\ }$$ Since $y=x$, eliminating $y$ yields $$\eqalign{ x &= 2x^2 \qiq x = \frac 12 \\ }$$ which produces another 3 locations where the gradient is zero $$\eqalign{ \LR{x,y,z} &= \LR{\frac 12, \frac 12, 0}, \quad \LR{\frac 12, 0, \frac 12}, \quad \LR{0, \frac 12, \frac 12} \\ }$$ Finally, assume that $y=z=0$, which leaves just one component equation $$\eqalign{ x &= x^2 \qiq x=\o \\ }$$ and yields 3 additional zero-gradient solutions $$\eqalign{ \LR{x,y,z} &= \LR{1, 0, 0}, \quad \LR{0, 1, 0}, \quad \LR{0, 0, 1} \\ }$$ The zero-gradient condition alone cannot distinuish between minima, maxima, and saddle-points. And calculating the Hessian is tedious. But evaluating the objective function for each of the solutions above is quick and easy (due to indistinguishability, you only need to check one from each group). $$\eqalign{ f\LR{\frac 12, \frac 14, \frac 14} &= \frac {3}{16} \\ f\LR{\frac 12, \frac 12, 0} &= \frac 14 &&\{{\rm maximum}\} \\ f\BR{1, 0, 0} &= 0 &\quad&\{{\rm minimum}\} \\ }$$

Answer 3

You may use KKT conditions instead.

Or you may apply Lagrange Multiplier for the following equivalent problem:
Find the maximum of $F(a, b, c) = a^2b^2 + b^2c^2 + c^2a^2 -4a^2b^2c^2$ subject to $a^2+b^2+c^2 = 1$.
(Note: We have only one constraint. )

Let $$L(a, b, c) := a^2b^2 + b^2c^2 + c^2a^2 -4a^2b^2c^2 + \lambda (a^2 + b^2 + c^2 - 1).$$ We have \begin{align*} \frac{\partial L}{\partial a} &= -2a(4b^2c^2 - b^2 - c^2 - \lambda) = 0,\\ \frac{\partial L}{\partial b} &= -2b(4c^2a^2 - a^2 - c^2 - \lambda ) = 0, \\ \frac{\partial L}{\partial c} &= -2c(4a^2b^2 - a^2 - b^2 - \lambda) = 0, \\ \frac{\partial L}{\partial \lambda} &= a^2 + b^2 + c^2 - 1 = 0. \end{align*}

Let us solve this system of equations.

If $abc \ne 0$, we have \begin{align*} 4b^2c^2 - b^2 - c^2 - \lambda &= 0, \tag{1}\\ 4c^2a^2 - a^2 - c^2 - \lambda & = 0, \tag{2}\\ 4a^2b^2 - a^2 - b^2 - \lambda &= 0, \tag{3}\\ a^2 + b^2 + c^2 - 1 &= 0. \tag{4} \end{align*} We can easily get all four solutions of $(a^2, b^2, c^2, \lambda)$: $$(1/4, 1/4, 1/2, -1/4), (1/2, 1/4, 1/4, -1/4), (1/4, 1/2, 1/4, -1/4), (1/3,1/3, 1/3, -2/9).$$ (Note: We actually need $a^2, b^2, c^2$. We don't need $a, b, c$.)

If $a=b=0$, we have $c^2 = 1, \lambda = 0$.

If $a=c=0$, we have $b^2 = 1, \lambda = 0$.

If $b=c=0$, we have $a^2 = 1, \lambda = 0$.

If $a = 0, bc \ne 0$, we have $b^2 = c^2 = 1/2$ and $\lambda = -1/2$.

If $b = 0, ac \ne 0$, we have $a^2 = c^2 = 1/2$ and $\lambda = -1/2$.

If $c = 0, ab \ne 0$, we have $a^2 = b^2 = 1/2$ and $\lambda = -1/2$.

It is easy to get the maximum $1/4$ when $a = 0, b^2 = c^2 = 1/2$ or $b = 0, c^2 = a^2 = 1/2$ or $c = 0, a^2 = b^2 = 1/2$.

Come back to the original problem. The maximum is $1/4$ when $x = 0, y = z = 1/2$ or $y = 0, x = z = 1/2$ or $z = 0, x = y = 1/2$.