Розрив двоїстості
Розри́в двої́стості — це різниця між прямим і двоїстим розв'язками. Якщо — оптимальне значення двоїстої задачі, а — оптимальне значення прямої задачі, то розрив двоїстості дорівнює . Це значення завжди більше або дорівнює нулю (для задач мінімізації). Розрив двоїстості дорівнює нулю тоді й лише тоді, коли має місце сильна двоїстість. В іншому випадку розрив строго додатний, і має місце слабка двоїстістьШаблон:Sfn.
Опис
У загальному випадку, нехай дано Шаблон:Не перекладено розділених локально опуклих просторів і . Тоді, якщо дано функцію , можна визначити пряму задачу як
Якщо є обмеження, їх можна вбудувати у функцію , додавши Шаблон:Не перекладено на обмеженнях — . Тоді нехай буде Шаблон:Не перекладено, такою що . Розрив двоїстості — це різниця, яка задається формулою
де — Шаблон:Не перекладено від обох зміннихШаблон:SfnШаблон:SfnШаблон:Sfn.
Альтернативи
В обчислювальній оптимізації часто згадується інший «розрив двоїстості», який дорівнює різниці значень між будь-яким розв'язком і значенням допустимого, але підоптимального значення прямої задачі. Цей альтернативний «розрив двоїстості» кількісно виражає розбіжність між значенням поточного допустимого, але підоптимального значення прямої задачі, і значенням двоїстої задачі. Значення двоїстої задачі, за умовами регулярності, дорівнює значенню опуклої релаксації прямої задачі. Опукла релаксація — це задача, яка виходить після заміни неопуклої множини допустимих розв'язків її замкнутою опуклою оболонкою і заміни неопуклої функції її опуклим замиканням, тобто функцією, надграфік якої є замкнутою опуклою оболонкою надграфіка початкової цільової функції прямої задачіШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn.