Método de estados adjuntos

Método numérico

El método de estados adjuntos es un método numérico para calcular de manera eficiente el gradiente de una función u operador en un problema de optimización numérica . ^[1] Tiene aplicaciones en geofísica , imágenes sísmicas , fotónica y, más recientemente, en redes neuronales . ^[2]

El espacio de estados adjunto se elige para simplificar la interpretación física de las restricciones de la ecuación . ^[3]

Las técnicas de estados adjuntos permiten el uso de la integración por partes , lo que da como resultado una forma que contiene explícitamente la cantidad de interés físico. Se introduce una ecuación de estado adjunto, que incluye una nueva variable desconocida.

El método adjunto formula el gradiente de una función en función de sus parámetros en forma de optimización de restricciones. Al utilizar la forma dual de este problema de optimización de restricciones, se puede calcular el gradiente muy rápidamente. Una propiedad interesante es que la cantidad de cálculos es independiente de la cantidad de parámetros para los que se desea el gradiente. El método adjunto se deriva del problema dual ^[4] y se utiliza, por ejemplo, en el método de iteración de Landweber . ^[5]

El nombre "método de estados adjuntos" se refiere a la forma dual del problema, donde se utiliza la matriz adjunta . ${\displaystyle A^{*}={\overline {A}}^{T}}$

Cuando el problema inicial consiste en calcular el producto y debe satisfacer , el problema dual puede realizarse como el cálculo del producto ( ) , donde debe satisfacer . Y se denomina vector de estado adjunto. ${\displaystyle s^{T}x}$ ${\displaystyle x}$ ${\displaystyle Ax=b}$ ${\displaystyle r^{T}b}$ ${\displaystyle =s^{T}x}$ ${\displaystyle r}$ ${\displaystyle A^{*}r=s}$ ${\displaystyle r}$

Caso general

El método original de cálculo adjunto se remonta a Jean Cea, ^[6] con el uso del Lagrangiano del problema de optimización para calcular la derivada de un funcional con respecto a un parámetro de forma .

Para una variable de estado , una variable de optimización , se define una función objetivo . La variable de estado a menudo depende implícitamente de mediante la ecuación de estado (directa) (normalmente la forma débil de una ecuación diferencial parcial ), por lo que el objetivo considerado es . Normalmente, uno estaría interesado en calcular utilizando la regla de la cadena : ${\displaystyle u\in {\mathcal {U}}}$ ${\displaystyle v\in {\mathcal {V}}}$ ${\displaystyle J:{\mathcal {U}}\times {\mathcal {V}}\to \mathbb {R} }$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle D_{v}(u)=0}$ ${\displaystyle j(v)=J(u_{v},v)}$ ${\displaystyle \nabla j(v)}$

${\displaystyle \nabla j(v)=\nabla _{v}J(u_{v},v)+\nabla _{u}J(u_{v})\nabla _{v}u_{v}.}$

Desafortunadamente, el término suele ser muy difícil de diferenciar analíticamente, ya que la dependencia se define a través de una ecuación implícita. El funcional lagrangiano se puede utilizar como una solución alternativa para este problema. Dado que la ecuación de estado se puede considerar como una restricción en la minimización de , el problema ${\displaystyle \nabla _{v}u_{v}}$ ${\displaystyle j}$

${\displaystyle {\text{minimize}}\ j(v)=J(u_{v},v)}$

${\displaystyle {\text{subject to}}\ D_{v}(u_{v})=0}$

tiene una funcional lagrangiana asociada definida por ${\displaystyle {\mathcal {L}}:{\mathcal {U}}\times {\mathcal {V}}\times {\mathcal {U}}\to \mathbb {R} }$

${\displaystyle {\mathcal {L}}(u,v,\lambda )=J(u,v)+\langle D_{v}(u),\lambda \rangle ,}$

donde es un multiplicador de Lagrange o variable de estado adjunta y es un producto interno en . El método de los multiplicadores de Lagrange establece que una solución al problema tiene que ser un punto estacionario del lagrangiano, es decir ${\displaystyle \lambda \in {\mathcal {U}}}$ ${\displaystyle \langle \cdot ,\cdot \rangle }$ ${\displaystyle {\mathcal {U}}}$

