弱双対性のソースを表示

[[応用数学]]の[[数理最適化|最適化]]の分野における'''弱双対性'''（じゃくそうついせい、{{Lang-en-short|weak duality}}）の概念は、{{仮リンク|双対性のギャップ|en|duality gap}}が常に 0 以上であることを意味する。これはすなわち、主（最小化）問題の解は「常に」関連する[[双対問題]]の解よりも大きいか等しいことを意味する。特別の場合にのみ成立する[[強双対性]]とは相対する概念である<ref>{{citation
 | last1 = Boţ | first1 = Radu Ioan
 | last2 = Grad | first2 = Sorin-Mihai
 | last3 = Wanka | first3 = Gert
 | doi = 10.1007/978-3-642-02886-1
 | isbn = 978-3-642-02885-4
 | location = Berlin
 | mr = 2542013
 | page = 1
 | publisher = Springer-Verlag
 | title = Duality in Vector Optimization
 | url = https://books.google.co.jp/books?id=nwB0qExrF00C&pg=PA1&redir_esc=y&hl=ja
 | year = 2009}}.</ref>。

== 使用法 ==
多くの主-双対[[近似アルゴリズム]]は、弱双対性の概念に基づいている<ref>{{citation|title=Handbook of Approximation Algorithms and Metaheuristics|first=Teofilo F.|last=Gonzalez|publisher=CRC Press|year=2007|isbn=9781420010749|page=2-12<!-- this is not a page range; do not replace the hyphen by a dash-->|url=https://books.google.co.jp/books?id=QK3_VU8ngK8C&pg=SA2-PA12&redir_esc=y&hl=ja}}.</ref>。

== 弱双対性の定理 ==
<math>(x_1,x_2,....,x_n)</math> が主最小化[[線型計画法|線型計画]]に対する実行可能解で、<math>(y_1,y_2,....,y_m)</math> が双対最大化線型計画に対する実行可能解であるとき、弱双対性の定理とは <math>\sum_{i=1}^m b_i y_i \leq \sum_{j=1}^n c_j x_j</math> が成り立つことを言う。ここで <math> c_j </math> と <math> b_i </math> はそれぞれの目的函数の係数とする。

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

== 関連項目 ==
* [[凸最適化]]

== 脚注 ==
{{reflist}}

{{DEFAULTSORT:しやくそうついせい}}
[[Category:最適化]]
[[Category:線型計画法]]
[[Category:凸最適化]]
[[Category:双対性]]
[[Category:数学に関する記事]]