Розрив двоїстості

Розри́в двої́стості — це різниця між прямим і двоїстим розв'язками. Якщо ${\displaystyle d^{*}}$ — оптимальне значення двоїстої задачі, а ${\displaystyle p^{*}}$ — оптимальне значення прямої задачі, то розрив двоїстості дорівнює ${\displaystyle p^{*}-d^{*}}$. Це значення завжди більше або дорівнює нулю (для задач мінімізації). Розрив двоїстості дорівнює нулю тоді й лише тоді, коли має місце сильна двоїстість. В іншому випадку розрив строго додатний, і має місце слабка двоїстість.

Опис

У загальному випадку, нехай дано ^[en] розділених локально опуклих просторів ${\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}$, додавши ^[en] ${\displaystyle I}$ на обмеженнях — ${\displaystyle f=f+I}$. Тоді нехай ${\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \}}$ буде ^[en], такою що ${\displaystyle F(x,0)=f(x)}$. Розрив двоїстості — це різниця, яка задається формулою

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

де ${\displaystyle F^{*}}$ — ^[en] від обох змінних.

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

В обчислювальній оптимізації часто згадується інший «розрив двоїстості», який дорівнює різниці значень між будь-яким розв'язком і значенням допустимого, але підоптимального значення прямої задачі. Цей альтернативний «розрив двоїстості» кількісно виражає розбіжність між значенням поточного допустимого, але підоптимального значення прямої задачі, і значенням двоїстої задачі. Значення двоїстої задачі, за умовами регулярності, дорівнює значенню опуклої релаксації прямої задачі. Опукла релаксація — це задача, яка виходить після заміни неопуклої множини допустимих розв'язків її замкнутою опуклою оболонкою і заміни неопуклої функції її опуклим замиканням, тобто функцією, надграфік якої є замкнутою опуклою оболонкою надграфіка початкової цільової функції прямої задачі.

Примітки

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. — .
• Radu Ioan Boţ, Gert Wanka, Sorin-Mihai Grad. Duality in Vector Optimization. — Springer, 2009. — .
• 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. — .
• Zălinescu C. Convex analysis in general vector spaces. — River Edge, NJ : World Scientific Publishing Co. Inc, 2002. — .
• Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Network Flows: Theory, Algorithms and Applications. — Prentice Hall, 1993. — .
• Dimitri P. Bertsekas. Nonlinear Programming. — 2nd. — Athena Scientific, 1999. — .
• 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) — . — 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]) — .
• 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]) — . — DOI:10.1007/978-3-662-06409-2_4.
• Leon S. Lasdon. Optimization theory for large systems = Reprint of the 1970 Macmillan. — Mineola, New York : Dover Publications, Inc, 2002. — .
• 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)) — . — 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. — . Перевод книги
  • Programmation mathématique : Théorie et algorithmes. — 2nd. — Paris : Tec & Doc, 2008. — С. xxx+711 pp. — .
• Jeremy F. Shapiro. Mathematical programming: Structures and algorithms. — New York : Wiley-Interscience [John Wiley & Sons], 1979. — .