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

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

ОписаниеПравить

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

$\underset{x\in <!--\; \in \; -->X}{inf}f(x).$$\inf _{x\in X}f(x).\,$ 

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

$\underset{x\in <!--\; \in \; -->X}{inf}[F(x,0)]-<!--\; -\; -->\underset{y^{\ast <!--\; \ast \; -->}\in <!--\; \in \; -->Y^{\ast <!--\; \ast \; -->}}{sup}[-<!--\; -\; -->F^{\ast <!--\; \ast \; -->}(0,y^{\ast <!--\; \ast \; -->})]$$\inf _{x\in X}[F(x,0)]-\sup _{y^{*}\in Y^{*}}[-F^{*}(0,y^{*})]$ 

где $F^{\ast <!--\; \ast \; -->}$$F^{*}$  — сопряжённой функцией^[en] от обоих переменных.

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

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

ЛитератураПравить

• 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.