随伴状態法

随伴状態法は、数値最適化問題における関数または演算子の勾配を効率的に計算するための数値手法である。^[1]地球物理学、地震画像、フォトニクス、そして最近ではニューラルネットワーク に応用されている。^[2]

随伴状態空間は方程式の制約の物理的な解釈を簡素化するために選択される。^[3]

随伴状態技法では、部分積分の使用が可能になり、物理的に興味深い量を明示的に含む形式が得られます。新しい未知の変数を含む随伴状態方程式が導入されます。

随伴法は、制約最適化形式で関数のパラメータに対する勾配を定式化します。この制約最適化問題の双対形式を使用すると、勾配を非常に高速に計算できます。計算回数が勾配を求めるパラメータの数に依存しないという優れた特性があります。随伴法は双対問題^{[4]から派生したもので、たとえば}ランドウェーバー反復法で使用されます。^[5]

随伴状態法という名前は、随伴行列が使用される問題の双対形式を指します。 ${\displaystyle A^{*}={\overline {A}}^{T}}$

初期問題が積の計算で構成され、を満たす必要がある場合、双対問題は積( )を計算することで実現できます。ここで、を満たす必要があります。 および は 随伴状態ベクトルと呼ばれます。 ${\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}$

^{元々の随伴計算法はJean Cea [6]}に遡り、最適化問題のラグランジアンを使用して形状パラメータに関する関数の導関数を計算します。

状態変数、最適化変数に対して、目的関数が定義されます。状態変数 は、 (直接的な)状態方程式(通常は偏微分方程式の弱形式) を通じて暗黙的に に依存することが多いため、考慮される目的は です。通常は、連鎖律を使用した計算が対象となります。 ${\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}。 }$

残念ながら、依存性は暗黙の方程式で定義されているため、項を解析的に微分することは非常に難しいことがよくあります。この問題を回避するには、ラグランジアン関数を使用することができます。状態方程式は の最小化における制約として考えることができるため、問題は ${\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}$

関連するラグランジアン関数は次のように定義される。 ${\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 ,}$

ここで はラグランジュ乗数または随伴状態変数であり、は の内積である。ラグランジュ乗数法によれば、問題の解はラグランジュ関数の 定常点、すなわち${\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}}}$

ここで は の方向に関するガトー微分です。最後の方程式は 、つまり状態方程式に相当し、その解は です。最初の方程式は、いわゆる随伴状態方程式です。 ${\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}},}$

関係する演算子は、の随伴演算子であるためです。この方程式を解くと、随伴状態 が得られます。に対する関心のある量の勾配は(およびを含む 2 番目の方程式)であるため、直接状態方程式と随伴状態方程式を後で解くことで簡単に識別できます。演算子が自己随伴または対称である場合、直接状態方程式と随伴状態方程式は右辺のみが異なるため、プロセスはさらに簡単になります。 ${\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}}$

実際の有限次元線形計画法のコンテキストでは、目的関数は、に対してとなり、状態方程式は、に対してとなります。 ${\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}}$

この問題のラグランジアン関数は であり、 です。 ${\displaystyle {\mathcal {L}}(u,v,\lambda )=\langle Au,v\rangle +\langle B_{v}u-b,\lambda \rangle }$${\displaystyle \lambda \in \mathbb {R} ^{m}}$

を について微分すると、前に示した状態方程式が得られ、状態変数は となる。 を について微分すると、随伴方程式と等しくなり、任意のに対して、 ${\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.}$

したがって、記号的に書くと、勾配は次のようになる。 ${\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 ,}$

ここで、は3次テンソル、は直接状態と随伴状態の間の2項積、 は二重テンソル収縮を表します。 は簡単に微分できる既知の解析表現を持つ と仮定します。${\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}}$

演算子が自己随伴である場合、直接状態方程式と随伴状態方程式の左辺は同じになります。数値的には非常に遅いプロセスである行列の反転を決して行わないという目標では、代わりにLU 分解を使用して状態方程式を解き、分解の演算と解決の演算を行うことができます。同じ分解を使用して、行列が同じであるため、演算 のみで随伴状態方程式を解くことができます。${\displaystyle B_{v}}$${\displaystyle B_{v}=B_{v}^{\top }}$${\displaystyle O(m^{3})}$${\displaystyle O(m^{2})}$${\displaystyle O(m^{2})}$

• 随伴方程式
• バックプロパゲーション
• ラグランジュ乗数法
• 形状最適化

• Errico によるわかりやすい説明: 随伴モデルとは何ですか?
• ブラッドリー[1]による、実例を交えた分かりやすい説明。
• より技術的な説明: 地球物理学的応用における関数の勾配を計算するための随伴状態法のレビュー
• MITコース [2]
• MITノート[3]