Fig. 1. Drawn in green is the locus (contour) of points satisfying the constraint g( x, y) = c. Drawn in blue are contours of f. Arrows represent the gradient, which points in a direction normal to the contour. In mathematical optimization problems, Lagrange multipliers, named after Joseph Louis Lagrange, is a method for finding the extrema of a function of several variables subject to one or more constraints: it is the basic tool in nonlinear constrained optimization. Image File history File links This is a lossless scalable vector image. ...
Image File history File links Lagrange_multiplier. ...
Image File history File links Lagrange_multiplier. ...
In mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an allowed set. ...
Joseph-Louis, comte de Lagrange (January 25, 1736 Turin, Kingdom of Sardinia - April 10, 1813 Paris) was an Italian-French mathematician and astronomer who made important contributions to all fields of analysis and number theory and to classical and celestial mechanics as arguably the greatest mathematician of the 18th century. ...
In mathematics, particularly in calculus, a stationary point is a point on the graph of a function where the tangent to the graph is parallel to the x-axis or, equivalently, where the derivative of the function equals zero (known as a critical number). ...
Graph of example function, The mathematical concept of a function expresses the intuitive idea of deterministic dependence between two quantities, one of which is viewed as primary (the independent variable, argument of the function, or its input) and the other as secondary (the value of the function, or output). A...
Constraint is an equation that defines a restriction of solutions of an optimization problem to a so called feasible set. ...
Lagrange multipliers compute the stationary points of the constrained function; by Fermat's theorem, extrema occur at these points (or on the boundary or at points where the function is not differentiable). Stationary points (red pluses) and inflection points (green circles). ...
Fermats theorem is a theorem in real analysis, named after Pierre de Fermat. ...
In mathematics, the derivative of a function is one of the two central concepts of calculus. ...
It replaces finding stationary points of a constrained function in n variables with k constraints to finding stationary points of an unconstrained function in n+k variables: the method introduces a new unknown scalar variable, the Lagrange multiplier, for each constraint and defines a new function (the Lagrangian) in terms of the original function, the constraints, and the Lagrange multipliers. Stationary points (red pluses) and inflection points (green circles). ...
Introduction
Consider a two-dimensional case. Suppose we have a function, f(x,y), to maximize, subject to the constraint  where c is a constant. We can visualize contours of f given by The Comet Nucleus Tour (CONTOUR) was a Discovery-class space mission. ...
 for various values of dn, and the contour of g given by g(x,y) = c.
Suppose we walk along the contour line with g = c. In general the contour lines of f and g may be distinct, so traversing the contour line for g = c could intersect with or cross the contour lines of f. This is equivalent to saying that whilst moving along the contour line for g = c the value of f can vary. Only when the contour line for g = c touches contour lines of f tangentially, we do not increase or decrease the value of f - that is, when the contour lines touch but do not cross. In mathematics, contact of order k of functions is an equivalence relation, corresponding to having the same value at a point P and also the same derivatives there, up to order k. ...
This occurs exactly when the tangential component of the total derivative vanishes:  , which is at the constrained stationary points of f (which include the constrained local extrema, assuming f is differentiable). Computationally, this is when the gradient of f is normal to the constraint(s): when  for some scalar λ. Illustration of tangential and normal components of a vector to a surface. ...
In mathematics, a total derivative may be either. ...
Stationary points (red pluses) and inflection points (green circles). ...
Illustration of tangential and normal components of a vector to a surface. ...
A familiar example can be obtained from weather maps, with their contour lines for temperature and pressure: the constrained extrema will occur where the superposed maps show touching lines (isopleths). Elevation contour map A contour line shows elevation. ...
An isopleth is a feature of meteorological charts, connecting points which have an equal value of some variable at a given time and spatial area. ...
Geometrically we translate the tangency condition to saying that the gradients of f and g are parallel vectors at the maximum, since the gradients are always normal to the contour lines. Thus we want points (x,y) where  , and, further, g(x,y) = c. To incorporate both these conditions into one equation, we introduce an unknown scalar, λ, and solve For other uses, see Gradient (disambiguation). ...
 with  and 
