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