Dlaczego algorytmy optymalizacyjne są zdefiniowane w kontekście innych problemów optymalizacyjnych?

Prowadzę badania nad technikami optymalizacji w uczeniu maszynowym, ale jestem zaskoczony, że duża liczba algorytmów optymalizacji jest definiowana pod kątem innych problemów z optymalizacją. Poniżej zilustruję kilka przykładów.

Na przykład https://arxiv.org/pdf/1511.05133v1.pdf

Wszystko wygląda ładnie i dobrze, ale jest to w aktualizacji .... więc jaki algorytm rozwiązuje dla ? Nie wiemy i nie mówi. Tak więc magicznie mamy rozwiązać kolejny problem optymalizacji, którym jest znalezienie wektora minimalizującego, tak aby wewnętrzny produkt był na minimum - jak to zrobić?$\text{argmin}_x$$z^{k+1}$$\text{argmin}$

Weź inny przykład: https://arxiv.org/pdf/1609.05713v1.pdf

Wszystko wygląda ładnie i dobrze, dopóki nie trafisz tego bliższego operatora w środku algorytmu, a jaka jest definicja tego operatora?

Bum:

A teraz pomódl się, powiedz, jak rozwiązać ten w bliższym operatorze? Nie mówi W każdym razie problem optymalizacji wygląda na trudny (NP HARD) w zależności od .$\text{argmin}_x$$f$

Czy ktoś może mi oświecić co do:

1. Dlaczego tak wiele algorytmów optymalizacji jest definiowanych w kategoriach innych problemów optymalizacyjnych?

(Czy nie byłby to jakiś problem z kurczakiem i jajkiem: aby rozwiązać problem 1, musisz rozwiązać problem 2, stosując metodę rozwiązania problemu 3, która polega na rozwiązaniu problemu ...)

2. Jak rozwiązać te problemy optymalizacji, które są wbudowane w te algorytmy? Na przykład , jak znaleźć minimalizator po prawej stronie?$x^{k+1} = \text{argmin}_x \text{really complicated loss function}$

3. Ostatecznie zastanawiam się, w jaki sposób te algorytmy mogą być implementowane numerycznie. Rozumiem, że dodawanie i mnożenie wektorów to proste operacje w pythonie, ale co z , czy jest jakaś funkcja (skrypt), która magicznie daje ci minimalizator funkcji?$\text{argmin}_x$

(Bounty: czy ktokolwiek może odwołać się do artykułu, w którym autorzy wyjaśnili algorytm podproblemu wbudowany w algorytm optymalizacji wysokiego poziomu?)

Patrzysz na schematy blokowe algorytmu najwyższego poziomu. Niektóre z poszczególnych kroków na schemacie blokowym mogą wymagać własnych szczegółowych schematów blokowych. Jednak w publikowanych artykułach, które kładą nacisk na zwięzłość, wiele szczegółów jest często pomijanych. Szczegóły dotyczące standardowych problemów z optymalizacją wewnętrzną, które są uważane za „stary kapelusz”, mogą w ogóle nie zostać dostarczone.

Ogólna idea jest taka, że ​​algorytmy optymalizacji mogą wymagać rozwiązania szeregu ogólnie łatwiejszych problemów optymalizacji. Często zdarza się, że 3 lub nawet 4 poziomy algorytmów optymalizacji w algorytmie najwyższego poziomu, chociaż niektóre z nich są wewnętrznymi standardowymi optymalizatorami.

Nawet podjęcie decyzji o zakończeniu algorytmu (na jednym z poziomów hierarchicznych) może wymagać rozwiązania problemu optymalizacji bocznej. Na przykład problem nieliniowo ograniczonego liniowego najmniejszego kwadratu może zostać rozwiązany w celu ustalenia mnożników Lagrange'a użytych do oceny wyniku optymalizacyjnego KKT użytego do podjęcia decyzji, kiedy zadeklarować optymalność.

Jeśli problem optymalizacji jest stochastyczny lub dynamiczny, mogą istnieć dodatkowe hierarchiczne poziomy optymalizacji.

