Двойственность (оптимизация) (:fkwvmfyuukvm, (khmnbn[genx))

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

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

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

В общем случае, если дана двойственная пара^[англ.]^[2] отделимого локального выпуклого пространства $\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)$ ^[3].

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

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

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

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

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

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

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

Задачи линейного программирования — это задачи оптимизации, в которых целевая функция и ограничения^[англ.] линейны. В прямой задаче целевая функция является линейной комбинацией 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)$ , в общем случае, нелинейно, так что двойственная задача Вулфа, обычно, является невыпуклой задачей оптимизации. В любом случае имеет место слабая двойственность^[18].

История

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

См. также

Примечания

↑ Boyd, Vandenberghe, 2004.
↑ Двойственная пара — это тройка $\left(X,X^{*},\langle ,\rangle \right)$ , где $X$ — векторное пространств над полем $F$ , $X^{*}$ — множество всех линейных отображений $\phi \colon X\to F$ , а третий элемент — билинейная форма $X^{*}\times X\to F\colon (\phi ,x)\mapsto \phi (x)$ .
↑ ¹ ² Boţ, Wanka, Grad, 2009.
↑ Csetnek, 2010.
↑ Zălinescu, 2002, с. 106–113.
↑ Borwein, Zhu, 2005.
↑ Ahuja, Magnanti, Orlin, 1993.
↑ Bertsekas, Nedic, Ozdaglar, 2003.
↑ Bertsekas, 1999.
↑ Bertsekas, 2009.
↑ Bonnans, Gilbert, Lemaréchal, Sagastizábal, 2006, с. xiv+490.
↑ Hiriart-Urruty, Lemaréchal, 1993, с. xviii+417.
↑ Hiriart-Urruty, Lemaréchal, 1993, с. xviii+346.
↑ Lasdon, 2002, с. xiii+523.
↑ Lemaréchal, 2001, с. 112–156.
↑ Minoux, 1986, с. xxviii+489.
↑ Shapiro, 1979, с. xvi+388.
↑ Geoffrion, 1971, с. 1–37.
↑ Nering, Tucker, 1993, с. предисловие Данцига.

Литература

Книги

Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal. Convex analysis and minimization algorithms. Часть I: Fundamentals. — Berlin: Springer-Verlag, 1993. — Т. 305. — С. xviii+417. — (Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]). — ISBN 3-540-56850-6.
Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal. 14 Duality for Practitioners // Convex analysis and minimization algorithms. Часть II: Advanced theory and bundle methods. — Berlin: Springer-Verlag, 1993. — Т. 306. — С. xviii+346. — (Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]). — ISBN 3-540-56852-2.
Leon S. Lasdon. Optimization theory for large systems. — Mineola, New York: Dover Publications, Inc., 2002. — С. xiii+523. — ISBN 978-0-486-41999-2.
Claude Lemaréchal. Lagrangian relaxation // Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. — Berlin: Springer-Verlag, 2001. — Т. 2241. — С. 112–156. — (Lecture Notes in Computer Science (LNCS)). — ISBN 3-540-42877-1. — doi:10.1007/3-540-45586-8_4.
Michel Minoux. Mathematical programming: Theory and algorithms. — Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd., 1986. — С. xxviii+489. — ISBN 0-471-90170-9.
- М. Мину. Математическое программирование. Теория и алгоритмы.
Evar D. Nering, Albert W. Tucker. Linear Programming and Related Problems. — Boston, MA: Academic Press, 1993. — ISBN 978-0-12-515440-6.
Stephen P. Boyd, Lieven Vandenberghe. Convex Optimization. — Cambridge University Press, 2004. — ISBN 978-0-521-83378-3.
Radu Ioan Boţ, Gert Wanka, Sorin-Mihai Grad. Duality in Vector Optimization. — Springer, 2009. — ISBN 978-3-642-02885-4.
Ernö Robert Csetnek. Overcoming the failure of the classical generalized interior-point regularity conditions in convex optimization. Applications of the duality theory to enlargements of maximal monotone operators. — Logos Verlag Berlin GmbH, 2010. — ISBN 978-3-8325-2503-3.
Constantin Zălinescu. Convex analysis in general vector spaces. — River Edge, NJ: World Scientific Publishing Co., Inc., 2002. — С. 106–113. — ISBN 981-238-067-1.
Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Network Flows: Theory, Algorithms and Applications. — Prentice Hall, 1993. — ISBN 0-13-617549-X.
Dimitri Bertsekas, Angelia Nedic, Asuman Ozdaglar. Convex Analysis and Optimization. — Athena Scientific, 2003. — ISBN 1-886529-45-0.
Dimitri P. Bertsekas. Nonlinear Programming. — 2nd. — Athena Scientific, 1999. — ISBN 1-886529-00-0.
Dimitri P. Bertsekas. Convex Optimization Theory. — Athena Scientific, 2009. — ISBN 978-1-886529-31-1.
J. Frédéric Bonnans, J. Charles Gilbert, Claude Lemaréchal, Claudia A. Sagastizábal. Numerical optimization: Theoretical and practical aspects. — Second revised ed. of translation of 1997. — Berlin: Springer-Verlag, 2006. — С. xiv+490. — (Universitext). — ISBN 3-540-35445-X. — doi:10.1007/978-3-540-35447-5.
Jeremy F. Shapiro. Mathematical programming: Structures and algorithms. — New York: Wiley-Interscience [John Wiley & Sons], 1979. — С. xvi+388. — ISBN 0-471-77886-9.
Jonathan Borwein, Qiji Zhu. Techniques of Variational Analysis. — Springer, 2005. — ISBN 978-1-4419-2026-3.

