Pomoc w podejmowaniu decyzji między interpolacją sześcienną i kwadratową w wyszukiwaniu liniowym

9

Przeprowadzam wyszukiwanie linii w ramach quasi-Newtona algorytmu BFGS. W jednym kroku wyszukiwania linii używam interpolacji sześciennej, aby zbliżyć się do lokalnego minimalizatora.

Niech będzie funkcją będącą przedmiotem zainteresowania. Chcę znaleźć takie, że .f:RR,fC1xf(x)0

Niech , , i będą znane. Załóżmy również . Dopasowuję sześcienny wielomian tak, że ,f(xk)f(xk)f(xk+1)f(xk+1)0xk<x<xk+1Q(x)=ax3+bx2+cx+dQ(0)=f(xk)Q(0)=f(xk), Q(xk+1xk)=f(xk+1) i Q(xk+1xk)=f(xk+1).

Rozwiązuję równanie kwadratowe: (1):Q(xxk)=0 dla moich poszukiwanych x za pomocą rozwiązania w formie zamkniętej.

Powyższe działa dobrze w większości przypadków, z wyjątkiem kiedy f(x)=O(x2) jako rozwiązanie w formie zamkniętej dla (1) dzieli przez a która staje się bardzo bliska lub dokładnie 0.

Moim rozwiązaniem jest spojrzenie a a jeśli jest „za mały”, po prostu weź formę zamkniętą dla minimalizatora kwadratowego wielomianu Q2(x)=bx2+cx+d dla których mam już współczynniki b,c,d od wcześniejszego dopasowania do Q(x).

Moje pytanie brzmi: w jaki sposób opracować dobry test, kiedy wziąć interpolację kwadratową nad sześcienną? Naiwne podejście do testowaniaa0 jest zły z powodów numerycznych, więc patrzę |a|<ϵτ gdzie ϵ jest precyzja maszyny, ale nie jestem w stanie zdecydować się na dobro τ to niezmiennik skali f.

Pytanie dodatkowe: czy są jakieś problemy numeryczne ze stosowaniem współczynników,b,c,d, z nieudanego dopasowania sześciennego, czy powinienem wykonać nowe dopasowanie kwadratowe z odpowiednim sposobem obliczania współczynników?

Edytuj dla wyjaśnienia: w moim pytaniuf jest tak naprawdę powszechnie nazywany ϕ(α)=f(x¯k+αpk¯)w literaturze. Właśnie uprościłem formułowanie pytania. Problem optymalizacji, który rozwiązuję, jest nieliniowy w 6 wymiarach. I jestem w pełni świadomy, że warunki Wolfe'a wystarczają do wyszukiwania linii BFGS, stąd stwierdzam, że byłem zainteresowanyf(x)0; Szukam czegoś, co zaspokoi silne warunki Wolfe'a, a przyjęcie minimalizatora przybliżenia sześciennego to dobry krok na drodze.

Pytanie nie dotyczyło BFGS, ale raczej, jak ustalić, kiedy współczynnik sześcienny jest wystarczająco mały, aby bardziej odpowiednie było przybliżenie kwadratowe.

Edycja 2: Zaktualizuj notację, równania nie ulegną zmianie.

Emily L.
źródło

Odpowiedzi:

4

Hmm ... interpolacja sześcienna nie jest niespotykana w przypadku przeszukiwania linii, ale zwykle przesada.

Jeśli poprawnie czytam twój problem, xjest tylko skalarem? W takim przypadku BFGS nie jest prawdopodobnie najbardziej efektywnym sposobem rozwiązania problemu. Algorytmy optymalizacji skalarnej, takie jak metoda Brentha, mogą szybciej rozwiązać Twój problem.

Istnieje wiele algorytmów wyszukiwania linii dla BFGS. W przypadku moich własnych aplikacji, przy użyciu ograniczonej pamięci BFGS (L-BFGS), wyszukiwanie liniowe działa bardzo dobrze. Pamiętaj, że musisz tylko spełnić warunki Wolfe'a i prawdopodobnie nie zyskasz dużo, znajdując dokładny minimalizator.

W każdym razie, aby odpowiedzieć na twoje pytanie: rozważyłbym po prostu przejście do wielomianu kwadratowego, jeśli rozwiązanie sześciennego daje „złe” wartości, takie jak NaN lub Inf (jak to tutaj zrobiono ).

Nie jestem do końca pewien, co masz na myśli, mówiąc b,c,d? Te współczynniki dopasowania sześciennego nie będą takie same jak dla dopasowania kwadratowego, więc nie można ich ponownie użyć.

Wreszcie możesz użyć f(xk1) , zamiast f(x0), ponieważ twoja funkcja będzie (prawdopodobnie) lokalnie w przybliżeniu sześcienna lub kwadratowa, oraz xk i xk1 powinny być bliżej siebie (i rozwiązania) niż x0.

Mam nadzieję że to pomoże.

LKlevin
źródło
Edytowane dla jasności. Używającb,c,d„Mam na myśli to, że dopasowałem się do sześciennego Q(x)=ax3+bx2+cx+d i znalazłem to a0 tak mam Q(x)=bx2+cx+dktóry jest już kwadratowym wielomianem. Pytanie dotyczyło tego, czy współczynnikib,c,duzyskane dla tego dopasowania są rozsądne do wykorzystania do wykonania interpolacji lub jeśli powinienem ponownie obliczyć nowe współczynniki dla typowego dopasowania kwadratowego.
Emily L.
Ach, racja, oczywiście. Nie widzę żadnego problemu w stosowaniu współczynników z liczbowego punktu widzenia. Myślę, że jedynym punktem, w którym miałoby to znaczenie, jest rozwiązanie bardzo blisko rozwiązania.
LKlevin
Czy potrafisz motywować swoją odpowiedź obliczaniem sześciennej i sprawdzaniem „złych” wartości? Dlaczego bezpiecznie to zrobić, kiedy?a<<b lub a0?
Emily L.,
Kiedy a0, b,c i dbędą w przybliżeniu te dla przypadku kwadratowego. Ponieważ wyszukiwanie liniowe BFGS jest dość solidne, powinieneś z nich korzystać, nawet jeśli nie są one całkowicie dokładne. Dopóki będziesz przestrzegać warunków Wolfe'a, osiągniesz zbieżność. Jeśli chodzi o „złe” wartości, o ile komputer może dokładnie wykonać obliczenia z wymaganą precyzją, wszystko jest dobrze. Kiedy nie będzie, zaczniesz widzieć inf i NaN.
LKlevin
4

Jest artykuł autorstwa Moré, wdrożony przez Nocedal, na ten temat:

Jorge J. Moré i David J. Thuente. 1994. Algorytmy wyszukiwania linii z gwarantowanym wystarczającym zmniejszeniem. ACM Trans. Matematyka Oprogramowanie 20, 3 (wrzesień 1994), 286-307. DOI http://dx.doi.org/10.1145/192115.192132 ( preprint ).

Juan Pablo Frias
źródło
Witamy w SciComp.SE! Sformatowałem twój post, aby ułatwić znalezienie papieru. Jeśli znajdziesz link do implementacji Nocedal, byłoby to pomocne.
Christian Clason