Davidon – Fletcher – Powellův vzorec - Davidon–Fletcher–Powell formula

The Davidon – Fletcher – Powellův vzorec (nebo DFP; pojmenoval podle William C. Davidon, Roger Fletcher, a Michael J. D. Powell ) najde řešení sečancové rovnice, které je nejblíže aktuálnímu odhadu a splňuje podmínku zakřivení. Bylo to první kvazi-Newtonova metoda zobecnit sekansová metoda k vícerozměrnému problému. Tato aktualizace zachovává symetrii a pozitivní definitivitu Hesenská matice.

Vzhledem k funkci ${displaystyle f (x)}$, své spád (${displaystyle abla f}$), a pozitivní-definitivní Hesenská matice ${displaystyle B}$, Taylor série je

${displaystyle f (x_ {k} + s_ {k}) = f (x_ {k}) + abla f (x_ {k}) ^ {T} s_ {k} + {frac {1} {2}} s_ {k} ^ {T} {B} s_ {k} + tečky,}$

a Taylor série samotného gradientu (secantová rovnice)

${displaystyle abla f (x_ {k} + s_ {k}) = abla f (x_ {k}) + Bs_ {k} + tečky}$

slouží k aktualizaci ${displaystyle B}$.

Vzorec DFP najde řešení, které je symetrické, kladně definitivní a nejblíže současné přibližné hodnotě ${displaystyle B_ {k}}$:

${displaystyle B_ {k + 1} = (I-gamma _ {k} y_ {k} s_ {k} ^ {T}) B_ {k} (I-gamma _ {k} s_ {k} y_ {k} ^ {T}) + gamma _ {k} y_ {k} y_ {k} ^ {T},}$

kde

${displaystyle y_ {k} = abla f (x_ {k} + s_ {k}) - abla f (x_ {k}),}$

${displaystyle gamma _ {k} = {frac {1} {y_ {k} ^ {T} s_ {k}}},}$

a ${displaystyle B_ {k}}$ je symetrický a pozitivně definitivní matice.

Odpovídající aktualizace inverzní hesenské aproximace ${displaystyle H_ {k} = B_ {k} ^ {- 1}}$ darováno

${displaystyle H_ {k + 1} = H_ {k} - {frac {H_ {k} y_ {k} y_ {k} ^ {T} H_ {k}} {y_ {k} ^ {T} H_ {k } y_ {k}}} + {frac {s_ {k} s_ {k} ^ {T}} {y_ {k} ^ {T} s_ {k}}}.}$

${displaystyle B}$ se předpokládá, že jsou kladně definitivní a vektory ${displaystyle s_ {k} ^ {T}}$ a ${displaystyle y}$ musí splňovat podmínku zakřivení

${displaystyle s_ {k} ^ {T} y_ {k} = s_ {k} ^ {T} Bs_ {k}> 0.}$

Vzorec DFP je docela efektivní, ale brzy byl nahrazen Broyden – Fletcher – Goldfarb – Shanno vzorec, což je jeho dvojí (záměna rolí y a s).^[1]

Viz také

• Newtonova metoda
• Newtonova metoda v optimalizaci
• Kvazi-Newtonova metoda
• Broyden – Fletcher – Goldfarb – Shanno (BFGS) metoda
• Metoda BFGS s omezenou pamětí
• Symetrický vzorec první řady
• Metoda Nelder – Mead

Reference

Další čtení

• Davidon, W. C. (1959). "Variabilní metrická metoda pro minimalizaci". Zpráva o výzkumu a vývoji AEC ANL-5990. doi:10.2172/4252678.
• Fletcher, Roger (1987). Praktické metody optimalizace (2. vyd.). New York: John Wiley & Sons. ISBN  978-0-471-91547-8.
• Kowalik, J .; Osborne, M. R. (1968). Metody pro neomezené optimalizační problémy. New York: Elsevier. str.45–48. ISBN  0-444-00041-0.
• Nocedal, Jorge; Wright, Stephen J. (1999). Numerická optimalizace. Springer-Verlag. ISBN  0-387-98793-2.
• Walsh, G. R. (1975). Metody optimalizace. London: John Wiley & Sons. 110–120. ISBN  0-471-91922-5.