Comprendre le coût de la méthode adjointe pour l'optimisation contrainte pde

J'essaie de comprendre comment fonctionne la méthode d'optimisation basée sur l'adjoint pour une optimisation contrainte PDE. En particulier, j'essaie de comprendre pourquoi la méthode adjointe est plus efficace pour les problèmes où le nombre de variables de conception est grand, mais le "nombre d'équations est petit".

Ce que je comprends:

Considérez le problème d'optimisation contraint PDE suivant:

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

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

où $I$ est une fonction objective (suffisamment continue) d'un vecteur de variables de conception $\beta$ et d'un vecteur de variables de champ inconnues $u(\beta)$ qui dépendent des variables de conception, et $R(u)$ est la forme résiduelle de l'EDP.

De toute évidence, nous pouvons les premières variations de I et R comme

δ je = \frac{\partial je}{\partial β} δ β + \frac{\partial je}{\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$

En introduisant un vecteur de multiplicateurs de lagrange $\lambda$ , la variation de la fonction objectif peut s'écrire

δ je = \frac{\partial je}{\partial β} δ β + \frac{\partial je}{\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]$

En réarrangeant les termes, nous pouvons écrire:

δ je = [\frac{\partial je}{\partial β} + λ^{T} \frac{\partial R}{\partial β}] δ β + [\frac{\partial je}{\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$

Ainsi, si nous pouvons résoudre pour telle sorte que $\lambda$

\frac{\partial je}{\partial u} + λ^{T} \frac{\partial R}{\partial u} = 0 (équation adjointe)

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

Ensuite, le gradient est évalué uniquement en termes de variables de conception . $\delta I= \left[\frac{\partial I}{\partial \beta} + \lambda^T\frac{\partial R}{\partial \beta}\right]\delta \beta$ $\beta$

Ainsi, un algorithme d'optimisation basé sur l'adjoint bouclerait sur les étapes suivantes:

Compte tenu des variables de conception actuelles $\beta$
Résoudre pour les variables de champ (à partir de la PDE) $u$
Résoudre pour les multiplicateurs de lagrange (à partir de l'équation adjointe) $\lambda$
Calculer les gradients $\frac{\partial I}{\partial \beta}$
Mettre à jour les variables de conception $\beta$

Ma question

Comment cette «astuce» adjointe améliore-t-elle le coût de l'optimisation par itération dans le cas où le nombre de variables de conception est important? J'ai entendu dire que le coût de l'évaluation du gradient pour la méthode adjointe est «indépendant» du nombre de variables de conception. Mais comment est-ce vrai?

Je suis sûr qu'il y a quelque chose de très évident que j'oublie d'une manière ou d'une autre.

optimization pde Paul
la source

Soit dit en passant, le multiplicateur de Lagrange est généralement ajouté à la fonction objective, pas à la variation; ainsi . Mettre la dérivée par rapport à à zéro donne l'équation adjointe, et l'insérer (et la solution de l'équation d'état ) dans la dérivée par rapport à donne le gradient. Si vous commencez avec la formulation faible de la PDE, les choses deviennent encore plus simples: il suffit d'insérer le multiplicateur de Lagrange à la place de la fonction de test. Pas besoin de la forme forte ou de l'intégration partielle n'importe où.

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

La partie la plus coûteuse de toute simulation est la phase de résolution. En utilisant l'adjoint, vous obtenez le gradient en deux résolutions, beaucoup moins cher que les différences finies où vous avez au moins besoin de n + 1 résolutions, n étant le nombre de paramètres libres dans votre modèle.

stali

Réponses:

Comment cette «astuce» adjointe améliore-t-elle le coût de l'optimisation par itération dans le cas où le nombre de variables de conception est important?

Je pense au coût du point de vue de l'algèbre linéaire. (Voir ces notes de Stephen G. Johnson , que je trouve plus intuitives que l'approche du multiplicateur de Lagrange). L'approche prospective revient à résoudre directement les sensibilités:

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

ce qui implique de résoudre un système linéaire pour chaque paramètre du vecteur , puis d'évaluer $\beta$

\begin{aligned} \frac{ré je}{ré β} = \frac{\partial je}{\partial β} + \frac{\partial je}{\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}$

où désigne une dérivée totale et désigne une dérivée partielle. $\mathrm{d}$ $\partial$

L'approche adjointe note que

\begin{aligned} \frac{ré je}{ré β} = \frac{\partial je}{\partial β} - \frac{\partial je}{\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}$

donc la variable adjointe (multiplicateur de Lagrange) peut être définie par $\lambda$

\begin{aligned} - \frac{\partial je}{\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}$

ce qui correspond à l'équation adjointe

\begin{aligned} \frac{\partial je}{\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}$

Ce regroupement de termes ne nécessite qu'une seule résolution linéaire, au lieu d'une résolution linéaire pour chaque paramètre, ce qui rend l'évaluation adjointe bon marché pour le cas à plusieurs paramètres.

J'ai entendu dire que le coût de l'évaluation du gradient pour la méthode adjointe est «indépendant» du nombre de variables de conception. Mais comment est-ce vrai?

Ce n'est pas totalement indépendant; sans doute le coût de l'évaluation et augmentera avec le nombre de paramètres. Les résolutions linéaires, cependant, seront toujours de la même taille, tant que la taille de ne change pas. L'hypothèse est que les résolutions sont beaucoup plus chères que les évaluations de fonctions. $(\partial{I}/\partial{\beta})$ $(\partial{R}/\partial{\beta})$ $u$

Geoff Oxberry
la source

En résumé, l'avantage vient du fait que pour calculer les dérivées de l'objectif réduit , il n'est pas vraiment nécessaire de connaître la dérivée de par rapport à comme un objet séparé, mais seulement la partie de celui-ci qui conduit à des variations de . $I(\beta,u(\beta))$ $u(\beta)$ $\beta$ $I(\beta,u(\beta))$

Permettez-moi de passer à une notation avec laquelle je suis un peu plus à l'aise: ( étant le variable de conception, étant la variable d'état et étant l'objectif). Disons que est assez agréable pour appliquer le théorème de fonction implicite, donc l'équation a une solution unique qui est continuellement différenciable par rapport à , et la dérivée est donné par la solution de ( et étant les dérivées partielles) .

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$

Cela signifie que vous pouvez définir l'objectif réduit , qui est également différenciable (si est). Une façon de caractériser le gradient est d'utiliser des dérivées directionnelles (par exemple, calculer toutes les dérivées partielles par rapport à une base de l'espace de conception). Ici, la dérivée directionnelle dans la direction est donnée par la règle de chaîne comme Si est bien, la seule chose difficile à calculer est pour donné . Cela peut être fait en multipliant par $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$ à partir de la droite et en résolvant (ce que permet le théorème de la fonction implicite), c'est-à-dire calculer et en branchant cette expression dans . Dans l'optimisation contrainte par PDE, cela revient à résoudre une PDE linéarisée pour chaque vecteur de base de l'espace de conception.

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$

Cependant, si nous trouvons un opérateur tel que alors ce doit être le gradient souhaité. En regardant , nous pouvons écrire (avec étant l'opérateur adjoint), donc tout ce dont nous avons besoin pour calculer est . En utilisant cela , cela peut être fait en utilisant , c'est-à-dire en calculant et en définissant Dans l'optimisation contrainte par PDE, $\nabla j$

j^{'} (u; h) = ⟨ \nabla j, h ⟩ pour tous 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)$ est généralement une sorte de résidu, et le calcul implique la résolution d'un PDE adjoint (linéaire) unique , indépendant de la dimension de l'espace de conception. (En fait, cela fonctionne même pour les paramètres distribués, c'est-à-dire si est une fonction dans un espace de Banach de dimension infinie, où la première approche est irréalisable.)

λ

$\lambda$

u

$u$

Christian Clason
la source