Lagrange multipliers

Lagrange multipliers is a technique to solve constrained optimization problems: find the extrema of a multivariate objective function that is subject to the constraint .

Note that is a vector of inputs

Key observations for

1. Along a path (constraint ), critical points of = level curves of  that are tangent to the contour representing 
2. At each of these points, the gradient is always perpendicular to the line tangent to the level curve passing through the point. Therefore, it is tangent to both the level curve and the constraint function at the critical point.
3. and are parallel to each other and point towards the same direction. They are constant multiples of each other

where is called Lagrange multipliers

Process with Example

1. Make sure the problem follow a form:
   1. The problem can be represented by a differentiable, multivariate function with n-dimensional inputs
   2. There are constraint functions, each takes the form of multivariate function , where is a constant and has the same dimension as
   3. Both and are twice-differentiable around the open neighborhood of the optimizer
2. For each constraint function , introduce a new variables —Lagrange multiplier. Then define the Lagrangian function as follows:

3. Set the gradient of to the zero vector to find critical points of . All components (partial derivatives) of must equate to 0.

4. This leads to a system of equations

5. Each candidate solution looks like . Remove , then we have found critical points of , namely

To classify these critical point, there are two ways:

1. Plug back the values into function and compare function values, to determine the global maximum and minimum over the feasible region ). Easy and recommended.
2. Check bordered Hessian : if the leading principal minor

Examples

Guided Example

Lagrange Multiplier as Sensitivity to change in constraint

(Khan Academy)

The Lagrange multipliers describes the rate of change of the local extremum as the constant varies. In other words, it describes how sensitive the optimum is to the change in constraint

Derivation

Assume one constraint . Recall the Lagrangian function is

Optimizing is the same as optimizing subject to the constraint . The optimal value of Lagrangian function

Considering the optimal value of Lagrangian function as a function of

Take the partial derivative of