弱双対性

応用数学の最適化の分野における弱双対性（じゃくそうついせい、テンプレート:Lang-en-short）の概念は、テンプレート:仮リンクが常に 0 以上であることを意味する。これはすなわち、主（最小化）問題の解は「常に」関連する双対問題の解よりも大きいか等しいことを意味する。特別の場合にのみ成立する強双対性とは相対する概念である。

使用法

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

弱双対性の定理

$(x_1,x_2,....,x_n)$ が主最小化線型計画に対する実行可能解で、$(y_1,y_2,....,y_m)$ が双対最大化線型計画に対する実行可能解であるとき、弱双対性の定理とは $\sum _{i=1}^m{b}_i{y}_i\le \sum _{j=1}^n{c}_j{x}_j$ が成り立つことを言う。ここで $c_j$ と $b_i$ はそれぞれの目的函数の係数とする。

一般化

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

関連項目

• 凸最適化