CH 5150: Optimization Techniques I
Autumn 2024
Instructor: Dr. Kishalay Mitra
Global Optimization & Knowledge Unearthing Lab (GOKUL)
Department of Chemical Engineering
Indian Institute of Technology Hyderabad
(kishalay@[Link])
[Link]
Indian Institute of Technology Hyderabad
Classification
General Approach
• Start with a point (initial guess)
• Identify a direction
• Provide some movement in the identified direction to find
the next point
X i +1 = X i + *iSi
2 Indian Institute of Technology Hyderabad
Steepest Descent
11 Indian Institute of Technology Hyderabad
Steepest Descent - Example
12 Indian Institute of Technology Hyderabad
Steepest Descent - Example
13 Indian Institute of Technology Hyderabad
Steepest Descent - Example
14 Indian Institute of Technology Hyderabad
Steepest Descent - Example
15 Indian Institute of Technology Hyderabad
Steepest Descent - Example
Start from anywhere to Takes several iterations and
converge in one iteration Depends on the starting point
16 Indian Institute of Technology Hyderabad
Steepest Descent – contd…
1 and n are the smallest and largest Eigen values of
Hessian H
17 Indian Institute of Technology Hyderabad
Scaling - Example
21 Indian Institute of Technology Hyderabad
Newton
Approximate the quadratic function at every point
& find the minimum of that and proceed
23 Indian Institute of Technology Hyderabad
Newton
24 Indian Institute of Technology Hyderabad
Newton
For a quadratic function, Newton’s algorithm converges
to the minimum in single iteration starting
from any point
25 Indian Institute of Technology Hyderabad
Newton Example
26 Indian Institute of Technology Hyderabad
Newton Example
27 Indian Institute of Technology Hyderabad
Newton
28 Indian Institute of Technology Hyderabad
Newton
29 Indian Institute of Technology Hyderabad
Newton Example
• Finds minima in lesser number of steps than the original
• Finds minima in all cases whereas the original method
diverges in many cases
• Usually avoids convergence to maxima / saddle point
However, this is impractical for a problem with complicated
objective function and large number of design variables due to
• Storing Hessian
• Computation of Hessian
• Inverse of Hessian at every step
30 Indian Institute of Technology Hyderabad
Marquardt Method
• Steepest descent works fine when the point is away from
optimum and oscillates near the optimum
• Newton works better when the point is near to optimum due
to quadratic approximation
• Can we exploit the two to take advantage of both
• Steepest descent when away and newton when near
For large , modified Hessian is identity matrix & for small
, modified Hessian is original Hessian matrix – is
constant for making [Ji] positive definite when it is not
31 Indian Institute of Technology Hyderabad
Marquardt Method (contd.)
• In Marquardt method, we start with a very large value of
(104) and this value is reduced gradually to ZERO
• This mimics the algorithm of STEEPEST descent in the
beginning and NEWTON towards later part
32 Indian Institute of Technology Hyderabad
Marquardt Method (contd.)
33 Indian Institute of Technology Hyderabad
Marquardt Method (contd.)
34 Indian Institute of Technology Hyderabad
Quasi Newton Method
• Basic idea is to approximate the Hessian (Ji) or its inverse using first order
derivatives
• Quadratic, hessian in not changing with X – what for higher order?
[Bi] = [Ji]-1 [Ai] = [Ji]
• Considering Taylor series expansion for the gradient,
n2 unknowns with n equations – can
be done by many ways – symmetry
and positive definiteness should be
maintained
40 Indian Institute of Technology Hyderabad
X i +1 = X i − *Bi f (X i )
Rank 1 Update
• Bi is the update – can be as high as rank n – practically 1 or 2
AT=[1 2 3 4]; AAT rank 1
Broyden:
Start with
symmetric,
+ve definite B1, scalar
calculate new X
(top equation),
Calculate d, g,
next calculate
new B2 and
continue
Guarantee of symmetry - No guarantee of positive definiteness
41 Indian Institute of Technology Hyderabad
X i +1 = X i − *Bi f (X i )
Rank 2 Update
• Bi is the update – can be as high as rank n – practically 1 or 2
DFP:
Start with
symmetric,
+ve definite B1,
calculate new X
(top equation),
Calculate d, g,
next calculate
new B2 and
continue
Davidon - Fletcher - Powel l (DFP)
42 Indian Institute of Technology Hyderabad
Rank 2 Update
• Guarantee of symmetry & positive definiteness in subsequent
iterations once a symmetric and positive definite matrix is supplied
• DFP is inverse update formula as we approximate the inverse of
Hessian
• Similarly Hessian itself can also be approximated
• If we follow the same process for approximating the Hessian itself, we
can get Broydon - Fletcher - Goldfarb - Shanno (BFGS) formula
• BFGS shows superlinear convergence near optima
• Numerical experience shows BFGS is better
43 Indian Institute of Technology Hyderabad
DFP Algorithm
44 Indian Institute of Technology Hyderabad
DFP Algorithm
45 Indian Institute of Technology Hyderabad
DFP Algorithm - Example
46 Indian Institute of Technology Hyderabad
DFP Algorithm - Example
47 Indian Institute of Technology Hyderabad
DFP Algorithm - Example
48 Indian Institute of Technology Hyderabad
DFP Algorithm - Example
49 Indian Institute of Technology Hyderabad
DFP Algorithm - Example
50 Indian Institute of Technology Hyderabad
DFP Algorithm - Example
51 Indian Institute of Technology Hyderabad
DFP Another Example
52 Indian Institute of Technology Hyderabad
DFP Another Example
53 Indian Institute of Technology Hyderabad
DFP Another Example
54 Indian Institute of Technology Hyderabad
DFP Another Example
55 Indian Institute of Technology Hyderabad
BFGS Algorithm
56 Indian Institute of Technology Hyderabad
BFGS Algorithm
57 Indian Institute of Technology Hyderabad
BFGS Example
58 Indian Institute of Technology Hyderabad
BFGS Example
59 Indian Institute of Technology Hyderabad
BFGS Example
60 Indian Institute of Technology Hyderabad
BFGS Example
61 Indian Institute of Technology Hyderabad