Разрыв двойственности
Разрыв двойственности — это разница между прямым и двойственным решениями. Если является оптимальным значением двойственной задачи, а является оптимальным значением прямой задачи, то разрыв двойственности равен . Это значение всегда больше либо равно нулю (для задач минимизации). Разрыв двойственности равен нулю тогда и только тогда, когда имеет место сильная двойственность. В противном случае разрыв строго положителен, и имеет место слабая двойственностьШаблон:Sfn.
Описание
В общем случае пусть дана Шаблон:Не переведено 5 разделённых локально выпуклых пространств и . Тогда, если дана функция , мы можем определить прямую задачу как
Если есть ограничения, они могут быть встроены в функцию путём добавления Шаблон:Не переведено 5 на ограничениях — . Тогда пусть будет Шаблон:Не переведено 5, такой что . Разрыв двойственности — это разность, которая задаётся формулой
где — Шаблон:Не переведено 5 от обоих переменныхШаблон:SfnШаблон:SfnШаблон:Sfn.
Альтернативы
В вычислительной оптимизации часто упоминается другой «разрыв двойственности», который равен разности значений между любым решением и значением допустимого, но подоптимального значения прямой задачи. Этот альтернативный «разрыв двойственности» количественно выражает расхождение между значением текущего допустимого, но подоптимального значения прямой задачи, и значением двойственной задачи. Значение двойственной задачи, по условиям регулярности, равно значению выпуклой релаксации прямой задачи. Выпуклая релаксация — это задача, которая получается путём замены невыпуклого множества допустимых решений на его замкнутую выпуклую оболочку и заменой невыпуклой функции на её выпуклое замыкание, то есть на функцию, надграфик которой является замкнутой выпуклой оболочкой надграфика исходной целевой функции прямой задачи Шаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn.