# Constrained Optimization - Lagrange Multipliers (Example)

Let $f(x, y, z) = xyz$

$h1(x, y, z) = x + y + z − 4$5

and $h2(x, y, z) = 2x − y$.

Goal:

Minimize $f(x, y, z)$ subject to $h1(x, y, z) = 0$ and $h2(x, y, z) = 0$.

First part: Show that every feasible point is regular.

Clear since $h1$ and $h2$ will always be linearly independent given that $z$ is zero.

Now:

1. Use the first order necessary conditions to find all candidates for local minimum points.

2. Compute the tangent spaces to all the candidates.

3. Use second order necessary and sufficient conditions to decide which of the points are indeed local minimum points.

I obtained the following system with $\lambda_1$ = lambda one and $\lambda_2$ = lambda two:

$yz - \lambda_1 - 2\lambda_2 = 0$

$xz - \lambda_1 - \lambda_2 = 0$

$xy - \lambda_1 = 0$

$x+y+z-45 =0$

$2x-y =0$

Main questions:

Is this system correct? Will answering 2 involve simply determining $x,y,z$ in terms of $L1/L2$ and solving? Is there a general procedure for answering parts 2 and 3? If nothing else, how might one compute tangent spaces for candidates?

Thank you for taking the time to read this rather long question.

-

The Lagrangian of your problem is $L(x,y,z,\lambda_1, \lambda_2) = xyz - \lambda_1 (x+y+z-45) - \lambda_2 (2x-y)$ so your system of first-order conditions is almost correct: the second equation should be $xz - \lambda_1 + \lambda_2 = 0$.

I did not understand your justification that all feasible points are regular. Here you need to compare the gradients $\nabla h_1(x,y,z)$ and $\nabla h_2(x,y,z)$. In addition, they don't need to be linearly independent at all feasible points but only at solutions of the first-order conditions.

For each candidate $(x^*,y^*,z^*)$ the tangent space is defined as $$\mathcal{K}(x^*,y^*,z^*) := \left\{ d \mid \nabla h_i(x^*,y^*,z^*)^T d = 0, \ i = 1, 2 \right\}.$$ It must be recomputed for each candidate. Finally, second-order necessary conditions require that the Hessian $\nabla^2 L(x^*,y^*,z^*,\lambda_1^*,\lambda_2^*)$ be positive semi-definite on $\mathcal{K}(x^*,y^*,z^*)$. This means that for all $d$ in $\mathcal{K}(x^*,y^*,z^*)$, $$d^T \nabla^2 L(x^*,y^*,z^*,\lambda_1^*,\lambda_2^*) d \geq 0.$$ The second-order sufficient conditions require $> 0$ instead of $\geq 0$. Again, these conditions must be checked for each candidate. Note that the second derivatives of $L$ are only computed with respect to $x$, $y$ and $z$---the variables of the problem.

It's also possible that in some cases, the gradients $\nabla h_1$ and $\nabla h_2$ are not linearly independent but yet there exist solutions to the first-order conditions. In this case, there will be multiple possible choices of $\lambda^*$ and the second-order conditions take a slightly different form.

-
@user60684 I understand. For such small-dimensional examples, you can often determine independence by inspection. More generally, you'd have to check that the matrix $\begin{bmatrix} \nabla h_1 & \cdots & \nabla h_m \end{bmatrix}$ has full column rank. In your example, $\mathcal{K}$ is a straight line: the vectors $d = (d_1, d_2, d_3)$ orthogonal to $\nabla h_1$ are such that $d_1 + d_2 + d_3 = 0$. Those orthogonal to $\nabla h_2$ are such that $d_2 = 2 d_1$. Substituting into the first equality, you get $d = (d_1, 2 d_1, -3d_1)$. – Dominique Feb 2 '13 at 21:15
$\mathcal{K}$ is the set of vectors $d$ that are orthogonal to all equality constraint gradients, so the conditions add up. You found two independent vectors orthogonal to $\nabla h_1$ and they determine a plane. Similarly you can find two independent vectors orthogonal to $\nabla h_2$ and they determine another plane. $\mathcal{K}$ is the intersection of the two planes. The Hessian must be positive definite for those vectors $d$ in $\mathcal{K}$, i.e., those that are orthogonal to all the gradients. Your Hessian is correct. – Dominique Feb 2 '13 at 23:14
That makes sense, and in this case since we already know h1 and h2 are linearly independent at our desired points we know that vectors orthogonal to them will be linearly independent as well? That is, why is it not redundant to check each of the four vectors orthogonal to h1 and h2? – user60684 Feb 3 '13 at 15:14
@user60684 In the 2nd-order conditions you want to check all vectors $d \in \mathcal{K}$, not just a few select ones. So you need to express $\mathcal{K}$ in a generic way, i.e., give the general form of any vector in $\mathcal{K}$. In your example, $\mathcal{K}$ consists of all vectors of the form $(d_1, 2d_1, -3d_1)$ with $d_1 \in \mathbb{R}$. If you use such a generic vector when you check 2nd-order conditions, you've checked them for all elements of $\mathcal{K}$. Does that make sense? – Dominique Feb 3 '13 at 16:08
min(xyz)=600 right ? – Erogol Dec 6 '13 at 16:25