Adjoint state method explained

The adjoint state method is a numerical method for efficiently computing the gradient of a function or operator in a numerical optimization problem.^[1] It has applications in geophysics, seismic imaging, photonics and more recently in neural networks.^[2]

The adjoint state space is chosen to simplify the physical interpretation of equation constraints.^[3]

Adjoint state techniques allow the use of integration by parts, resulting in a form which explicitly contains the physically interesting quantity. An adjoint state equation is introduced, including a new unknown variable.

The adjoint method formulates the gradient of a function towards its parameters in a constraint optimization form. By using the dual form of this constraint optimization problem, it can be used to calculate the gradient very fast. A nice property is that the number of computations is independent of the number of parameters for which you want the gradient.The adjoint method is derived from the dual problem^[4] and is used e.g. in the Landweber iteration method.^[5]

A ^{*=\overline} A ^{T} is used.

When the initial problem consists of calculating the product

s ^{T} x and x must satisfy Ax = b , the dual problem can be realized as calculating the product, where r must satisfy A ^{*} r = s . And r is called the adjoint state vector.

General case

The original adjoint calculation method goes back to Jean Cea,^[6] with the use of the Lagrangian of the optimization problem to compute the derivative of a functional with respect to a shape parameter.

For a state variable

u \in l{U} , an optimization variable v\in l{V} , an objective functional J: l{U} x l{V}\to R is defined. The state variable u is often implicitly dependant on v through the (direct) state equation D _{v(u)=0} (usually the weak form of a partial differential equation), thus the considered objective is j(v) = J(u _{v,v)} . Usually, one would be interested in calculating \nabla j(v) using the chain rule:\nabla j(v) = \nabla _{v} J(u _{v,v)} + \nabla _{u} J(u _{v)\nabla} _{v} u _{v.}

Unfortunately, the term

\nabla _{v} u _{v} is often very hard to differentiate analytically since the dependance is defined through an implicit equation. The Lagrangian functional can be used as a workaround for this issue. Since the state equation can be considered as a constraint in the minimization of j , the problemminimize j(v) = J(u _{v,v)} subjectto D _{v(u} _{v)} = 0

has an associate Lagrangian functional

l{L}: l{U} x l{V} x l{U} \to R defined byl{L}(u,v,λ) = J(u,v) + \langle D _{v(u),λ\rangle,}

where

λ \in l{U} is a Lagrange multiplier or adjoint state variable and \langle ⋅ , ⋅ \rangle is an inner product on l{U} . The method of Lagrange multipliers states that a solution to the problem has to be a stationary point of the lagrangian, namely\begin{cases} d _{ul{L}(u,v,λ;\delta} _{u)} = d _{uJ(u,v;\delta} _{u)} + \langle \delta _{u,D} ^{*( λ )\rangle} ^{v} = 0 & \forall \delta _{u} \in l{U},\\ d _{vl{L}(u,v,λ;\delta} _{v)} = d _{vJ(u,v;\delta} _{v)} + \langle d _{vD} _{v(u;\delta} _{v),λ\rangle} = 0 & \forall \delta _{v\inl{V},\\ d} _{λl{L}(u,v,λ;\delta} _{λ)} = \langle D _{v(u),} \delta _{λ\rangle} = 0 & \forall \delta _{λ} \in l{U}, \end{cases} where d _{xF(x;\delta} _{x)} is the Gateaux derivative of F with respect to x in the direction \delta _{x} . The last equation is equivalent to D _{v(u)} = 0 , the state equation, to which the solution is u _{v} . The first equation is the so-called adjoint state equation,\langle \delta _{u,D} ^{*( λ )\rangle} ^{v} = - d _{uJ(u} _{v,v;\delta} _{u)} \forall \delta _{u} \in l{U},

because the operator involved is the adjoint operator of

D _{v} , D ^{*} _{v} . Resolving this equation yields the adjoint state λ _{v} .The gradient of the quantity of interest j with respect to v is \langle \nabla j(v),\delta _{v\rangle} = d _{v} j(v;\delta _{v)} = d _{v} l{L}(u _{v,v,λ} _{v;\delta} _{v)} (the second equation with u = u _{v} and λ=λ _{v} ), thus it can be easily identified by subsequently resolving the direct and adjoint state equations. The process is even simpler when the operator D _{v} is self-adjoint or symmetric since the direct and adjoint state equations differ only by their right-hand side.

Example: Linear case

In a real finite dimensional linear programming context, the objective function could be

J(u,v) = \langle Au , v \rangle , for v\in R ^{n} , u\in R ^{m} and A \in R ^{n x} , and let the state equation be B _{vu} = b , with B _{v} \in R ^{m x} and b\in R ^{m} .

