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

Intuicyjna motywacja do aktualizacji BFGS

Odpowiedzi:

... krótka odpowiedź