Algorytm Broydena – Fletchera – Goldfarba – Shanno - Broyden–Fletcher–Goldfarb–Shanno algorithm

W numerycznej optymalizacji The Broyden-Fletcher-Goldfarb-Shanno ( BFGS ) algorytm jest iteracyjna metoda dla rozwiązania nie ograniczające nieliniowych optymalizacji problemów. Tak jak związane z metodą Davidon-Fletcher Powell , BFGS określa kierunek zanurzania przez wstępnego z gradientem z informacjami krzywizny. Czyni to zwiększając stopniowo aproksymacją Heskiego matrycy do funkcji strat uzyskane wyłącznie z ocen nachylenia (gradientu lub przybliżonej oceny) poprzez uogólnionej metody siecznej .

Ponieważ aktualizacje BFGS krzywizna matryca nie wymaga odwracania macierzy , jej złożoność obliczeniowa jest tylko w stosunku do w metodzie Newtona . W powszechnym użyciu jest również L-BFGS , który jest wersją BFGS z ograniczoną pamięcią, który jest szczególnie dostosowany do problemów z bardzo dużą liczbą zmiennych (np.> 1000). Wariant BFGS-B obsługuje proste ograniczenia pola. ${\ Displaystyle {\ mathcal {O}} (n ^ {2})}$${\ Displaystyle {\ mathcal {O}} (n ^ {3})}$

Algorytm został nazwany na cześć Charlesa George'a Broydena , Rogera Fletchera , Donalda Goldfarba i Davida Shanno .

Racjonalne uzasadnienie

Problem optymalizacji polega na zminimalizowaniu , gdzie jest wektor i jest różniczkowalną funkcją skalarną. Nie ma ograniczeń co do wartości, które mogą przyjąć. ${\ displaystyle f (\ mathbf {x})}$${\ displaystyle \ mathbf {x}}$${\ displaystyle \ mathbb {R} ^ {n}}$${\ displaystyle f}$${\ displaystyle \ mathbf {x}}$

Algorytm rozpoczyna się od wstępnego oszacowania optymalnej wartości i przechodzi iteracyjnie, aby uzyskać lepsze oszacowanie na każdym etapie. ${\ displaystyle \ mathbf {x} _ {0}}$

Kierunku wyszukiwania P _K w etapie K otrzymuje przez roztwór analogu równania Newton:

${\ Displaystyle B_ {k} \ mathbf {p} _ {k} = - \ nabla f (\ mathbf {x} _ {k}),}$

gdzie jest przybliżeniem do macierzy Hesja , która jest aktualizowana iteracyjnie na każdym etapie, i jest gradientem funkcji obliczanej przy x _k . Wyszukiwania linia w kierunku p _k jest następnie wykorzystywany do znalezienia następnego punktu x _{k +1} minimalizując przez skalar ${\ displaystyle B_ {k}}$${\ displaystyle \ nabla f (\ mathbf {x} _ {k})}$${\ Displaystyle f (\ mathbf {x} _ {k} + \ gamma \ mathbf {p} _ {k})}$${\ displaystyle \ gamma> 0.}$

Warunek quasi-Newtona nałożony na aktualizację wynosi ${\ displaystyle B_ {k}}$

${\ Displaystyle B_ {k + 1} (\ mathbf {x} _ {k + 1} - \ mathbf {x} _ {k}) = \ nabla f (\ mathbf {x} _ {k + 1}) - \ nabla f (\ mathbf {x} _ {k}).}$

