Quasi Newton

Information about Quasi Newton

Published on January 16, 2008

Author: Reginaldo

Source: authorstream.com

Content

Quasi-Newton Methods:  Quasi-Newton Methods Background:  Background Assumption: the evaluation of the Hessian is impractical or costly. Central idea underlying quasi-Newton methods is to use an approximation of the inverse Hessian. Form of approximation differs among methods. Question: What is the simplest approximation? The quasi-Newton methods that build up an approximation of the inverse Hessian are often regarded as the most sophisticated for solving unconstrained problems. Modified Newton Method:  Modified Newton Method Question: What is a measure of effectiveness for the Classical Modified Newton Method? Quasi-Newton Methods:  Quasi-Newton Methods Big question: What is the update matrix? In quasi-Newton methods, instead of the true Hessian, an initial matrix H0 is chosen (usually H0 = I) which is subsequently updated by an update formula: Hk+1 = Hk + Hku where Hku is the update matrix. This updating can also be done with the inverse of the Hessian H-1as follows: Let B = H-1; then the updating formula for the inverse is also of the form Bk+1 = Bk + Bku Hessian Matrix Updates:  Hessian Matrix Updates Given two points xk and xk+1 , we define gk = y(xk) and gk+1 =  y(xk+1). Further, let pk = xk+1 - xk , then gk+1 - gk ≈ H(xk) pk If the Hessian is constant, then gk+1 - gk = H pk which can be rewritten as qk = H pk If the Hessian is constant, then the following condition would hold as well H-1k+1 qi = pi 0 ≤ i ≤ k This is called the quasi-Newton condition. Rank One and Rank Two Updates:  Rank One and Rank Two Updates Let B = H-1, then the quasi-Newton condition becomes Bk+1 qi = pi 0 ≤ i ≤ k Substitute the updating formula Bk+1 = Bk + Buk and the condition becomes pi = Bk qi + Buk qi (1) (remember: pi = xi+1 - xi and qi = gi+1 - gi ) Note: There is no unique solution to funding the update matrix Buk A general form is Buk = a uuT + b vvT where a and b are scalars and u and v are vectors satisfying condition (1). The quantities auuT and bvvT are symmetric matrices of (at most) rank one. Quasi-Newton methods that take b = 0 are using rank one updates. Quasi-Newton methods that take b ≠ 0 are using rank two updates. Note that b ≠ 0 provides more flexibility. Update Formulas:  Update Formulas The following two update formulas have received wide acceptance: • Davidon -Fletcher-Powell (DFP) formula • Broyden-Fletcher-Goldfarb-Shanno (BFGS) formula. Davidon-Fletcher-Powel Formula:  Davidon-Fletcher-Powel Formula Earliest (and one of the most clever) schemes for constructing the inverse Hessian was originally proposed by Davidon (1959) and later developed by Fletcher and Powell (1963). It has the interesting property that, for a quadratic objective, it simultaneously generates the directions of the conjugate gradient method while constructing the inverse Hessian. The method is also referred to as the variable metric method (originally suggested by Davidon). Broyden–Fletcher–Goldfarb–Shanno Formula:  Broyden–Fletcher–Goldfarb–Shanno Formula Some Comments on Broyden Methods:  Some Comments on Broyden Methods Broyden–Fletcher–Goldfarb–Shanno formula is more complicated than DFP, but straightforward to apply BFGS update formula can be used exactly like DFP formula. Numerical experiments have shown that BFGS formula's performance is superior over DFP formula. Hence, BFGS is often preferred over DFP. Both DFP and BFGS updates have symmetric rank two corrections that are constructed from the vectors pk and Bkqk. Weighted combinations of these formulae will therefore also have the same properties. This observation leads to a whole collection of updates, know as the Broyden family, defined by: Bf = (1 - f)BDFP + fBBFGS where f is a parameter that may take any real value. Quasi-Newton Algorithm:  Quasi-Newton Algorithm Note: You do have to calculate the vector of first order derivatives g for each iteration. 1. Input x0, B0, termination criteria. 2. For any k, set Sk = – Bkgk. 3. Compute a step size a (e.g., by line search on y(xk + aSk)) and set xk+1 = xk + aSk. 4. Compute the update matrix Buk according to a given formula (say, DFP or BFGS) using the values qk = gk+1 - gk , pk = xk+1 - xk , and Bk. 5. Set Bk+1 = Bk + Buk. 6. Continue with next k until termination criteria are satisfied. Some Closing Remarks:  Some Closing Remarks Both DFP and BFGS methods have theoretical properties that guarantee superlinear (fast) convergence rate and global convergence under certain conditions. However, both methods could fail for general nonlinear problems. Specifically, • DFP is highly sensitive to inaccuracies in line searches. • Both methods can get stuck on a saddle-point. In Newton's method, a saddle-point can be detected during modifications of the (true) Hessian. Therefore, search around the final point when using quasi-Newton methods. • Update of Hessian becomes "corrupted" by round-off and other inaccuracies. All kind of "tricks" such as scaling and preconditioning exist to boost the performance of the methods.

Related presentations


