強い二重性

強い双対性は、数学的最適化において、主最適目的と双対最適目的が等しい条件です。定義により、強い双対性は双対性ギャップが 0 に等しい場合にのみ成立します。これは弱い双対性(主問題の最適値が双対問題以下、つまり双対性ギャップが 0 以上) とは対照的です。

強い双対性が成立するには、以下の各条件を満たす必要があります。

• ${\displaystyle F=F^{**}}$ここで、は主問題と双対問題に関連する摂動関数であり、はの共役である（双対ギャップの構築によって従う）${\displaystyle F}$${\displaystyle F^{**}}$${\displaystyle F}$
• ${\displaystyle F}$は凸で下半連続である（フェンシェル・モローの定理の最初の点に相当）
• 主な問題は線形最適化問題である
• 凸最適化問題に対するスレーターの条件。^{[1] [2]}

特定の条件（「制約条件」と呼ばれる）の下で、問題が多項式時間で解ける場合、それは強い双対性（ラグランジュ双対性の意味で）を持ちます。反対の方向も成り立つかどうか、つまり強い双対性が多項式時間で解けることを意味するかどうかは未解決の問題です。^[3]

• 凸最適化