Metody optymalizacji Newtona a rozwiązywanie układów równań nieliniowych

Poprosiłem o wyjaśnienia na temat ostatniego pytania na temat minpack i otrzymałem następujący komentarz:

Każdy układ równań jest równoznaczny z problemem optymalizacji, dlatego metody optymalizacji oparte na Newtonie przypominają metody rozwiązywania układów równań nieliniowych oparte na Newtonie.

To, co myli mnie w tym komentarzu (i powiązane negatywne opinie na temat wyspecjalizowanych nieliniowych solverów najmniejszych kwadratów, takich jak minpack), można najlepiej wyjaśnić na przykładzie metody gradientu sprzężonego . Sposób ten ma zastosowanie w systemach z symetrycznym dodatnim określonej macierzy . Można go również wykorzystać do rozwiązania ogólnego problemu najmniejszych kwadratów nazwa dla dowolnej macierzy , ale nie jest to zalecane. Jednym z powodów, dla których nie powinniśmy tego robić, jest to, że liczba warunków w systemie znacznie by wzrosła. $Ax=b$ $A$ $\operatorname{min}_x||Ax-b||^2$ $A$

Ale jeśli przekształcenie układu równań w problem optymalizacji jest uważane za problematyczne nawet w przypadku liniowym, dlaczego miałoby być mniej problematyczne w przypadku ogólnym? Wydaje się, że jest to w jakiś sposób powiązane z wykorzystaniem najnowocześniejszego algorytmu optymalizacji, zamiast z użyciem nieco przestarzałego nieliniowego solwera najmniejszych kwadratów. Ale czy problemy związane z wyrzucaniem informacji i zwiększaniem liczby stanów systemu są względnie niezależne od faktycznie używanego algorytmu optymalizacji?

optimization least-squares Thomas Klimpel
źródło

Odpowiedzi:

Ponieważ cytowano jedną z moich odpowiedzi, postaram się wyjaśnić, dlaczego zasugerowałem użycie IPOPT zamiast MINPACK.

Moje zastrzeżenia do używania MINPACK nie mają nic wspólnego z algorytmami używanymi przez MINPACK i wszystkim, co ma związek z ich implementacją. Moje główne zastrzeżenie polega na tym, że oprogramowanie pochodzi z 1980 r. I zostało ostatnio zaktualizowane w 1999 r. Jorge Moré jest na emeryturze; Wątpię, czy on lub którykolwiek z innych autorów oprogramowania ma to na oku, i nie ma zespołu ludzi aktywnie go wspierających. Jedyną dokumentacją, którą mogę znaleźć na temat oprogramowania, jest oryginalny raport techniczny Argonne z 1980 roku napisany przez Jorge Moré i innych autorów MINPACK. (Rozdziały 1-3 można znaleźć tutaj , a rozdział 4 można znaleźć tutaj.) Po przeszukaniu kodu źródłowego MINPACK i przejrzeniu dokumentacji (pliki PDF to zeskanowane obrazy i nie można ich przeszukiwać), nie widzę żadnych opcji, aby uwzględnić ograniczenia. Ponieważ oryginalny plakat nieliniowego problemu najmniejszych kwadratów chciał rozwiązać ograniczony problem nieliniowego najmniejszego kwadratu, MINPACK nawet nie rozwiąże tego problemu.

Jeśli spojrzysz na listę mailingową IPOPT, niektórzy użytkownicy wskazują, że wydajność pakietu w przypadku problemów z nieliniowymi najmniejszymi kwadratami (NLS) jest mieszana w porównaniu do algorytmów Levenberga-Marquardta i bardziej wyspecjalizowanych algorytmów NLS (patrz tutaj , tutaj i tutaj ). Wydajność IPOPT w stosunku do algorytmów NLS jest oczywiście zależna od problemu. Biorąc pod uwagę opinie użytkowników, IPOPT wydaje się rozsądną rekomendacją w stosunku do algorytmów NLS.

Trzeba jednak przyznać, że należy zbadać algorytmy NLS. Zgadzam się. Po prostu uważam, że należy użyć pakietu nowocześniejszego niż MINPACK, ponieważ uważam, że będzie działał lepiej, będzie bardziej użyteczny i będzie obsługiwany. Ceres wydaje się interesującym pakietem kandydackim, ale nie radzi sobie teraz z ograniczonymi problemami. TAOdziałałby na ograniczonych kwadratach problemach najmniejszych kwadratów, chociaż nie implementuje klasycznego Levenberga-Marquardta, ale zamiast tego implementuje algorytm bez pochodnych. Algorytm bez pochodnych prawdopodobnie działałby dobrze w przypadku problemów na dużą skalę, ale nie używałbym go w przypadku problemów na małą skalę. Nie mogłem znaleźć żadnych innych pakietów, które wzbudziłyby duże zaufanie do ich inżynierii oprogramowania. Na przykład GALAHAD na pierwszy rzut oka nie używa kontroli wersji ani żadnych automatycznych testów. Wydaje się, że MINPACK też tego nie robi. Jeśli masz doświadczenie z MINPACK lub zalecenia dotyczące lepszego oprogramowania, jestem cały w uszach.

