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

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

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

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

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

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

{\begin{align}&{\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{align}}

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

{\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] $\nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)$

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

Ссылки

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

Эта статья по прикладной математике – заглушка . Вы можете помочь Википедии, расширив ее.

[Wolfe-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.