This is a method for solving nonlinear programming problems, ie problems of form
maximize f (x)
Subject to
gi (x) = 0
With gi: Rn → R
f: Rn → R
y x ∈ Rn
i positive integer such as 1 ≤ i≤ m
We assume that both f, gi are functions at least twice differentiable
Lagrange multipliers Method
Basic concepts and principles
The idea is to study the level sets of function f, ie, those vectorial values x such us
N (f, k) = { x∈ Rn : f(x) = k}
Since f, is restricted to gi(x) = 0, the feasible set is the intersection of this set with the set level 0 of each of the gi, ie each set given by
N (gi, 0) = { x∈ Rn : gi (x) = 0}
Therefore
FS = Feasible Set = N (f, k) ∩ N (gi, 0) , with i = 1, 2, ..., m
N (f, k) = { x∈ Rn : f(x) = k}
Since f, is restricted to gi(x) = 0, the feasible set is the intersection of this set with the set level 0 of each of the gi, ie each set given by
N (gi, 0) = { x∈ Rn : gi (x) = 0}
Therefore
FS = Feasible Set = N (f, k) ∩ N (gi, 0) , with i = 1, 2, ..., m
Extended Theory
The first thing to note is that f be continuous and compact FS compact (finite intersection of compacts and f is continue), so f reaches it maximum and its minimum at FS.
Suppose that f has a maximum at x 0 and assume for now that ∇ f(x0)≠ 0 .
if we move by the level sets of f in the direction of increased growth of the f, thus is, in the direction of ∇ f, f peaks at x0, suppose the value k0, therefore we have the level set N (f, k0).
On the other hand, because x0 is in the feasible region, the level set intersects with each N(gi, 0) at x0.
It is possible to show that at x0, the level sets N (f, k0), N (gi, 0) both cut on a tangent form, ie ∇ f and ∇ gi are parallels ∀ i exactly at x0, and so we have
∇f (x0) = λi ∇gi (x0)
Therefore the maximum of f restricted to gi = 0 is the maximum of the function
L(x, λ) = f(x) - λi gi (x)
The numbers λi are called Lagrange multipliers
Reminding one of the gradient conditions: a necessary condition for x 0 is a critical point of L is that it holds the following:
Method of Lagrange multipliers
∇L (x0) = 0
With
L(x, λ) = f(x) - λi gi (x)
Note that ∇L is a vectorial function with n+m coordinates, ie ∇L = (Lx1, ... , Lxn, Lλ1, ..., Lλm),
So, our non-linear programming problem is reduced to solving a nonlinear n+m equations system for xj, λi, where. 1 ≤ i ≤ m, 1 ≤ j ≤ n. Which is a problem, in principle, not trivial to solve, whose equations are.
Lagrange multipliers methods equations
Lx1 = 0
...
Lxn = 0
Lλ1= g1(x) = 0
...
Lλm = gm(x) = 0
With
L(x, λ) = f(x) - λi gi (x)
Note also that the points where the equations system holds can be maximum, minimum or saddle points, so the solution in principle is not guaranteed by this method, such solutions will require a bit more analysis, including the calculation of the Hessian or we can resort to an analysis of the neighborhood of the point in question to discuss what kind of solution we have.
There are several numerical methods for calculating the maximum of L one of them is to apply the gradient method to the function L that is, numerically calculate ∇ L and we will go forward in the direction that tends to become zero, found this point, the method the Hessian or other type of analysis will tell us if founded critical point is a maximum, minimum or saddle point.
