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

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 : R \rightarrow R, f \in C^1$$x^*$$f'(x^*) \approx 0$

Niech , , i będą znane. Załóżmy również . Dopasowuję sześcienny wielomian tak, że ,$f(x_k)$$f'(x_k)$$f(x_{k+1})$$f'(x_{k+1})$$0\le x_k<x^*<x_{k+1}$$Q(x)=ax^3+bx^2+cx+d$$Q(0)=f(x_k)$$Q'(0)=f'(x_k)$, $Q(x_{k+1}-x_{k})=f(x_{k+1})$ i $Q'(x_{k+1}-x_{k})=f'(x_{k+1})$.

Rozwiązuję równanie kwadratowe: $(1): Q'(x^*-x_k) = 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)=\mathcal{O}(x^2)$ 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 $Q_2(x)=bx^2+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 testowania$a \equiv 0$ jest zły z powodów numerycznych, więc patrzę $|a| < \epsilon\tau$ gdzie $\epsilon$ jest precyzja maszyny, ale nie jestem w stanie zdecydować się na dobro $\tau$ 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 pytaniu$f$ jest tak naprawdę powszechnie nazywany $\phi(\alpha)=f(\bar{x}_k+\alpha \bar{p_k})$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 zainteresowany$f'(x^*) \approx 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.

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

Jeśli poprawnie czytam twój problem, $x$jest 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(x_{k-1})$ , zamiast $f(x_0)$, ponieważ twoja funkcja będzie (prawdopodobnie) lokalnie w przybliżeniu sześcienna lub kwadratowa, oraz $x_k$ i $x_{k-1}$ powinny być bliżej siebie (i rozwiązania) niż $x_0$.

Mam nadzieję że to pomoże.

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 ).