Lagrange multiplier

The method of Lagrange multipliers (after Joseph Louis Lagrange - ) in a mathematical optimization method to reformulate optimization problems with constraints. An optimization problem with constraints is the task of a local extremum of a function in several variables with one or to find several side conditions, where the side conditions by setting functions are defined on the given values ​​. This method introduces a new unknown scalar variable for each constraint a, a Lagrange multiplier, and defines a linear combination that integrates the multipliers as coefficients. The solutions of the original optimization problem can then be determined as critical points of the so-called Lagrange function under certain conditions.

Description

To understand how, we consider the two-dimensional case with a secondary condition. Suppose we want to maximize a function, a constraint must be maintained for a constant. When tracking contour line touch or we cross contour lines of. A common point of constraint and a height line can only be solving the optimization problem, if our movement is tangent to the contour line: Otherwise, we may increase or decrease the function value of carried forward or reverse motion on the given height line, without the constraint to hurt.

A well-known example can be seen from the weather maps with their contour lines for temperature and pressure. The extrema under the constraint occur where touch when overlaying the lines of cards. Geometrically, we translate the tangent condition by saying that the gradient of and the maximum parallel vectors, the gradient of must not disappear.

So we are looking for points at which and

The following abbreviations were used and definitions of the respective gradient:

And

The constant Lagrange multiplier is needed here because, although the two gradients should be parallel, but can be of different lengths as vectors. To summarize all these conditions to an equation, it is useful to use the following Lagrangian:

The solution of the optimization problem described above with a secondary condition now corresponds to a local extremum of the Lagrangian. This extremum can be calculated by the gradient of the Lagrangian:

The first two components of this equation correspond to the requirement of parallelism of the two original gradient and the third component is the same.

Points where the gradient of the Lagrange function or the constraint vanishes are called critical points of the Lagrangian. The latter are called in because the method of Lagrange multipliers can not say anything about them and they are therefore as potential candidates for extrema into consideration. Since, in general not every critical point of the Lagrangian solve the original optimization problem, this method provides only a necessary condition for the solution of the optimization problem.

Examples

Example with constraint without vanishing gradient

In this example, the function to be optimized under the constraint. The constraint therefore corresponds to the unit circle. With the help of the graphic, the maximum can be determined in very easily. The minimum of the optimization problem is.

First, we check at which points of the unit circle, the gradient of the constraint function vanishes. So we calculate

And see that this is the same only at the origin. However, this point is not located on the unit circle, in other words does not satisfy the constraint condition, and is thus not included in the list of the critical points.

To apply the method of Lagrange multipliers, and is

The condition results in the following three equations:

The third equation ( iii ) as always corresponds to the required constraint. With can be resolved (i ) to. The same thing you do for equation ( ii ) and. Obtained thus. Is used in the (III) is obtained, ie. The critical points are calculated to order and. To optimizing the function f has the values ​​at these two points, respectively.

Example with constraint with vanishing gradient

We consider with the function. If we examine now, so you can use the sufficient criterion for local extrema of the function to determine Extrema Extrema all the interior of the domain. The Randextrema but are found using the Lagrange multiplier. The edge of the domain is the constraint. Here are the two positive coordinate axes and the origin. So we find with the constraint.

We start with the Lagrangian function:

The equation

Leads us to the system of equations

The third equation states that or. Suppose it would be, then this leads - used in the second equation - a contradiction, because the equation

Has no solution, since the function has no zeros. Analogous results in the case with the first equation to a contradiction. Thus, the Lagrange multiplier provides no critical points.

However, we have not checked the points at which the gradient of the constraint disappears. It is

Thus the origin of the gradient of the constraint disappears and this is on the edge of the definition range ( it satisfies the constraint ). As described above, these points should also be considered as candidates for extrema considered. And is in fact and for all. The origin is therefore the global maximum of the function.

However, the presence of critical points does not say anything about the presence of extrema. If one were to replace the definition of areas and in this example, one would indeed get the same single critical point, however, the origin would be no global (and not local) maximum of (eg diverges the function in the third quadrant ). In fact, this possessed no local maxima or minima.

Several constraints

It should be a function defined on an open subset function. We define independent constraints. That the gradients of the constraints are for each point, with for all linearly independent. In particular, this means that none of the gradient disappears. If the gradient but be linearly dependent at one point, this point will be added to the list of critical points. Now we set

Let us now look at the critical point of

Which is equivalent to

We determine the unknown multipliers using our constraint equations and thus have a critical point ( ie ) of found. This is a necessary condition for an extremum on the set of points satisfying the constraints has. That Again, the extremes must be filtered out of the list of the critical points with other agents.

Note that it is therefore particularly wrong to speak of " maximizing Lagrangian " the. The Lagrangian is unbounded and therefore has no global extrema and therefore can not be maximized. Merely the critical points of the Lagrangian indicate points at which the objective function with respect to the constraints might adopt a maximum.

Sufficient conditions

This method provides only a necessary condition for extreme points. In order to detect the extreme positions and their way to determine there are various criteria. Generally edged Hessian matrix is formed and calculates their determinant or certain minors. However, this approach does not always result in a statement. Alternatively, you can also rely on a visualization and geometric considerations, to determine the nature of the extreme point.

Meaning of Lagrange multipliers in physics

The meaning of the Lagrange multipliers in physics is visible in the application in classical mechanics. For this, they were introduced by Lagrange also (about 1777? ). The equations of motion of classical mechanics can be obtained in the Lagrangian formalism using the Euler -Lagrange equation from the condition that the action - with variation of the coordinates and their time derivatives independently - assumes an extremum. A physical constraint, which limits the movement appears as a constraint of the extremum. The Lagrange multiplier, which the constraint is added to the Lagrangian, turns out to be the physical urging force with which the object described by the equation of motion to meet the constraint is placed. The following example of a free point mass moving in two dimensions on a path of constant radius, makes this clear:

Lagrangian (kinetic energy in polar coordinates):

Constraint:

New Lagrangian:

Euler-Lagrange equation ( here formulated only for the radial coordinate, since the constraint condition dependent on this, the results in the angular momentum for the movement of rotation ):

With and, and ( angular velocity).

This corresponds to the formulated in polar coordinates centripetal forces the point mass to move in a circular path.