Статьи

Duality in Linear Programming Gary D. Knott
Arthur M. Geoffrion. Duality in Nonlinear Programming: A Simplified Applications-Oriented Development // SIAM Review. — 1971. — Т. 13, вып. 1. — doi:10.1137/1013001. — JSTOR 2028848.

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

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.

[_98a1133c19e48b84-1] Boyd, Vandenberghe, 2004.

[2] Двойственная пара — это тройка $\left(X,X^{*},\langle ,\rangle \right)$ , где $X$ — векторное пространств над полем $F$ , $X^{*}$ — множество всех линейных отображений $\phi \colon X\to F$ , а третий элемент — билинейная форма $X^{*}\times X\to F\colon (\phi ,x)\mapsto \phi (x)$ .

[_8b41c46d048fe46f-3] ¹ ² Boţ, Wanka, Grad, 2009.

[_9e2bbebd6b37a601-4] Csetnek, 2010.

[_150f5072fba39540-5] Zălinescu, 2002, с. 106–113.

[_a33fd6bb11432c7f-6] Borwein, Zhu, 2005.

[_3e7e0d20dcfd3fa9-7] Ahuja, Magnanti, Orlin, 1993.

[_6bdd65ff80cda579-8] Bertsekas, Nedic, Ozdaglar, 2003.

[_d046438f55e4775f-9] Bertsekas, 1999.

[_cbc6bb2ff592af24-10] Bertsekas, 2009.

[_1cbc0cba916cdfea-11] Bonnans, Gilbert, Lemaréchal, Sagastizábal, 2006, с. xiv+490.

[_52f1941159c99701-12] Hiriart-Urruty, Lemaréchal, 1993, с. xviii+417.

[_5302971159d80fb4-13] Hiriart-Urruty, Lemaréchal, 1993, с. xviii+346.

[_1c5f26e7a957805a-14] Lasdon, 2002, с. xiii+523.

[_aa34c4510de8552e-15] Lemaréchal, 2001, с. 112–156.

[_9b5f5f0ecf659754-16] Minoux, 1986, с. xxviii+489.

[_b20d2b60ec49a714-17] Shapiro, 1979, с. xvi+388.

[_d4131e4854166bdc-18] Geoffrion, 1971, с. 1–37.

[_734442fe2e00e1a6-19] Nering, Tucker, 1993, с. предисловие Данцига.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]