弱双対性
応用数学の最適化の分野における弱双対性（じゃくそうついせい、英: weak duality）の概念は、双対性のギャップが常に 0 以上であることを意味する。これはすなわち、主（最小化）問題の解は「常に」関連する双対問題の解よりも大きいか等しいことを意味する。特別の場合にのみ成立する強双対性とは相対する概念である[1]。
使用法
[編集]多くの主-双対近似アルゴリズムは、弱双対性の概念に基づいている[2]。
弱双対性の定理
[編集]が主最小化線型計画に対する実行可能解で、 が双対最大化線型計画に対する実行可能解であるとき、弱双対性の定理とは が成り立つことを言う。ここで と はそれぞれの目的函数の係数とする。
一般化
[編集]より一般に、 が主最小化問題に対する実行可能解で、 が双対最大化問題に対する実行可能解であるとき、弱双対性は を意味する。ここで と はそれぞれ主問題と双対問題の目的函数である。
関連項目
[編集]脚注
[編集]- ^ Boţ, Radu Ioan; Grad, Sorin-Mihai; Wanka, Gert (2009), Duality in Vector Optimization, Berlin: Springer-Verlag, p. 1, doi:10.1007/978-3-642-02886-1, ISBN 978-3-642-02885-4, MR2542013.
- ^ Gonzalez, Teofilo F. (2007), Handbook of Approximation Algorithms and Metaheuristics, CRC Press, p. 2-12, ISBN 9781420010749.