Niech a , wówczas spełnia , co stanowi sieczną równanie. Warunek krzywizny powinien być spełniony, aby był określony dodatnio, co można zweryfikować przez wstępne pomnożenie równania siecznego przez . Jeśli funkcja nie jest mocno wypukła, warunek musi zostać wymuszony jawnie. ${\ Displaystyle \ mathbf {r} _ {k} = \ nabla f (\ mathbf {x} _ {k + 1}) - \ nabla f (\ mathbf {x} _ {k})}$${\ Displaystyle \ mathbf {s} _ {k} = \ mathbf {x} _ {k + 1} - \ mathbf {x} _ {k}}$${\ displaystyle B_ {k + 1}}$${\ Displaystyle B_ {k + 1} \ mathbf {s} _ {k} = \ mathbf {y} _ {k}}$${\ displaystyle \ mathbf {s} _ {k} ^ {\ top} \ mathbf {y} _ {k}> 0}$${\ displaystyle B_ {k + 1}}$${\ displaystyle \ mathbf {s} _ {k} ^ {T}}$

Zamiast wymagać pełnej macierzy Hesji w punkcie do obliczenia jako , przybliżony Hesjan na etapie k jest aktualizowany przez dodanie dwóch macierzy: ${\ displaystyle \ mathbf {x} _ {k + 1}}$${\ displaystyle B_ {k + 1}}$

${\ Displaystyle B_ {k + 1} = B_ {k} + U_ {k} + V_ {k}.}$

Obie i są symetrycznymi macierzami rangi jeden, ale ich suma jest macierzą aktualizacji rzędu drugiego. Macierz aktualizacji BFGS i DFP różnią się od swojego poprzednika macierzą drugiego stopnia. Inna prostsza metoda pierwszego rzędu jest znana jako symetryczna metoda pierwszego rzędu , która nie gwarantuje jednoznaczności pozytywnej . W celu zachowania symetrii i pozytywnej określoności , forma aktualizacji może zostać wybrana jako . Nakładając warunek sieczny, . Wybierając i możemy uzyskać: ${\ displaystyle U_ {k}}$${\ displaystyle V_ {k}}$${\ displaystyle B_ {k + 1}}$${\ Displaystyle B_ {k + 1} = B_ {k} + \ alpha \ mathbf {u} \ mathbf {u} ^ {\ top} + \ beta \ mathbf {v} \ mathbf {v} ^ {\ top} }$${\ Displaystyle B_ {k + 1} \ mathbf {s} _ {k} = \ mathbf {y} _ {k}}$${\ displaystyle \ mathbf {u} = \ mathbf {y} _ {k}}$${\ displaystyle \ mathbf {v} = B_ {k} \ mathbf {s} _ {k}}$

${\ Displaystyle \ alpha = {\ Frac {1} {\ mathbf {y} _ {k} ^ {T} \ mathbf {s} _ {k}}},}$

${\ Displaystyle \ beta = - {\ Frac {1} {\ mathbf {s} _ {k} ^ {T} B_ {k} \ mathbf {s} _ {k}}}.}$

Wreszcie możemy zastąpić i do i uzyskać równanie aktualizacji systemu : ${\ displaystyle \ alpha}$${\ displaystyle \ beta}$${\ Displaystyle B_ {k + 1} = B_ {k} + \ alpha \ mathbf {u} \ mathbf {u} ^ {\ top} + \ beta \ mathbf {v} \ mathbf {v} ^ {\ top} }$${\ displaystyle B_ {k + 1}}$

${\ Displaystyle B_ {k + 1} = B_ {k} + {\ Frac {\ mathbf {y} _ {k} \ mathbf {y} _ {k} ^ {\ mathrm {T}}} {\ mathbf { y} _ {k} ^ {\ mathrm {T}} \ mathbf {s} _ {k}}} - {\ frac {B_ {k} \ mathbf {s} _ {k} \ mathbf {s} _ { k} ^ {\ mathrm {T}} B_ {k} ^ {\ mathrm {T}}} {\ mathbf {s} _ {k} ^ {\ mathrm {T}} B_ {k} \ mathbf {s} _ {k}}}.}$

Algorytm

Od początkowego przypuszczenia i przybliżonej macierzy Hesja, następujące kroki są powtarzane, aby uzyskać rozwiązanie: ${\ displaystyle \ mathbf {x} _ {0}}$${\ displaystyle B_ {0}}$${\ displaystyle \ mathbf {x} _ {k}}$

