Двоїста задача

Двоїстість, або принцип двоїстості, — принцип, за яким задачу оптимізації можна розглядати з двох точок зору, як пряму задачу або двоїсту задачу. Розв'язання двоїстої задачі дає нижню межу прямої задачі (при мінімізації). Однак, у загальному випадку, значення цільових функцій оптимальних розв'язків прямої та двоїстої задач не обов'язково збігаються. Різницю цих значень, якщо вона спостерігається, називають розривом двоїстості. Для задач опуклого програмування розрив двоїстості дорівнює нулю за виконання умов регулярності обмежень.

Двоїста задача

Зазвичай термін «двоїста задача» означає лагранжеву двоїсту задачу, але використовуються й інші двоїсті задачі, наприклад, ^[en] і двоїста задача Фенхеля. Двоїста задача Лагранжа виходить при утворенні лагранжіана, використанні невід'ємних множників Лагранжа для додавання обмежень до цільової функції та мінімізації лагранжіана відносно деяких змінних прямої задачі. Такий розв'язок дає змінні прямої задачі як функції від множників Лагранжа, які називаються двоїстими змінними, так що нова задача стає задачею максимізації цільової функції за двоїстими змінними за породжених обмежень на двоїсті змінні (принаймні, невід'ємність).

У загальному випадку, якщо дано ^[en] відокремлюваних локальних опуклих просторів ${\displaystyle \left(X,X^{*}\right)}$ та функцію ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \}}$, можна визначити пряму задачу як знаходження ${\displaystyle {\hat {x}}}$, такого, що ${\displaystyle f({\hat {x}})=\inf _{x\in X}f(x).\,}$ Іншими словами, ${\displaystyle f({\hat {x}})}$ — це інфімум (точна нижня межа) функції ${\displaystyle f}$.

Якщо є обмеження, їх можна вбудувати у функцію ${\displaystyle f}$, якщо покласти ${\displaystyle {\tilde {f}}=f+I_{\mathrm {constraints} }}$, де ${\displaystyle I}$ — ^[en]. Нехай тепер ${\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \}}$ (для іншої двоїстої пари ${\displaystyle \left(Y,Y^{*}\right)}$) буде ^[en], такою що ${\displaystyle F(x,0)={\tilde {f}}(x)}$.

Розрив двоїстості — це різниця правої та лівої частин нерівності

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

де ${\displaystyle F^{*}}$ — спряжена функція від обох змінних, а ${\displaystyle \sup }$ означає супремум (точна верхня межа).

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

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

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

Лінійний випадок

Задачі лінійного програмування — це завдачі оптимізації, в яких цільова функція та обмеження лінійні. У прямій задачі цільова функція є лінійною комбінацією n змінних. Є m обмежень, кожне з яких обмежує зверху лінійну комбінацію n змінних. Ціль — максимізувати значення цільової функції при обмеженнях. Розв'язок — це вектор (список) із n значень, що дає максимальне значення цільової функції.

У двоїстій задачі цільова функція є лінійною комбінацією m значень, які є правими частинами m обмежень прямої задачі. Є n двоїстих обмежень, кожне з яких обмежує знизу лінійну комбінацію m двоїстих змінних.

Зв'язок між прямою та двоїстою задачами

У лінійному випадку в прямій задачі, з кожної точки локального оптимуму, що задовольняє всім обмеженням, існує напрямок або підпростір напрямків і рух у цьому напрямку збільшує цільову функцію. Кажуть, що рух у будь-якому такому напрямку зменшує зазор між допустимим розв'язком (або допустимим планом) та одним із обмежень. Недопустимий можливий розв'язок — це розв'язок, що порушує одне чи більше обмежень.

У двоїстій задачі елементи двоїстого вектора множиться на стовпці, які відповідають обмеженням у прямій задачі. Збурення двоїстого вектора у двоїстій задачі еквівалентне перегляду верхньої межі прямої задачі. При розв'язуванні двоїстої задачі шукається найменша верхня межа, тобто двоїстий вектор змінюється так, щоб зменшити зазор між допустимим розв'язком та дійсним оптимумом.

Докладніше про зв'язок прямої та двоїстої задач див. розділ у статті «Лінійне програмування».

Економічна інтерпретація

Якщо ми розуміємо нашу пряму задачу лінійного програмування як класичну задачу «розподілу ресурсів», двоїсту задачу можна інтерпретувати як задачу ^[en]».

