弱双対性

ウィキペディア

弱双対性

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/09/11 21:41 UTC 版)

応用数学の最適化の分野における弱双対性（じゃくそうついせい、英: 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}$ はそれぞれ主問題と双対問題の目的函数である。

関連項目

• 凸最適化

脚注

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, https://books.google.co.jp/books?id=nwB0qExrF00C&pg=PA1&redir_esc=y&hl=ja .
2. ^ Gonzalez, Teofilo F. (2007), Handbook of Approximation Algorithms and Metaheuristics, CRC Press, p. 2-12, ISBN 9781420010749, https://books.google.co.jp/books?id=QK3_VU8ngK8C&pg=SA2-PA12&redir_esc=y&hl=ja .