LP-双対性

Transcript

1. CompML LP-双対性 Masanari Kimura (@machinery81)
2. CompML TL;DR • 線形計画問題（LP）に関する基礎概念をおさらい • 双対定理とその主張のまとめ 1
3. CompML いろいろな最適化問題 • 線形計画問題 • 整数計画問題 • 非線形計画問題 • 組み合わせ最適化問題 2
4. CompML 線形計画問題（Linear Programming problem） 線形計画問題は，線形目的関数を線形不等式制約の元で最適化する問題． 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 7𝑥! + 𝑥" + 5𝑥# 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑥! − 𝑥" + 3𝑥# ≥ 10 5𝑥! + 2𝑥" − 𝑥# ≥ 6 𝑥! , 𝑥" , 𝑥# ≥ 0 上の例では変数が全て非負かつ制約式が全て≥ （正準形） 3
5. CompML 実行可能解（Feasible Solution） 全ての制約式を満足する線形計画問題の解は実行可能解と呼ばれる． 例えば， 𝑥! , 𝑥" , 𝑥# = (2,1,3)は先ほどの問題の2つの制約式を満たす； 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 7𝑥! + 𝑥" + 5𝑥# 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑥! − 𝑥" + 3𝑥# ≥ 10 5𝑥! + 2𝑥" − 𝑥# ≥ 6 𝑥! , 𝑥" , 𝑥# ≥ 0 4 ① ②
6. CompML 実行可能性の確認 𝑥! , 𝑥" , 𝑥# = (2,1,3)のとき， • ①= 2 − 1 + 9 = 10 ≥ 10 • ②= 10 + 2 − 3 = 9 ≥ 6 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 7𝑥! + 𝑥" + 5𝑥# 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑥! − 𝑥" + 3𝑥# ≥ 10 5𝑥! + 2𝑥" − 𝑥# ≥ 6 𝑥! , 𝑥" , 𝑥# ≥ 0 5 ① ② 目的関数値= 14 + 1 + 15 = 30
7. CompML 目的関数値の上界 線形計画問題の目的関数の最適値𝑧∗は，ある有理数𝛼以下であるか？ → 目的関数値が𝛼以下となる実行可能解を一つでも見つければ良い 例えば𝛼 = 30のとき，先ほど見つけた 𝑥! , 𝑥" , 𝑥# = (2,1,3)は 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 7𝑥! + 𝑥" + 5𝑥# 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑥! − 𝑥" + 3𝑥# ≥ 10 5𝑥! + 2𝑥" − 𝑥# ≥ 6 𝑥! , 𝑥" , 𝑥# ≥ 0 の実行可能解でかつ，目的関数値= 7 ⋅ 2 + 1 + 5 ⋅ 3 = 30 ≤ 𝛼． 6
8. CompML 目的関数値の下界 線形計画問題の目的関数の最適値𝑧∗は，ある有理数𝛼以上であるか？ →𝑧∗についてのできるだけ良い下界を与えて，それが𝛼以上であることを示す 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 7𝑥! + 𝑥" + 5𝑥# 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑥! − 𝑥" + 3𝑥# ≥ 10 5𝑥! + 2𝑥" − 𝑥# ≥ 6 𝑥! , 𝑥" , 𝑥# ≥ 0 7
9. CompML より良い下界の探索 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑧 = 7𝑥! + 𝑥" + 5𝑥# 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑥! − 𝑥" + 3𝑥# ≥ 10 5𝑥! + 2𝑥" − 𝑥# ≥ 6 𝑥! , 𝑥" , 𝑥# ≥ 0 下界の候補1 ：𝑥% ≥ 0 (∀𝑖 ∈ {1,2,3})と最初の不等式から， 𝑧 ≥ 𝑥! − 𝑥" + 3𝑥# ≥ 10 ⇒ 𝑧∗ ≥ 10 下界の候補2：2つの制約式の和から， 𝑧 ≥ 𝑥! − 𝑥" + 3𝑥# + 5𝑥! + 2𝑥" − 𝑥# ≥ 16 ⇒ 𝑧∗ ≥ 16 基本方針：目的関数の𝑥! の係数以下になるように各制約式に非負数をかけて和をとる 8
10. CompML 双対問題 より良い下界を探す問題は，制約式の和の右辺の最大化問題とも言える： 双対問題（dual program） 𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑒 10𝑦! + 6𝑦" 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑦! + 5𝑦" ≤ 7 −𝑦! + 2𝑦" ≤ 1 3𝑦! − 𝑦" ≤ 5 𝑦! , 𝑦" ≥ 0 主問題（primal program） 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 7𝑥! + 𝑥" + 5𝑥# 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑥! − 𝑥" + 3𝑥# ≥ 10 5𝑥! + 2𝑥" − 𝑥# ≥ 6 𝑥! , 𝑥" , 𝑥# ≥ 0 9
11. CompML 主問題と双対問題を以下のように形式化する． 𝑛個の変数（𝑖 = 1, … , 𝑛），𝑚個の制約式（𝑗 = 1, … , 𝑚）について， 主問題と双対問題の形式化 10 双対問題（dual program） 𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑒 ∑%&! ' 𝑏% 𝑦% 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 ∑ %&! ' 𝑎%( 𝑦% ≤ 𝑐( 𝑦% ≥ 0 主問題（primal program） 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 ∑(&! ) 𝑐( 𝑥( 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 ∑ (&! ) 𝑎%( 𝑥( ≥ 𝑏% 𝑥( ≥ 0
12. CompML LP-双対定理 定理（LP-双対定理）LPにおいて主問題が有界な最適解をもつための必要十 分条件は双対問題が有界な最適解を持つことである．また，主問題の最適解 𝑥∗ = (𝑥! ∗, … 𝑥) ∗ )と双対問題の最適解𝑦∗ = (𝑦! ∗, … , 𝑦' ∗ )について以下の等式が成立す る． W (&! ) 𝑐( 𝑥( ∗ = W %&! ' 𝑏% 𝑦% ∗ . 11
13. CompML 双対問題の最適値＝主問題の最適値 12 0 26 ∞ 双対問題の実行可能解 主問題の実行可能解 LP-双対定理から，主問題と双対問題それぞれに対する実行可能解で目的関数値の一致するものを見つ ければ，それらは共に最適解になる．
14. CompML 弱双対定理 定理（弱双対定理）主問題の任意の実行可能解x = (𝑥! , … 𝑥" )と双対問題の任意の実行可能解𝑦 = (𝑦! , … , 𝑦# )について以下の不等式が成立する． " !"# $ 𝑐!𝑥! ≥ " %"# & 𝑏%𝑦% . 証明．𝑦は双対問題の実行可能解であり，𝑥$ は全て非負であるので， ! !"# $ 𝑐! 𝑥! ≥ ! !"# $ ! %"# & 𝑎%! 𝑦% 𝑥! 同様に，𝑥は主問題の実行可能解であり，𝑦% は全て非負であるので， ! %"# & ! !"# $ 𝑎%! 𝑥! 𝑦% ≥ ! %"# & 𝑏% 𝑦% 以上の2式を組み合わせることで定理が得られる． 13
15. CompML 相補条件 定理（相補条件）𝑥と𝑦をそれぞれ主問題と双対問題の実行可能解とする．こ のとき，𝑥と𝑦がそれぞれ最適解であるための必要十分条件は，以下の条件が成 立することである． 主相補条件 ：∀𝑗 ∈ {1, … , 𝑛}について，𝑥( = 0もしくは∑%&! ' 𝑎%( 𝑦% = 𝑐( ． 双対相補条件：∀𝑖 ∈ {1, … , 𝑚}について，𝑦% = 0もしくは∑(&! ) 𝑎%( 𝑥( = 𝑏% ． 厳密解／近似解どちらを求める場合でも相補条件は重要な役割を担う． 14
16. CompML LP-双対問題の性質とLP-双対定理の主張まとめ • 一方が最小化問題で他方が最大化問題になる • 双対問題の双対問題は元々の主問題になる • 双対問題のどの実行可能解も主問題の最適値の下界を与える • 主問題のどの実行可能解も双対問題の最適値の上界を与える • 主問題と双対問題それぞれに対する実行可能解で目的関数値の一致するもの を見つければ，それらは共に最適解になる 15
17. CompML PuLP: https://github.com/coin-or/pulp Pythonの線形計画問題ソルバ 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 7𝑥! + 𝑥" + 5𝑥# 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑥! − 𝑥" + 3𝑥# ≥ 10 5𝑥! + 2𝑥" − 𝑥# ≥ 6 𝑥! , 𝑥" , 𝑥# ≥ 0 16
18. CompML 参考文献 • 今野浩. 線形計画法. 日科技連出版社, 1987. • Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8. Pages 81–104. • A. A. Ahmadi (2016). "Lecture 6: linear programming and matching”. Princeton University. 17