Mając to na uwadze, wracając do cytatu mojego komentarza:

Każdy układ równań jest równoznaczny z problemem optymalizacji, dlatego metody optymalizacji oparte na Newtonie przypominają metody rozwiązywania układów równań nieliniowych oparte na Newtonie.

Lepszy komentarz jest prawdopodobnie efektem:

Kiedy chcemy rozwiązać układ równań z niewiadomymi , możemy sformułować to jako problem optymalizacji najmniejszych kwadratów. (Parafraza ostatniego akapitu str. 102 programowania nieliniowego , wydanie drugie, autor: Dmitri Bertsekas.) $n$ $n$ $g(x) = 0$

To stwierdzenie dotyczy nawet rozwiązywania układów równań w ograniczeniach. Nie znam żadnych algorytmów, które są uważane za „rozwiązujące równania” dla przypadku, w którym istnieją ograniczenia dotyczące zmiennych. Powszechnie znanym mi podejściem, być może zlekceważonym przez kilka semestrów kursów optymalizacyjnych i badań w laboratorium optymalizacyjnym, jest włączenie ograniczeń układu równań do sformułowania optymalizacyjnego. Jeśli spróbujesz użyć ograniczeń w schemacie podobnym do Newtona-Raphsona do rozwiązywania równań, prawdopodobnie uzyskasz prognozowany gradient lub metodę prognozowanego regionu zaufania, podobnie jak metody stosowane w ograniczonej optymalizacji.

Geoff Oxberry
źródło

Mam doświadczenie z MINPACK. Jest wystarczająco dobry jako metoda lokalna. Podoba mi się, że kryteria zatrzymania działają dobrze bez poprawiania. Wiem, że sprawa z ograniczeniami może być denerwująca, zwłaszcza że nie byłaby to znacząca zmiana w samym algorytmie. Wiem nawet o implementacjach LM, które oferują granice zmiennych i ogólne ograniczenia liniowe, ale te implementacje nie są dużo młodsze niż sam MINPACK i nie zadałem sobie trudu, aby je ocenić.

Thomas Klimpel

Kilka gnidów: mam dokładnie przeciwną perspektywę na metody bez pochodnych. Pochodne są jedynym „szybkim” sposobem na eksplorację wielowymiarowej przestrzeni projektowej. Jeśli przestrzeń projektowa jest niewielka, łatwiej jest pomijać pochodne, ale liczba iteracji z konieczności rośnie wraz ze wzrostem wymiaru. Ponadto półtonowy Newton, metody aktywnego zestawu i monotoniczny multigrid mogą być stosowane do nierówności wariacyjnych, w tym niesymetrycznych VI. Wreszcie, jeśli i zminimalizujesz , nie będziesz już mieć lokalnej miary pozwalającej zidentyfikować globalne rozwiązanie.

g (x) = 0

$g(x)=0$

‖ g (x) ‖^{2}

$\lVert g(x) \rVert^2$

Jed Brown,

@JedBrown: Powinienem zmienić język. Moim zdaniem optymalizacja bez pochodnych (DFO) jest lepsza tylko wtedy, gdy oceny funkcji są bardzo drogie. Z jakiegoś powodu najważniejszym przypadkiem, który przychodzi mi na myśl, jest moment, w którym cel polega na rozwiązaniu PDE, dlatego powiedziałem „na dużą skalę” (oczywiście dla mnie, w optymalizacji, „na dużą skalę PDE” oznacza coś innego niż dla Ciebie, który regularnie rozwiązuje PDE). Kiedy myślę o „rozwiązywaniu równań z ograniczeniami”, mam na myśli problem . (kont.)

g (x) = 0, x \in S, S \subset R^{n}, S \neq R^{n}

$g(x) = 0, x \in S, S \subset \mathbb{R}^{n}, S \neq \mathbb{R}^{n}$

Geoff Oxberry

@JedBrown: Standardowym sposobem rozwiązania tego problemu jest rozwiązanie . Mogą być inne sposoby, ale nie znam żadnych. Nie sugeruję, aby jeden odrzucić ; minima z niezerowymi wartościami funkcji celu wyraźnie nie rozwiązują układu równań, które są rozwiązywane. W przypadku niewypukłym konieczne są globalne metody optymalizacji, aby potwierdzić istnienie lub nieistnienie rozwiązań. Nie mam dużego doświadczenia z nierównościami wariacyjnymi, więc nie od razu jest dla mnie jasne, gdzie pojawiają się VI, zwłaszcza że niekoniecznie jest stożkiem.

