弱い二元性

応用数学において、弱双対性とは、双対ギャップが常に0以上であることを示す最適化の概念です。これは、主問題と呼ばれる任意の最小化問題について、主問題の解は常に双対最大化問題の解以上であることを意味します。^{[ 1 ] : 225}あるいは、主最大化問題の解は常に双対最小化問題の解以下です。つまり、簡単に言うと、弱双対性とは、双対問題の実行可能な解は主問題の解の下限であるということです。^{[ 2 ]}

弱い双対性は強い双対性とは対照的で、強い双対性とは主最適目的と双対最適目的が等しいということを意味する。強い双対性は特定の場合にのみ成り立つ。^{[ 3 ]}

多くの主双対近似アルゴリズムは弱双対性の原理に基づいている。^{[ 4 ]}

線形計画問題を考えてみましょう。

どこ${\displaystyle A}$は${\displaystyle m\times n}$そして${\displaystyle b}$は${\displaystyle m\times 1}$（１）の双対問題は

弱双対性定理は次のように述べている。$\displaystyle c^{\top }x^{*}\leq b^{\top }y^{*}}$すべてのソリューションについて${\displaystyle x^{*}}$原始問題（１）およびすべての解$\displaystyle y^{*}}$双対問題（2）へ。

つまり、もし${\displaystyle (x_{1},x_{2},....,x_{n})}$は主最大化線形計画問題の実行可能な解であり、${\displaystyle (y_{1},y_{2},....,y_{m})}$が双対最小化線形計画問題の実行可能な解である場合、弱双対性定理は次のように述べることができる。 $\displaystyle \sum _{j=1}^{n}c_{j}x_{j}\leq \sum _{i=1}^{m}b_{i}y_{i}}$、 どこ${\displaystyle c_{j}}$そして${\displaystyle b_{i}}$これらはそれぞれの目的関数の係数です。

証明: c ^T x = x ^T c ≤ x ^T A ^T y ≤ b ^T y

• 凸最適化
• 最大最小不等式