Нелінійний випадок

У нелінійному програмуванні обмеження необов'язково лінійні. Однак, багато принципів лінійного випадку застосовні.

Щоб забезпечити, щоб глобальний максимум нелінійної задачі міг бути визначений просто, у формулюванні задачі часто потрібно, щоб функції були опуклими і мали компактні множини нижніх рівнів (тобто множини, на яких функція набуває значень, менших від певного рівня).

У цьому полягає умова Каруша — Куна — Таккера. Вони довели необхідні умови визначення локального оптимуму нелінійних задач. Існують додаткові умови (умова регулярності обмежень), які необхідні для визначення напрямку на оптимальний розв'язок. Тут оптимальний розв'язок — це один із локальних оптимумів, який, можливо, не є глобальним.

Строгий принцип Лагранжа: двоїстість Лагранжа

Якщо задано задачу нелінійного програмування у стандартній формі

мінімізувати	${\displaystyle f_{0}(x)}$
за умов	${\displaystyle f_{i}(x)\leqslant 0,\ i\in \left\{1,\dots ,m\right\}}$
	${\displaystyle h_{i}(x)=0,\ i\in \left\{1,\dots ,p\right\}}$

з областю визначення ${\displaystyle {\mathcal {D}}\subset \mathbb {R} ^{n}}$, що має непорожню внутрішність, функція Лагранжа ${\displaystyle \Lambda :\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R} }$ визначається як

${\displaystyle \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).}$

Вектори ${\displaystyle \lambda }$ і ${\displaystyle \nu }$ називають двоїстими змінними або векторами множників Лагранжа, пов'язаними із задачею. Двоїста функція Лагранжа ${\displaystyle g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R} }$ визначається як

${\displaystyle 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 увігнута, навіть якщо початкова задача не опукла, оскільки вона є поточковим інфімумом афінних функцій. Двоїста функція дає нижні межі оптимального значення ${\displaystyle p^{*}}$ початкової задачі. Для будь-якого ${\displaystyle \lambda \geqslant 0}$ та будь-якого ${\displaystyle \nu }$ маємо ${\displaystyle g(\lambda ,\nu )\leqslant p^{*}}$.

Якщо виконуються умови регулярності обмежень, такі як умова Слейтера, і початкова задача опукла, ми маємо сильну двоїстість, тобто ${\displaystyle d^{*}=\max _{\lambda \geqslant 0,\nu }g(\lambda ,\nu )=\inf f_{0}=p^{*}}$.

Опуклі задачі

Для задачі опуклої мінімізації з обмеженнями-нерівностями,

мінімізувати	${\displaystyle f(x)}$
за умов	${\displaystyle g_{i}(x)\leqslant 0,\quad i=1,\dots ,m}$

Лагранжевою двоїстою задачею буде

максимізувати	${\displaystyle \inf _{x}\left(f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\right)}$
за умов	${\displaystyle u_{i}\geqslant 0,\quad i=1,\dots ,m}$

де цільовою функцією є двоїста функція Лагранжа. Якщо відомо, що функції ${\displaystyle f}$ і ${\displaystyle g_{1},\cdots ,g_{m}}$ неперервно диференційовні, інфімум перебуває в точках, де градієнт дорівнює нулю. Задача

максимізувати	${\displaystyle f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)}$
за умов	${\displaystyle \nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)=0}$
${\displaystyle u_{i}\geqslant 0,\quad i=1,\dots ,m}$

називається двоїстою задачею Вулфа. Ця задача обчислювально може виявитися складною, оскільки цільова функція не опукла в координатах ${\displaystyle (u,x)}$. Також обмеження ${\displaystyle \nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)}$, у загальному випадку, нелінійне, отже двоїста задача Вулфа, зазвичай, є неопуклою задачею оптимізації. У кожному разі має місце слабка двоїстість.

Історія

За Джорджом Данцігом, теорему двоїстості для лінійної оптимізації висловив як гіпотезу Джон фон Нейман відразу після того, як Данціг представив задачу лінійного програмування. Фон Нейман помітив, що той використав інформацію з його теорії ігор і висловив припущення, що матрична гра двох осіб із нульовою сумою еквівалентна задачі лінійного програмування. Строге доведення цього факту вперше опублікували 1948 року ^[en] і його група.

Див. також

• ^[en]

Примітки