${\displaystyle {\begin{cases}d_{u}{\mathcal {L}}(u,v,\lambda ;\delta _{u})=d_{u}J(u,v;\delta _{u})+\langle \delta _{u},D_{v}^{*}(\lambda )\rangle =0&\forall \delta _{u}\in {\mathcal {U}},\\d_{v}{\mathcal {L}}(u,v,\lambda ;\delta _{v})=d_{v}J(u,v;\delta _{v})+\langle d_{v}D_{v}(u;\delta _{v}),\lambda \rangle =0&\forall \delta _{v}\in {\mathcal {V}},\\d_{\lambda }{\mathcal {L}}(u,v,\lambda ;\delta _{\lambda })=\langle D_{v}(u),\delta _{\lambda }\rangle =0\quad &\forall \delta _{\lambda }\in {\mathcal {U}},\end{cases}}}$

donde es la derivada de Gateaux de con respecto a en la dirección . La última ecuación es equivalente a , la ecuación de estado, cuya solución es . La primera ecuación es la llamada ecuación de estado adjunta, ${\displaystyle d_{x}F(x;\delta _{x})}$ ${\displaystyle F}$ ${\displaystyle x}$ ${\displaystyle \delta _{x}}$ ${\displaystyle D_{v}(u)=0}$ ${\displaystyle u_{v}}$

${\displaystyle \langle \delta _{u},D_{v}^{*}(\lambda )\rangle =-d_{u}J(u_{v},v;\delta _{u})\quad \forall \delta _{u}\in {\mathcal {U}},}$

porque el operador involucrado es el operador adjunto de , . Resolver esta ecuación produce el estado adjunto . El gradiente de la cantidad de interés con respecto a es (la segunda ecuación con y ), por lo tanto, se puede identificar fácilmente resolviendo posteriormente las ecuaciones de estado directas y adjuntas. El proceso es aún más simple cuando el operador es autoadjunto o simétrico ya que las ecuaciones de estado directas y adjuntas difieren solo por su lado derecho. ${\displaystyle D_{v}}$ ${\displaystyle D_{v}^{*}}$ ${\displaystyle \lambda _{v}}$ ${\displaystyle j}$ ${\displaystyle v}$ ${\displaystyle \langle \nabla j(v),\delta _{v}\rangle =d_{v}j(v;\delta _{v})=d_{v}{\mathcal {L}}(u_{v},v,\lambda _{v};\delta _{v})}$ ${\displaystyle u=u_{v}}$ ${\displaystyle \lambda =\lambda _{v}}$ ${\displaystyle D_{v}}$

Ejemplo: Caso lineal

En un contexto real de programación lineal de dimensión finita , la función objetivo podría ser , para , y , y sea la ecuación de estado , con y . ${\displaystyle J(u,v)=\langle Au,v\rangle }$ ${\displaystyle v\in \mathbb {R} ^{n}}$ ${\displaystyle u\in \mathbb {R} ^{m}}$ ${\displaystyle A\in \mathbb {R} ^{n\times m}}$ ${\displaystyle B_{v}u=b}$ ${\displaystyle B_{v}\in \mathbb {R} ^{m\times m}}$ ${\displaystyle b\in \mathbb {R} ^{m}}$

La función lagrangiana del problema es , donde . ${\displaystyle {\mathcal {L}}(u,v,\lambda )=\langle Au,v\rangle +\langle B_{v}u-b,\lambda \rangle }$ ${\displaystyle \lambda \in \mathbb {R} ^{m}}$

La derivada de con respecto a produce la ecuación de estado como se mostró anteriormente, y la variable de estado es . La derivada de con respecto a es equivalente a la ecuación adjunta, que es, para cada , ${\displaystyle {\mathcal {L}}}$ ${\displaystyle \lambda }$ ${\displaystyle u_{v}=B_{v}^{-1}b}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle u}$ ${\displaystyle \delta _{u}\in \mathbb {R} ^{m}}$

${\displaystyle d_{u}[\langle B_{v}\cdot -b,\lambda \rangle ](u;\delta _{u})=-\langle A^{\top }v,\delta u\rangle \iff \langle B_{v}\delta _{u},\lambda \rangle =-\langle A^{\top }v,\delta u\rangle \iff \langle B_{v}^{\top }\lambda +A^{\top }v,\delta _{u}\rangle =0\iff B_{v}^{\top }\lambda =-A^{\top }v.}$

