Upgrade to Pro — share decks privately, control downloads, hide ads and more …

LP-双対性

 LP-双対性

Masanari Kimura

April 23, 2021
Tweet

More Decks by Masanari Kimura

Other Decks in Science

Transcript

  1. CompML 線形計画問題(Linear Programming problem) 線形計画問題は,線形目的関数を線形不等式制約の元で最適化する問題. 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 7𝑥! + 𝑥" +

    5𝑥# 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑥! − 𝑥" + 3𝑥# ≥ 10 5𝑥! + 2𝑥" − 𝑥# ≥ 6 𝑥! , 𝑥" , 𝑥# ≥ 0 上の例では変数が全て非負かつ制約式が全て≥ (正準形) 3
  2. CompML 実行可能解(Feasible Solution) 全ての制約式を満足する線形計画問題の解は実行可能解と呼ばれる. 例えば, 𝑥! , 𝑥" , 𝑥#

    = (2,1,3)は先ほどの問題の2つの制約式を満たす; 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 7𝑥! + 𝑥" + 5𝑥# 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑥! − 𝑥" + 3𝑥# ≥ 10 5𝑥! + 2𝑥" − 𝑥# ≥ 6 𝑥! , 𝑥" , 𝑥# ≥ 0 4 ① ②
  3. 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
  4. CompML 目的関数値の上界 線形計画問題の目的関数の最適値𝑧∗は,ある有理数𝛼以下であるか? → 目的関数値が𝛼以下となる実行可能解を一つでも見つければ良い 例えば𝛼 = 30のとき,先ほど見つけた 𝑥! ,

    𝑥" , 𝑥# = (2,1,3)は 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 7𝑥! + 𝑥" + 5𝑥# 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑥! − 𝑥" + 3𝑥# ≥ 10 5𝑥! + 2𝑥" − 𝑥# ≥ 6 𝑥! , 𝑥" , 𝑥# ≥ 0 の実行可能解でかつ,目的関数値= 7 ⋅ 2 + 1 + 5 ⋅ 3 = 30 ≤ 𝛼. 6
  5. 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
  6. CompML 双対問題 より良い下界を探す問題は,制約式の和の右辺の最大化問題とも言える: 双対問題(dual program) 𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑒 10𝑦! + 6𝑦" 𝑠𝑢𝑏𝑗𝑒𝑐𝑡

    𝑡𝑜 𝑦! + 5𝑦" ≤ 7 −𝑦! + 2𝑦" ≤ 1 3𝑦! − 𝑦" ≤ 5 𝑦! , 𝑦" ≥ 0 主問題(primal program) 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 7𝑥! + 𝑥" + 5𝑥# 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑥! − 𝑥" + 3𝑥# ≥ 10 5𝑥! + 2𝑥" − 𝑥# ≥ 6 𝑥! , 𝑥" , 𝑥# ≥ 0 9
  7. CompML 主問題と双対問題を以下のように形式化する. 𝑛個の変数(𝑖 = 1, … , 𝑛),𝑚個の制約式(𝑗 = 1,

    … , 𝑚)について, 主問題と双対問題の形式化 10 双対問題(dual program) 𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑒 ∑%&! ' 𝑏% 𝑦% 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 ∑ %&! ' 𝑎%( 𝑦% ≤ 𝑐( 𝑦% ≥ 0 主問題(primal program) 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 ∑(&! ) 𝑐( 𝑥( 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 ∑ (&! ) 𝑎%( 𝑥( ≥ 𝑏% 𝑥( ≥ 0
  8. CompML LP-双対定理 定理(LP-双対定理)LPにおいて主問題が有界な最適解をもつための必要十 分条件は双対問題が有界な最適解を持つことである.また,主問題の最適解 𝑥∗ = (𝑥! ∗, … 𝑥)

    ∗ )と双対問題の最適解𝑦∗ = (𝑦! ∗, … , 𝑦' ∗ )について以下の等式が成立す る. W (&! ) 𝑐( 𝑥( ∗ = W %&! ' 𝑏% 𝑦% ∗ . 11
  9. CompML 弱双対定理 定理(弱双対定理)主問題の任意の実行可能解x = (𝑥! , … 𝑥" )と双対問題の任意の実行可能解𝑦 =

    (𝑦! , … , 𝑦# )について以下の不等式が成立する. " !"# $ 𝑐!𝑥! ≥ " %"# & 𝑏%𝑦% . 証明.𝑦は双対問題の実行可能解であり,𝑥$ は全て非負であるので, ! !"# $ 𝑐! 𝑥! ≥ ! !"# $ ! %"# & 𝑎%! 𝑦% 𝑥! 同様に,𝑥は主問題の実行可能解であり,𝑦% は全て非負であるので, ! %"# & ! !"# $ 𝑎%! 𝑥! 𝑦% ≥ ! %"# & 𝑏% 𝑦% 以上の2式を組み合わせることで定理が得られる. 13
  10. CompML 相補条件 定理(相補条件)𝑥と𝑦をそれぞれ主問題と双対問題の実行可能解とする.こ のとき,𝑥と𝑦がそれぞれ最適解であるための必要十分条件は,以下の条件が成 立することである. 主相補条件 :∀𝑗 ∈ {1, …

    , 𝑛}について,𝑥( = 0もしくは∑%&! ' 𝑎%( 𝑦% = 𝑐( . 双対相補条件:∀𝑖 ∈ {1, … , 𝑚}について,𝑦% = 0もしくは∑(&! ) 𝑎%( 𝑥( = 𝑏% . 厳密解/近似解どちらを求める場合でも相補条件は重要な役割を担う. 14
  11. CompML PuLP: https://github.com/coin-or/pulp Pythonの線形計画問題ソルバ 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 7𝑥! + 𝑥" + 5𝑥#

    𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑥! − 𝑥" + 3𝑥# ≥ 10 5𝑥! + 2𝑥" − 𝑥# ≥ 6 𝑥! , 𝑥" , 𝑥# ≥ 0 16
  12. 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