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

В математическая оптимизация, Двойственность Вульфа, названный в честь Филип Вулф, это тип двойная проблема в которой целевая функция и ограничения все дифференцируемые функции. Используя эту концепцию, можно найти нижнюю границу для задачи минимизации из-за слабая двойственность принцип.^[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] Эта проблема использует Условия ККТ как ограничение. Кроме того, ограничение равенства ${\displaystyle \nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)}$ в общем случае нелинейна, поэтому двойственная задача Вульфа может быть невыпуклой задачей оптимизации. В любом случае имеет место слабая двойственность.^[3]

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

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

Рекомендации

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