双対ギャップ

双対ギャップとは

双対ギャップ（そうついギャップ）とは、数理最適化の分野において、主問題とその双対問題の最適解の差を指します。数理最適化において、主問題とは与えられた条件を満たす中で最適な解を見つける問題であり、双対問題は主問題に対して対になる形で設定される補完的な問題です。この双対ギャップは、主問題の最適値を表す記号を `p∗`、双対問題の最適値の記号を `d∗` とした場合、次のように定義されます。

$$
双対ギャップ = p^{} - d^{}
$$

双対ギャップは基本的に非負の値を持つことが特徴で、つまり常にゼロ以上となります。特に、「強双対性」という条件が成り立つ状況では、この双対ギャップはゼロに等しくなり、主問題と双対問題の最適値が一致することを示します。一方、強双対性が確立されていない場合には、「弱双対性」が成り立ち、この場合、双対ギャップは常に正の値を持ちます。

主問題の定義と双対問題の設定

数理最適化において、双対問題を設定する際には、一般的に局所的な凸空間とその双対を考えます。具体的には、局所的に凸である2つの空間 $(X, X^{})$ と $(Y, Y^{})$ が存在し、関数 $f: X o ext{R} igcup igrace{+∞}$ が与えられた場合、この関数に基づき主問題が以下のように定義されます。

$$
ext{主問題: } ext{inf}_{x orall X} f(x)
$$

また、この問題に制約条件が課される場合、関数 $f$ にこれらの制約を組み込むことができます。この場合、制約を表現する指示関数 $I$ を用いて、次のように書くことが可能です。

$$
f = f + I_{ ext{constraints}}
$$

この設定において、摂動関数 $F: X imes Y o ext{R} igcup igrace{+∞}$ も考慮されることがあります。ここで、特に $F(x, 0) = f(x)$ が成り立つとし、双対ギャップが以下の形で定義されます。

$$
ext{双対ギャップ: } ext{inf}_{x orall X} [F(x, 0)] - ext{sup}_{y^{} orall Y^{}} [-F^{}(0, y^{})]
$$

この場合、$F^{*}$ は両変数の凸共役を示します。至る所で、双対ギャップはただの最適値の差を表すだけではなく、さまざまな文脈で異なる意味合いを持つことがあります。

実行可能解と反復法による収束

特に、数理最適化の領域では、最適とは言えない主問題の解と、制約を満たす双対問題の解との目的関数値の差もまた「双対ギャップ」と呼ばれることがあります。このケースでは、解法の反復過程において、最適解の保証がない主問題の実行可能解の性能を見積もるためにこのギャップを使うことができます。具体的には、このようなギャップを用いることで、反復法における収束度合いを評価するのです。

特に、双対問題の元々の値は、制約行列が特定の条件（正則性）を満たす場合に、主問題の凸緩和の値と等しくなります。凸緩和とは、非凸が故に難解な実行可能集合をその閉凸包に置き換え、また非凸な目的関数を適当な形に変換することで得られる問題設定を指します。

もう一度検索