Разрыв двойственности

В задачах оптимизации прикладной математики представляет разрыв двойственности собой разницу между основным и двойственным решениями . Если $d^{*}$ является оптимальным двойным значением и $p^{*}$ является оптимальным исходным значением, то разрыв двойственности равен $p^{*}-d^{*}$. Это значение всегда больше или равно 0 (для задач минимизации). Разрыв двойственности равен нулю тогда и только тогда, когда имеет место сильная двойственность . В противном случае разрыв строго положителен и сохраняется слабая двойственность .

В общем случае даны две двойственные пары, разделяющие локально выпуклые пространства. $\left(X,X^{*}\right)$ и $\left(Y,Y^{*}\right)$. Тогда, учитывая функцию $f:X\to \mathbb {R} \cup \{+\infty \}$, мы можем определить основную проблему как

$\inf _{x\in X}f(x).\,$

Если существуют условия ограничения, их можно встроить в функцию $f$ позволяя $f=f+I_{\text{constraints}}$ где $I$ – индикаторная функция . Тогда пусть $F:X\times Y\to \mathbb {R} \cup \{+\infty \}$ — функция возмущения такая, что $F(x,0)=f(x)$. — Разрыв двойственности это разница, определяемая выражением

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

где $F^{*}$ является выпуклым сопряжением по обеим переменным.

В вычислительной оптимизации часто сообщается о другом «разрыве двойственности», который представляет собой разницу в ценности между любым двойственным решением и ценностью возможной, но неоптимальной итерации для основной проблемы. Этот альтернативный «разрыв двойственности» количественно определяет несоответствие между значением текущей осуществимой, но неоптимальной итерации для основной проблемы и ценностью двойственной проблемы; значение двойственной задачи в условиях регулярности равно значению выпуклой релаксации основной задачи: Выпуклая релаксация — это задача, возникающая при замене невыпуклого допустимого множества на его замкнутую выпуклую оболочку и при замене невыпуклого выпуклая функция с ее выпуклым замыканием , то есть функция, надграфик которой представляет собой замкнутую выпуклую оболочку исходной первичной целевой функции.