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

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

Описание

В общем случае пусть дана двойственная пара^[англ.] разделённых локально выпуклых пространств ${\displaystyle \left(X,X^{*}\right)}$ и ${\displaystyle \left(Y,Y^{*}\right)}$. Тогда, если дана функция ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \}}$, мы можем определить прямую задачу как

${\displaystyle \inf _{x\in X}f(x).\,}$

Если есть ограничения, они могут быть встроены в функцию ${\displaystyle f}$ путём добавления индикаторной функции^[англ.] ${\displaystyle I}$ на ограничениях — ${\displaystyle f=f+I}$. Тогда пусть ${\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \}}$ будет функцией возмущений^[англ.], такой что ${\displaystyle F(x,0)=f(x)}$. Разрыв двойственности — это разность, которая задаётся формулой

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

где ${\displaystyle F^{*}}$ — сопряжённой функцией^[англ.] от обоих переменных[2][3][4].

Альтернативы

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

Примечания

1. Borwein, Zhu, 2005.
2. Boţ, Wanka, Grad, 2009.
3. Csetnek, 2010.
4. Zălinescu, 2002, с. 106–113.
5. Ahuja, Magnanti, Orlin, 1993.
6. Bertsekas, 1999.
7. Bonnans, Gilbert, Lemaréchal, Sagastizábal, 2006, с. xiv+490.
8. Hiriart-Urruty, Lemaréchal, 1993, с. xviii+417.
9. Hiriart-Urruty, Lemaréchal, 1993, с. xviii+346.
10. Lasdon, 2002, с. xiii+523.
11. Lemaréchal, 2001, с. 112–156.
12. Minoux, 1986, с. xxviii+489.
13. Shapiro, 1979, с. xvi+388.

Литература

• Jonathan Borwein, Qiji Zhu. Techniques of Variational Analysis. — Springer, 2005. — ISBN 978-1-4419-2026-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.
• Zălinescu C. Convex analysis in general vector spaces. — River Edge, NJ: World Scientific Publishing Co. Inc, 2002. — 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 P. Bertsekas. Nonlinear Programming. — 2nd. — Athena Scientific, 1999. — ISBN 1-886529-00-0.
• 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 French. — Berlin: Springer-Verlag, 2006. — (Universitext). — ISBN 3-540-35445-X. — doi:10.1007/978-3-540-35447-5.
• Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal. Convex analysis and minimization algorithms, Volume I: Fundamentals. — Berlin: Springer-Verlag, 1993. — Т. 305. — (Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]). — ISBN 3-540-56850-6.
• Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal. XII. Abstract Duality for Practitioners // Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods. — Berlin: Springer-Verlag, 1993. — Т. 306. — (Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]). — ISBN 3-540-56852-2. — doi:10.1007/978-3-662-06409-2_4.
• Leon S. Lasdon. Optimization theory for large systems. — Mineola, New York: Dover Publications, Inc., 2002. — 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 / Michael Jünger, Denis Naddef. — Berlin: Springer-Verlag, 2001. — Т. 2241. — (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 / Egon Balas (forward); Steven Vajda (trans) from the (1983 Paris: Dunod). — Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd., 1986. — ISBN 0-471-90170-9. Перевод книги
  • Programmation mathématique : Théorie et algorithmes. — 2nd. — Paris: Tec & Doc, 2008. — С. xxx+711 pp.. — ISBN 978-2-7430-1000-3.
• Jeremy F. Shapiro. Mathematical programming: Structures and algorithms. — New York: Wiley-Interscience [John Wiley & Sons], 1979. — ISBN 0-471-77886-9.