Розрив двоїстості
Розри́в двої́стості — це різниця між прямим і двоїстим розв'язками. Якщо — оптимальне значення двоїстої задачі, а — оптимальне значення прямої задачі, то розрив двоїстості дорівнює . Це значення завжди більше або дорівнює нулю (для задач мінімізації). Розрив двоїстості дорівнює нулю тоді й лише тоді, коли має місце сильна двоїстість. В іншому випадку розрив строго додатний, і має місце слабка двоїстість[1].
У загальному випадку, нехай дано двоїсту пару[en] розділених локально опуклих просторів і . Тоді, якщо дано функцію , можна визначити пряму задачу як
Якщо є обмеження, їх можна вбудувати у функцію , додавши індикаторну функцію[en] на обмеженнях — . Тоді нехай буде функцією збурень[en], такою що . Розрив двоїстості — це різниця, яка задається формулою
де — спряжена функція[en] від обох змінних[2][3][4].
В обчислювальній оптимізації часто згадується інший «розрив двоїстості», який дорівнює різниці значень між будь-яким розв'язком і значенням допустимого, але підоптимального значення прямої задачі. Цей альтернативний «розрив двоїстості» кількісно виражає розбіжність між значенням поточного допустимого, але підоптимального значення прямої задачі, і значенням двоїстої задачі. Значення двоїстої задачі, за умовами регулярності, дорівнює значенню опуклої релаксації прямої задачі. Опукла релаксація — це задача, яка виходить після заміни неопуклої множини допустимих розв'язків її замкнутою опуклою оболонкою і заміни неопуклої функції її опуклим замиканням, тобто функцією, надграфік якої є замкнутою опуклою оболонкою надграфіка початкової цільової функції прямої задачі[5][6][7][8][9][10][11][12][13].
- ↑ Borwein, Zhu, 2005.
- ↑ Boţ, Wanka, Grad, 2009.
- ↑ Csetnek, 2010.
- ↑ Zălinescu, 2002, с. 106–113.
- ↑ Ahuja, Magnanti, Orlin, 1993.
- ↑ Bertsekas, 1999.
- ↑ 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.
- 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:
- 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:
- Leon S. Lasdon. Optimization theory for large systems = Reprint of the 1970 Macmillan. — 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:
- 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.