Intuicyjna motywacja do aktualizacji BFGS

Prowadzę zajęcia z analizy numerycznej i szukam motywacji do metody BFGS dla studentów z ograniczonym zapleczem / intuicją w optymalizacji!

Chociaż nie mam czasu, aby rygorystycznie udowodnić, że wszystko się zbiega, staram się uzasadnić, dlaczego może pojawić się aktualizacja Hesji BFGS. Analogicznie, metodę znalezienia root Broydena (mój opis jest tutaj ) można zmotywować, prosząc, aby twoje obecne przybliżenie jakobianów minimalizowało różnicę ze starym jakobianem z zastrzeżeniem, że bierze ono pod uwagę najnowszą : . $\|J_k-J_{k-1}\|^2_{\textrm{Fro}}$ $J_k(\vec x_k-\vec x_{k-1})=f(\vec x_k)-f(\vec x_{k-1})$

Pochodne aktualizacji BFGS wydają się o wiele bardziej zaangażowane i mętne! W szczególności nie chciałbym zakładać z góry, że aktualizacja powinna mieć rangę 2 lub przyjąć określoną formę. Czy istnieje krótka motywacja wyglądająca na wariację dla aktualizacji BFGS w Hesji, jak ta dla Broydena?

optimization iterative-method nonlinear-programming

— Justin Solomon
źródło

Jeśli zezwolisz na dowolną aktualizację, możesz po prostu użyć pełnego Hesji w metodzie Newtona. Jedną z głównych zalet obliczeniowych aktualizacji niskiej rangi jest to, że pozwala ona bardzo szybko zaktualizować faktoryzację przybliżonego Hesji.

— Brian Borchers,

Wyprowadzenie BFGS jest bardziej intuicyjne, gdy weźmie się pod uwagę (ściśle) funkcjonały wypukłego kosztu:

Jednak niektóre t informacje niezbędne jest: Załóżmy chce się minimalizować wypukłą funkcjonalny Powiedz, że istnieje przybliżone rozwiązanie . Następnie przybliżamy minimum do minimum obciętego rozszerzenia Taylora Oznacza to, że szuka się takiego, że jest minimalne i ustawia . Obliczenie gradientu - „względem ” - i ustawienie go na zero daje relację

fa (x) \to min_{x \in R^{n}} .

$f(x) \to \min_{x\in \mathbb R^n}.$

x_{k}

$x_k$

f

$f$

fa (x_{k} + p) \approx fa (x_{k}) + \nabla fa (x_{k})^{T.} p + \frac{1}{2)} p^{T.} H. (x_{k}) p . (*)

$f(x_k+p) \approx f(x_k) +\nabla f(x_k)^Tp + \frac{1}{2}p^T H(x_k)p. \quad(*)$

p

$p$

(*)

$(*)$

x_{k + 1} := x_{k} + p

$x_{k+1} := x_k + p$

(*)

$(*)$

p

$p$

H. (x_{k}) [x_{k + 1} - x_{k}] = \nabla fa (x_{k + 1}) - \nabla fa (x_{k}),

$H(x_k)[x_{k+1} - x_k] = \nabla f(x_{k+1}) - \nabla f(x_k),$ gdzie jest „jakobianem gradientu” lub macierzą Hesji.

H

$H$

Ponieważ obliczenia i inwersja Hesjan są drogie ...

... krótka odpowiedź

(por. aktualizacja Broydena) może być tak, że aktualizacja BFGS minimalizuje w inteligentnie wybranej ważonej normie Frobeniusa, z zastrzeżeniem $H_{k+1}^{-1}$

‖ {H.}_{k}^{- 1} - {H.}^{- 1} ‖_{W.}

$\|H_k^{-1} - H^{-1}\|_W$

$H[x_{k+1} - x_k] = \nabla f(x_{k+1}) - \nabla f(x_k)$ - po to jest jeden - i
$H^T = H$ , ponieważ Hesjan jest symetryczny.

Następnie wybór masy w ~~jako odwrotność~~ uśrednionego Heskiego , por. tutaj dla instrukcji, ale bez dowodu, podaje formułę aktualizacji BFGS (z ). $W$ $\|H\|_W := \|W^{1/2}HW^{1/2}\|_F$ $G:=\int_0^1 H(x_k + \tau p) d\tau$ $\alpha_k = 1$

Główne punkty to:

Próbuje się zbliżyć rozwiązanie do faktycznych kosztów przez rozwiązanie dla kwadratowego przybliżenia
Obliczenia Hesji i ich odwrotności są drogie. Preferuje się proste aktualizacje.
Aktualizacja jest wybierana optymalnie dla odwrotnego, a nie dla samego Hesji.
To, że jest to aktualizacja rangi 2, jest konsekwencją konkretnego wyboru wag w normie Frobeniusa.

Już odpowiedź powinna zawierać jak wybrać wagi, jak do tej pracy za problemy nonconvex (gdzie pojawia się krzywizny stan, który wymaga skalowania kierunku szukaj ), i jak czerpać rzeczywistego wzoru na aktualizację. Referencje znajdują się tutaj (w języku niemieckim). $p$

— Jan
źródło

Dzięki bardzo, to jest świetne (i mniej więcej to, czego się spodziewałem na podstawie dyskusji w Nocedal i Wright). Pozostaje mi jedno pytanie: dlaczego wybieramy i normę tak jak my? Rozumiem, że ma to związek z jednostkami, ale istnieje duży potencjalny wybór i norm, które to robią.

W

$W$

W

$W$

— Justin Solomon

Tak, prawda. Nie wiem. Jedna odpowiedź jest taka, że daje prostą do obliczenia i dobrze działającą formułę aktualizacji. Historycznie takie podejście do aktualizacji - minimalizujące różnicę w aktualizacji - było takie, jak Shanno. To był sędzia (Goldfarb), który stwierdził, że określony wybór wag prowadzi do formuły Broydena i Fletchera. Zobacz tę pracę doktorską Historyczny rozwój metody siecznej BFGS ... dla intuicji twórców BFGS. Jednak wszystkie 3 podejścia są dość abstrakcyjne.

— stycznia 13

Ciekawe, dzięki za wskazówki! Mój obecny opis (z kilkoma błędami matematycznymi, które wymagają pomocy) jest tutaj: graphics.stanford.edu/courses/cs205a-13-fall/assets/notes/… (jeśli chciałbyś podziękować za twoją pomoc, z przyjemnością ją udzielę - napisz do mnie z odpowiednimi danymi kontaktowymi)

— Justin Solomon,

@jan Dlaczego twoje równanie a nie Czy nie jest to warunek sieczny podany przez , gdzie . Dzięki!

H. (x_{k}) [x_{k + 1} - x_{k}] = \nabla fa (x_{k + 1}) - \nabla fa (x_{k})

$H(x_k)[x_{k+1} - x_k] = \nabla f(x_{k+1}) - \nabla f(x_k)$

H. (x_{k + 1}) [x_{k + 1} - x_{k}] = \nabla fa (x_{k + 1}) - \nabla fa (x_{k}) ?

$H(x_{k+1})[x_{k+1} - x_k] = \nabla f(x_{k+1}) - \nabla f(x_k)?$

H_{k + 1} s_{k} = y_{k}

$H_{k+1}s_k =y_k$

s_{k} = x_{k + 1} - x_{k}, y_{k} = \nabla f_{k + 1} - \nabla f_{k}

$s_k=x_{k+1}-x_k, y_k=\nabla f_{k+1}-\nabla f_k$

— Jeff Faraci