Двойственность Вульфа

В математической оптимизации двойственность Вульфа , названная в честь Филиппа Вульфа , является типом двойственной задачи , в которой целевая функция и ограничения являются дифференцируемыми функциями . Используя эту концепцию, можно найти нижнюю границу для задачи минимизации из-за слабого принципа двойственности . ^[1]

Математическая формулировка

Для задачи минимизации с ограничениями типа неравенства,

${\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\end{aligned}}}$

Двойственная задача Лагранжа — это

${\displaystyle {\begin{aligned}&{\underset {u}{\operatorname {maximize} }}&&\inf _{x}\left(f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\right)\\&\operatorname {subject\;to} &&u_{i}\geq 0,\quad i=1,\dots ,m\end{aligned}}}$

где целевая функция — это двойственная функция Лагранжа. При условии, что функции и выпуклы и непрерывно дифференцируемы, инфимум возникает там, где градиент равен нулю. Задача ${\displaystyle f}$ ${\displaystyle g_{1},\ldots ,g_{m}}$

${\displaystyle {\begin{aligned}&{\underset {x,u}{\operatorname {maximize} }}&&f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\\&\operatorname {subject\;to} &&\nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)=0\\&&&u_{i}\geq 0,\quad i=1,\dots ,m\end{aligned}}}$

называется двойственной задачей Вульфа. ^[2] Эта задача использует условия KKT в качестве ограничения. Кроме того, ограничение равенства в общем случае нелинейно, поэтому двойственная задача Вульфа может быть невыпуклой задачей оптимизации. В любом случае, слабая двойственность имеет место. ^[3] ${\displaystyle \nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)}$

Смотрите также

• Лагранжева двойственность
• Дуальность Фенхеля

Ссылки

1. Филип Вулф (1961). «Теорема двойственности для нелинейного программирования». Quarterly of Applied Mathematics . 19 (3): 239–244. doi : 10.1090/qam/135625 .
2. "Глава 3. Двойственность в выпуклой оптимизации" (PDF) . 30 октября 2011 г. . Получено 20 мая 2012 г. .
3. Джеффрион, Артур М. (1971). «Двойственность в нелинейном программировании: упрощенная разработка, ориентированная на приложения». Обзор SIAM . 13 (1): 1–37. doi :10.1137/1013001. JSTOR  2028848.