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

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

Двойственная задача

Обычно термин «двойственная задача» предполагает лагранжеву двойственную задачу, но используются и другие двойственные задачи, например, двойственная задача Вулфа и двойственная задача Фенхеля. Двойственная задача Лагранжа получается при образовании лагранжиана, использовании неотрицательных множителей Лагранжа для добавления ограничений к целевой функции и минимизации лагранжиана относительно некоторых переменных прямой задачи. Такое решение даёт переменные прямой задачи как функции от множителей Лагранжа, которые называются двойственными переменными, так что новая задача становится задачей максимизации целевой функции по двойственным переменным при порождённых ограничениях на двойственные переменные (по меньшей мере, неотрицательность).

В общем случае, если дана двойственная пара отделимого локального выпуклого пространства $\left(X,X^{*}\right)$ и функция $f:X\to \mathbb {R} \cup \{+\infty \}$, мы можем определить прямую задачу как нахождение ${\hat {x}}$, такого, что $f({\hat {x}})=\inf _{x\in X}f(x).\,$ Другими словами, $f({\hat {x}})$ — это инфимум (точная нижняя граница) функции $f$.

Если имеются ограничения, они могут быть встроены в функцию $f$, если положить ${\tilde {f}}=f+I_{\mathrm {constraints} }$, где $I$ — индикаторная функция. Пусть теперь $F:X\times Y\to \mathbb {R} \cup \{+\infty \}$ (для другой двойственной пары $\left(Y,Y^{*}\right)$) будет функцией возмущений, такой что $F(x,0)={\tilde {f}}(x)$.

Разрыв двойственности — это разность правой и левой частей неравенства

$\sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leqslant \inf _{x\in X}F(x,0),\,$

где $F^{*}$ — сопряжённая функция от обоих переменных, а $\sup$ означает супремум (точную верхнюю границу).

Разрыв двойственности

Основная статья: Разрыв двойственности

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

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

Линейный случай

Основная статья: Двойственная задача линейного программирования

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

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

Связь между прямой и двойственной задачами

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

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

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

Экономическая интерпретация

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

Нелинейный случай

В нелинейном программировании ограничения не обязательно линейны. Тем не менее, многие принципы линейного случая применимы.

Чтобы обеспечить, чтобы глобальный максимум нелинейной задачи мог быть определён просто, в формулировке задачи часто требуется, чтобы функции были выпуклы и имели компактные множества нижних уровней (то есть множеств, на которых функция принимает значение, меньшее некоторого уровня).

В этом заключается условие Каруша — Куна — Таккера. Они доказали необходимые условия для определения локального оптимума нелинейных задач. Существуют дополнительные условия (условие регулярности ограничений), которые необходимы, чтобы определить направление на оптимальное решение. Здесь оптимальное решение — это одно из локальных оптимумов, которое, возможно, не является глобальным.

Строгий принцип Лагранжиана: Двойственность Лагранжа

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

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

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

$\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).$

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

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

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

Выпуклые задачи

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

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

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

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

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

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

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

История

Согласно Джорджу Данцигу теорема двойственности для линейной оптимизации была высказана в качестве гипотезы Джоном фон Нейманом сразу после того, как Данциг представил задачу линейного программирования. Фон Нейман заметил, что он использовал информацию из его теории игр и высказал предположение, что матричная игра двух лиц с нулевой суммой эквивалентна задаче линейного программирования. Строгое доказательство этого факта было впервые опубликовано в 1948 году Альбертом Такером и его группой.

См. также

• Принцип двойственности
• Ослабление (аппроксимация)

Литература для дополнительного чтения

• William J. Cook,William H. Cunningham, William R. Pulleyblank, Alexander Schrijver. Combinatorial Optimization. — 1st. — John Wiley & Sons, 1997. — ISBN 0-471-55894-X.
• Xugang Ye, Shih-Ping Han, Anhua Lin. A Note on the Connection between Primal-Dual and the A* Algorithms // International Journal of Operations Research and Information Systems. — 2010. — Т. 1, вып. 1. — С. 73–85.
• George B. Dantzig. Linear Programming and Extensions. — Princeton, NJ: Princeton University Press, 1963.
• Eugene Lawler. 4.5. Combinatorial Implications of Max-Flow Min-Cut Theorem, 4.6. Linear Programming Interpretation of Max-Flow Min-Cut Theorem // Combinatorial Optimization: Networks and Matroids. — Dover, 2001. — С. 117–120. — ISBN 0-486-41453-1.
• Andrzej Piotr Ruszczyński. Nonlinear Optimization. — Princeton, NJ: Princeton University Press, 2006. — С. xii+454. — ISBN 978-0691119151.
• Christos H. Papadimitriou, Kenneth Steiglitz. Combinatorial Optimization : Algorithms and Complexity. — Dover, 1998. — ISBN 0-486-40258-4.
• Krzysztof C. Kiwiel, Torbjörn Larsson, P. O. Lindberg. Lagrangian relaxation via ballstep subgradient methods // Mathematics of Operations Research. — 2007. — Август (т. 32, вып. 3). — С. 669–686. — doi:10.1287/moor.1070.0261.