min_{x \in S} ‖ g (x) ‖^{2}

$\min_{x \in S} \|g(x)\|^2$

g (x) = 0

$g(x) = 0$

S

$S$

Geoff Oxberry

Więc trzeba jeszcze być w stanie precyzyjnie określić, co masz na myśli przez rozwiązania, które leży na granicy . VI, często napisane jako sformułowanie komplementarności, właśnie to robią. Mam przeciwne zdanie na temat bez pochodnych, szczególnie gdy przestrzeń projektowa jest duża. Jeśli cel wiąże się z kosztownym rozwiązaniem PDE, uważam to za wymaganie, abyśmy mieli połączenie, abyśmy mogli używać gradientów do badania przestrzeni projektowej. Przystawka PDE kosztuje tylko niewielką wielokrotność rozwiązania naprzód niezależnie od wymiaru przestrzeni. To nakłada dodatkowe wymagania na gładkość modelu.

S

$S$

Jed Brown

Jeśli dany system nieliniowy jest warunkiem optymalizacji pierwszego rzędu dla problemu optymalizacji, wówczas często możemy stworzyć bardziej niezawodny algorytm, wykorzystując te informacje. Rozważmy na przykład równanie

f (x) = x^{2} - \exp (- 4 (x - 2)^{2}) [click for Wolfram Alpha]

$f(x) = x^2 - \exp\big(-4(x-2)^2 \big) \qquad \text{[click for Wolfram Alpha]}$

Fabuła pierwotnego celu

To oczywiście ma unikalne minimum i oczekujemy, że nasza metoda optymalizacji ją znajdzie, niezależnie od punktu początkowego. Ale jeśli spojrzymy tylko na warunki optymalności pierwszego rzędu, szukamy rozwiązania z [Wolfram Alpha] $x$ $\nabla f(x) = 0$

gradient

który ma unikalne rozwiązanie, ale wiele metod wyszukiwania korzeni może utknąć na lokalnym minimum.

Jeśli przeformułujemy nowy problem optymalizacji w celu zminimalizowania normy kwadratu gradientu, szukamy globalnego minimum z [Wolfram Alpha], który ma wiele lokalnych minimów. $x$ $\lVert\nabla f(x)\rVert^2$

wprowadź opis zdjęcia tutaj

Podsumowując, zaczęliśmy od problemu optymalizacji, który miał unikalne rozwiązanie, które mogliśmy zagwarantować, że metoda znajdzie. Przeformułowaliśmy jako nieliniowy problem ze znalezieniem korzenia, który miał unikalne rozwiązanie, które moglibyśmy zidentyfikować lokalnie, ale metoda znajdowania korzeni (jak Newton) mogła się zatrzymać przed osiągnięciem. Następnie przeformułowaliśmy problem znalezienia roota jako problem optymalizacji, który miał wiele lokalnych rozwiązań (nie można zastosować żadnej lokalnej miary, aby stwierdzić, że nie jesteśmy na globalnym minimum).

Zasadniczo za każdym razem, gdy przekształcamy problem z optymalizacji w wyszukiwanie korzeni lub odwrotnie, zmniejszamy dostępne metody i powiązane z nimi gwarancje zbieżności. Rzeczywista mechanika metod jest często bardzo podobna, więc możliwe jest ponowne użycie dużej ilości kodu między rozwiązaniami nieliniowymi a optymalizacją.

Jed Brown
źródło

Jed, te linki WA nie do końca prowadzą do tego, co mówisz. Nawiasy są ignorowane lub niepoprawnie przekazywane w adresie URL.

Bill Barth

Dziwne, linki działają dla mnie. Czy może zależeć od przeglądarki internetowej? Wszelkie sugestie dotyczące alternatywnego sposobu przedstawienia tego?

Jed Brown

Niepewny. Wycinanie i wklejanie ponownie sformatowanego łącza z jednej zakładki do drugiej powoduje, że wkręca WA, aby zepsuło się samo!

Bill Barth

Czy ktoś ma problem z linkami? Próbowałem w wielu przeglądarkach i działa dobrze w każdym przypadku.

Jed Brown,

To miła odpowiedź. Postanowiłem jednak zaakceptować odpowiedź Geoffa Oxberry, ponieważ próbowałem zrozumieć część „rzeczywistego świata” związaną z pytaniem. Obejmuje to, że ludzie tacy jak ja używają i polecają MINPACK, mimo że wiedzą o jego wadach, i że inni ludzie proszą o porady na temat rozwiązywania „trywialnie małych” systemów nieliniowych, ale nie udaje im się przetestować ani jednego solwera w ciągu trzech miesięcy ramy czasowe.

Thomas Klimpel,