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

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

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

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

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

лагранжева двойственная задача

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

где целевая функция представляет собой двойственную функцию Лагранжа. При условии, что функции $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}}$

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

См. также

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