6.内点法と錐線形計画

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