Метод присоединенного состояния

Метод сопряженного состояния — это численный метод эффективного вычисления градиента функции оператора или в задаче численной оптимизации . Он находит применение в геофизике , сейсмической визуализации , фотонике и, в последнее время, в нейронных сетях .

Сопряженное пространство состояний выбрано для упрощения физической интерпретации ограничений уравнения .

Методы сопряженного состояния позволяют использовать интегрирование по частям , в результате чего получается форма, которая явно содержит физически интересную величину. Вводится сопряженное уравнение состояния, включающее новую неизвестную переменную.

Сопряженный метод формулирует градиент функции к ее параметрам в форме оптимизации ограничений. Используя двойную форму этой задачи оптимизации ограничений, ее можно использовать для очень быстрого расчета градиента. Приятным свойством является то, что количество вычислений не зависит от количества параметров, для которых вам нужен градиент.Сопряженный метод вытекает из двойственной задачи и используется, например, в итерационном методе Ландвебера .

Название метода сопряженного состояния относится к двойственной форме задачи, где сопряженная матрица $A^{*}={\overline {A}}^{T}$ используется.

Когда исходная задача состоит в вычислении произведения $s^{T}x$ и $x$ должен удовлетворить $Ax=b$, двойственная задача может быть реализована как вычисление произведения $r^{T}b$ ( $=s^{T}x$) , где $r$ должен удовлетворить $A^{*}r=s$. И $r$ называется вектором присоединенного состояния.

Общий случай

Оригинальный метод сопряженных вычислений восходит к Жану Сеа. с использованием лагранжиана задачи оптимизации для вычисления производной функционала по параметру формы .

Для переменной состояния $u\in {\mathcal {U}}$, переменная оптимизации $v\in {\mathcal {V}}$, целевой функционал $J:{\mathcal {U}}\times {\mathcal {V}}\to \mathbb {R}$ определяется. Переменная состояния $u$ часто неявно зависит от $v$ через (прямое) уравнение состояния $D_{v}(u)=0$ (обычно слабая форма уравнения в частных производных ), поэтому рассматриваемая цель $j(v)=J(u_{v},v)$. Обычно интересуют расчеты $\nabla j(v)$ используя правило цепочки :

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

К сожалению, термин $\nabla _{v}u_{v}$ часто очень трудно дифференцировать аналитически, поскольку зависимость определяется с помощью неявного уравнения. В качестве решения этой проблемы можно использовать функционал Лагранжа. Поскольку уравнение состояния можно рассматривать как ограничение при минимизации $j$, проблема

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

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

имеет ассоциированный лагранжев функционал ${\mathcal {L}}:{\mathcal {U}}\times {\mathcal {V}}\times {\mathcal {U}}\to \mathbb {R}$ определяется

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

где $\lambda \in {\mathcal {U}}$ является множителем Лагранжа или присоединенной переменной состояния и $\langle \cdot ,\cdot \rangle$ является внутренним продуктом на ${\mathcal {U}}$. Метод множителей Лагранжа утверждает, что решением задачи должна быть стационарная точка лагранжиана, а именно

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

где $d_{x}F(x;\delta _{x})$ является производной Гато от $F$ относительно $x$ в направлении $\delta _{x}$. Последнее уравнение эквивалентно $D_{v}(u)=0$, уравнение состояния, решением которого является $u_{v}$. Первое уравнение представляет собой так называемое уравнение сопряженного состояния.

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

поскольку задействованный оператор является сопряженным оператором $D_{v}$, $D_{v}^{*}$. Решение этого уравнения дает сопряженное состояние $\lambda _{v}$.Градиент интересующего количества $j$ относительно $v$ является $\langle \nabla j(v),\delta _{v}\rangle =d_{v}j(v;\delta _{v})=d_{v}{\mathcal {L}}(u_{v},v,\lambda _{v};\delta _{v})$ (второе уравнение с $u=u_{v}$ и $\lambda =\lambda _{v}$), поэтому его можно легко идентифицировать путем последующего решения прямых и сопряженных уравнений состояния. Процесс еще проще, если оператор $D_{v}$ является самосопряженным или симметричным, поскольку прямое и сопряженное уравнения состояния различаются только правой частью.

Пример: линейный случай

В реальном конечномерном контексте линейного программирования целевая функция может быть такой: $J(u,v)=\langle Au,v\rangle$, для $v\in \mathbb {R} ^{n}$, $u\in \mathbb {R} ^{m}$ и $A\in \mathbb {R} ^{n\times m}$, и пусть уравнение состояния будет $B_{v}u=b$, с $B_{v}\in \mathbb {R} ^{m\times m}$ и $b\in \mathbb {R} ^{m}$.

Лагранжева функция задачи равна ${\mathcal {L}}(u,v,\lambda )=\langle Au,v\rangle +\langle B_{v}u-b,\lambda \rangle$, где $\lambda \in \mathbb {R} ^{m}$.

Производная от ${\mathcal {L}}$ относительно $\lambda$ дает уравнение состояния, как показано ранее, а переменная состояния равна $u_{v}=B_{v}^{-1}b$. Производная от ${\mathcal {L}}$ относительно $u$ эквивалентно сопряженному уравнению, то есть для любого $\delta _{u}\in \mathbb {R} ^{m}$,

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

Таким образом, мы можем написать символически $\lambda _{v}=B_{v}^{-\top }A^{\top }v$. Градиент будет

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

где $\nabla _{v}B_{v}={\frac {\partial B_{ij}}{\partial v_{k}}}$ третьего порядка – тензор , $\lambda _{v}\otimes u_{v}=\lambda _{v}^{\top }u_{v}$ представляет собой диадический продукт между прямым и присоединенным состояниями и $:$ обозначает двойное тензорное сжатие . Предполагается, что $B_{v}$ имеет известное аналитическое выражение, которое легко дифференцировать.

Численное рассмотрение самосопряженного случая

Если оператор $B_{v}$ был самосопряженным, $B_{v}=B_{v}^{\top }$, прямое уравнение состояния и уравнение сопряженного состояния будут иметь одну и ту же левую часть. Чтобы никогда не инвертировать матрицу, что в численном отношении является очень медленным процессом, LU-разложение для решения уравнения состояния, в вместо этого можно использовать $O(m^{3})$ операции по разложению и $O(m^{2})$ операции по разрешению. Затем то же самое разложение можно использовать для решения сопряженного уравнения состояния всего за $O(m^{2})$ операций, поскольку матрицы одинаковы.

См. также

• Сопряженное уравнение
• Обратное распространение ошибки
• Метод множителей Лагранжа
• Оптимизация формы

Внешние ссылки

• Хорошо написанное объяснение Эррико: Что такое присоединенная модель?
• Еще одно хорошо написанное объяснение с проработанными примерами, написанное Брэдли [1].
• Более техническое объяснение: обзор метода сопряженного состояния для вычисления градиента функционала в геофизических приложениях.
• курс Массачусетского технологического института [2]
• С примечаниями [3]