1. Uzyskaj wskazówki , rozwiązując . ${\ displaystyle \ mathbf {p} _ {k}}$${\ Displaystyle B_ {k} \ mathbf {p} _ {k} = - \ nabla f (\ mathbf {x} _ {k})}$
2. Wykonaj jednowymiarową optymalizację ( wyszukiwanie liniowe ), aby znaleźć akceptowalną wielkość kroku w kierunku znalezionym w pierwszym kroku. Jeśli przeprowadzane jest dokładne wyszukiwanie wierszy, to . W praktyce zwykle wystarcza niedokładne przeszukiwanie linii, z akceptowalnymi, spełniającymi warunkami Wolfe'a . ${\ displaystyle \ alpha _ {k}}$${\ Displaystyle \ alpha _ {k} = \ arg \ min f (\ mathbf {x} _ {k} + \ alpha \ mathbf {p} _ {k})}$${\ displaystyle \ alpha _ {k}}$
3. Ustaw i zaktualizuj . ${\ displaystyle \ mathbf {s} _ {k} = \ alpha _ {k} \ mathbf {p} _ {k}}$${\ Displaystyle \ mathbf {x} _ {k + 1} = \ mathbf {x} _ {k} + \ mathbf {s} _ {k}}$
4. ${\ Displaystyle \ mathbf {r} _ {k} = {\ nabla f (\ mathbf {x} _ {k + 1}) - \ nabla f (\ mathbf {x} _ {k})}}$ .
5. ${\ Displaystyle B_ {k + 1} = B_ {k} + {\ Frac {\ mathbf {y} _ {k} \ mathbf {y} _ {k} ^ {\ mathrm {T}}} {\ mathbf { y} _ {k} ^ {\ mathrm {T}} \ mathbf {s} _ {k}}} - {\ frac {B_ {k} \ mathbf {s} _ {k} \ mathbf {s} _ { k} ^ {\ mathrm {T}} B_ {k} ^ {\ mathrm {T}}} {\ mathbf {s} _ {k} ^ {\ mathrm {T}} B_ {k} \ mathbf {s} _ {k}}}}$ .

${\ displaystyle f (\ mathbf {x})}$ oznacza minimalizowaną funkcję celu. Zbieżność może być kontrolowane przez obserwowanie normę gradientu . Jeśli jest zainicjowany za pomocą , pierwszy krok będzie równoważny z obniżaniem gradientu , ale dalsze kroki są coraz bardziej dopracowane przez przybliżenie do Hesji. ${\ Displaystyle || \ nabla f (\ mathbf {x} _ {k}) ||}$${\ displaystyle B_ {0}}$${\ displaystyle B_ {0} = I}$${\ displaystyle B_ {k}}$

Pierwszy krok algorytmu jest wykonywany z wykorzystaniem odwrotności macierzy , którą można skutecznie uzyskać stosując wzór Shermana-Morrisona do kroku 5 algorytmu, dając ${\ displaystyle B_ {k}}$

${\ Displaystyle B_ {k + 1} ^ {- 1} = \ lewo (ja - {\ Frac {\ mathbf {s} _ {k} \ mathbf {y} _ {k} ^ {T}} {\ mathbf) {y} _ {k} ^ {T} \ mathbf {s} _ {k}}} \ right) B_ {k} ^ {- 1} \ left (I - {\ frac {\ mathbf {y} _ { k} \ mathbf {s} _ {k} ^ {T}} {\ mathbf {y} _ {k} ^ {T} \ mathbf {s} _ {k}}} \ right) + {\ frac {\ mathbf {s} _ {k} \ mathbf {s} _ {k} ^ {T}} {\ mathbf {y} _ {k} ^ {T} \ mathbf {s} _ {k}}}.}$

