双対ギャップ

双対ギャップ（そうついギャップ、英: duality gap）とは、応用数学の数理最適化におけるある主問題と双対問題の最適値の差を指す。${\displaystyle d^{*}}$ を双対問題の最適値とし、${\displaystyle p^{*}}$ を主問題の最適値としたとき、双対ギャップは ${\displaystyle p^{*}-d^{*}}$ と等価である。（最小化問題に対する）双対ギャップは常に ${\displaystyle 0}$ かそれ以上となる。強双対性が成り立つとき、双対ギャップはゼロとなる。強双対性が成り立たないときは弱双対性が成り立ち、双対ギャップは厳密に正の値となる^[1]。

一般的に、局所凸空間で分離された双対組 ${\displaystyle \left(X,X^{*}\right)}$、${\displaystyle \left(Y,Y^{*}\right)}$ が与えられているとする。このとき、関数 ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \}}$ が与えられたとすると、主問題は以下の通りに定義される:

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

もし問題に制約条件（Constraints）が与えられていたとすると、それらは関数 ${\displaystyle f}$ に組み込むことができ、指示関数 ${\displaystyle I}$ を用いて ${\displaystyle f=f+I_{\text{constraints}}}$ と表すことができる。ここで、${\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \}}$ を摂動関数とし、${\displaystyle F(x,0)=f(x)}$ が成り立つとする。このとき、双対ギャップは以下のこれらの差によって定義される:

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

ただし、${\displaystyle F^{*}}$ は両変数の凸共役である^[2][3]。

また、数理最適化において双対ギャップはしばしば別の意味合いで用いられることがあり、最適でない主問題の解と実行可能な双対問題の解に対して、それらの目的関数値の差を表すことがある。このもう一つの双対ギャップは反復解法などにおいて求まった最適解の保証がない主問題の実行可能解がその双対問題の実行可能解とそれらの目的関数値の差によって反復解法の収束具合を推定することができる。このとき、双対問題の値は、制約行列が正則であるとき、主問題の凸緩和の値と等しくなる。この凸緩和とは非凸な実行可能集合をそれに対応する閉凸包に置き換え、非凸な目的関数を元の主問題の目的関数のエピグラフの閉凸包をエピグラフにもつ凸閉包に置き換えることによって得られる問題である^[4]。