Verständnis der Kosten der adjungierten Methode für die pde-beschränkte Optimierung

Ich versuche zu verstehen, wie die adjungierte Optimierungsmethode für eine PDE-beschränkte Optimierung funktioniert. Insbesondere versuche ich zu verstehen, warum die adjungierte Methode bei Problemen effizienter ist, bei denen die Anzahl der Entwurfsvariablen groß ist, die "Anzahl der Gleichungen jedoch klein".

Was ich verstehe:

Betrachten Sie das folgende Optimierungsproblem mit eingeschränkter PDE:

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

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

wobei eine (ausreichend kontinuierliche) Zielfunktion einer Vektorentwurfsvariablen und eines Vektors von Feldvariablen unbekannt die von den Entwurfsvariablen abhängen, und die Restform der PDE ist. $I$ $\beta$ $u(\beta)$ $R(u)$

Klar, wir können die ersten Variationen von I und R als

δ 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$

Durch Einführung eines Vektors von Lagrange-Multiplikatoren kann die Variation der Zielfunktion wie folgt geschrieben werden $\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]$

Wenn wir Begriffe neu ordnen, können wir schreiben:

δ 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$

Wenn wir also in der Lage sind, nach zu lösen, so dass $\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)}$

Dann wird der Gradient ausgewertet nur in Bezug auf die Designvariablen . $\delta I= \left[\frac{\partial I}{\partial \beta} + \lambda^T\frac{\partial R}{\partial \beta}\right]\delta \beta$ $\beta$

Somit würde ein adjungierter Optimierungsalgorithmus die folgenden Schritte durchlaufen:

Angesichts der aktuellen Designvariablen $\beta$
Löse nach den Feldvariablen (aus der PDE) $u$
Löse nach den Lagrange-Multiplikatoren (aus der nebenstehenden Gleichung) $\lambda$
Berechnen Sie die Farbverläufe $\frac{\partial I}{\partial \beta}$
Designvariablen $\beta$

Meine Frage

Wie verbessert dieser zusätzliche Trick die Kosten für die Optimierung pro Iteration, wenn die Anzahl der Entwurfsvariablen groß ist? Ich habe gehört, dass die Kosten für die Gradientenbewertung für die adjungierte Methode "unabhängig" von der Anzahl der Entwurfsvariablen sind. Aber wie genau ist das wahr?

Ich bin sicher, es gibt etwas sehr Offensichtliches, das ich irgendwie übersehen habe.

optimization pde Paul
quelle

Übrigens wird der Lagrange-Multiplikator normalerweise zur Zielfunktion hinzugefügt, nicht zur Variation. also . Das Setzen der Ableitung in Bezug auf auf Null ergibt die adjungierte Gleichung, und das Einfügen dieser (und der Lösung der Zustandsgleichung ) in die Ableitung in Bezug auf ergibt den Gradienten. Wenn Sie mit der schwachen Formulierung der PDE beginnen, wird es noch einfacher: Fügen Sie einfach den Lagrange-Multiplikator anstelle der Testfunktion ein. Keine Notwendigkeit für die starke Form oder teilweise Integration irgendwo.

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

Der teuerste Teil jeder Simulation ist die Lösungsphase. Wenn Sie den Zusatz verwenden, erhalten Sie den Gradienten in zwei Lösungen, viel billiger als bei endlichen Differenzen, bei denen Sie mindestens n + 1 Lösungen benötigen, wobei n die Anzahl der freien Parameter in Ihrem Modell ist.

stali

Antworten:

Wie verbessert dieser zusätzliche Trick die Kosten für die Optimierung pro Iteration, wenn die Anzahl der Entwurfsvariablen groß ist?

Ich denke über die Kosten aus der Perspektive der linearen Algebra nach. (Siehe diese Notizen von Stephen G. Johnson , die ich intuitiver finde als den Lagrange-Multiplikator-Ansatz). Der Forward-Ansatz läuft darauf hinaus, Sensitivitäten direkt zu lösen:

