Zrozumienie kosztu metody łączenia dla optymalizacji ograniczonej przez pde

Próbuję zrozumieć, jak działa metoda optymalizacji oparta na sprzężeniu dla optymalizacji ograniczonej przez PDE. W szczególności staram się zrozumieć, dlaczego metoda łączenia jest bardziej wydajna w przypadku problemów, w których liczba zmiennych projektowych jest duża, ale „liczba równań jest niewielka”.

Co rozumiem:

Rozważ następujący problem optymalizacji ograniczonej przez PDE:

min_{β} I (β, u (β)) s . t . R (u (β)) = 0

$\min_\beta \text{ } I(\beta,u(\beta))\\ s.t. R(u(\beta))=0$

gdzie jest (wystarczająco ciągłą) funkcją celu wektorowych zmiennych projektowych i wektora zmiennych polowych nieznanych które zależą od zmiennych projektowych, a jest resztową postacią PDE. $I$ $\beta$ $u(\beta)$ $R(u)$

Oczywiście możemy pierwsze odmiany I i R jako

δ I = \frac{\partial I}{\partial β} δ β + \frac{\partial I}{\partial u} δ u

$\delta I = \frac{\partial I}{\partial \beta}\delta\beta + \frac{\partial I}{\partial u}\delta u$

δ R = \frac{\partial R}{\partial β} δ β + \frac{\partial R}{\partial u} δ u = 0

$\delta R = \frac{\partial R}{\partial \beta}\delta\beta + \frac{\partial R}{\partial u}\delta u = 0$

Wprowadzając wektor mnożników Lagrange'a , zmienność funkcji celu można zapisać jako $\lambda$

δ I = \frac{\partial I}{\partial β} δ β + \frac{\partial I}{\partial u} δ u + λ^{T} [\frac{\partial R}{\partial β} δ β + \frac{\partial R}{\partial u} δ u]

$\delta I = \frac{\partial I}{\partial \beta}\delta\beta + \frac{\partial I}{\partial u}\delta u + \lambda^T\left[ \frac{\partial R}{\partial \beta}\delta\beta + \frac{\partial R}{\partial u}\delta u\right]$

Zmieniając warunki, możemy napisać:

δ I = [\frac{\partial I}{\partial β} + λ^{T} \frac{\partial R}{\partial β}] δ β + [\frac{\partial I}{\partial u} + λ^{T} \frac{\partial R}{\partial u}] δ u

$\delta I = \left[\frac{\partial I}{\partial \beta} + \lambda^T\frac{\partial R}{\partial \beta}\right]\delta\beta + \left[\frac{\partial I}{\partial u} + \lambda^T\frac{\partial R}{\partial u}\right]\delta u$

Zatem jeśli jesteśmy w stanie rozwiązać dla takie, że $\lambda$

\frac{\partial I}{\partial u} + λ^{T} \frac{\partial R}{\partial u} = 0 (adjoint equation)

$\frac{\partial I}{\partial u} + \lambda^T\frac{\partial R}{\partial u}=0 \text{ (adjoint equation)}$

Następnie gradient oceniano tylko pod względem zmiennych projektowych . $\delta I= \left[\frac{\partial I}{\partial \beta} + \lambda^T\frac{\partial R}{\partial \beta}\right]\delta \beta$ $\beta$

Dlatego algorytm optymalizacji oparty na sprzężeniu zapętlałby następujące kroki:

Biorąc pod uwagę aktualne zmienne projektowe $\beta$
Rozwiąż dla zmiennych pola (z PDE) $u$
Rozwiąż mnożniki Lagrange'a (z równania sąsiadującego) $\lambda$
Oblicz gradienty $\frac{\partial I}{\partial \beta}$
Zaktualizuj zmienne projektowe $\beta$

Moje pytanie

W jaki sposób ta przylegająca „sztuczka” poprawia koszt optymalizacji na iterację w przypadku, gdy liczba zmiennych projektowych jest duża? Słyszałem, że koszt oceny gradientu dla metody łączenia jest „niezależny” od liczby zmiennych projektowych. Ale jak dokładnie to prawda?

Jestem pewien, że coś bardzo oczywistego przeoczyłem.

optimization pde

— Paweł
źródło

Nawiasem mówiąc, mnożnik Lagrange'a jest zwykle dodawany do funkcji celu, a nie odmiany; zatem . Ustawienie pochodna względem jest na zero, otrzymuje się równanie sprzężone, i umieszczanie w tym (i roztwór równania stanu ), do pochodnej względem otrzymuje się gradient. Jeśli zaczniesz od słabego sformułowania PDE, wszystko stanie się jeszcze prostsze: wystarczy wstawić mnożnik Lagrange'a zamiast funkcji testowej. Nigdzie nie ma potrzeby silnej formy ani częściowej integracji.

min_{u, β} max_{λ} I (u, β) + λ^{T} R (u, β)

