Dlaczego SQP jest lepszy od Augmented Lagrangian dla programowania nieliniowego?

W raporcie technicznym na temat Galahada [1] autorzy stwierdzają, w kontekście ogólnych problemów programowania nieliniowego,

Naszym zdaniem nigdy tak naprawdę nie było wątpliwości, że metody SQP [sekwencyjnego programowania kwadratowego] odniosą większy sukces [niż metody Augmented Lagrangian] w dłuższej perspektywie ...

Jaka może być podstawa tego przekonania? Tj. Czy są jakieś wyniki teoretyczne, które sugerują, że metody SQP powinny być szybsze / bardziej niezawodne niż metody Augmented Lagrangian?

[1] Galahad, biblioteka bezpiecznych dla wątków pakietów Fortran 90 do nieliniowej optymalizacji na dużą skalę, autorstwa Goulda, Orbana i Tointa

nonlinear-programming

— cjordan1
źródło

Metody SQP wymagają, aby cel był dwukrotnie różniczkowalny (por. Https://en.m.wikipedia.org/wiki/Sequential_quadratic_programming ), podczas gdy Augmented Lagrangians działają nawet wtedy, gdy cel jest nieróżniczkowy (stąd ich niedawne odrodzenie w społeczności przetwarzania obrazu por. Ftp: //arachne.math.ucla.edu/pub/camreport/cam09-05.pdf )

Nie wiem o oprogramowaniu Galahad, ale jeśli ma rozwiązać różne problemy optymalizacyjne, to prawdopodobnie zrobi to znacznie lepiej, stosując metodę pozwalającą na różnicowanie funkcji celu.

— dranxo
źródło

Nie jest prawdą, że SQP wymaga dwukrotnie rozróżnialnych funkcji celu. Możesz po prostu uzyskać metodę, która ma mniejszy stopień zbieżności, jeśli funkcja celu ma mniejszą różniczkowalność, ale jest dokładnie taka sama jak w przypadku rozszerzonych metod Lagrangian.

— Wolfgang Bangerth

Jeśli chodzi o zewnętrzne iteracje, SQP powinien wygrać, ponieważ zawiera informacje o drugiej pochodnej, podczas gdy ulepszone metody lagranżańskie, takie jak ADMM, nie.

Należy jednak pamiętać, że każda iteracja tych metod wymaga rozwiązania systemu liniowego, więc aby dokonać rzetelnego porównania, należy wziąć pod uwagę, jak łatwe jest rozwiązanie tych systemów.

W przypadku rozszerzonych metod Lagrange'a (naprzemiennych) każda iteracja, którą rozwiązujesz,

(A^{T} A + ρ I) x = b,

$(A^TA + \rho I)x = b,$ gdzie

A

$A$ jest operatorem forward wprost z funkcji celu, która jest znana i zwykle łatwiejsza w obsłudze lub warunku wstępnym, oraz

ρ

$\rho$ to parametr kary. (np. masz problem

min_{x} | | A x - b | |^{2}

$\min_x ||Ax-b||^2$ z zastrzeżeniem pewnych uregulowań i ograniczeń).

W przypadku metod SQP rozwiązujesz coś w rodzaju gdzie jest Hessem (lub jego przybliżeniem), który jest zwykle dostępny tylko domyślnie pod względem działania na wektory, a jest gradientem. Hesjan zawiera nie tylko , ale także kombinację innych macierzy i odwrotności macierzy pochodzących z linearyzacji ograniczeń i regularyzacji.

H x = g,

$Hx = g,$

H

$H$

g

$g$

A

$A$

Wstępne przygotowanie Hesjan jest dość trudnym przedsięwzięciem i jest znacznie mniej zbadane niż wstępne przygotowanie problemów. Standardową metodą jest przybliżenie odwrotności Hesji za pomocą L-BFGS, ale ma to ograniczoną skuteczność, gdy odwrotność Hesji ma wysoką rangę. Inną popularną metodą jest przybliżenie Hesji jako sumy macierzy niskiej rangi plus macierzy łatwej do odwrócenia, ale ma to również ograniczoną skuteczność w przypadku trudnych problemów. Inne popularne techniki szacowania Hesji oparte są na rzadkich przybliżeniach, ale problemy z ciągłością często mają Hesów, którzy mają słabe przybliżenia.

— Nick Alger
źródło

+1, chociaż chciałbym przestrzec przed wyciągami zbiorczymi (przez co nie mam na myśli konkretnie tej odpowiedzi). Na przykład w optymalizacji ograniczonej przez PDE, zastosowanie często wiąże się z rozwiązaniem nieliniowego PDE, podczas gdy można zastosować, rozwiązując dwa liniowe PDE - które mogą być znacznie tańsze (i łatwiejsze do spełnienia), jeśli oryginalny PDE jest nieprzyjemny.

A

$A$

H

$H$

— Christian Clason

Zatem można zastosować, rozwiązując dwa PDE, ale aby zastosować , musisz rozwiązać 2 PDE na iterację kryolv w swoim solverie . Z drugiej strony jest operatorem forward, więc zwykle nie wymaga żadnych rozwiązań PDE. Zazwyczaj tak naprawdę zna się matrycę , np. 5-punktową matrycę różnic skończonych na siatce. Przygotowujące do może być wykorzystane do budowy przygotowujące do , ale trudniej jest je wykorzystać do wstępny warunek .

H

$H$

H^{- 1}

$H^{-1}$

A

$A$

A

$A$

A

$A$

A^{T} A + ρ I

$A^TA + \rho I$

H

$H$

— Nick Alger

Jeśli jest liniowym operatorem do przodu (czego nie ma w przypadku optymalizacji nieliniowej ograniczonej przez PDE), to oczywiście masz rację. W przeciwnym razie zastosowanie wymaga rozwiązania liniowego PDE dla iteracji Newtona (lub iteracji ustalonego punktu), a następnie dla (która jest zawsze liniowa). Która z tych dwóch metod wymaga mniej całkowitej pracy (powiedzmy, liczby liniowych rozwiązań PDE) zależy w dużym stopniu od konkretnego problemu. Różne narzędzia do różnych zadań, to wszystko co mówię.

A

$A$

A

$A$

A^{T}

$A^T$

— Christian Clason

Zgadzam się na temat różnych narzędzi do różnych zadań. Gaussa-Newtona Heskiego dla ograniczonego problemu optymalizacji PDE Mam na myśli - takie, że - to , a pełny Hesjan to plus inne terminy. Więc tutaj zawiera dwa odwrotności, a zawiera dwa odwrotności w odwrotności.

min_{q, u} \frac{1}{2} | | C u - y | |^{2} + \frac{α}{2} | | R q | |^{2}

$\min_{q,u} \frac{1}{2}||Cu - y||^2 + \frac{\alpha}{2}||Rq||^2$

A u = q

$Au=q$

H = A^{- T} C^{T} C A^{- 1} + α R^{T} R

$H = A^{-T}C^TCA^{-1} + \alpha R^T R$

H

$H$

H^{- 1}

$H^{-1}$

— Nick Alger

I miały ograniczenie uwadze (np odwzorowuje do roztworu o , który pojawia się w identyfikacji lub optymalizacji parametrów topologii).

S (q) = u

$S(q) = u$

S

$S$

q

$q$

u

$u$

- \nabla \cdot (q \nabla u) = f

$-\nabla\cdot(q\nabla u) = f$

— Christian Clason