\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}$

Dabei wird für jeden Parameter im Vektor ein lineares System gelöst und anschließend ausgewertet $\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}$

Dabei bezeichnet eine Gesamtableitung und eine partielle Ableitung. $\mathrm{d}$ $\partial$

Der adjungierte Ansatz stellt fest, dass

\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}$

so kann die adjungierte Variable (Lagrange-Multiplikator) definiert werden durch $\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}$

was der adjungierten Gleichung entspricht

\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}$

Diese Umgruppierung von Begriffen erfordert nur eine lineare Lösung anstelle einer linearen Lösung für jeden Parameter, was eine adjungierte Auswertung für den Fall mit vielen Parametern billig macht.

Ich habe gehört, dass die Kosten für die Gradientenbewertung für die adjungierte Methode "unabhängig" von der Anzahl der Entwurfsvariablen sind. Aber wie genau ist das wahr?

Es ist nicht völlig unabhängig; vermutlich steigen die Kosten für die Auswertung und mit der Anzahl der Parameter. Die linearen Lösungen haben jedoch immer noch die gleiche Größe, solange sich die Größe von nicht ändert. Die Annahme ist, dass die Lösungen viel teurer sind als die Funktionsbewertungen. $(\partial{I}/\partial{\beta})$ $(\partial{R}/\partial{\beta})$ $u$

Geoff Oxberry
quelle

Kurz gesagt, der Vorteil ergibt sich aus der Tatsache, dass Sie zur Berechnung von Ableitungen des reduzierten Ziels die Ableitung von in Bezug auf nicht wirklich kennen müssen als separates Objekt, aber nur der Teil davon, der zu Variationen in . $I(\beta,u(\beta))$ $u(\beta)$ $\beta$ $I(\beta,u(\beta))$

Lassen Sie mich zu einer Notation wechseln, mit der ich mich ein bisschen besser : ( ist das Entwurfsvariable, wobei die Zustandsvariable und das Ziel ist). Nehmen wir an, ist nett genug, um den impliziten Funktionssatz anzuwenden, also hat die Gleichung eine eindeutige Lösung die in Bezug auf und die Ableitung kontinuierlich differenzierbar ist ist gegeben durch die Lösung von ( und sind die partiellen Ableitungen) .

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$

Dies bedeutet, dass Sie das reduzierte Ziel , das ebenfalls differenzierbar ist (wenn ist). Eine Möglichkeit, den Gradienten zu charakterisieren, besteht in gerichteten Ableitungen (z. B. Berechnung aller partiellen Ableitungen in Bezug auf eine Basis des Entwurfsraums). Hier ist die Richtungsableitung in Richtung durch die Kettenregel gegeben als Wenn nett ist, ist die einzige schwierige Sache, für gegebenes zu berechnen . Dies kann durch Multiplizieren von mit $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$ von rechts und Auflösen nach (was der implizite Funktionssatz erlaubt), dh Berechnen von und Einfügen dieses Ausdrucks in . Bei der PDE-beschränkten Optimierung läuft dies darauf hinaus, eine linearisierte PDE für jeden Basisvektor des Entwurfsraums zu lösen .

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$

Wenn wir jedoch einen Operator so dass dann muss dies der gewünschte Gradient sein. Wenn wir uns , können wir (wobei der adjungierte Operator ist), also müssen wir nur berechnen . Unter Verwendung von kann dies unter Verwendung von , dh Berechnen von und Setzen von Bei der PDE-beschränkten Optimierung ist $\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)$ ist normalerweise eine Art Residuum, und bei der Berechnung von eine einzelne (lineare) adjungierte PDE gelöst , unabhängig von der Dimension des Entwurfsraums. (Tatsächlich funktioniert dies sogar für verteilte Parameter, dh wenn eine Funktion in einem unendlich dimensionalen Banach-Raum ist, in dem der erste Ansatz nicht möglich ist.)

λ

$\lambda$

u

$u$

Christian Clason
quelle