Двойственность (оптимизация)

Разрыв двойственности — это разность между значениями любых решений прямой задачи и значениями любых решений двойственной задачи. Если ${\displaystyle d^{*}}$ — оптимальное значение двойственной задачи, а ${\displaystyle p^{*}}$ — оптимальное значение прямой задачи, разрыв двойственности равенo ${\displaystyle p^{*}-d^{*}}$. Это значение всегда больше либо равно 0. Разрыв двойственности равен нулю тогда и только тогда, когда имеет место сильная двойственность. В противном случае разрыв строго положителен и имеет место слабая двойственность[6].

В задачах численной оптимизации часто используется другой «разрыв двойственности», который равен разности между любым двойственным решением и значением допустимой, но не локально оптимальной итерации для прямой задачи. Альтернативный «разрыв двойственности» выражает несоответствие между значением текущего допустимого, но не локально оптимального решения, для прямой задачи и значением двойственной задачи. Значение двойственной задачи равно, при условии регулярности ограничений, значению выпуклому ослаблению прямой задачи, где выпуклое ослабление возникает в результате замены невыпуклого множества допустимых решений его замкнутой выпуклой оболочкой и заменой невыпуклой функции на её выпуклое замыкание, то есть на функцию, надграфик которой является замкнутым выпуклым замыканием исходной целевой функции прямой задачи[7][8][9][10][11][12][13][14][15][16][17].

В линейном случае в прямой задаче, из каждой точки локального оптимума, удовлетворяющей всем ограничениям, существует направление или подпространство направлений и движение в этом направлении увеличивает целевую функцию. Говорят, что движение в любом таком направлении уменьшает зазор между допустимым решением (или допустимым планом) и одним из ограничений. Недопустимое возможное решение — это решение, нарушающее одно или более ограничений.

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

Более подробно о связи прямой и двойственной задач см. в статье «Двойственные задачи линейного программирования».

Если мы понимаем нашу прямую задачу линейного программирования как классическую задачу «распределения ресурсов», двойственную ей задачу можно интерпретировать как задачу «оценки ресурсов».

Если задана задача нелинейного программирования в стандартной форме

минимизировать	${\displaystyle f_{0}(x)}$
при условиях	${\displaystyle f_{i}(x)\leqslant 0,\ i\in \left\{1,\dots ,m\right\}}$
	${\displaystyle h_{i}(x)=0,\ i\in \left\{1,\dots ,p\right\}}$

с областью определения ${\displaystyle {\mathcal {D}}\subset \mathbb {R} ^{n}}$, имеющей непустую внутренность, функция Лагранжа ${\displaystyle \Lambda$ :\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R} } определяется как

${\displaystyle \Lambda (x,\lambda ,\nu )=f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x).}$

Вектора ${\displaystyle \lambda }$ и ${\displaystyle \nu }$ называются двойственными переменными или векторами множителей Лагранжа, связанными с задачей. Двойственная функция Лагранжа ${\displaystyle g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R} }$ определяется как

${\displaystyle g(\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}\Lambda (x,\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}\left(f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x)\right).}$

Двойственная функция g вогнута, даже если начальная задача не выпукла, поскольку она является поточечным инфимумом аффинных функций. Двойственная функция даёт нижние границы оптимального значения ${\displaystyle p^{*}}$ исходной задачи. Для любого ${\displaystyle \lambda \geqslant 0}$ и любого ${\displaystyle \nu }$ имеем ${\displaystyle g(\lambda ,\nu )\leqslant p^{*}}$.

Если выполняется условия регулярности ограничений, такое как условие Слейтера, и исходная задача выпукла, то мы имеем строгую двойственность, то есть ${\displaystyle d^{*}=\max _{\lambda \geqslant 0,\nu }g(\lambda ,\nu )=\inf f_{0}=p^{*}}$.

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

минимизировать	${\displaystyle f(x)}$
при условиях	${\displaystyle g_{i}(x)\leqslant 0,\quad i=1,\dots ,m}$

Лагранжевой двойственной задачей будет

максимизировать	${\displaystyle \inf _{x}\left(f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\right)}$
при условиях	${\displaystyle u_{i}\geqslant 0,\quad i=1,\dots ,m}$

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

максимизировать	${\displaystyle f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)}$
при условиях	${\displaystyle \nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)=0}$
${\displaystyle u_{i}\geqslant 0,\quad i=1,\dots ,m}$

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