弱双対性

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

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

 弱双対性の定理 
 が主最小化線型計画に対する実行可能解で、 が双対最大化線型計画に対する実行可能解であるとき、弱双対性の定理とは  が成り立つことを言う。ここで  と  はそれぞれの目的函数の係数とする。

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

 脚注 

 関連項目 
 凸最適化

Category:最適化
Category:線型計画法
Category:凸最適化
Category:双対性
Category:数学に関する記事