Conditional minimization problem

148 Views Asked by At

Solve the constrained optimization:

Minimize $$f(x,y,z,w)=2x^2+3y^2+3z^2+w^2-2xy+xz$$ subject to the constraints $$ \begin{cases} x+2y-z=7\\[4pt] x-z+w=6\\ \end{cases} $$

I tried to solve with Lagrangean, but I'm getting into systems with more variables than equations, and even manipulating can't solve.

I'm studying with Luenberger's book (Linear and nonlinear programming. Cap 11 - Constrained Minizimation Conditions), but didn't help much

2

There are 2 best solutions below

1
On BEST ANSWER

There's no need for Lagrange multipliers . . .

Using the two linear constraints, one can solve for $w,z$ in terms of $x,y$ and then replace $w,z$ in $f$, yielding

$$f(x,y,z,w) = g(x,y) = 6x^2+19y^2+12xy-49x-88y+148$$

Taking partial derivatives of $g$, you get a unique critical point $$(x_1,y_1)=\bigl({\small{\frac{31}{12}}},{\small{\frac{3}{2}}}\bigr)$$ which yields the value $$g(x_1,y_1)={\small{\frac{449}{24}}}\approx 18.7$$

Claim: $g(x_1,y_1)$ is a global minimum value of $g$.

To prove the claim, it suffices to show $$g(x,y) \ge g(x_1,y_1)$$ for all $(x,y)\in D$, where $$D=\{(x,y)\in \mathbb{R}^2\mid 6x^2+19y^2\ge (120)^2\}$$

So fix $(x,y)\in D$, and let $u=\sqrt{6x^2+19y^2}$.

Then we get the inequalities \begin{align*} |x| &\le \frac{u}{\sqrt{6}} \le \frac{u}{2}\\[4pt] |y| &\le\frac{u}{\sqrt{19}} \le \frac{u}{4}\\[4pt] \end{align*} and also, by $\text{AM}$-$\text{GM}$, we get $$u^2 = 6x^2+19y^2 \ge \left(2\sqrt{114}\right)|xy| \ge 20|xy|$$ hence $$|xy|\le \frac{u^2}{20}$$

Since $(x,y)\in D$, we have $u \ge 120$, hence \begin{align*} g(x,y) &=6x^2+19y^2+12xy-49x-88y+148\\[4pt] &=(6x^2+19y^2)+12(xy) - (49x + 88y) + 148\\[4pt] &\ge u^2 - 12\left({\small{\frac{u^2}{20}}}\right) - \left( 49\bigl({\small{\frac{u}{2}}}\bigr) + 88\bigl({\small{\frac{u}{4}}}\bigr) \right) +148 \\[4pt] &={\small{\frac{2}{5}}}u^2-{\small{\frac{93}{2}}}u+148\\[4pt] &={\small{\frac{1}{10}}}u(4u-465)+148\\[4pt] &\ge{\small{\frac{1}{10}}}(120)(4(120)-465)+148\\[4pt] &=328\\[4pt] &> {\small{\frac{449}{24}}}\\[4pt] &=g(x_1,y_1)\\[4pt] \end{align*} Therefore $g(x_1,y_1)= {\large{\frac{449}{24}}}\\[4pt]$ is a global minimum value of $g$, as claimed.

It follows that ${\large{\frac{449}{24}}}$ is a global minimum value of $f$, subject to the given constraints.

Note:

  • Finding the critical point $(x_1,y_1)$ of $g$ was the easy.$\\[4pt]$
  • Showing that $g(x_1,y_1)$ is the global minimum value of $g$ required a fair amount of work.

Next, consider an alternative solution via Lagrange multipliers . . .

We want to minimize $$f(x,y,z,w)=2x^2+3y^2+3z^2+w^2-2xy+xz$$ subject to the constraints \begin{align*} p(x,y,z,w)&=x+2y-z=7\\[4pt] q(x,y,z,w)&=x-z+w=6\\[4pt] \end{align*} Then we have \begin{align*} \nabla f &= \langle{4x-2y+z,6y-2x,6z+x,2w}\rangle\\[4pt] \nabla p &= \langle{1,2,-1,0}\rangle\\[4pt] \nabla q &= \langle{1,0,-1,1}\rangle\\[4pt] \end{align*} The local extrema of $f$, subject to the given constraints, satisfy $$\nabla f = a\nabla{p}+ b\nabla{q}$$ for some $a,b \in \mathbb{R}$.

Hence, we get the system \begin{align*} x+2y-z&=7\tag{eq1}\\[4pt] x-z+w&=6\tag{eq2}\\[4pt] 4x-2y+z&=a+b\tag{eq3}\\[4pt] 6y-2z&=2a\tag{eq4}\\[4pt] 6z+x&=-a-b\tag{eq5}\\[4pt] 2w&=b\tag{eq6}\\[4pt] \end{align*} of $6$ linear equations in $6$ unknowns, which has the unique solution $$ (x_1,y_1,z_1,w_1,a_1,b_1)= \bigl( {\small{\frac{31}{12}}}, {\small{\frac{3}{2}}}, {\small{\frac{-17}{12}}}, 2, {\small{\frac{23}{12}}}, 4 \bigr) $$ yielding $$f(x_1,y_1,z_1,w_1)={\small{\frac{449}{24}}}$$ matching our previous result.

However, short of reverting back to the non-Lagrange proof, I don't see an easy way of showing that ${\large{\frac{449}{24}}}$ is a global minimum value of $f$, subject to the given constraints.

Thus, for this problem, I would regard the non-Lagrange approach as the better approach.

1
On

I plowed through Lagrange multipliers, not the hardest I've done, not the easiest. As the gradient of a quadratic form is just the Hessian matrix times the position vector, setting it equal to a linear combination ends up a 6 by 6 linear system. Extreme at $$ (x,y,z,w) = \left( \frac{31}{12}, \; \frac{18}{12}, \;\frac{-17}{12}, \;\frac{24}{12} \right) $$ The gradient of the quadratic form at that point is $$ (x,y,z,w) = \left( \frac{71}{12}, \; \frac{46}{12}, \;\frac{-71}{12}, \;\frac{48}{12} \right) $$ which is $$ \frac{23}{12}(1,2,-1,0) + \frac{48}{12}(1,0,-1,1) $$

The value of the quadratic form there is $$ \frac{449}{24} \approx 18.70833 $$