６．錐線形計画 2014/7/18 1 線形計画はなぜ有効か？モデルが簡単記述できる問題が多い大規模な問題を高速に解くことができるシンプレックス法（主双対）内点法数千万変数＋制約 2014/7/18 2 LPに対する主双対内点法標準形の主問題 T （Ｐ） min c x s.t. Ax b, x 0 双対問題（Ｄ） max b T y s.t. 2014/7/18 AT y z c, z 0 3 双対定理によれば T Ax b, A 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のベクトル 2014/7/18 4 非線形方程式系 T Ax b, A y z c, x 0, z 0, Xz e 0 に対し唯一の内点解を持つ．は，各 x 0, z 0 0 のときの解の軌跡は，解へ収束する滑らかな曲線（主双対中心パス） 2014/7/18 5 LPに対する主双対内点法 Ax b T A y Xz A x z c e A T Z k Ax y z x k X k b T A y z k z k X z k k c ke をニュートン法で解き，主双対内点パス（の近傍）をたどりながら解へ収束する点列を生成内点法の中で，最も効率がよい 2014/7/18 6 イメージ中心パス x 0 x 1 x x 2 x x 2 1 近傍 * シンプレックス法 2014/7/18 x 0 内点法 7 線形計画から錐線形計画へ主双対内点法は，ある種の凸計画問題まで拡張できる錐線形計画半正定値計画（Semidefinite Programming, SDP）二次錐計画（Second-Order Cone Programming, SOCP） 2014/7/18 8 錐線形計画問題 min c, x s.t. ai , x bi , i 1, ,m x K ai n R (i 1, , は内積，K 2014/7/18 , m), bi m R ,c R n n R は閉凸錐（の直積） 9 錐（cone）の定義 Rn は K ・空でない・0 K ・ x K, 0 0 に対し x K のとき，錐という錐が凸集合のとき凸錐，さらに閉集合ならば閉凸錐 0 2014/7/18 10 例題1 非負象限 R n n x R xi 0, i 1, ,n x2 x1 0 K R n , x, y n xi yi （普通の内積） LPの標準形 i 1 2014/7/18 11 例題２ 3 x R x1 , x3 X 0, x1 x3 x1 x2 x2 x3 2 x2 0 X : 半正定値一般に， n n 半正定値対称行列の錐（閉凸錐） X 2014/7/18 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 2014/7/18 0, X bi , i 1, S ,m n 13 双対問題は max b T m s.t. S i Ai c i 1 S 0, S S n LMI（Linear Matrix Inequality）の一般化 2014/7/18 14 例題３ x R n 2 x1 2 x2 2 xn , x1 0 二次錐（Second Order Cone），Lorentz錐 x1 x1 2014/7/18 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Ｐは非線形計画 2014/7/18 16 SDPの制約 3 x R x1 , x3 0, x1 x3 2 x2 0 二次錐制約 x R n 2 x1 2 x2 2 xn , x1 0 いずれも線形ではない 2014/7/18 17 ソフトウェア SDP LMIツールボックス（Matlab） SDPA,SeDuMi など二次錐計画 Nuopt SSなど 2014/7/18 18