Unit - I

CLASSICAL OPTIMIZATION
TECHNIQUES

PART –V :
MULTI VARIABLE
OPTIMIZATION
WITH EQUALITY CONSTRAINTS

Lagrange’s Multiplier Method

 LAGRANGE’S MULTIPLIER METHOD

Find the vector X [x1 , x2 , x3 , . . . . . . . . , xn ]T , which

minimizes the objective function f (X) ; subject to
the constraints g j (X) 0 , j 1, 2 , 3, . . . . . m

We define the Lagrange's function L as

L  f ( X )  1 g1 ( X )  2 g 2 ( X )  . . . . . .  m g m ( X )
m
L  f jg j
j 1

07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES

025 2
 LAGRANGE’S MULTIPLIER METHOD

Necessary condition:
m g j
L f
 j 0 ; i 1, 2, . . . . . n
xi xi j 1 xi
L
 g j 0 ; j 1, 2, . . . . . m
 j
thus we get (n+m) equations in (n+m) unknowns.
solving which we get values of (n+m) unknowns.

X * [x1, x2 , x3 , . . . . . xn ]T and *=[1, 2 , . . . . m ]T

07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES
025 3
 LAGRANGE’S MULTIPLIER METHOD

Sufficient condition: we define the quadratic form Q as

n m  2 L 
Q   hi h j  
 xi x j 
i 1 j 1   X*

A sufficient condition for f(X) to have minimum at X*

is that the quadratic form Q must be positive definite.
The quadratic form Q is positive definite if all the roots
of polynomial equation in z, given by determinent of
order (n+m), are positive.

07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES

025 4
 LAGRANGE’S MULTIPLIER METHOD

L11  z L12 L13 . . L1n g11 g 21 . . g m1

L21 L22  z L23 . . L2 n g12 g 22 . . g m2
L31 L32 L33  z . . L3n g13 g 23 . . g m3
. . . . . . . . . . .
. . . . . . . . . . .
Ln1 Ln 2 Ln3 . . Lnn  z g1n g 2n . . g mn 0
g11 g12 g13 . . g1m 0 0 . . 0
g 21 g 22 g 23 . . g 2m 0 0 . . 0
. . . . . . . . . . .
. . . . . . . . . . .
g m1 gm2 g m3 . . g mn 0 0 . . 0

07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES

025 5
 LAGRANGE’S MULTIPLIER METHOD

2 L g j
where Lij  and g jk 
xi x j xk

1. If all the roots (values of z) are positive,

then the function f has minima at X*
2. If all the roots (values of z) are negative,
then the function f has maxima at X*
3. otherwise Q is indefinite and the function
f has no minima/maxima at X*
07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES
025 6
 LAGRANGE’S MULTIPLIER METHOD

Ex.1: Find the maximum of the function

f ( X ) 2 x1  x2  10 subject to the constraint
2
x1  2 x2 3, using Lagrange's Method.
2
Here f ( X ) 2 x1  x2  10 & g ( X ) x1  2 x2  3 0

we define Lagrange's function L as


L  f ( X )   g ( X ) 2 x1  x2  10  + x1  2 x2  3 2

07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES
025 7
 LAGRANGE’S MULTIPLIER METHOD

Necessary Condition :
L f g
0   2   0
x1 x1 x1
L f g
0   1  4 x2 0
x2 x2 x2

L
0  g ( X )  x1  2 x2 2  3 0


solving these eq n ,   =-2, x1 =2.96875, x 2 =0.125

07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES

025 8
 LAGRANGE’S MULTIPLIER METHOD

Sufficient Condition: At x1 =2.9687, x 2 =0.125,  =-2

2 L 2 L 2 L
L11  0, L12 L21  0, L22  4  8
x12 x1x2 x2 2

g g
g11   1 , g12  4 x2 0.5
x1 x2

L11  z L12 g11 0 z 0 1

L21 L22  z g12 0  0  8 z 0.5 0
g11 g12 0 1 0.5 0

07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES

025 9
 LAGRANGE’S MULTIPLIER METHOD

 ( z ){0  0.25}  0  1{0  ( 8  z )} 0

 (0.25) z  8  z 0
 (1.25) z  8
 z  6.4
All the roots (here only one) are negative.
 f has maximum at X*
 2.9687 
X*=   and f max 16.0625
 0.125 
07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES
025 10
 LAGRANGE’S MULTIPLIER METHOD

1

Ex.2: Minimize f ( X )  x12  x2 2  x32
2

subject to the constraint x1  x2 0 and
x1  x2  x3 1, using Lagrange's Method.
1

2 2
here f ( X )  x1  x2  x3
2
2

