The Lagrange multiplier method is the method of finding a conditional extremum of the function:
fx, xϵRn
according to a number of m constraints where i is from 1 to m.
The algorithm is the following:
- Form the Lagrange function as a linear combination of the function f and functions φi, taken with the coefficients, called Lagrange multipliers – λi:
where
- Construct the system of m+n equations, equating to zero the partial derivatives of the Lagrangian by and
- If the resulting system has a solution with respect to parameters and , then may be conditional extremum, i.e. the solution of the original problem. Note that this condition is necessary but not sufficient character.
Application
Lagrange multipliers method is used for solving nonlinear programming problems arising in many areas (e.g., the economy).
The basic method of solving the problem of optimizing the quality of audio and video coding information for a given average bitrate (Rate-Distortion optimization).
We can illustrate this method by the following example:
Solve:
min f(x) = x12 + x22 h1(x) = 2x1 + x2 -2 = 0
Corresponding problem of unconstrained optimization is written as follows:
L(x, λ) = x12 + x22 + λ(2x1 + x2 – 2) → min
Solution:
In order to check whether the stationary point is a minimum X, compute the Hessian matrix L(x, λ):
,
this matrix is positive definite (2 * 2 - 0 * 0 = 4> 0).
This means that L (x, λ) is a convex function. Consequently, the coordinates x * = (-λ,λ/2) define a point of the global minimum.
Hence, the minimum is at a point (0.8, 0.4) and the objective function is f(0.8, 0.4)=0.8
Works Cited
Bertsekas, Dimitri P. (1999). Nonlinear Programming (Second ed.). Cambridge, MA.: Athena Scientific. ISBN 1-886529-00-0.
