６．内点法と錐線形計画 2016/7/22 1 線形計画はなぜ有効か？ モデルが簡単 記述できる問題が多い 大規模な問題を高速に解くことができる シンプレックス法 （主双対）内点法 数千万変数＋制約 2016/7/22 2 LPに対する主双対内点法 標準形の主問題 （Ｐ） min c T x s.t. Ax b, x 0 双対問題 （Ｄ） max b T y s.t. AT y z c, z 0 3 2016/7/22 双対定理によれば Ax b, AT y z c, x 0, z 0, Xz 0 を満たす x, y, z を求めることと等価． （ただし，X diag ( x) ） 0 を導入 c, x 0, z 0, Xz 相補条件にパラメータ Ax b, AT y z e ただし， e は要素がすべて1のベクトル 2016/7/22 4 非線形方程式系 Ax b, AT y z c, x 0, z 0, Xz e 0 に対し唯一の内点解を持つ． は，各 x 0, z 0 0 のときの解の軌跡は，解へ収束する滑 らかな曲線（主双対中心パス） 5 2016/7/22 LPに対する主双対内点法 Ax b AT y Xz z c e A x Ax k AT y z Zk x Xk z b AT y k zk X k zk c ke をニュートン法で解き，主双対内点パス（の近 傍）をたどりながら解へ収束する点列を生成 内点法の中で，最も効率がよい 2016/7/22 6 イメージ 中心パス x0 x x 1 x 2 x 0 x1 2 近傍 x* シンプレックス法 内点法 7 2016/7/22 線形計画から錐線形計画へ 主双対内点法は，ある種の凸計画問題まで 拡張できる 錐線形計画 半正定値計画 （Semidefinite Programming, SDP） 二次錐計画 （Second-Order Cone Programming, SOCP） 2016/7/22 8 錐線形計画問題 min c, x s.t. ai , x bi , i 1, ,m x K R n (i 1, ai , は内積，K , m), bi Rm , c Rn R n は閉凸錐（の直積） 9 2016/7/22 錐（cone）の定義 Rn は K ・空でない ・0 K ・ x K, 0 0 に対し x K のとき，錐という 錐が凸集合のとき凸錐， さらに閉集合ならば閉凸錐 0 2016/7/22 10 例題1 非負象限 R n x R n xi 0, i 1, ,n x2 x1 0 K n n R , x, y xi yi （普通の内積） LPの標準形 i 1 11 2016/7/22 例題２ x R 3 x1 , x3 X 0, x1 x3 x1 x2 x2 x3 x22 0 X : 半正定値 一般に， n n 半正定値対称行列の錐（閉凸錐） X 2016/7/22 S n X : 半正定値 X 0 R n(n 1) 2 12 K : n n 半正定値対称行列 n X ,Y n trace XY X ij Yij i 1 j 1 とおくと，標準形のＳＤＰ（主問題） min C, X s.t. Ai , X X bi , i 1, ,m Sn 0, X 13 2016/7/22 双対問題は max b T s.t. S m i Ai C i 1 S 0, S Sn LMI（Linear Matrix Inequality）の一般化 2016/7/22 14 例題３ x R n x12 x22 xn2 , x1 0 二次錐（Second Order Cone），Lorentz錐 x1 x1 2016/7/22 n 0 2 のとき x2 x2 0 n 3 のとき x3 15 n x, y xi yi , K : 二次錐（の直積集合） i 1 とすると，二次錐計画問題（SOCP） 摩擦円錐の拘束 xy 0, x 0 T T 凸二次不等式 x Qx q x c 0 凸二次計画問題 ＳＤＰやSOCＰは非線形計画 2016/7/22 16 SDPの制約 x R 3 x1 , x3 0, x1 x3 x22 0 二次錐制約 x R n x12 x22 xn2 , x1 0 いずれも線形ではない 2016/7/22 17 ソフトウェア SDP LMIツールボックス（Matlab） SDPA,SeDuMi など 二次錐計画 Numerical Optimizer SSなど 2016/7/22 18
© Copyright 2025 ExpyDoc