Oto przykład. Sekwencyjne programowanie kwadratowe (SQP). Początkowy problem optymalizacji rozwiązuje się iteracyjnie rozwiązując warunki optymalne Karusha-Kuhna-Tuckera, zaczynając od punktu początkowego z celem, którym jest kwadratowe przybliżenie Lagrangiana problemu, i linearyzacja ograniczeń. Powstały Program Kwadratowy (QP) został rozwiązany. Rozwiązanie QP, które zostało rozwiązane, ma ograniczenia regionu zaufania lub przeszukiwanie linii jest przeprowadzane z bieżącego iteratu do rozwiązania QP, które samo w sobie jest problemem optymalizacji, w celu znalezienia następnego iteratu. Jeśli stosowana jest metoda Quasi-Newtona, należy rozwiązać problem optymalizacji, aby określić aktualizację Quasi-Newtona dla Hesjan z Lagrangian - zwykle jest to optymalizacja formy zamkniętej przy użyciu formuł zamkniętych, takich jak BFGS lub SR1, ale może to być optymalizacja numeryczna. Następnie nowy QP zostaje rozwiązany itp. Jeśli QP jest kiedykolwiek nieosiągalny, w tym na początek, problem optymalizacji zostaje rozwiązany, aby znaleźć wykonalny punkt. Tymczasem wewnątrz solvera QP może być wywołany jeden lub dwa poziomy wewnętrznych problemów optymalizacyjnych. Na końcu każdej iteracji można rozwiązać nieujemny problem liniowych najmniejszych kwadratów w celu ustalenia wyniku optymalizacyjnego. Itp.

Jeśli jest to problem z mieszaną liczbą całkowitą, wówczas ten cały shebang można wykonać w każdym węźle rozgałęzienia, jako część algorytmu wyższego poziomu. Podobnie w przypadku globalnego optymalizatora - lokalny problem optymalizacyjny jest wykorzystywany do utworzenia górnej granicy globalnie optymalnego rozwiązania, następnie rozluźnia się niektóre ograniczenia w celu wygenerowania dolnego problemu optymalizacyjnego. Tysiące lub nawet miliony „łatwych” problemów optymalizacyjnych z gałęzi i powiązań można rozwiązać, aby rozwiązać jeden problem optymalizacji mieszanej liczby całkowitej lub globalnej.

To powinno zacząć dać ci pomysł.

Edycja : W odpowiedzi na pytanie dotyczące kurczaka i jaj, które zostało dodane do pytania po mojej odpowiedzi: Jeśli występuje problem z kurczakiem i jajkiem, to nie jest to dobrze zdefiniowany praktyczny algorytm. W podanych przykładach nie ma kurczaka i jajka. Kroki algorytmu wyższego poziomu wywołują solwery optymalizacyjne, które są albo zdefiniowane, albo już istnieją. SQP iteracyjnie wywołuje solver QP w celu rozwiązania podproblemów, ale solver QP rozwiązuje łatwiejszy problem, QP, niż problem pierwotny. Jeśli istnieje jeszcze wyższy poziom globalnego algorytmu optymalizacji, może on wywołać solver SQP w celu rozwiązania lokalnych nieliniowych podproblemów optymalizacji, a solver SQP z kolei wywołuje solver QP w celu rozwiązania podproblemów QP. Bez chiicken i jajka.

Uwaga: Możliwości optymalizacji są „wszędzie”. Eksperci od optymalizacji, tacy jak ci, którzy opracowują algorytmy optymalizacji, częściej widzą te możliwości optymalizacji i postrzegają je jako takie, niż przeciętny Joe lub Jane. Ponieważ są skłonni algorytmicznie, całkiem naturalnie dostrzegają możliwości budowania algorytmów optymalizacji z algorytmów optymalizacji niższego poziomu. Formułowanie i rozwiązywanie problemów optymalizacyjnych służą jako elementy składowe innych (wyższego poziomu) algorytmów optymalizacyjnych.

Edycja 2 : W odpowiedzi na prośbę o nagrodę, która została właśnie dodana przez PO. Artykuł opisujący nieliniowy optymalizator SQP SNOPT https://web.stanford.edu/group/SOL/reports/snopt.pdf konkretnie wspomina o rozwiązaniu SQOPT QP, które jest oddzielnie dokumentowane, jako stosowane do rozwiązywania podproblemów QP w SNOPT.