Justification As discussed above, we are looking for stationary points of f seen while traveling on the level set g(x,y) = c. This occurs just when the gradient of f has no component tangential to the level sets of g. This condition is equivalent to  for some λ. Stationary points (x,y,λ) of F also satisfy g(x,y) = c as can be seen by considering the derivative with respect to λ.
Caveat: extrema versus stationary points Be aware that the solutions are the stationary points of the Lagrangian F, and are saddle points: they are not extrema of F. F is unbounded: given a point (x,y) that doesn't lie on the constraint, letting  makes F arbitrarily large or small. Stationary points (red pluses) and inflection points (green circles). ...
Plot of y = x3 with a saddle-point at (0,0). ...
A more general formulation in Euclidean space Denote the objective function by  and let the constraints be given by  , perhaps by moving constants to the left, as in  . The domain of f should be an open set containing all points satisfying the constraints. Furthermore, f and the gk must have continuous first partial derivatives and the gradients of the gk must not be zero on the domain.[1] Now, define the Lagrangian, Λ, as  - k is an index for variables and functions associated with a particular constraint, k.
 without a subscript indicates the vector with elements  , which are taken to be independent variables. Observe that both the optimization criteria and constraints gk(x) are compactly encoded as stationary points of the Lagrangian:  if and only if   means to take the gradient only with respect to each element in the vector  , instead of all variables. and ↔ ⇔ ≡ logical symbols representing iff. ...
 implies gk = 0. Collectively, the stationary points of the Lagrangian,  , give a number of unique equations totaling the length of plus the length of . This often makes it possible to solve for every x and λk, without inverting the gk.[1] For this reason, the Lagrange multiplier method can be useful in situations where it is easier to find derivatives of the constraint functions than to invert them.
Often the Lagrange multipliers have an interpretation as some salient quantity of interest. To see why this might be the case, observe that:
 So, λk is the rate of change of the quantity being optimized as a function of the constraint variable. As examples, in Lagrangian mechanics the equations of motion are derived by finding stationary points of the action, the time integral of the difference between kinetic and potential energy. Thus, the force on a particle due to a scalar potential, F = −∇V, can be interpreted as a Lagrange multiplier determining the change in action (transfer of potential to kinetic energy) following a variation in the particle's constrained trajectory. In economics, the optimal profit to a player is calculated subject to a constrained space of actions, where a Lagrange multiplier is the value of relaxing a given constraint (e.g. through bribery or other means). Lagrangian mechanics is a re-formulation of classical mechanics that combines conservation of momentum with conservation of energy. ...
In physics, the action is an integral quantity that is used to determine the evolution of a physical system between two defined states using the calculus of variations. ...
The method of Lagrange multipliers is generalized by the Karush-Kuhn-Tucker conditions. In mathematics, the Karush-Kuhn-Tucker conditions (also known as the Kuhn-Tucker or the KKT conditions) are necessary for a solution in nonlinear programming to be optimal. ...
Examples
Very simple example
 Fig. 2. Illustration of the constrained optimization problem. Suppose you wish to maximize f(x,y) = x + y subject to the constraint x2 + y2 = 1. The constraint is the unit circle, and the level sets of f are diagonal lines (with slope -1), so one can see graphically that the maximum occurs at  (and the minimum occurs at  ) Image File history File links No higher resolution available. ...
Image File history File links No higher resolution available. ...
In mathematics, a level set of a real-valued function f of n variables is a set of the form { (x1,...,xn) | f(x1,...,xn) = c } where c is a constant. ...
Formally, set g(x,y) = x2 + y2 − 1, and
- Λ(x,y,λ) = f(x,y) + λg(x,y) = x + y + λ(x2 + y2 − 1)
Set the derivative dΛ = 0, which yields the system of equations:  As always, the  equation is the original constraint.
Combining the first two equations yields x = y (explicitly,  (otherwise (i) yields 1 = 0), so one can solve for λ, yielding λ = − 1 / (2x), which one can substitute into (ii)).
Substituting into (iii) yields 2x2 = 1, so  and the stationary points are and . Evaluating the objective function f on these yields
 thus the maximum is  , which is attained at and the minimum is  , which is attained at .
Simple example
 Fig. 3. Illustration of the constrained optimization problem. Suppose you want to find the maximum values for Image File history File links No higher resolution available. ...
