Entendendo o custo do método adjunta para otimização com restrição de pde

Estou tentando entender como o método de otimização baseado em adjuntos funciona para uma otimização restrita do PDE. Particularmente, estou tentando entender por que o método adjunta é mais eficiente para problemas em que o número de variáveis de design é grande, mas o "número de equações é pequeno".

O que eu entendo:

Considere o seguinte problema de otimização restrita do PDE:

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

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

onde $I$ é uma função objetiva (suficientemente contínua) de uma variável de projeto vetorial $\beta$ e um vetor de variável de campo desconhecida $u(\beta)$ que depende das variáveis de design, e $R(u)$ é a forma residual do PDE.

Claramente, podemos as primeiras variações de I e R como

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

Introduzindo um vetor de multiplicadores de lagrange $\lambda$ , a variação na função objetivo pode ser escrita como

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

Reorganizando os termos, podemos escrever:

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

Portanto, se formos capazes de resolver modo que $\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)}$

Então, o gradiente é avaliado somente em termos das variáveis de design . $\delta I= \left[\frac{\partial I}{\partial \beta} + \lambda^T\frac{\partial R}{\partial \beta}\right]\delta \beta$ $\beta$

Assim, um algoritmo de otimização baseado em loop repetiria as seguintes etapas:

Dadas as variáveis de design atuais $\beta$
Solução para as variáveis de campo (do PDE) $u$
Resolva para os multiplicadores de lagrange (da equação adjunta) $\lambda$
Calcular gradientes $\frac{\partial I}{\partial \beta}$
Atualizar variáveis de design $\beta$

Minha pergunta

Como esse "truque" adicional melhora o custo da otimização por iteração no caso em que o número de variáveis de design é grande? Ouvi dizer que o custo da avaliação de gradiente para o método adjacente é 'independente' do número de variáveis de design. Mas como exatamente isso é verdade?

Tenho certeza de que há algo muito óbvio que de alguma forma estou ignorando.

optimization pde Paulo
fonte

A propósito, o multiplicador de Lagrange é geralmente adicionado ao objetivo funcional, não à variação; assim . Definir a derivada em relação a como zero produz a equação adjunta e inserir esta (e a solução da equação de estado ) na derivada em relação a produz o gradiente. Se você começar com a formulação fraca do PDE, as coisas ficam ainda mais simples: basta inserir o multiplicador Lagrange no lugar da função de teste. Não há necessidade de forma forte ou integração parcial em qualquer lugar.

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

A parte mais cara de qualquer simulação é a fase de resolução. Usando o adjunto, você obtém o gradiente em duas soluções, muito mais barato comparado às diferenças finitas, nas quais você precisa pelo menos n + 1, n sendo o número de parâmetros livres em seu modelo.

Stali

Respostas:

Como esse "truque" adicional melhora o custo da otimização por iteração no caso em que o número de variáveis de design é grande?

Penso no custo de uma perspectiva de álgebra linear. (Veja estas notas de Stephen G. Johnson , que acho mais intuitivas que a abordagem multiplicadora de Lagrange). A abordagem avançada equivale a solucionar diretamente as sensibilidades:

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

que envolve resolver um sistema linear para cada parâmetro no vetor , e avaliar $\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}$

onde indica uma derivada total e indica uma derivada parcial. $\mathrm{d}$ $\partial$

A abordagem adjunta observa que

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

para que a variável adjunta (multiplicador de Lagrange) possa ser definida por $\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}$

que corresponde à equação adjunta

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

Esse reagrupamento de termos requer apenas uma resolução linear, em vez de uma resolução linear para cada parâmetro, o que torna a avaliação adjunta barata para o caso de muitos parâmetros.

Ouvi dizer que o custo da avaliação de gradiente para o método adjacente é 'independente' do número de variáveis de design. Mas como exatamente isso é verdade?

Não é totalmente independente; presumivelmente, o custo da avaliação e aumentará com o número de parâmetros. As soluções lineares, no entanto, ainda terão o mesmo tamanho, desde que o tamanho de não seja alterado. O pressuposto é que as soluções são muito mais caras que as avaliações de função. $(\partial{I}/\partial{\beta})$ $(\partial{R}/\partial{\beta})$ $u$

Geoff Oxberry
fonte

Em poucas palavras, a vantagem vem do fato de que, para calcular derivadas do objetivo reduzido , você realmente não precisa conhecer a derivada de em relação a como um objeto separado, mas apenas a parte dele que leva a variações em . $I(\beta,u(\beta))$ $u(\beta)$ $\beta$ $I(\beta,u(\beta))$

Deixe-me mudar para uma notação eu sou um pouco mais confortável com: ( ser o variável de projeto, sendo a variável de estado e sendo o objetivo). Digamos que seja bom o suficiente para aplicar o teorema da função implícita, então a equação tem uma solução única que é continuamente diferenciável em relação a e a derivada é dada pela solução de ( e são os derivados parciais) .

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$

Isso significa que você pode definir o objetivo reduzido , que também é diferenciável (se for). Uma maneira de caracterizar o gradiente é através de derivadas direcionais (por exemplo, calcule todas as derivadas parciais em relação a uma base do espaço de design). Aqui, a derivada direcional na direção é dada pela regra da cadeia como Se for bom, a única coisa difícil de calcular é para determinado . Isso pode ser feito multiplicando por $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$ da direita e resolvendo (permitido pelo teorema da função implícita), ou seja, calculando e inserindo esta expressão em . Na otimização com restrição de PDE, isso equivale a resolver um PDE linearizado para cada vetor base do espaço de design.

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$

No entanto, se encontrarmos um operador tal que então esse deve ser o gradiente desejado. Olhando para , podemos escrever (com sendo o operador adjunto), então tudo o que precisamos calcular é . Usando isso , isso pode ser feito usando , ou seja, computando e definindo Na otimização com restrição de 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)$ geralmente é algum tipo de resíduo, e computação envolve a solução de um único PDE (linear) adjacente, independente da dimensão do espaço de design. (De fato, isso funciona mesmo para parâmetros distribuídos, isto é, se é uma função em algum espaço de Banach de dimensão infinita, onde a primeira abordagem é inviável.)

λ

$\lambda$

u

$u$

Christian Clason
fonte