$\min_{u,\beta}\max_\lambda I(u,\beta) + \lambda^T R(u,\beta)$

u

$u$

u

$u$

R (u, β) = 0

$R(u,\beta)=0$

β

$\beta$

— Christian Clason

Najdroższą częścią każdej symulacji jest faza rozwiązywania. Używając punktu sąsiedniego otrzymujesz gradient w dwóch rozwiązaniach, znacznie tańszy w porównaniu do różnic skończonych, w których potrzebujesz co najmniej n + 1 rozwiązań, gdzie n jest liczbą wolnych parametrów w twoim modelu.

— stali

Odpowiedzi:

W jaki sposób ta przylegająca „sztuczka” poprawia koszt optymalizacji na iterację w przypadku, gdy liczba zmiennych projektowych jest duża?

Myślę o koszcie z perspektywy algebry liniowej. (Zobacz te notatki Stephena G. Johnsona , które uważam za bardziej intuicyjne niż mnożnik Lagrange'a). Podejście przyszłościowe polega na bezpośrednim rozwiązaniu problemu wrażliwości:

\begin{aligned} \frac{\partial u}{\partial β} = - {(\frac{\partial R}{\partial u})}^{- 1} \frac{\partial R}{\partial β} \end{aligned}

$\begin{align} \frac{\partial{u}}{\partial{\beta}} = -\left(\frac{\partial{R}}{\partial{u}}\right)^{-1}\frac{\partial{R}}{\partial{\beta}} \end{align}$

który polega na rozwiązaniu układu liniowego dla każdego parametru w wektorze , a następnie ocenie $\beta$

\begin{aligned} \frac{d I}{d β} = \frac{\partial I}{\partial β} + \frac{\partial I}{\partial u} \frac{\partial u}{\partial β}, \end{aligned}

$\begin{align} \frac{\mathrm{d}I}{\mathrm{d}\beta} = \frac{\partial{I}}{\partial{\beta}} + \frac{\partial{I}}{\partial{u}}\frac{\partial{u}}{\partial{\beta}}, \end{align}$

gdzie oznacza całkowitą pochodną, a oznacza pochodną częściową. $\mathrm{d}$ $\partial$

Podejście sąsiednie zauważa, że

\begin{aligned} \frac{d I}{d β} = \frac{\partial I}{\partial β} - \frac{\partial I}{\partial u} {(\frac{\partial R}{\partial u})}^{- 1} \frac{\partial R}{\partial β}, \end{aligned}

$\begin{align} \frac{\mathrm{d}I}{\mathrm{d}\beta} = \frac{\partial{I}}{\partial{\beta}} - \frac{\partial{I}}{\partial{u}}\left(\frac{\partial{R}}{\partial{u}}\right)^{-1}\frac{\partial{R}}{\partial{\beta}}, \end{align}$

więc zmienna przylegająca (mnożnik Lagrange'a) może być zdefiniowana przez $\lambda$

\begin{aligned} - \frac{\partial I}{\partial u} {(\frac{\partial R}{\partial u})}^{- 1} = λ^{T}, \end{aligned}

$\begin{align} -\frac{\partial{I}}{\partial{u}}\left(\frac{\partial{R}}{\partial{u}}\right)^{-1} = \lambda^{T}, \end{align}$

co odpowiada równaniu sąsiadującemu

\begin{aligned} \frac{\partial I}{\partial u} + λ^{T} \frac{\partial R}{\partial u} = 0. \end{aligned}

$\begin{align} \frac{\partial{I}}{\partial{u}} + \lambda^{T}\frac{\partial{R}}{\partial{u}} = 0. \end{align}$

To przegrupowanie terminów wymaga tylko jednego liniowego rozwiązania zamiast liniowego rozwiązania dla każdego parametru, co sprawia, że ocena przyłączy jest tania w przypadku wielu parametrów.

Słyszałem, że koszt oceny gradientu dla metody łączenia jest „niezależny” od liczby zmiennych projektowych. Ale jak dokładnie to prawda?

Nie jest całkowicie niezależny; przypuszczalnie koszt oceny i wzrośnie wraz z liczbą parametrów. Rozwiązania liniowe będą jednak nadal tego samego rozmiaru, o ile rozmiar się nie zmieni. Zakłada się, że rozwiązania są znacznie droższe niż oceny funkcji. $(\partial{I}/\partial{\beta})$ $(\partial{R}/\partial{\beta})$ $u$

— Geoff Oxberry
źródło

W skrócie, korzyść wynika z faktu, że aby obliczyć pochodne zredukowanego celu , tak naprawdę nie musisz znać pochodnej w odniesieniu do jako osobny obiekt, ale tylko ta jego część, która prowadzi do zmian w . $I(\beta,u(\beta))$ $u(\beta)$ $\beta$ $I(\beta,u(\beta))$

Przejdźmy do notacji Czuję się bardziej komfortowo z: ( jest zmienna projektowa, jest zmienną stanu, a jest celem). Powiedzmy, że jest wystarczająco ładne, aby zastosować twierdzenie o funkcji niejawnej, więc równanie ma unikalne rozwiązanie które jest stale różnicowalne względem , i pochodna jest podane przez rozwiązanie ( i są pochodnymi częściowymi) .

min_{y, u} J (y, u) subject to e (y, u) = 0

$\min_{y,u} J(y,u) \quad\text{subject to}\quad e(y,u)=0$

u

$u$

y

$y$

J

$J$

e (y, u)

$e(y,u)$

e (y, u) = 0

$e(y,u)=0$

y (u)

$y(u)$

u

$u$

y^{'} (u)

$y'(u)$

\begin{matrix} (1) & e_{y} (y (u), u) y^{'} (u) + e_{u} (y (u), u) = 0 \end{matrix}

$e_y(y(u),u)y'(u) + e_u(y(u),u) = 0\tag{1}$

e_{y}

$e_y$

e_{u}

$e_u$

Oznacza to, że możesz zdefiniować zredukowany cel , który również jest różniczkowalny (jeśli jest). Jednym ze sposobów scharakteryzowania gradientu są pochodne kierunkowe (np. Obliczenie wszystkich pochodnych cząstkowych w odniesieniu do podstawy przestrzeni projektowej). W tym przypadku pochodną kierunkową w kierunku podaje reguła łańcucha jako Jeśli jest fajny, jedyną trudną rzeczą do obliczenia jest dla danego . Można tego dokonać mnożąc przez $j(u):=J(y(u),u)$ $J(y,u)$ $\nabla j(u)$ $h$

\begin{matrix} (2) & j^{'} (u; h) = ⟨ J_{y} (y (u), u), y^{'} (u) h ⟩ + ⟨ J_{u} (y (u), u), h ⟩ . \end{matrix}

$j'(u;h) = \langle J_y(y(u),u),y'(u)h \rangle + \langle J_u(y(u),u),h\rangle.\tag{2}$

J

$J$

y^{'} (u) h

$y'(u)h$

h

$h$

(1)

$(1)$

h

$h$ od prawej i rozwiązywanie dla (na co pozwala twierdzenie o funkcji niejawnej), tj. obliczanie i podłączając to wyrażenie do . W optymalizacji ograniczonej przez PDE oznacza to rozwiązanie zlinearyzowanego PDE dla każdego wektora podstawowego przestrzeni projektowej.

y^{'} (u) h

$y'(u)h$

\begin{matrix} (3) & [y^{'} (u) h] = e_{y} (y (u), u)^{- 1} [e_{u} (y (u), u) h] \end{matrix}

$[y'(u)h] = e_y(y(u),u)^{-1} [e_u(y(u),u)h]\tag{3}$

(2)

$(2)$

h

$h$

Jeśli jednak znajdziemy operator taki, że to musi to być pożądany gradient. Patrząc na , możemy napisać (gdzie jest operatorem sąsiednim), więc wystarczy obliczyć . Używając tego , można to zrobić za pomocą , tj. i ustawienie W optymalizacji ograniczonej przez PDE, $\nabla j$

j^{'} (u; h) = ⟨ \nabla j, h ⟩ for all h,

$j'(u;h) = \langle \nabla j,h\rangle\qquad \text{for all }h,$

(1)

$(1)$

⟨ J_{y} (y (u), u), y^{'} (u) h ⟩ = ⟨ y^{'} (u)^{*} J_{y} (y (u), u), h ⟩

$\langle J_y(y(u),u),y'(u)h \rangle = \langle y'(u)^*J_y(y(u),u),h \rangle$

y^{'} (u)^{*}

$y'(u)^*$

y^{'} (u)^{*} j_{y} (y (u), u)

$y'(u)^*j_y(y(u),u)$

(A B)^{*} = B^{*} A^{*}

$(AB)^* = B^* A^*$

(3)

$(3)$

λ := e_{y} (y (u), u)^{- *} J_{y} (y (u), u)

$\lambda:= e_y(y(u),u)^{-*}J_y(y(u),u)$

\nabla j (u) = e_{u} (y (u), u)^{*} λ + J_{u} (y (u), u) .

$\nabla j(u) = e_u(y(u),u)^*\lambda +J_u(y(u),u).$

J_{y} (y (u), u)

$J_y(y(u),u)$ jest zwykle pewnego rodzaju resztkowym, a obliczenia obejmują rozwiązanie pojedynczego (liniowego) sprzężonego PDE, niezależnego od wymiaru przestrzeni projektowej. (W rzeczywistości działa to nawet w przypadku parametrów rozproszonych, tj. Jeśli jest funkcją w nieskończenie wymiarowej przestrzeni Banacha, gdzie pierwsze podejście jest niemożliwe.)

λ

$\lambda$

u

$u$

— Christian Clason
źródło