To można obliczyć efektywnie bez przejściowych matrycach, uznając, że jest symetryczny, a i są skalary, używając rozszerzenia takie jak ${\ Displaystyle B_ {k} ^ {- 1}}$${\ Displaystyle \ mathbf {r} _ {k} ^ {\ mathrm {T}} B_ {k} ^ {- 1} \ mathbf {y} _ {k}}$${\ displaystyle \ mathbf {s} _ {k} ^ {\ mathrm {T}} \ mathbf {y} _ {k}}$

${\ Displaystyle B_ {k + 1} ^ {- 1} = B_ {k} ^ {- 1} + {\ Frac {(\ mathbf {s} _ {k} ^ {\ mathrm {T}} \ mathbf { y} _ {k} + \ mathbf {y} _ {k} ^ {\ mathrm {T}} B_ {k} ^ {- 1} \ mathbf {y} _ {k}) (\ mathbf {s} _ {k} \ mathbf {s} _ {k} ^ {\ mathrm {T}})} {(\ mathbf {s} _ {k} ^ {\ mathrm {T}} \ mathbf {y} _ {k}) ) ^ {2}}} - {\ frac {B_ {k} ^ {- 1} \ mathbf {y} _ {k} \ mathbf {s} _ {k} ^ {\ mathrm {T}} + \ mathbf {s} _ {k} \ mathbf {y} _ {k} ^ {\ mathrm {T}} B_ {k} ^ {- 1}} {\ mathbf {s} _ {k} ^ {\ mathrm {T }} \ mathbf {y} _ {k}}}.}$

W problemach estymacji statystycznej (takich jak maksymalne prawdopodobieństwo lub wnioskowanie bayesowskie) wiarygodne przedziały lub przedziały ufności dla rozwiązania można oszacować na podstawie odwrotności ostatecznej macierzy Hesja. Jednak wielkości te są technicznie zdefiniowane przez prawdziwą macierz Hesja, a przybliżenie BFGS może nie zbiegać się z prawdziwą macierzą Hesja.

Godne uwagi implementacje

• Oprogramowanie do optymalizacji nieliniowej na dużą skalę Artelys Knitro implementuje między innymi algorytmy BFGS i L-BFGS.
• W GSL narzędzia BFGS jak gsl_multimin_fdfminimizer_vector_bfgs2.
• W MATLAB Optimization Toolbox funkcja fminunc używa BFGS z wyszukiwaniem w linii sześciennej, gdy rozmiar problemu jest ustawiony na „średnią skalę”.
• W R algorytm BFGS (i wersja L-BFGS-B, która dopuszcza ograniczenia skrzynek) jest zaimplementowana jako opcja funkcji bazowej optim ().
• W SciPy funkcja scipy.optimize.fmin_bfgs implementuje BFGS. Możliwe jest również uruchomienie BFGS przy użyciu dowolnego z algorytmów L-BFGS poprzez ustawienie parametru L na bardzo dużą liczbę.

Zobacz też

Bibliografia

Dalsza lektura

• Avriel, Mordecai (2003), Nonlinear Programming: Analysis and Methods , Dover Publishing, ISBN   978-0-486-43227-4
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006), „Metody Newtona”, Optymalizacja numeryczna: aspekty teoretyczne i praktyczne (wydanie drugie), Berlin: Springer, str. 51–66, ISBN   3-540-35445-X
• Fletcher, Roger (1987), Practical Methods of Optimization (2nd ed.), New York: John Wiley & Sons , ISBN   978-0-471-91547-8
• Luenberger, David G .; Ye, Yinyu (2008), Programowanie liniowe i nieliniowe , International Series in Operations Research & Management Science, 116 (wydanie trzecie), New York: Springer, pp. Xiv + 546, ISBN   978-0-387-74502-2 , MR   2423726
• Kelley, CT (1999), Iterative Methods for Optimization , Philadelphia: Society for Industrial and Applied Mathematics, str. 71–86, ISBN   0-89871-433-8
• Nocedal Jorge; Wright, Stephen J. (2006), Numerical Optimization (2nd ed.), Berlin, New York: Springer-Verlag , ISBN   978-0-387-30303-1