skalować niezmienność algorytmów wyszukiwania linii i regionu zaufania

W książce Nocedal & Wright o optymalizacji numerycznej znajduje się stwierdzenie w sekcji 2.2 (strona 27): „Ogólnie rzecz biorąc, łatwiej jest zachować niezmienność skali dla algorytmów wyszukiwania linii niż dla algorytmów regionu zaufania”. W tej samej sekcji mówią o posiadaniu nowych zmiennych, które są skalowanymi wersjami oryginalnych zmiennych, które mogą pomóc zarówno w wyszukiwaniu linii, jak i regionie zaufania. Innym podejściem jest wstępne przygotowanie. W przypadku metod regionu zaufania wstępne przygotowanie jest równoważne z eliptycznymi regionami zaufania, a zatem zapewnia niezmienność skali. Jednak podobna intuicja nie jest jasna w przypadku wstępnego przygotowania do wyszukiwania linii. W jaki sposób wyszukiwanie liniowe lepiej nadaje się do niezmienności skali? Czy są jakieś względy praktyczne?

Mam też pytanie dotyczące wstępnego przygotowania metod regionu zaufania. Czy w przypadku bardzo źle uwarunkowanego problemu dobry warunek wstępny zmniejszy zarówno liczbę zewnętrznych iteracji Newtona, jak i wewnętrznych iteracji CG, czy tylko te ostatnie? Ponieważ obszar zaufania jest elipsoidalny w pierwotnej przestrzeni, dobry warunek wstępny powinien doprowadzić do elipsoidy, która lepiej pasuje do krajobrazu. Wydaje mi się, że może to zmniejszyć liczbę zewnętrznych iteracji Newtona, zmuszając algorytm do wybierania lepszych kierunków. Czy to jest poprawne?

Przypuszczam, że może istnieć pewna różnica między tym, jak metody wyszukiwania linii i regionu zaufania traktują skalowanie, ale tak naprawdę nie widzę, aby działało to w praktyce, dopóki jesteśmy świadomi skalowania. I, dla jasności, książka Nocedal i Wright mówiła o skalowaniu afinicznym. Skalowanie nieliniowe jest nieco trudniejsze do oszacowania.

$f:X\rightarrow \mathbb{R}$$A\in\mathscr{L}(X)$$J:X\rightarrow \mathbb{R}$

$$\begin{align*} J(x) =& f(Ax)\\ \nabla J(x) =& A\nabla f(Ax)\\ \nabla^2 J(x) =& A\nabla^2 f(Ax) A \end{align*}$$ $A$ $$\nabla^2 J(x) \delta x = -\nabla J(x)$$ $$A\nabla^2 f(Ax) A \delta x = -A\nabla f(Ax)$$ $$A \delta x = -\nabla^2 f(Ax)^{-1} \nabla f(Ax)$$

$$H \delta x = -\nabla J(x)$$ $H$ $$H \delta x = -A \nabla f(Ax)$$ $A$$H$

$\phi$

$$\delta x = \phi(-A\nabla f(Ax))$$ $\phi$$\phi$$\phi$$A$

$$\nabla^2 J(x) \delta x = -\nabla J(x)$$ niedokładnie używając CG. To właśnie używa Steihaug-Toint w ustawieniach regionu zaufania (s. 171 w Nocedal i Wright) lub Newton-CG do wyszukiwania linii (s. 169 w Nocedal i Wright). Działają prawie tak samo i nie dbają o skalowanie afiniczne. Nie wymagają również przechowywania Hesji, wymagane są tylko produkty z Hesji. Naprawdę, te algorytmy powinny być końmi roboczymi dla większości problemów i nie dbają o skalowanie afiniczne.

Jeśli chodzi o warunek wstępny dla problemu regionu zaufania, nie sądzę, że istnieje prosty sposób, aby powiedzieć apriori, czy zamierzasz poprawić ogólną liczbę iteracji optymalizacji, czy nie. Naprawdę pod koniec dnia metody optymalizacji działają w dwóch trybach. W trybie pierwszym jesteśmy zbyt daleko od promienia zbieżności metody Newtona, więc globalizujemy i po prostu zmuszamy iteracje do upewnienia się, że cel spadnie. Region zaufania jest jednym ze sposobów. Kolejne jest wyszukiwanie liniowe. W trybie drugim jesteśmy w promieniu zbieżności metody Newtona, więc staramy się nie zadzierać i pozwolić, aby metoda Newtona wykonała swoją pracę. W rzeczywistości możemy to zobaczyć w dowodach konwergencji takich rzeczy, jak metody oparte na zaufaniu. Na przykład spójrz na Twierdzenie 4.9 (s. 93 w Nocedal i Wright). Mówią bardzo wyraźnie, w jaki sposób region zaufania staje się nieaktywny. W tym kontekście, jaka jest użyteczność warunku wstępnego? Oczywiście, gdy jesteśmy w promieniu zbieżności metody Newtona, wykonujemy znacznie mniej pracy, a liczba iteracji CG maleje. Co się stanie, gdy znajdziemy się poza tym promieniem? To trochę zależy. Jeśli obliczymy krok pełnego Newtona, korzyścią jest to, że wykonaliśmy mniej pracy. Jeśli wcześniej odetniemy nasz krok z powodu obcięcia od obciętego CG, wówczas nasz kierunek będzie w podprzestrzeni Kryłowa

$$\{-P\nabla J(x),-(PH)(P\nabla J(x)),\dots,-(PH)^k(P\nabla J(x))\}$$ $P$$H$ $$\{-\nabla J(x),-(H)(\nabla J(x)),\dots,-(H)^k(\nabla J(x))\}?$$

Nie oznacza to, że zdefiniowanie dobrego warunku wstępnego nie ma żadnej wartości. Nie jestem jednak pewien, jak ktoś definiuje warunek wstępny, który ma pomóc w optymalizacji punktów oddalonych od promienia zbieżności metody Newtona. Zazwyczaj projektujemy warunek wstępny do zgrupowania wartości własnych przybliżenia Hesji, który jest namacalnym, mierzalnym celem.

tldr; Praktycznie rzecz biorąc, istnieje wiele różnych sposobów generowania iteracji przez metodę wyszukiwania linii niż metoda regionu zaufania, więc możliwe jest, że istnieje niesamowity sposób obsługi skalowania afinicznego. Jednak po prostu użyj niedokładnej metody Newtona i nie ma to znaczenia. Warunek wstępny wpływa na wydajność algorytmu poza promieniem zbieżności metody Newtona, ale trudno jest określić ilościowo, więc po prostu zaprojektuj warunek wstępny, aby skupić wartości własne aproksymacji Hessiasna.