Lec 24 Lagrange Multiplier
Lec 24 Lagrange Multiplier
Lec 24 Lagrange Multiplier
Lagrange Multipliers
The method of Lagrange multipliers gives a set of necessary conditions to
identify optimal points of equality constrained optimization problems.
This is done by converting a constrained problem to an equivalent
unconstrained problem with the help of certain unspecified parameters
known as Lagrange multipliers.
The classical problem formulation
minimize :
f(x1, x2, ..., xn)
Subject to :
h1(x1, x2, ..., xn) = 0 (equality constraints)
can be converted to
minimize :
L(x, ) = f(x) - h1(x)
Where
L(x, v) is the Lagrangian function
The is an unspecified positive or negative constant.
It is called the Lagrangian Multiplier
Method
1. Original problem is rewritten as:
minimize L(x, ) = f(x) - h1(x)
1. Take derivatives of L(x, ) with respect to xi and set them
equal to zero.
If there are n variables (i.e., x1, ..., xn) then you will get n
equations with n + 1 unknowns (i.e., n variables xi and one
Lagrangian multiplier )
2. Express all xi in terms of Langrangian multiplier
3. Plug x in terms of in constraint h1(x) = 0 and solve .
4. Calculate x by using the just found value for .
Multiple constraints
The Lagrangian multiplier method can be used for any number of
equality constraints.
Suppose we have a classical problem formulation with k equality
constraints
minimize :
Subject to :
R ( x, y ) = 5 x + 2 x 2 4 y
subject to G ( x , y ) = 2 x + y 20 = 0
Construct Lagrangian
L ( x , y , ) = R ( x , y ) G ( x , y ) = 5 x + 2 x 2 4 y (2 x + y 20)
L
= 0 5 + 4 x = 2
x
13
L
= 3.25
= 0 4 + = 0 = 4 x =
4
y
L
= 0 2 x + y = 20 y = 27.5
Example 1
Consider the problem:
Example 2
We have the problem with
inequality constraint:
Then we have
Example 2
Case 1: (x 2) = 0 means that = 0
From equation for Lx we get x = 4, which also satisfies x 2 0 or
positive.
Hence, this solution (x* = 4), which makes h (4) =16, is a possible
candidate for the maximum solution.
Case 2: (x 2) = 0 then Suppose is not zero and x = 2
Now from equation for Lx , we get = - 4, which does not satisfy
the inequality 0.
From these two cases we conclude that the optimum
solution is x* = 4 and h* = 16
Example 3
Find the shortest distance between the point (2, 2) and the upper
half of the semicircle of radius one, whose center is at the origin. In
order to simplify the calculation, we minimize h , the square of the
distance:
Example 3
The Lagrangian function for this problem is
Example 3
Example 4
From (8.25) we conclude that either
v =0
or y =0. If v = 0 ,
then from (8.20), (8.21) and >0, we get x = y.
Solving the latter with x2+y2 =1 , gives
Example 4
Objective: Minimize the material (surface area) for any volume.
R
Area = f
= 2 ( R 2 ) + 2 R H
= R H =C
2
C
H=
R2
Example 4
3. Set up the Lagrange expression.
L = 2 R 2 + 2 R H + ( R 2 H C )
objective
constraint
L
= 2 R + ( R 2 ) = 0
H
L
= R2 H - C = 0
2 R + R 2 = 0 = -
2
R
R2 H - C = 0
H=
R2
Example 4
6. Then by substitution
C 2
C
(2
R)
4R + 2
+
= 0
2
2
R R
R
4 R3 + 2C - 4C = 0
C = R H
2
R=
H
2
2
H
R
R= 3
2
R= 3
C
2
2
H
R
=
R
2
3
f =
xi
i =1
= a1 x1 + a 2 x 2 +
j=
b
i =1
ij
xi
= X1 +3X2
Constraint Functions
2 =>
1 => X1 + X2 10
X1 > 0
X1 + 4X2 16
X2 > 0
12
X2 variable
10
8
6
4
2
Feasible solution area
0
0
8
X1 Variable
10
12
14
16
X 1 = 10 X 2
X2 = 4
= 0 + 3(4) = 12
X1 = 8
X2 = 2
= 8 + 3(2) = 14
X 1 = 10
X2 = 0
= 10 + 3(0) = 10
X1 = 8
(10 X 2 ) + 4 X 2 = 16