Lagrangian Optimization

The Lagrangian multiplier is a method of mathematical optimization that provides a means of finding the maxima and minima of a mathematical function, f, subject to constraints, g. The contour map below shows an optimization problem. We want to consider the problem where we maximize f \left ( x, y \right ) subject to the constraints g \left ( x, y \right ) = c. The solution to this problem then is the point where the red line tangentially touches a blue contour. This answer can be found using Lagrangian multipliers.

Lagrangian Optimization

Contour Map where the red line shows the constraint g(x,y) = c and the blue times are contours of f(x,y).

We can construct a Lagrangian function as shown below. [1] We assume that function, f, is the problem for which an extremum of a function is desired:
f \left ( x_1, x_2, \ldots, x_n \right )

with a set of any number of constraint functions:
\begin{matrix}  g_i \left (x_1, x_2, \ldots, x_n \right ) = b_i, & i = 1,2,\ldots, m, & m < n  \end{matrix}

Then our Lagrangian function is defined as:
\Lambda \left ( x_1, x_2, \ldots, x_n,\lambda  \right ) = f\left ( x_1, x_2, \ldots, x_n \right ) + \sum_{i=1}^{m}\lambda _i\cdot \left ( b_i - g_i(x_1, x_2, \ldots, x_n) \right )

The Lagrangian multiplier can be used in any multidimensional space. The example below is given in [2].

A box is to be constructed out of various materials. The material to be used for the front and back sides costs $1 per square meter. The material to be used for the left and right sides costs $2 per square meter. The material to be used for the top and bottom costs $4 per square meter. What is the maximum volume that can be enclosed for a total material cost of $192?

We know the constraint, C. We should also know that the Volume of a cube (box) is V = LWH. We must find the constraint function…

Since we have a front and back side that cost $1 each, we have 2 planes that are length times width. We have a left and right side that cost $2 each at width time height. And lastly, we have a top and bottom side that cost $4 each at length times width:

2\left ( 1 L H \right ) + 2\left ( 2WH \right ) + 2\left ( 4LW \right ) = C \\  2LH+4WH+8LW - C = 0

We can then write our Lagrangian function:
\Lambda (L,W,H,\lambda ) = LWH + \lambda \left ( 2LH+4WH+8LW - C \right )

If we continue solving this out using partial derivatives and some algebraic techniques, as shown in [2], we eventually determine the maximal volume for the cost, C, of $192, is a Volume of 64 meters3. This is an example of how we can use the Lagrangian multiplier in a 3-dimensional space. The multiplier can work in any higher dimensional space as well.

What does the Lagrangian multiplier, λ, represent then? Well in the problems above, the Lagrangian multiplier represents a scalar value that allows us to change the size of the values used to scale the shape (circle in the contour map, and cube in the Volume problem). However, the Lagrangian multiplier can be used to represent actual values as well. [3] shares some examples of what the λ functions can represent in both physics and economics.

In the case of the physics of forces and potential energy, we might think of the constraint functions as representing forces that are helping to bring a point to it minimum or maximum. The Multiplier can then be thought of as a measure of how hard the constraint has to pull in order to balance our the forces on the constraint surface. In economics, we might think of maximizing profits based on some limited number of resources. The multiplier then represents the marginal value of the resource, or the rate at which the function changes if we change the constraints.

Therefore, understanding what the multiplier means takes an understanding of the problem that it is being applied. In some cases, it may only be a scaling value; in others, it may have a more significant meaning.

Impact on Computers

The Lagrangian Multiplier is useful in the field of optimal control theory. The multipliers can be interpreted as a cost ate variables. In Pontryagin’s maximum principle (or minimum principle), applied to deterministic problems, yields the same solution as many of the Bellman principles of Dynamic Programming, without the curse of dimensionality. The multiplier then works as a means of deriving the optimal minimum or maximum in control theory in a quicker means than Bellman’s equations for dynamic programming in higher dimensional spaces. [4]

Works Cited:

[1] Vapnyarkii, I.B., “Lagrange multipliers” in Encyclopaedia of Mathematics, New York: Springer, 2001.
[2] Hahn, K. Lagrange Multiplier Method for finding Optimums Internet: http://www.karlscalculus.org/pdf/lagrange.pdf [September 5, 2011]
[3] Jensen, S. An Introduction to Lagrange Multipliers Internet: http://www.slimy.com/~steuard/teaching/tutorials/Lagrange.html [September 5, 2011]
[4] Todorov, E. “Optimal Control Theory” in Bayesian Brain, Boston: MIT Press, 2006.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>