Optimising under arbitrarily many constraint equations

post by dkl9 · 2024-09-12T14:59:28.475Z · LW · GW · 0 comments

This is a link post for https://dkl9.net/essays/general_lagrange.html

Contents

  Lagrange, anyway
  Determinants
  § Example
None
No comments

Say we have a multivariate function to optimise, like $f=x^2+y^2+z^2$, under some constraints, like $g_1=x^2+y^2-z$ and $g_2=y+z-1$, both to equal zero.

The common method is that of Lagrange multipliers.

1. Add a variable $\lambda$ for each constraint function — here, we'll use ${\lambda }_1$ and ${\lambda }_2$.
2. Declare the set of equations $\nabla f={\lambda }_1\nabla g_1+{\lambda }_2\nabla g_2$.
3. Bring in the equations $g_1=0$ and $g_2=0$ (etc, if there are more constraints).
4. Solve for $\lambda$ and, more importantly, the inputs $x$, $y$, $z$.

Lagrange multipliers annoy me, insofar as they introduce extra variables. There is another way — arguably more direct, if perhaps more tedious in calculation and less often taught. I found it alone, tho surely someone else did first — probably Euler.

Lagrange, anyway

For the sake of a standard answer to check against, let's use Lagrange multipliers.

The gradient of $x^2+y^2+z^2$ is $[2x,2y,2z]$. Likewise, $\nabla (x^2+y^2-z)=[2x,2y,-1]$, and $\nabla (y+z-1)=[0,1,1]$. So step 2 gives these equations:

• $2x=2x{\lambda }_1$
• $2y=2y{\lambda }_1+{\lambda }_2$
• $2z=-{\lambda }_1+{\lambda }_2$

It readily follows that ${\lambda }_1=1$ or $x=0$.

If ${\lambda }_1=1$, then ${\lambda }_2=0$, and $z=-\frac{1}{2}$. By the second constraint, $y+z-1=0$, find that $y=\frac{3}{2}$. By the first constraint, $x^2+y^2-z=0$, find that $x^2=-\frac{11}{4}$, which is a contradiction for real inputs.

If $x=0$, then, by the first constraint, $z=y^2$, and, by the second constraint, $y^2+y-1=0$, so $y=\frac{-1\pm \sqrt{5}}{2}$ and $z=\frac{3\mp \sqrt{5}}{2}$.

Determinants

With one constraint, the method of Lagrange multipliers reduces to $\nabla f=\lambda \nabla g$. $\nabla f$ and $\nabla g$ are vectors, which differ by a scalar factor iff they point in the same (or directly opposite) directions iff (for three dimensions) the cross product $\nabla f\times \nabla g=0$ iff (for two dimensions) the two-by-two determinant $\left|\nabla f\nabla g\right|=0$.

With two constraints, the method asks when $\nabla f=\lambda \nabla g+\mu \nabla h$. That would mean $\nabla f$ is a linear combination of $\nabla g$ and $\nabla h$, which it is iff $\nabla f$, $\nabla g$, and $\nabla h$ are all coplanar iff (for three dimensions) the three-by-three determinant $\left|\nabla f\nabla g\nabla h\right|=0$.

As it happens, the cross product is a wolf that can wear determinant's clothing. Just fill one column with basis vectors: $\nabla f\times \nabla g=\left|\nabla f\nabla g\right[\hat{i}\hat{j}\hat{k}\left]\right|$.

Likewise, with zero constraints, the "method of Lagrange multipliers" — really, the first-derivative test — asks when $\nabla f=0$. Fill a three-by-three matrix with two columns of basis vectors: $\left[\nabla f\right[\hat{i}\hat{j}\hat{k}\left]\right[\hat{i}\hat{j}\hat{k}\left]\right]$. Suppose the basis vectors multiply like the cross product, as in geometric algebra. Then the determinant, rather than the usual 0 for a matrix with two equal columns, turns out to equal that ordinary column vector $\nabla f$ (up to a scalar constant).

In every scenario so far — and I claim this holds for higher dimensions and more constraints — the core equations to optimise under constraints are the actual constraint equations, along with a single determinant. The matrix has its columns filled with the gradient of the function to optimise, each constraint gradient, and copies of the basis vectors, in order, to make it square.

§ Example

Fill a matrix with those gradients given above. We'll take its determinant.

$\nabla f$	$\nabla g_1$	$\nabla g_2$
$2x$	$2x$	$0$
$2y$	$2y$	$1$
$2z$	$-1$	$1$

The determinant, when simplified, is $2x(1+2z)$. The equations to consider are just

• $2x(1+2z)=0$
• $x^2+y^2-z=0$
• $y+z-1=0$

The first tells us that $x=0$ or $z=-\frac{1}{2}$. If $x=0$, $z=y^2$, so $y^2+y-1=0$, so $y=\frac{-1\pm \sqrt{5}}{2}$, and $z=\frac{3\mp \sqrt{5}}{2}$. If $z=-\frac{1}{2}$, then $y=\frac{3}{2}$ and $x$ is imaginary. These are the same results as above; the method works, using only the variables given in the problem.

0 comments

Comments sorted by top scores.