弱双対性 From Wikipedia, the free encyclopedia 応用数学の最適化の分野における弱双対性（じゃくそうついせい、英: weak duality）の概念は、双対ギャップが常に 0 以上であることを意味する。これはすなわち、主（最小化）問題の解は「常に」関連する双対問題の解よりも大きいか等しいことを意味する。特別の場合にのみ成立する強双対性とは相対する概念である[1]。 多くの主-双対近似アルゴリズムは、弱双対性の概念に基づいている[2]。 弱双対性の定理 ( x 1 , x 2 , . . . . , x n ) {\displaystyle (x_{1},x_{2},....,x_{n})} が主最小化線型計画に対する実行可能解で、 ( y 1 , y 2 , . . . . , y m ) {\displaystyle (y_{1},y_{2},....,y_{m})} が双対最大化線型計画に対する実行可能解であるとき、弱双対性の定理とは ∑ i = 1 m b i y i ≤ ∑ j = 1 n c j x j {\displaystyle \sum _{i=1}^{m}b_{i}y_{i}\leq \sum _{j=1}^{n}c_{j}x_{j}} が成り立つことを言う。ここで c j {\displaystyle c_{j}} と b i {\displaystyle b_{i}} はそれぞれの目的函数の係数とする。 一般化 より一般に、 x {\displaystyle x} が主最小化問題に対する実行可能解で、 y {\displaystyle y} が双対最大化問題に対する実行可能解であるとき、弱双対性は g ( y ) ≤ f ( x ) {\displaystyle g(y)\leq f(x)} を意味する。ここで f {\displaystyle f} と g {\displaystyle g} はそれぞれ主問題と双対問題の目的函数である。 脚注 [脚注の使い方] ↑ 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 . ↑ 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 . 関連項目 凸最適化 Related Articles
が主最小化線型計画に対する実行可能解で、
が双対最大化線型計画に対する実行可能解であるとき、弱双対性の定理とは 
が成り立つことを言う。ここで 
と 
はそれぞれの目的函数の係数とする。
が主最小化問題に対する実行可能解で、
が双対最大化問題に対する実行可能解であるとき、弱双対性は 
を意味する。ここで 
と 
はそれぞれ主問題と双対問題の目的函数である。