Other presentations created by Reginaldo

fall construction
08. 01. 2008
0 views

fall construction

Maori Culture
10. 01. 2008
0 views

Maori Culture

3rdconf tonetti
11. 01. 2008
0 views

3rdconf tonetti

GoodFaith
13. 01. 2008
0 views

GoodFaith

2004 u apresentacao
13. 01. 2008
0 views

2004 u apresentacao

MetaRx
14. 01. 2008
0 views

MetaRx

pp4
15. 01. 2008
0 views

pp4

BLAST
16. 01. 2008
0 views

BLAST

Cultural Competence
17. 01. 2008
0 views

Cultural Competence

miracles gcse
17. 01. 2008
0 views

miracles gcse

AC Grad Presentation
18. 01. 2008
0 views

AC Grad Presentation

The Colonial Period
19. 01. 2008
0 views

The Colonial Period

farag
22. 01. 2008
0 views

farag

Georgia MRSA
23. 01. 2008
0 views

Georgia MRSA

khan
24. 01. 2008
0 views

khan

kelly
05. 02. 2008
0 views

kelly

TireFBCpowerpoint
12. 02. 2008
0 views

TireFBCpowerpoint

Backyard Biology
25. 01. 2008
0 views

Backyard Biology

statia pptreview1
28. 01. 2008
0 views

statia pptreview1

ER to REL
29. 01. 2008
0 views

ER to REL

Doctor Faustus
29. 01. 2008
0 views

Doctor Faustus

Event Planning Record 9
06. 02. 2008
0 views

Event Planning Record 9

ciforp
07. 02. 2008
0 views

ciforp

Yuan and Ming Dynasties
07. 02. 2008
0 views

Yuan and Ming Dynasties

MissionPossible
13. 02. 2008
0 views

MissionPossible

20050517 TCBACMeeting Process
14. 02. 2008
0 views

20050517 TCBACMeeting Process

SpiralDynamics IPGA
18. 02. 2008
0 views

SpiralDynamics IPGA

cs554 lect05
11. 01. 2008
0 views

cs554 lect05

NIHPCS1002f
24. 01. 2008
0 views

NIHPCS1002f

mandarin 103007
11. 03. 2008
0 views

mandarin 103007

AAMAS07 Invitation
14. 03. 2008
0 views

AAMAS07 Invitation

lahey9e 08
08. 02. 2008
0 views

lahey9e 08

2006 12 01 Roman
28. 03. 2008
0 views

2006 12 01 Roman

M6
09. 01. 2008
0 views

M6

Hurd IRAC
12. 01. 2008
0 views

Hurd IRAC

Applications January 2007v2
10. 04. 2008
0 views

Applications January 2007v2

maxine brown
16. 04. 2008
0 views

maxine brown

aegean
08. 03. 2008
0 views

aegean

200571816522254
18. 04. 2008
0 views

200571816522254

Gross Domestic Product vs
21. 04. 2008
0 views

Gross Domestic Product vs

2000 annual results analyst
22. 04. 2008
0 views

2000 annual results analyst

CERTUnit8
24. 04. 2008
0 views

CERTUnit8

Chap05
07. 05. 2008
0 views

Chap05

PPT RobertScollay
08. 05. 2008
0 views

PPT RobertScollay

Overview2006
05. 02. 2008
0 views

Overview2006

caring
30. 04. 2008
0 views

caring

8 09 15
02. 05. 2008
0 views

8 09 15

Abilene Metadata 2 20070919
03. 03. 2008
0 views

Abilene Metadata 2 20070919

491158BECB
02. 05. 2008
0 views

491158BECB

LT1053N 01 2007
04. 02. 2008
0 views

LT1053N 01 2007

Washingtons Presidency
22. 01. 2008
0 views

Washingtons Presidency

1 20080121100630
14. 04. 2008
0 views

1 20080121100630

mccrory
12. 03. 2008
0 views

mccrory

EHS Tech Update1 6 23 20041
09. 01. 2008
0 views

EHS Tech Update1 6 23 20041

FrancoisViruly
04. 02. 2008
0 views

FrancoisViruly

Hamburgpipe
14. 01. 2008
0 views

Hamburgpipe

Sercel
17. 01. 2008
0 views

Sercel

fg alt off learn sept 06
15. 01. 2008
0 views

fg alt off learn sept 06

1 800 MAR TIAN
24. 01. 2008
0 views

1 800 MAR TIAN

bergmann erf 1999
29. 02. 2008
0 views

bergmann erf 1999

YLemel Brno
07. 02. 2008
0 views

YLemel Brno

A Lamond Triton
11. 01. 2008
0 views

A Lamond Triton

Sarcoidosis 3
11. 02. 2008
0 views

Sarcoidosis 3

Bilanz Mediakomm Kraft
31. 01. 2008
0 views

Bilanz Mediakomm Kraft

BJA IED Mod1 IntrotoIED
11. 01. 2008
0 views

BJA IED Mod1 IntrotoIED

Vols of Yr Event 2006 26 Apr
04. 02. 2008
0 views

Vols of Yr Event 2006 26 Apr