全文

(1)

6.内点法と錐線形計画

(2)

線形計画はなぜ有効か?

 モデルが簡単

 記述できる問題が多い

 大規模な問題を高速に解くことができる

シンプレックス法

(主双対)内点法 数千万変数+制約

(3)

LP に対する主双対内点法

標準形の主問題

双対問題

0 ,

s.t.

min c

T

x Ax  b x 

(P)

0 ,

s.t.

max b

T

y A

T

y  z  c z 

(D)

(4)

双対定理によれば

を満たす を求めることと等価.

(ただし, )

相補条件にパラメータ を導入

ただし, は要素がすべて 1 のベクトル

0 ,

0 ,

0 ,

,

T

    

 b A y z c x z Xz Ax

z y x , ,

) ( diag x X 

 0

e Xz

z x

c z

y A b

Ax  ,

T

  ,  0 ,  0 ,  

e

(5)

非線形方程式系

は,各 に対し唯一の内点解を持つ.

のときの解の軌跡は,解へ収束する滑 らかな曲線(主双対中心パス)

e Xz

z x

c z

y A b

Ax  ,

T

  ,  0 ,  0 ,  

 0

0 ,

0 

 z x

 0

(6)

LP に対する主双対内点法

をニュートン法で解き,主双対内点パス(の近 傍)をたどりながら解へ収束する点列を生成

内点法の中で,最も効率がよい

 

 

 

 

e z

X z

X x

Z

c z

y A z

y A

b Ax

x A e

Xz

c z

y A

b Ax

k k

k k

k

k k

k

 

T T

T

(7)

イメージ

シンプレックス法 内点法

x 0

x 1

x 2

x *

x 0

中心パス

近傍

x 1

x 2

(8)

線形計画から錐線形計画へ

 主双対内点法は,ある種の凸計画問題まで 拡張できる

 錐線形計画

半正定値計画

Semidefinite Programming, SDP

二次錐計画

Second-Order Cone Programming, SOCP

(9)

錐線形計画問題

K x

m i

b x

a x c

i i

 , 1 , , ,

s.t.

, min

は閉凸錐(の直積)

は内積, n

n m

i n

i

R K

R c

R b

m i

R a

 ,

, ),

, ,

1

( 

(10)

錐( cone )の定義

凸錐 さらに閉集合ならば閉

, 錐が凸集合のとき凸錐 のとき,錐という

に対し

・空でない は

K x

K x

K R K

n

,  0 

0

0

(11)

例題 1

非負象限 R

n

  xR

n

x

i

 0 , i  1 ,  , n

x

1

x

2

0

の標準形

(普通の内積)

LP ,

,

1

 

n i

i i

n

x y x y

R

K

(12)

例題2

一般に, 半正定値対称行列の錐(閉凸錐)

 x  R

3

x

1

, x

3

0 , x

1

x

3

 x

22

0



 



 

 

 

 

 : 半正定値

3 2

2

1

X

x x

x X x

 

X n S

n

n X : 半正定値 X 0 R

n(n1) 2

(13)

半正定値対称行列

とおくと,標準形のSDP(主問題)

n n

K : 

  

 

n

i

n j

ij ij

Y X XY

Y X

1 1

trace ,

n i

i

S X

X

m i

b X

A

X C

 ,

0

, ,

1 ,

, s.t.

, min

(14)

双対問題は

LMI ( Linear Matrix Inequality )の一般化

n m

i

i i

S S

S

C A

S b

 

, 0 s.t.

max

1 T

(15)

例題3

二次錐( Second Order Cone ), Lorentz 錐

2 2

,

1

0

2 2

1

   

 R x x x x

x

n

n

x

2

x

1

0

3

x

x

2

0

x

1

(16)

とすると,二次錐計画問題(

SOCP

 摩擦円錐の拘束

 凸二次不等式

 凸二次計画問題

SDPや

SOC

Pは非線形計画

二次錐(の直積集合)

: ,

,

1

K y

x y

x

n i

i

i

T

0

T

Qx  q x  c  x

0 ,

0 

 x

xy

(17)

SDP の制約

二次錐制約

いずれも線形ではない

 x  R

3

x

1

, x

3

0 , x

1

x

3

 x

22

0

2 2

,

1

0

2 2

1

   

 R x x x x

x

n

n

(18)

ソフトウェア

SDP

 LMI ツールボックス( Matlab )

 SDPA,SeDuMi など 二次錐計画

 Numerical Optimizer

 SS など

Updating...

参照

Updating...

関連した話題 :