Lagrange multipliers

de:Lagrange-Multiplikator fr:Multiplicateur de Lagrange

In mathematical optimization problems, Lagrange multipliers are a method for dealing with constraints. Suppose the question as given is to find local extrema of a function of several variables subject to one or more constraints given by setting further functions of the variables to given values. The method introduces a new unknown scalar variable, the Lagrange multiplier, for each constraint; and forms a linear combination involving the multipliers as coefficients. This reduces the constrained problem to an unconstrained problem. It may then be solved, for example by the usual gradient method.

To explain why this has a chance of working, consider a two-dimensional case. Suppose we have a function f(x,y) to maximise, subject to

g(x,y) = c,

where c is a given constant. We can also visualise level sets or contours of f given by

f(x,y) = d

for various values of d. The constraint is to stay on one contour of g, given by fixing the value of g to be c. Suppose we are walking along the g=c contour. Since the contours of f and g will be distinct, traversing the g=c contour may in general cross many contours of f. So let us take note of the various contours f = d we cross for different values of d. If we cross the contour transversally, we can increase the value of f by walking 'uphill': that is following the direction leading to higher values of f. Only if the contour f = d we are trying to cross actually touches tangentially the contour g = c we are confined to, will this not be possible. At a constrained maximum of f, that must be true.

A familiar example can be obtained from weather maps, with their contours for temperature and pressure: the constrained extrema will occur where the superposed maps show touching lines (isopleths).

Geometrically we translate the tangency condition to saying that the gradients of f and g are parallel vectors at the maximum. Introducing an unknown scalar λ, the gradient of

f − λg

is then 0 for some value of λ. This in geometrical form is the Lagrange multiplier argument:

f − λg

must be stationary, where the multiplier λ is a new variable, at a local extremum.

The method of Lagrange multipliers

Let f (x) be a function defined on an n-dimensional open set {x ∈ Rⁿ}. We define k constraints g_k (x) = 0, and see that (if the constraints are indeed satisfied)

<math>h(\mathbf x, \mathbf \lambda) = f + \sum_k \lambda_k g_k <math>

We proceed to look for an extremum of h

<math>\frac{\partial h}{\partial x_i} = 0,<math>

which is equivalent to

<math>\frac{\partial f}{\partial x_i} = - \sum_k \lambda_k \frac{\partial g_k}{\partial x_i}.<math>

We determine the unknown multipliers λ_k from our constraint equations and have therefore found an extremum for h while enforcing the constraints (i.e. g_k=0), implying that f has been extremized.

Example

Suppose we wish to find the discrete probability distribution with maximal information entropy. Then

<math>f(p_1,p_2,\cdots,p_n) = -\sum_{k=1}^n p_k\log_2 p_k.<math>

Of course, the sum of these probabilities equals 1, so our constraint function is

<math>g(p_1,p_2,\cdots,p_n)=\sum_{k=1}^n p_k=1.<math>

To find the point of maximum entropy (depending on the probabilities), we can use the Lagrange multiplier. We set:

<math>\mbox{For } i = 1,\cdots,n,<math>

<math>\frac{\partial}{\partial p_i}\left(-\sum_{k=1}^n p_k \log_2 p_k + \lambda\sum_{k=1}^n p_k\right) = 0<math>

Carrying out the differentiation of these n equations, we get

<math>-\left(\frac{1}{\ln 2}+\log_2 p_i \right) + \lambda = 0.<math>

This shows that all p_i are equal (because they depend on λ only). By using the constraint ∑_k p_k = 1 again, we get the uniform distribution:

<math>p_i = \frac{1}{n}.<math>

For another example, see also derivation of the partition function.

The method of Lagrange multipliers is generalized by the Kuhn-Tucker theorem.

External links

For references to Lagrange's original work and for an account of the terminology see the Lagrange Multiplier entry in

• Earliest known uses of some of the words of mathematics: L (http://members.aol.com/jeff570/l.html)

For additional text and interactive applets

• Applet (http://www-math.mit.edu/18.02/applets/LagrangeMultipliersTwoVariables.html)
• Tutorial and applet (http://www.math.gatech.edu/~carlen/2507/notes/lagMultipliers.html)
• Conceptual introduction (http://www.slimy.com/~steuard/tutorials/Lagrange.html) (plus a brief discussion of Lagrange multipliers in the calculus of variations as used in physics)