The lagrangian function of the problem is

l{L}(u,v,λ) = \langle Au,v\rangle + \langle B _{vu} - b, λ \rangle , where λ \in R ^{m} .

The derivative of

l{L} with respect to λ yields the state equation as shown before, and the state variable is u _{v} = B ^{-1} _{v} b . The derivative of l{L} with respect to u is equivalent to the adjoint equation, which is, for every \delta _{u} \in R ^{m} ,d _{u[\langle} B _{v ⋅ -} b, λ \rangle](u;\delta _{u)=} - \langle A ^{\top} v,\delta u\rangle \iff \langle B _{v} \delta _{u,λ\rangle} = - \langle A ^{\top} v,\delta u\rangle \iff \langle B ^{\top} _{v} λ + A ^{\top} v,\delta _{u\rangle} = 0 \iff B ^{\top} _{v} λ = - A ^{\top} v. Thus, we can write symbolically λ _{v} = B ^{- \top} _{v} A ^{\top} v . The gradient would be\langle \nabla j(v),\delta _{v\rangle} = \langle Au _{v,\delta} _{v\rangle} + \langle \nabla _{vB} _{v} : λ _{v ⊗} u _{v,\delta} _{v\rangle,} where \nabla _{v} B _{v} = (\partial B _{ij})/(\partial v _{k}) is a third order tensor, λ _{v} ⊗ u _{v} = λ ^{\top} _{v} u _{v} is the dyadic product between the direct and adjoint states and : denotes a double tensor contraction. It is assumed that B _{v} has a known analytic expression that can be differentiated easily.

Numerical consideration for the self-adjoint case

If the operator

B _{v} was self-adjoint, B _{v} = B ^{\top} _{v} , the direct state equation and the adjoint state equation would have the same left-hand side. In the goal of never inverting a matrix, which is a very slow process numerically, a LU decomposition can be used instead to solve the state equation, in O(m ^{3)} operations for the decomposition and O(m ^{2)} operations for the resolution. That same decomposition can then be used to solve the adjoint state equation in only O(m ^{2)} operations since the matrices are the same.

See also

• Adjoint equation
• Backpropagation
• Method of Lagrange multipliers
• Shape optimization

References

1. Pollini. Nicolò. Lavan. Oren. Amir. Oded. 2018-06-01. Adjoint sensitivity analysis and optimization of hysteretic dynamic systems with nonlinear viscous dampers. Structural and Multidisciplinary Optimization. en. 57. 6. 2273–2289. 10.1007/s00158-017-1858-2. 125712091. 1615-1488.
2. Ricky T. Q. Chen, Yulia Rubanova, Jesse Bettencourt, David Duvenaud Neural Ordinary Differential Equations Available online
3. Plessix, R-E. "A review of the adjoint-state method for computing the gradient of a functional with geophysical applications." Geophysical Journal International, 2006, 167(2): 495-503. free access on GJI website
4. McNamara . Antoine . Treuille . Adrien . Popović . Zoran . Stam . Jos . Fluid control using the adjoint method . 28 October 2022 . https://web.archive.org/web/20220129011505/https://www.dgp.toronto.edu/public_user/stam/reality/Research/pdf/sig04.pdf . 29 January 2022 . ACM Transactions on Graphics . 23 . 3. 449–456 . 10.1145/1015706.1015744 . August 2004 . live.
5. Web site: Lundvall . Johan . Data Assimilation in Fluid Dynamics using Adjoint Optimization . . 28 October 2022 . https://web.archive.org/web/20221009083111/http://liu.diva-portal.org/smash/get/diva2:24091/FULLTEXT01.pdf . 9 October 2022 . Sweden . en . 2007 . live.
6. Cea. Jean. 1986. Conception optimale ou identification de formes, calcul rapide de la dérivée directionnelle de la fonction coût. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique. fr. 20. 3. 371–402. 10.1051/m2an/1986200303711 . free.

External links

• A well written explanation by Errico: What is an adjoint Model?
• Another well written explanation with worked examples, written by Bradley http://cs.stanford.edu/~ambrad/adjoint_tutorial.pdf
• More technical explanation: A review of the adjoint-state method for computing the gradient of a functional with geophysical applications
• MIT course https://web.archive.org/web/20150906095132/http://ocw.mit.edu/courses/mathematics/18-325-topics-in-applied-mathematics-waves-and-imaging-fall-2012/lecture-notes/MIT18_325F12_Chapter4.pdf
• MIT notes http://math.mit.edu/~stevenj/18.336/adjoint.pdf