6.内点法と錐線形計画 2016/7/22 1 線形計画はなぜ有効か? モデルが簡単 記述できる問題が多い 大規模な問題を高速に解くことができる シンプレックス法 (主双対)内点法 数千万変数+制約 2016/7/22 2 LPに対する主双対内点法 標準形の主問題 (P) min c T x s.t. Ax b, x 0 双対問題 (D) 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 例題2 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 とおくと,標準形のSDP(主問題) 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 例題3 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 凸二次計画問題 SDPやSOCPは非線形計画 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