Method to solve constrained optimization problems
In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the local maxima and minima of a function subject to equation constraints (i.e., subject to the condition that one or more equations have to be satisfied exactly by the chosen values of the variables). It is named after the mathematician Joseph-Louis Lagrange.
Summary and rationale.
The basic idea is to convert a constrained problem into a form such that the derivative test of an unconstrained problem can still be applied. The relationship between the gradient of the function and gradients of the constraints rather naturally leads to a reformulation of the original problem, known as the Lagrangian function or Lagrangian. In the general case, the Lagrangian is defined as
formula_1
for functions formula_2; the notation formula_3 denotes an inner product. The value formula_4 is called the Lagrange multiplier.
In simple cases, where the inner product is defined as the dot product, the Lagrangian is
formula_5
The method can be summarized as follows: in order to find the maximum or minimum of a function formula_6 subject to the equality constraint formula_7, find the stationary points of formula_8 considered as a function of formula_9 and the Lagrange multiplier formula_10. This means that all partial derivatives should be zero, including the partial derivative with respect to formula_10.
 ;templatestyles src="Block indent/styles.css"/ ;formula_12   and   formula_13
or equivalently
 ;templatestyles src="Block indent/styles.css"/ ;formula_14   and  formula_15
The solution corresponding to the original constrained optimization is always a saddle point of the Lagrangian function, which can be identified among the stationary points from the definiteness of the bordered Hessian matrix.
The great advantage of this method is that it allows the optimization to be solved without explicit parameterization in terms of the constraints. As a result, the method of Lagrange multipliers is widely used to solve challenging constrained optimization problems. Further, the method of Lagrange multipliers is generalized by the Karush–Kuhn–Tucker conditions, which can also take into account inequality constraints of the form formula_16 for a given constant formula_17.
Statement.
The following is known as the Lagrange multiplier theorem.
Let formula_18 be the objective function and let formula_19 be the constraints function, both belonging to formula_20 (that is, having continuous first derivatives). Let formula_21 be an optimal solution to the following optimization problem such that, for the matrix of partial derivatives formula_22, formula_23:
formula_24
Then there exists a unique Lagrange multiplier formula_25 such that formula_26 (Note that this is a somewhat conventional thing where formula_27 is clearly treated as a column vector to ensure that the dimensions match. But, we might as well make it just a row vector without taking the transpose.)
The Lagrange multiplier theorem states that at any local maximum (or minimum) of the function evaluated under the equality constraints, if constraint qualification applies (explained below), then the gradient of the function (at that point) can be expressed as a linear combination of the gradients of the constraints (at that point), with the Lagrange multipliers acting as coefficients. This is equivalent to saying that any direction perpendicular to all gradients of the constraints is also perpendicular to the gradient of the function. Or still, saying that the directional derivative of the function is 0 in every feasible direction.
Single constraint.
For the case of only one constraint and only two choice variables (as exemplified in Figure 1), consider the optimization problem
formula_28
(Sometimes an additive constant is shown separately rather than being included in formula_29, in which case the constraint is written formula_30 as in Figure 1.) We assume that both formula_31 and formula_32 have continuous first partial derivatives. We introduce a new variable (formula_33) called a Lagrange multiplier (or Lagrange undetermined multiplier) and study the Lagrange function (or Lagrangian or Lagrangian expression) defined by
formula_34
where the formula_33 term may be either added or subtracted. If formula_36 is a maximum of formula_37 for the original constrained problem and formula_38 then there exists formula_39 such that (formula_40) is a "stationary point" for the Lagrange function (stationary points are those points where the first partial derivatives of formula_41 are zero). The assumption formula_42 is called constraint qualification. However, not all stationary points yield a solution of the original problem, as the method of Lagrange multipliers yields only a necessary condition for optimality in constrained problems. Sufficient conditions for a minimum or maximum also exist, but if a particular candidate solution satisfies the sufficient conditions, it is only guaranteed that that solution is the best one "locally" – that is, it is better than any permissible nearby points. The "global" optimum can be found by comparing the values of the original objective function at the points satisfying the necessary and locally sufficient conditions.
The method of Lagrange multipliers relies on the intuition that at a maximum, "f"("x", "y") cannot be increasing in the direction of any such neighboring point that also has "g" = 0. If it were, we could walk along "g" = 0 to get higher, meaning that the starting point wasn't actually the maximum. Viewed in this way, it is an exact analogue to testing if the derivative of an unconstrained function is 0, that is, we are verifying that the directional derivative is 0 in any relevant (viable) direction.
We can visualize contours of f given by "f"("x", "y") = "d" for various values of d, and the contour of g given by "g"("x", "y") = "c".
Suppose we walk along the contour line with We are interested in finding points where f almost does not change as we walk, since these points might be maxima.
There are two ways this could happen:
To check the first possibility (we touch a contour line of f), notice that since the gradient of a function is perpendicular to the contour lines, the tangents to the contour lines of f and g are parallel if and only if the gradients of f and g are parallel. Thus we want points ("x", "y") where and
formula_43
for some formula_33
where
formula_45
are the respective gradients. The constant formula_33 is required because although the two gradient vectors are parallel, the magnitudes of the gradient vectors are generally not equal. This constant is called the Lagrange multiplier. (In some conventions formula_33 is preceded by a minus sign).
Notice that this method also solves the second possibility, that f is level: if f is level, then its gradient is zero, and setting formula_48 is a solution regardless of formula_49.
To incorporate these conditions into one equation, we introduce an auxiliary function
formula_50
and solve
formula_51
Note that this amounts to solving three equations in three unknowns. This is the method of Lagrange multipliers.
Note that formula_52 implies formula_53 as the partial derivative of formula_54 with respect to formula_4 is formula_56
To summarize
formula_57
The method generalizes readily to functions on formula_58 variables
formula_59
which amounts to solving "n" + 1 equations in "n" + 1 unknowns.
The constrained extrema of f are "critical points" of the Lagrangian formula_60, but they are not necessarily "local extrema" of formula_41 (see below).
One may reformulate the Lagrangian as a Hamiltonian, in which case the solutions are local minima for the Hamiltonian. This is done in optimal control theory, in the form of Pontryagin's minimum principle.
The fact that solutions of the method of Lagrange multipliers are not necessarily extrema of the Lagrangian, also poses difficulties for numerical optimization. This can be addressed by minimizing the "magnitude" of the gradient of the Lagrangian, as these minima are the same as the zeros of the magnitude, as illustrated in Example 5: Numerical optimization.
Multiple constraints.
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 formula_31 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 formula_31 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 formula_64 constraints and are walking along the set of points satisfying formula_65 Every point formula_66 on the contour of a given constraint function formula_67 has a space of allowable directions: the space of vectors perpendicular to formula_68 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 formula_69 and denote the span of the constraints' gradients by formula_70 Then formula_71 the space of vectors perpendicular to every element of formula_70
We are still interested in finding points where formula_31 does not change as we walk, since these points might be (constrained) extrema. We therefore seek formula_66 such that any allowable direction of movement away from formula_75 is perpendicular to formula_76 (otherwise we could increase formula_77 by moving along that allowable direction). In other words, formula_78 Thus there are scalars formula_79 such that
formula_80
These scalars are the Lagrange multipliers. We now have formula_64 of them, one for every constraint.
As before, we introduce an auxiliary function
formula_82
and solve
formula_83
which amounts to solving formula_84 equations in formula_85 unknowns.
The constraint qualification assumption when there are multiple constraints is that the constraint gradients at the relevant point are linearly independent.
Modern formulation via differentiable manifolds.
The problem of finding the local maxima and minima subject to constraints can be generalized to finding local maxima and minima on a differentiable manifold formula_86 In what follows, it is not necessary that formula_87 be a Euclidean space, or even a Riemannian manifold. All appearances of the gradient formula_88 (which depends on a choice of Riemannian metric) can be replaced with the exterior derivative formula_89
Single constraint.
Let formula_90 be a smooth manifold of dimension formula_91 Suppose that we wish to find the stationary points formula_92 of a smooth function formula_93 when restricted to the submanifold formula_94 defined by formula_95 where formula_96 is a smooth function for which 0 is a regular value.
Let formula_97 and formula_98 be the exterior derivatives of formula_99 and formula_100. Stationarity for the restriction formula_101 at formula_102 means formula_103 Equivalently, the kernel formula_104 contains formula_105 In other words, formula_106 and formula_107 are proportional 1-forms. For this it is necessary and sufficient that the following system of formula_108 equations holds:
formula_109
where formula_110 denotes the exterior product. The stationary points formula_92 are the solutions of the above system of equations plus the constraint formula_112 Note that the formula_113 equations are not independent, since the left-hand side of the equation belongs to the subvariety of formula_114 consisting of decomposable elements.
In this formulation, it is not necessary to explicitly find the Lagrange multiplier, a number formula_115 such that formula_116
Multiple constraints.
Let formula_90 and formula_99 be as in the above section regarding the case of a single constraint. Rather than the function formula_29 described there, now consider a smooth function formula_120 with component functions formula_121 for which formula_122 is a regular value. Let formula_123 be the submanifold of formula_90 defined by formula_125
formula_92 is a stationary point of formula_127 if and only if formula_128 contains formula_129 For convenience let formula_130 and formula_131 where formula_132 denotes the tangent map or Jacobian formula_133 (formula_134 can be canonically identified with formula_135). The subspace formula_136 has dimension smaller than that of formula_137, namely formula_138 and formula_139 formula_136 belongs to formula_141 if and only if formula_142 belongs to the image of formula_143 Computationally speaking, the condition is that formula_144 belongs to the row space of the matrix of formula_145 or equivalently the column space of the matrix of formula_146 (the transpose). If formula_147 denotes the exterior product of the columns of the matrix of formula_148 the stationary condition for formula_101 at formula_92 becomes
formula_151
Once again, in this formulation it is not necessary to explicitly find the Lagrange multipliers, the numbers formula_152 such that
formula_153
Interpretation of the Lagrange multipliers.
In this section, we modify the constraint equations from the form formula_154 to the form formula_155 where the formula_156 are m real constants that are considered to be additional arguments of the Lagrangian expression formula_54.
Often the Lagrange multipliers have an interpretation as some quantity of interest. For example, by parametrising the constraint's contour line, that is, if the Lagrangian expression is
formula_158
then
formula_159
So, "λk" is the rate of change of the quantity being optimized as a function of the constraint parameter.
As examples, in