Así, podemos escribir simbólicamente . El gradiente sería ${\displaystyle \lambda _{v}=B_{v}^{-\top }A^{\top }v}$

${\displaystyle \langle \nabla j(v),\delta _{v}\rangle =\langle Au_{v},\delta _{v}\rangle +\langle \nabla _{v}B_{v}:\lambda _{v}\otimes u_{v},\delta _{v}\rangle ,}$

donde es un tensor de tercer orden , es el producto diádico entre los estados directo y adjunto y denota una contracción tensorial doble . Se supone que tiene una expresión analítica conocida que se puede diferenciar fácilmente. ${\displaystyle \nabla _{v}B_{v}={\frac {\partial B_{ij}}{\partial v_{k}}}}$ ${\displaystyle \lambda _{v}\otimes u_{v}=\lambda _{v}^{\top }u_{v}}$ ${\displaystyle :}$ ${\displaystyle B_{v}}$

Consideración numérica para el caso autoadjunto

Si el operador fuera autoadjunto, , la ecuación de estado directa y la ecuación de estado adjunta tendrían el mismo lado izquierdo. Con el objetivo de no invertir nunca una matriz, que es un proceso numérico muy lento, se puede utilizar una descomposición LU para resolver la ecuación de estado, en operaciones para la descomposición y operaciones para la resolución. Esa misma descomposición se puede utilizar entonces para resolver la ecuación de estado adjunta en solo operaciones, ya que las matrices son las mismas. ${\displaystyle B_{v}}$ ${\displaystyle B_{v}=B_{v}^{\top }}$ ${\displaystyle O(m^{3})}$ ${\displaystyle O(m^{2})}$ ${\displaystyle O(m^{2})}$

Véase también

• Ecuación adjunta
• Retropropagación
• Método de multiplicadores de Lagrange
• Optimización de formas

Referencias

1. Pollini, Nicolò; Lavan, Oren; Amir, Oded (1 de junio de 2018). "Análisis de sensibilidad adjunto y optimización de sistemas dinámicos histeréticos con amortiguadores viscosos no lineales". Optimización estructural y multidisciplinaria . 57 (6): 2273–2289. doi :10.1007/s00158-017-1858-2. ISSN  1615-1488. S2CID  125712091.
2. Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, David Duvenaud Ecuaciones diferenciales ordinarias neuronales Disponible en línea
3. Plessix, RE. "Una revisión del método de estados adjuntos para calcular el gradiente de un funcional con aplicaciones geofísicas". Geophysical Journal International, 2006, 167(2): 495-503. Acceso gratuito en el sitio web de GJI
4. McNamara, Antoine; Treuille, Adrien; Popović, Zoran; Stam, Jos (agosto de 2004). "Control de fluidos mediante el método adjunto" (PDF) . ACM Transactions on Graphics . 23 (3): 449–456. doi :10.1145/1015706.1015744. Archivado (PDF) del original el 29 de enero de 2022 . Consultado el 28 de octubre de 2022 .
5. Lundvall, Johan (2007). "Asimilación de datos en dinámica de fluidos mediante optimización adjunta" (PDF) . Suecia: Universidad Tecnológica de Linköping . Archivado (PDF) del original el 9 de octubre de 2022. Consultado el 28 de octubre de 2022 .
6. Cea, Jean (1986). "Concepción óptima o identificación de formas, cálculo rápido de la derivación direccional de la función costera". ESAIM: Modelado matemático y análisis numérico - Modélisation Mathématique et Analyse Numérique (en francés). 20 (3): 371–402. doi : 10.1051/m2an/1986200303711 .

Enlaces externos

• Una explicación bien escrita de Errico: ¿Qué es un modelo adjunto?
• Otra explicación bien escrita con ejemplos resueltos, escrita por Bradley [1]
• Explicación más técnica: Una revisión del método de estados adjuntos para calcular el gradiente de un funcional con aplicaciones geofísicas
• Curso del MIT [2]
• Notas del MIT [3]