Czy dobrze wiadomo, że niektóre problemy związane z optymalizacją są równoważne ze skokami czasowymi?

Biorąc pod uwagę pożądany stan i parametr regulujący , rozważ problem znalezienia stanu i kontroli aby zminimalizować funkcjonalny podlega ograniczeniu \ begin {equation} Ay = u. \ end {równanie} gdzie dla uproszczenia możemy pomyśleć o y, y_0, u \ in \ mathbb R ^ n i A \ in \ mathbb R ^ {n \ times n} .$y_0$$\beta \in \mathbb R$$y$$u$

$$\begin{equation} \frac{1}{2} \| y - y_0 \|^2 + \frac{\beta}{2} \| u \|^2 \end{equation}$$ $$\begin{equation} Ay = u. \end{equation}$$ $y, y_0, u \in \mathbb R^n$$A \in \mathbb R^{n \times n}$

Formowanie Lagrange'a, patrząc punktów stacjonarnych i wyeliminowania kontroli $u$ otrzymujemy warunki pierwszego rzędu

$$\begin{align*} A^T \lambda &= y_0 - y \\ Ay &= \frac{1}{\beta} \lambda \end{align*}$$ Wstępne pomnożenie przez $A$ w pierwszym równaniu i $A^T$ w drugim, możemy napisać równania normalne $$\begin{align} (I + \beta A A^T) \lambda &= \beta A y_0 \\ (I + \beta A^T A) y &= y_0 \end{align}$$ Możemy zinterpretować je jako pojedyncze kroki przybliżenia wstecznego Eulera do równań różniczkowych $$\begin{align} \frac{\partial \lambda}{\partial b} &= -A A^T \lambda + A y_0, \quad \lambda(0) = 0 \\ \frac{\partial y}{\partial b} &= -A^T A y, \quad y(0) = y_0 \end{align}$$ z pseudotimestep $\beta$ .

Moje pytanie: czy to połączenie jest dobrze znane? Czy jest to omawiane w standardowych metodach pomiaru czasu lub optymalizacji? (Wydaje mi się, że zapewnia to pewne intuicyjne połączenie między nimi.)

Pomysł wydaje się na tyle prosty, że musi być dobrze znany, ale ani przeszukanie literatury, ani rozmawianie z ludźmi nie dało mi dobrego źródła, w którym jest omawiane. Najbliżej znalazłem artykuł O. Scherzera i J. Weicherta (J. Math Imaging Vision 12 (2000) str. 43–63), który podaje związek w pierwszym zdaniu streszczenia (!), Ale nie podać wszelkie odniesienia lub zbadać połączenie na dowolnej głębokości.

Idealnie szukam referencji, która nie tylko określa połączenie, ale także bada pewne konsekwencje (na przykład można sobie wyobrazić wstępne przygotowanie problemu optymalizacji za pomocą taniego kroku Eulera do przodu).

Jak wspomniał Jed Brown, związek między spadkiem gradientu w optymalizacji nieliniowej a skokami czasowymi układów dynamicznych jest ponownie odkrywany z pewną częstotliwością (co zrozumiałe, ponieważ jest to bardzo satysfakcjonujące połączenie z umysłem matematycznym, ponieważ łączy dwa pozornie różne pola). Jednak rzadko okazuje się przydatnym połączeniem, szczególnie w opisywanym kontekście.

Odwrotnie problemu jest zainteresowany w rozwiązaniu (III-postawione) operatora równania z nie w zakresie . (Twój optymalny problem z kontrolą może być postrzegany jako jeden jego przykład z i .) Kilka strategii regularyzacji (takich jak Tichonow lub Landweber) można interpretować jako pojedynczy pseudo-czas krok pewnej klasy. Chodzi o to, aby użyć interpretacji parametru regularyzacji jako długości kroku, aby uzyskać pewne reguły wyboru (adaptacyjne, a posteriori) dla parametru - podstawowy problem w odwrotnych problemach - i być może wykonać wiele kroków pseudo-czasowych, aby podejść do prawdziwego, nieregularnego rozwiązania (podobnie jaky δ F F = A - 1 rok δ = y $F(u)=y^\delta$$y^\delta$$F$$F=A^{-1}$$y^\delta = y_0$kontynuacja numeryczna ). Czasami nazywa się to ciągłą regularyzacją i zwykle omawia się ją w kontekście metod ustalania poziomu; patrz na przykład rozdział 6.1 Kaltenbacher, Scherzer, Neubauer: Iteracyjne metody regularyzacji nieliniowych problemów źle ułożonych (de Gruyter, 2008).