Podoba mi się odpowiedź Marka, ale pomyślałem, że wspomnę o „Symulowanym wyżarzaniu”, które w zasadzie może działać na dowolnym algorytmie optymalizacyjnym. Na wysokim poziomie działa to tak:

Ma parametr „temperatury”, który zaczyna się nagrzewać. Podczas gdy jest gorący, często odsuwa się i (i dalej) od miejsca, w którym wskazuje podrzędny algorytm optymalizacji. Gdy się ochładza, ściślej podąża za radą podrzędnego algorytmu, a przy zeru podąża za nim do dowolnego lokalnego optimum, na którym następnie skończył.

Intuicja polega na tym, że na początku będzie szeroko przeszukiwał przestrzeń, szukając „lepszych miejsc” w poszukiwaniu optymów.

Wiemy, że nie ma rzeczywistego ogólnego rozwiązania lokalnego / globalnego problemu optymalnego. Każdy algorytm będzie miał swoje martwe punkty, ale hybrydy takie jak ten wydają się dawać lepsze wyniki w wielu przypadkach.

Myślę, że moje odniesienie zaspokoić swoje pragnienie jest tutaj . Przejdź do sekcji 4 - Optymalizacja we współczesnym obliczeniu bayesowskim.

TL; DR - omawiają metody proksymalne. Jedną z zalet takich metod jest podział - możesz znaleźć rozwiązanie, optymalizując łatwiejsze podproblemy. Wiele razy (a przynajmniej czasami) w literaturze można znaleźć specjalistyczny algorytm do oceny konkretnej funkcji proksymalnej. W swoim przykładzie odwracają obraz. Jednym z kroków jest bardzo udany i wysoko cytowany algorytm Chambolle.

Jest to dość powszechne w wielu dokumentach optymalizacyjnych i ma to związek z ogólnością. Autorzy zwykle piszą algorytmy w ten sposób, aby pokazać, że technicznie działają dla dowolnej funkcji f. Jednak w praktyce są one użyteczne tylko w przypadku bardzo specyficznych funkcji, w których te pod-problemy można skutecznie rozwiązać.

Na przykład, a teraz mówię tylko o drugim algorytmie, ilekroć zobaczysz operator proksymalny (który, jak zauważyłeś, to kolejny problem optymalizacji, który może być naprawdę bardzo trudny do rozwiązania), zwykle zakłada, że ​​ma on rozwiązanie w postaci zamkniętej aby algorytm był wydajny. Dotyczy to wielu funkcji uczenia maszynowego, takich jak norma L1, normy grupowe i tak dalej. W takich przypadkach zastąpiłbyś podproblemy dla jawnej formuły operatora proksymalnego i nie jest potrzebny algorytm do rozwiązania tego problemu.

Jeśli chodzi o to, dlaczego są one pisane w ten sposób, wystarczy zauważyć, że jeśli miałbyś wymyślić inną funkcję i chciałbyś zastosować ten algorytm, najpierw sprawdziłbyś, czy proksymalne rozwiązanie ma postać zamkniętą lub czy można go obliczyć wydajnie. W takim przypadku wystarczy podłączyć formułę do algorytmu i możesz zacząć. Jak wspomniano wcześniej, gwarantuje to, że algorytm jest na tyle ogólny, że można go zastosować do przyszłych funkcji, które mogą pojawić się po pierwszej publikacji algorytmu, wraz z ich bliższymi wyrażeniami wydajnych algorytmów do ich obliczenia.

Na koniec, jako przykład, weź klasyczny papier oryginalny algorytm FISTA. Wyprowadzają algorytm dla dwóch bardzo specyficznych funkcji, straty kwadratowej i normy L1. Zauważają jednak, że nie można zastosować żadnych funkcji, o ile spełniają pewne warunki wstępne, jedną z nich jest to, że proksymalne miejsce w regularyzacji może być obliczone wydajnie. Nie jest to wymóg teoretyczny, ale praktyczny.

Ta komplementaryzacja nie tylko sprawia, że ​​algorytm jest ogólny, ale także łatwiejsza do analizy: tak długo, jak istnieją algorytmy dla podproblemów, które mają te właściwości, proponowany algorytm będzie miał ten współczynnik konwergencji lub cokolwiek innego.