# lagrangian minimisation problem and Karush-Kuhn-Tucker conditions

A rectangular box without a lid is to be made from 50m² of cardboard. Find the maximum volume of such a box.( i know how to solve this in the conventional way, i am trying to figure out how to do it using this method, where the problem needs to be converted to a minimisation method then using the Karush-Kuhn-Tucker conditions)

objective function and constraints will be: $\max [f(x,y,z)]=xyz$ subject to $h(x,y,z)=xy+2yz+2zx-50=0$

Now to Convert to standard Lagrangian minimisation problem I use the fact that $\min f(x)=\max -f(x)$ then the langrangian $$L(x,y,z)=f(x,y,z)-kc(x,y,z)= -xyz-k(xy+2yz+2zx-50)$$ and this should now be a minimisation problem

The Karush-Kuhn-Tucker conditions state that for a minimisation problem: $\nabla L(x^*,y^*,z^*,k^*)=0$ and $c(x^*,y^*,z^*)=0$ where the values of $x^*,y^* z^*$ are the solutions for the minimum.

then if i can show that the hessian matrix for the langrangian $L(x^*,y^*,z^*,k^*)$ is positive definite then this shows that the values i have found corespond to the global minimum.

I cant actually solve the equations $\nabla L(x*,y*,z*,k*)=0$ and $c(x*,y*,z*)=0$. When i put them in matrix form i get a mess, so this is what i am stuck on and i am starting to get a bit confused.

• From $L_z = 0$ derive $k$ as a functions of $x,y$ and from $c = 0$ derive a constraint for $z$ as a function of $x,y$. Plug those into $L_x =0$ and $L_y = 0$ to get a nonlinear system with 2 equations and 2 unknowns. Both left-hand sides should be rational functions, so it should boil down to polynomial factoring. – gt6989b Aug 7 '12 at 15:11
• As i said I'm stuck at this point. I have worked through deriving the expressions but have been unable to solve them, which is the point of my question. – Johnny Byr Aug 7 '12 at 23:53

Note first that since $L(x,y,z,k) = −xyz−k(xy+2z(x+y)−50) = L(y,x,z,k)$, the problem is symmetric in $x,y$.

Let's proceed with brutal arithmetic. We have 4 equations in 4 unknowns:

$$\begin{split} 0 &= -L_x = yz + k(y + 2z)\\ 0 &= -L_y = xz + k(x + 2z)\\ 0 &= -L_z = xy + 2k(x + y)\\ 50 &= xy+2z(x+y) \quad (\text{from } c=0) \end{split}$$

Claim 1. $x \neq 0$ and $y \neq 0$ and $x + y \neq 0$.

Proof. Note first that if $x=0$, then the second constraint implies $k=0$ or $z=0$. If $x=k=0$, the first constraint implies $yz=0$ and the last constraint implies $2yz=50$, which is impossible.

Similarly, if $x=z=0$, the first constraint implies $ky = 0$. As we proved, $k=0$ is impossible, so must be $x=y=z=0$, which contradicts the last constraint.

To establish the last claim, note that if $x+y =0$, the third constraint yields $xy=0$ and the last one yields $xy=50$, which is a contradiction. QED

Now, solving the last constraint for $z$ and the $L_z$ constraint for $k$, we get

$$k = \frac{-xy}{2(x+y)} \text{ and } z = \frac{50-xy}{2(x+y)}.$$

Both of these are well-defined since $x\neq0$ and $y \neq 0$. Plug both of these into the first constraint, getting

$$0 = \frac{y(50-xy)}{2(x+y)} - \frac{xy^2}{2(x+y)} - \frac{2xy(50-xy)}{2^2(x+y)^2}$$

and now multiply both sides by $2(x+y)^2 \neq 0$ to get

$$0 = y(50-xy)(x+y) - xy^2(x+y) - xy(50-xy).$$

Divide by $y \neq 0$ and bring the last term into the first term and divide by $y$ again: $$\begin{split} 0 &= (50-xy)(x+y) - xy(x+y) - x(50-xy)\\ 0 &= y(50-xy) - xy(x+y) \\ 0 &= 50-xy - x(x+y) = 50 - 2xy - x^2\\ 50 &= x^2 + 2xy \end{split}$$

and because the problem is symmetric, the symmetric constraint must hold (if you want, you can derive it the same way from the second constraint):

$$\begin{split} x^2 + 2xy &= 50 \\ y^2 + 2xy &= 50 \end{split}$$

Hence subtracting them yields $x^2 = y^2$, so $x = \pm y$, but $x \neq -y$ by Claim 1, so $x = y$. Now $50 = x^2 + 2xy = 3x^2$ implies $x = \pm \sqrt{50/3} = y$, and there are two solutions: $(\sqrt{50},\sqrt{50})$ and $(-\sqrt{50},-\sqrt{50})$.

Since $x,y$ are lengths, we know only one will make sense: $x = y = \sqrt{50/3}$. Now plug this back in to find $z$ and $k$ as desired.

• Thanks for that reply gt6989b, i ended up using maple to solve the equations. – Johnny Byr Aug 9 '12 at 9:13
• Great answer. Question: can both equality constraint and its associated multiplier be zero, r does one zero exclude the other? – Hass Feb 28 '18 at 12:49
• @Hass usually they are dual, so if one is non-zero the other is intended to be zero, but there is nothing forcing the other way, so if one is zero, not sure if it forces the other or not – gt6989b Feb 28 '18 at 18:18
• @gt6989b Thanks. Can they be both zero, or that's not possible? – Hass Feb 28 '18 at 21:39
• @Hass I think they can... – gt6989b Nov 25 '19 at 14:25