Drugim kontekstem, w którym często pojawia się ta idea, jest optymalizacja nieliniowa: jeśli spojrzysz na stopień opadania gradientu dla , możesz zinterpretować to jako krok Eulera do przodu dla układu dynamicznego Jak zauważył Jed Brown, na pierwszy rzut oka widać jedynie niezbyt zaskakującą obserwację, że ta metoda jest zbieżna, pod warunkiem, że kroki pseudo-czasowe są wystarczająco małe. Interesująca część przychodzi, gdy spojrzysz na układ dynamiczny i zadajesz sobie pytanie, jakie właściwości ma rozwiązanie ciągłe tak zwanego przepływu gradientowego$\min_x f(x)$

$$x^{k+1} = x^k - \gamma_k \nabla f(x^k),$$ $$\dot x(t) = -\nabla f(x(t)),\qquad x(0) = x^0.$$ x ( t $\gamma_k$$x(t)$ma (lub powinien mieć), niezależnie od spadku gradientu, i czy nie może to prowadzić do bardziej odpowiednich metod krokowych (a tym samym do optymalizacji) niż standardowy Euler. Kilka przykładów z mojej głowy:

1. Czy istnieje naturalna przestrzeń funkcji, w której żyje przepływ gradientu? Jeśli tak, krok gradientu powinien zostać pobrany z tej samej przestrzeni (tzn. Dyskretyzacja powinna być zgodna). Prowadzi to np. Do obliczenia reprezentacji gradientu Riesza w odniesieniu do różnych iloczynów wewnętrznych (czasami nazywanych gradientami Sobolewa ) i, w praktyce, do wstępnie przygotowanych iteracji, które zbiegają się znacznie szybciej.

2. Może powinno należeć do przestrzeni wektorowej, ale do rozmaitości (np. Symetryczne dodatnie określone macierze), lub przepływ gradientu powinien zachować pewną normę . W takim przypadku można spróbować zastosować schematy odmierzania czasu zachowujące strukturę (np. Polegające na wycofaniu w stosunku do odpowiedniej grupy Liego lub integratora geometrycznego).$x$$x$

3. Jeżeli nie jest różniczkowalny, ale wypukły, krok Eulera do przodu odpowiada metodzie opadania podgradienta, która może być bardzo wolna z powodu ograniczeń wielkości kroku. Z drugiej strony, domyślny krok Eulera odpowiada metodzie punktu bliższego , do której nie mają zastosowania takie ograniczenia (i która stała się bardzo popularna np. W przetwarzaniu obrazu).$f$

4. W podobny sposób metody te można znacznie przyspieszyć etapami ekstrapolacji. Jednym ze sposobów ich motywowania jest obserwowanie, że standardowe metody pierwszego rzędu cierpią z powodu konieczności wykonywania wielu małych kroków w pobliżu minimizatorów, ponieważ kierunki gradientu „oscylują” (pomyśl o standardowej ilustracji, dlaczego gradienty sprzężone przewyższają strome zejście). Aby temu zaradzić, można „tłumić” iterację, nie rozwiązując układu dynamicznego pierwszego rzędu, ale układu drugiego rzędu : dla odpowiednio wybranego . Przy odpowiedniej dyskretyzacji prowadzi to do iteracji (znanej jako metoda ciężkiej kuli Polyaka ) formy

   $$a_1 \ddot x(t) + a_2 \dot x(t) = -\nabla f(x(t))$$ $a_1,a_2$ $$x^{k+1} = x^k - \gamma_k \nabla f(x^k) + \alpha_k (x^k - x^{k-1})$$ (z zależności od ). Podobne pomysły istnieją dla metod punktów bliższych, patrz np. Artykuł http://arxiv.org/pdf/1403.3522.pdf autorstwa Dirka Lorenza i Thomasa Pocka.a 1 , a $\gamma_k,\alpha_k$$a_1,a_2$

---

(Powinienem dodać, że o ile wiem, w większości tych przypadków interpretacja jako system dynamiczny nie była absolutnie niezbędna do wyprowadzenia algorytmu algorytmu; nie można też zaprzeczyć, że takie pomysły jak pochodne ukryte lub jawne lub pochodne Lie są w rzeczywistości bardziej fundamentalne niż systemy dynamiczne lub metody zejścia gradientowego. Mimo to, nigdy nie boli mieć inny punkt widzenia, z którego można spojrzeć na problem.)

---

EDYCJA: Właśnie natknąłem się na doskonały przykład z drugiego kontekstu, w którym interpretacja ODE służy do wywnioskowania właściwości metody ekstradientowej Nesterova i zasugerowania ulepszeń: http://arxiv.org/pdf/1503.01243.pdf (zauważ, że jest to również przykład punktu Jeda Browna, w którym autorzy zasadniczo odkryli punkt 4 powyżej, najwyraźniej nie znając algorytmu Polyaka.)

EDYCJA 2: Jako wskazówkę, jak daleko możesz to zrobić, patrz strona 5 http://arxiv.org/pdf/1509.03616v1.pdf .

Chociaż nie widziałem dokładnego sformułowania, które tutaj zapisałeś, wciąż widzę przemówienia, w których ludzie „odkrywają” związek z integracją jakiegoś przejściowego systemu i przystępują do zapisywania algorytmu, który jest algebraicznie równoważny z jedną formą lub kolejna z istniejących gradientów lub metoda podobna do Newtona i nie przytacza nikogo innego. Myślę, że nie jest to zbyt przydatne, ponieważ wniosek jest w zasadzie taki, że „dopóki wykonasz wystarczająco małe kroki, metoda ostatecznie zbiega się do lokalnego minimum”. W 2014 roku przypada 45. rocznica pracy Philipa Wolfe'a pokazującej, jak to zrobić w sposób zgodny z zasadami. Istnieje również dobra teoria do uzyskiwania zbieżności q-kwadratowej lub q-superlinearnej z kontynuacji pseudotransjentów i powiązanych metod, takich jak Levenberg-Marquardt.

Jeśli chcesz instancji tego ponownego odkrycia przy użyciu formuły podobnej do Newtona do rozwiązywania równań algebraicznych (tj. Klasycznej kontynuacji pseudotransjentów) od matematyka z ponad 600 artykułami (więc może udowodni to, co uważasz za interesujące), spójrz na „ Metoda systemów dynamicznych ”autorstwa AG Ramm [1].

Jeśli intuicja uzyskana dzięki rozważeniu systemu przejściowego doprowadziłaby do zastosowania praktycznych algorytmów, które byłyby albo szybsze, albo bardziej niezawodne, myślę, że zobaczylibyśmy cytowane artykuły na ten temat. Myślę, że nie jest tajemnicą, że Nocedal i Wright ma ponad 13000 cytatów, podczas gdy książka Ramm ma około 80 (głównie autocytowania).

[1] Radzę wam nie informować prof. Ramma, że ​​jego DSM jest algebraicznie równoważny z czymś, co znajdowało się w niezliczonych pakietach inżynieryjnych od dziesięcioleci, albo możesz wydostać się z pokoju. #gradstudentmemories

Jeśli metody ODE mogą przyczynić się do optymalizacji, czy istnieje naprawdę prosty przykładowy problem, który można to pokazać?
Słomiany człowiek: czy istnieje solver ODE, który wykonuje rozsądną pracę na lub co sugeruje Christian Clason do powiedzieć funkcja Rosenbrocka, 2D i 10D? Jeśli to głupie, to czy ktoś ma lepszego człowieka ze słomy? (Uwaga: „rozsądny”, a nie „konkurencyjny z najnowocześniejszymi optymalizatorami”. Wyobrażam sobie, że potrzebna jest malejąca wielkość kroku / tolerancja, a może sztywny solver.)
$\qquad \dot{ x } = - \nabla f( x )$
$\quad \ddot{ x } = \beta \dot{ x } - \alpha \nabla f( x ) \ \ $
$f$

W praktyce „zbyt duże” kroki są znacznie bardziej problematyczne niż „zbyt małe” - oscylacje są chaotyczne.
Naiwnie pomyślałbym, że teoria kontroli może pomóc. Przepisy numeryczne p. 915 opisuje
adaptacyjną kontrolę kroków PI dla ODE, ale nie wiem, czy jest to stosowane w praktyce.