弱双対性

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

使用法[編集]

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

弱双対性の定理[編集]

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

一般化[編集]

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

脚注[編集]

[1] 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 .

[2] Gonzalez, Teofilo F. (2007), Handbook of Approximation Algorithms and Metaheuristics, CRC Press, p. 2-12, ISBN 9781420010749 .

[1]

[2]

使用法[編集]

弱双対性の定理[編集]

一般化[編集]

関連項目[編集]

脚注[編集]