Двоїстість (оптимізація)

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

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

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

У загальному випадку, якщо дано двоїсту пару^[en][2] відокремлюваних локальних опуклих просторів ${\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)}$^[3].

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

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

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

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

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

У задачах чисельної оптимізації часто використовують інший «розрив двоїстості», який дорівнює різниці між будь-яким двоїстим розв'язком та значенням допустимої, але не локально оптимальної ітерації для прямої задачі. Альтернативний «розрив двоїстості» виражає невідповідність між значенням поточного допустимого, але не локально оптимального розв'язку, для прямої задачі та значенням двоїстої задачі. Значення двоїстої задачі дорівнює, за умови регулярності обмежень, значенню опуклого ослаблення прямої задачі, де опукле ослаблення виникає внаслідок заміни неопуклої множини допустимих розв'язків його замкнутою опуклою оболонкою і заміною непуклої функції її опуклим замиканням, тобто замиканням початкової цільової функції прямої задачі^{[7][8][9][10][11][12][13][14][15][16][17]}.

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

Задачі лінійного програмування — це завдачі оптимізації, в яких цільова функція та обмеження лінійні. У прямій задачі цільова функція є лінійною комбінацією 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)}$, у загальному випадку, нелінійне, отже двоїста задача Вулфа, зазвичай, є неопуклою задачею оптимізації. У кожному разі має місце слабка двоїстість^[18].

Історія

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

Див. також

• Ослаблення (апроксимація)^[en]