Editing Lagrange multiplier (section)

== Multiple constraints ==
[[Image:As wiki lgm parab.svg|thumb|right|300px|Figure 2: A paraboloid constrained along two intersecting lines.]]
[[Image:As wiki lgm levelsets.svg|thumb|right|300px|Figure 3: Contour map of Figure 2.]]
The method of Lagrange multipliers can be extended to solve problems with multiple constraints using a similar argument. Consider a [[paraboloid]] subject to two line constraints that intersect at a single point. As the only feasible solution, this point is obviously a constrained extremum. However, the [[level set]] of <math> f </math> is clearly not parallel to either constraint at the intersection point (see Figure 3); instead, it is a linear combination of the two constraints' gradients. In the case of multiple constraints, that will be what we seek in general: The method of Lagrange seeks points not at which the gradient of <math> f </math> is a multiple of any single constraint's gradient necessarily, but in which it is a linear combination of all the constraints' gradients.

Concretely, suppose we have <math> M </math> constraints and are walking along the set of points satisfying <math> g_i(\mathbf{x}) = 0, i=1, \dots, M \,.</math> Every point <math> \mathbf{x} </math> on the contour of a given constraint function <math>g_i</math> has a space of allowable directions: the space of vectors perpendicular to <math> \nabla g_i(\mathbf{x}) \, .</math> The set of directions that are allowed by all constraints is thus the space of directions perpendicular to all of the constraints' gradients. Denote this space of allowable moves by <math>\ A\ </math> and denote the span of the constraints' gradients by <math> S \,.</math> Then <math> A = S^{\perp}\, ,</math> the space of vectors perpendicular to every element of <math> S \,.</math>

We are still interested in finding points where <math> f </math> does not change as we walk, since these points might be (constrained) extrema. We therefore seek <math> \mathbf{x} </math> such that any allowable direction of movement away from <math>\mathbf{x}</math> is perpendicular to <math> \nabla f(\mathbf{x}) </math> (otherwise we could increase <math>f</math> by moving along that allowable direction). In other words, <math> \nabla f(\mathbf{x}) \in A^{\perp} = S \,.</math> Thus there are scalars <math> \lambda_1, \lambda_2,\ \dots, \lambda_M </math> such that
<math display="block">\nabla f(\mathbf{x}) = \sum_{k=1}^M  \lambda_k \, \nabla g_k (\mathbf{x})  \quad \iff \quad \nabla f(\mathbf{x}) - \sum_{k=1}^M {\lambda_k \nabla g_k (\mathbf{x})} = 0 ~.</math>

These scalars are the Lagrange multipliers. We now have <math> M </math> of them, one for every constraint.

As before, we introduce an auxiliary function
<math display="block">\mathcal{L}\left( x_1,\ldots , x_n, \lambda_1, \ldots, \lambda _M \right) = f\left( x_1, \ldots, x_n \right) - \sum\limits_{k=1}^M {\lambda_k g_k\left( x_1, \ldots , x_n \right)}\ </math>
and solve
<math display="block"> \nabla_{x_1, \ldots , x_n, \lambda_1, \ldots, \lambda _M} \mathcal{L}(x_1, \ldots , x_n, \lambda_1, \ldots, \lambda _M)=0 \iff 
\begin{cases}
\nabla f(\mathbf{x}) - \sum_{k=1}^M {\lambda_k \, \nabla g_k (\mathbf{x})} = 0\\
 g_1(\mathbf{x}) = \cdots = g_M(\mathbf{x}) = 0
\end{cases}</math>
which amounts to solving <math> n+M </math> equations in <math>\ n+M\ </math> unknowns.

The constraint qualification assumption when there are multiple constraints is that the constraint gradients at the relevant point are linearly independent.