g1 ( X )  x1  x2 0 and
g 2 ( X )  x1  x2  x3  1 0
we define L  f  1 g1  2 g 2

07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES

025 11
 LAGRANGE’S MULTIPLIER METHOD
Necessary Condition :
L f g1 g 2
0   1  2  x1  1  2 0
x1 x1 x1 x1
L f g1 g 2
0   1  2  x2  1  2 0
x2 x2 x2 x2
L f g1 g 2
0   1  2  x3  2 0
x3 x3 x3 x3
L
0  g1 ( X )  x1  x2 0
1
L
0  g 2 ( X )  x1  x2  x3  1 0
2
07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES
025 12
 LAGRANGE’S MULTIPLIER METHOD
solving these eq n ,
 1 0, 2  0.333, and x1  x2  x2 0.333
thus,
 x1   0.333
*  1   0  *  x   0.333
      and X   2  

 2   0.333   x3   0.333
* *
Sufficient Condition: At X and 
2 L 2 L 2 L
L11  1, L12  0, L13  0,
x12 x1x2 x1x3

07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES

025 13
 LAGRANGE’S MULTIPLIER METHOD

2 L 2 L 2 L
L21  0, L22  2 1, L23  0,
x2x1 x2 x2x3

2 L 2 L 2 L
L31  0, L32  0, L33  2
1,
x3x1 x3x2 x3
g1 g1 g1
g11  1 , g12   1 , g13  0
x1 x2 x3

g 2 g 2 g 2
g 21  1 , g 22  1 , g 23  1
x1 x2 x3

07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES

025 14
 LAGRANGE’S MULTIPLIER METHOD

L11  z L12 L13 g11 g 21

L21 L22  z L23 g12 g 22
L31 L32 L33  z g13 g 23 0
g11 g12 g13 0 0
g 21 g 22 g 23 0 0

1 z 0 0 1 1
0 1 z 0 1 1
0 0 1 z 0 1 0 6 (1  z ) 0  z 1
1 1 0 0 0
1 1 1 0 0

07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES

025 15
 LAGRANGE’S MULTIPLIER METHOD

All the roots (here only one) are positive.

 f has minimum at X*
 0.333
*  
X  0.333 and f min 0.1666
 0.333

07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES

025 16
 LAGRANGE’S MULTIPLIER METHOD

Ex.3: Find the dimensions of the rectangular

3
box of volume V=1000 m , for which the total
length of its twelve edges is minimum.
Let the dimensions of the box are -
Length = x1 , width = x 2 , height = x 3
 volume = V= x1.x 2 .x 3 = 1000 m3

Total length of 12 edges =S= 4x1 +4x 2 +4x 3

 S is minimum if f x1 +x 2 +x 3 is minimum

07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES

025 17
 LAGRANGE’S MULTIPLIER METHOD

Min f ( X )  x1  x2  x3 SC g ( X )  x1x2 x3 -1000

L  f ( X )   g( X )
L f g
0   1   x2 x3 0
x1 x1 x1
L f g
0   1   x1 x3 0
x2 x2 x2
L f g
0   1   x1 x2 0
x3 x3 x3
L
0  g ( X )  x1x2 x3  1000

07/26/202 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES
5 18
 LAGRANGE’S MULTIPLIER METHOD

n
solving these eq , we get
1
 x2 x3 x1x3 x1x2   x1 x2 x3

and x1x2 x3 x1x1 x1 1000  x1 x2 x3 10
also   0.01
* *
Sufficient Condition: At X and 

07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES

025 19
 LAGRANGE’S MULTIPLIER METHOD

2 L 2 L 2 L
L11  0, L12   0.1, L13   0.1
x12 x1x2 x1x3

2 L 2 L 2 L
L21   0.1, L22  2 0, L23   0.1
x2x1 x2 x2x3

2 L 2 L 2 L
L31   0.1, L32   0.1, L33  2
0
x3x1 x3x2 x3
g1 g1 g1
g11  100 , g12  100 , g13  100
x1 x2 x3

07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES

025 20
 LAGRANGE’S MULTIPLIER METHOD

L11  z L12 L13 g11

L21 L22  z L23 g12
0
L31 L32 L33  z g13
g11 g12 g13 0

 z  0.1  0.1 100

 0.1  z  0.1 100
0  z 0.5
 0.1  0.1  z 100
100 100 100 0

07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES

025 21
 LAGRANGE’S MULTIPLIER METHOD

All the roots (here only one) are positive.

 f has minimum at X*
 10 
*  
X  10  and f min 30
 10 
and the minimum total length of 12 edges
= 4 (30) = 120m

07/26/2 UNIT-I : CLASSICAL OPTIMIZATION TECHNIQUES

025 22