弱双対性

応用数学の最適化の分野における弱双対性（じゃくそうついせい、英: weak duality）の概念は、双対ギャップが常に 0 以上であることを意味する。これはすなわち、主（最小化）問題の解は「常に」関連する双対問題の解よりも大きいか等しいことを意味する。特別の場合にのみ成立する強双対性とは相対する概念である^[1]。

使用法

多くの主-双対近似アルゴリズムは、弱双対性の概念に基づいている^[2]。

弱双対性の定理

${\displaystyle (x_{1},x_{2},....,x_{n})}$ が主最小化線型計画に対する実行可能解で、${\displaystyle (y_{1},y_{2},....,y_{m})}$ が双対最大化線型計画に対する実行可能解であるとき、弱双対性の定理とは ${\displaystyle \sum _{i=1}^{m}b_{i}y_{i}\leq \sum _{j=1}^{n}c_{j}x_{j}}$ が成り立つことを言う。ここで ${\displaystyle c_{j}}$ と ${\displaystyle b_{i}}$ はそれぞれの目的函数の係数とする。

一般化

より一般に、${\displaystyle x}$ が主最小化問題に対する実行可能解で、${\displaystyle y}$ が双対最大化問題に対する実行可能解であるとき、弱双対性は ${\displaystyle g(y)\leq f(x)}$ を意味する。ここで ${\displaystyle f}$ と ${\displaystyle g}$ はそれぞれ主問題と双対問題の目的函数である。