Image File history File links No higher resolution available. ...
 with the condition that the x and y coordinates lie on the circle around the origin with radius √3, that is,  As there is just a single condition, we will use only one multiplier, say λ.
Use the constraint to define a function g(x, y):
 The function g is identically zero on the circle of radius √3. So any multiple of g(x, y) may be added to f(x, y) leaving f(x, y) unchanged in the region of interest (above the circle where our original constraint is satisfied). Let  The critical values of Λ occur when its gradient is zero. The partial derivatives are  Equation (iii) is just the original constraint. Equation (i) implies λ = −y or x = 0. First if x = 0 then we must have  by (iii) or we would have a contradiction: − 3 = 0 in (iii) and by (ii) we have that λ=0. Secondly if λ = −y and substituting into equation (ii) we have that,  Then x2 = 2y2. Substituting into equation (iii) and solving for y gives this value of y:  Clearly there are six critical points:  Evaluating the objective at these points, we find  Therefore, the objective function attains a maximum at  and a minimum at the other two critical points. The points  are saddle points. Plot of y = x3 with a saddle-point at (0,0). ...
Example: entropy Suppose we wish to find the discrete probability distribution with maximal information entropy. Then In mathematics and statistics, a probability distribution is a function of the probabilities of a mutually exclusive and exhaustive set of events. ...
Claude Shannon In information theory, the Shannon entropy or information entropy is a measure of the uncertainty associated with a random variable. ...
 Of course, the sum of these probabilities equals 1, so our constraint is g(p) = 1 with  We can use Lagrange multipliers to find the point of maximum entropy (depending on the probabilities). For all k from 1 to n, we require that  which gives  Carrying out the differentiation of these n equations, we get  This shows that all pi are equal (because they depend on λ only). By using the constraint ∑k pk = 1, we find  Hence, the uniform distribution is the distribution with the greatest entropy.
Economics Constrained optimization plays a central role in economics. For example, the choice problem for a consumer is represented as one of maximizing a utility function subject to a budget constraint. The Lagrange multiplier has an economic interpretation as the shadow price associated with the constraint, in this case the marginal utility of income. Face-to-face trading interactions on the New York Stock Exchange trading floor. ...
Consumer theory is a theory of economics. ...
This article is about utility in economics and in game theory. ...
A Budget Constraint represents the combinations of goods and services that a consumer can purchase given current prices and his income. ...
A shadow price is the change in the objective value of the optimal solution of an optimization problem obtained by relaxing the right hand side of the constraint by one unit. ...
“Marginal revolution†redirects here. ...
Income, generally defined, is the money that is received as a result of the normal business activities of an individual or a business. ...
Lagrange duality Given a convex optimization problem in standard form Convex optimization is a subfield of mathematical optimization. ...
minimize f0(x) subject to
  with the domain  having non-empty interior, the Lagrangian function  is defined as  The vectors λ and ν are called the dual variables or Lagrange multiplier vectors associated with the problem. The Lagrange dual function  is defined as  The dual function g is concave, even when the initial problem is not convex. The dual function yields lower bounds on the optimal value p * of the initial problem; for any  and any ν we have  . If a constraint qualification such as Slater's condition holds and the original problem is convex, then we have strong duality, i.e.  .
See also - Karush-Kuhn-Tucker conditions: generalization of the method of Lagrange multipliers.
- Lagrange multipliers on Banach spaces: another generalization of the method of Lagrange multipliers.
In mathematics, the Karush-Kuhn-Tucker conditions (also known as the Kuhn-Tucker or the KKT conditions) are necessary for a solution in nonlinear programming to be optimal. ...
In the field of calculus of variations in mathematics, the method of Lagrange multipliers on Banach spaces can be used to solve certain infinite-dimensional constrained optimization problems. ...
References - ^ a b Gluss, David and Weisstein, Eric W., Lagrange Multiplier at MathWorld.
MathWorld is an online mathematics reference work, sponsored by Wolfram Research Inc. ...
External links For references to Lagrange's original work and for an account of the terminology see the Lagrange Multiplier entry in Exposition For additional text and interactive applets Calculus of variations is a field of mathematics that deals with functions of functions, as opposed to ordinary calculus which deals with functions of numbers. ...
| 
Feeds |
Contact