1. Boyd, Vandenberghe, 2004.
2. Двоїста пара — це трійка ${\displaystyle \left(X,X^{*},\langle ,\rangle \right)}$, де ${\displaystyle X}$ — векторний простір над полем ${\displaystyle F}$, ${\displaystyle X^{*}}$ — множина всіх лінійних відображень ${\displaystyle \phi \colon X\to F}$, а третій елемент — білінійна форма ${\displaystyle X^{*}\times X\to F\colon (\phi ,x)\mapsto \phi (x)}$ .
3. Boţ, Wanka, Grad, 2009.
4. Csetnek, 2010.
5. Zălinescu, 2002, с. 106–113.
6. Borwein, Zhu, 2005.
7. Ahuja, Magnanti, Orlin, 1993.
8. Bertsekas, Nedic, Ozdaglar, 2003.
9. Bertsekas, 1999.
10. Bertsekas, 2009.
11. Bonnans, Gilbert, Lemaréchal, Sagastizábal, 2006, с. xiv+490.
12. Hiriart-Urruty, Lemaréchal, 1993, с. xviii+417.
13. Hiriart-Urruty, Lemaréchal, 1993, с. xviii+346.
14. Lasdon, 2002, с. xiii+523.
15. Lemaréchal, 2001, с. 112–156.
16. Minoux, 1986, с. xxviii+489.
17. Shapiro, 1979, с. xvi+388.
18. Geoffrion, 1971, с. 1–37.
19. 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]) — .
• 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]) — .
• Leon S. Lasdon. Optimization theory for large systems = Reprint of the 1970 Macmillan. — Mineola, New York : Dover Publications, Inc, 2002. — С. xiii+523. — .
• 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)) — . — 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. — .
  • М. Мину. Математическое программирование. Теория и алгоритмы.
• Evar D. Nering, Albert W. Tucker. Linear Programming and Related Problems. — Boston, MA : Academic Press, 1993. — .
• Stephen P. Boyd, Lieven Vandenberghe. Convex Optimization. — Cambridge University Press, 2004. — . Архівовано з джерела 13 липня 2017
• 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. — .
• Constantin Zălinescu. Convex analysis in general vector spaces. — River Edge, NJ : World Scientific Publishing Co., Inc, 2002. — С. 106–113. — .
• Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Network Flows: Theory, Algorithms and Applications. — Prentice Hall, 1993. — .
• Dimitri Bertsekas, Angelia Nedic, Asuman Ozdaglar. Convex Analysis and Optimization. — Athena Scientific, 2003. — .
• Dimitri P. Bertsekas. Nonlinear Programming. — 2nd. — Athena Scientific, 1999. — .
• Dimitri P. Bertsekas. Convex Optimization Theory. — Athena Scientific, 2009. — .
• 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) — . — DOI:10.1007/978-3-540-35447-5. Архівовано з джерела 19 липня 2013
• Jeremy F. Shapiro. Mathematical programming: Structures and algorithms. — New York : Wiley-Interscience [John Wiley & Sons], 1979. — С. xvi+388. — .
• Jonathan Borwein, Qiji Zhu. Techniques of Variational Analysis. — Springer, 2005. — .

Статті

• Duality in Linear Programming [Архівовано 23 квітня 2021 у Wayback Machine.] Gary D. Knott (англ.)
• Arthur M. Geoffrion. Duality in Nonlinear Programming: A Simplified Applications-Oriented Development // SIAM Review. — 1971. — Т. 13, вип. 1. — DOI:10.1137/1013001.

Додаткова література

• William J. Cook,William H. Cunningham, William R. Pulleyblank, Alexander Schrijver. Combinatorial Optimization. — 1st. — John Wiley & Sons, 1997. — .
• 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. Архівовано з джерела 3 січня 2017. Процитовано 27 квітня 2022.
• 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. — .
• Andrzej Piotr Ruszczyński. Nonlinear Optimization. — Princeton, NJ : Princeton University Press, 2006. — С. xii+454. — .
• Christos H. Papadimitriou, Kenneth Steiglitz. Combinatorial Optimization : Algorithms and Complexity. — Dover, 1998. — .
• Krzysztof C. Kiwiel, Torbjörn Larsson, P. O. Lindberg. Lagrangian relaxation via ballstep subgradient methods // Mathematics of Operations Research. — 2007. — Т. 32, вип. 3 (August). — С. 669–686. — DOI:10.1287/moor.1070.0261. Архівовано з джерела 26 липня 2011. Процитовано 27 квітня 2022.