Lagrange multipliers Method

Basic concepts and principles

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
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

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.





Was useful? want add anything?



Post here

Post from other users





Post here
Update cookies preferences