区分線形凸計画問題に対する内点法

区分線形凸計画問題に対する
主双対内点法
東京工業大学経営工学専攻
小崎 敏寛 水野 眞治 中田 和秀
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
考える問題
• 区分線形凸計画問題
(piecewise linear convex problem)
min max (ci x  d i )
T
x
i 1,..., l
( P) s.t. Ax  b
x  0.
max (ci x  d i )
T
i 1,..., l
定数A   mn , b   m , ci   n , d i  ,
変数x   n .
関数 max (ci x  d i )は凸関数であるから
T
i 1,..., l
この問題は凸計画問題 .
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
発表の構成
1. 区分線形凸計画問題を線形計画問題に変形する.
2. 線形計画問題を標準形の問題で解けるように変
換する.
3. 区分線形凸計画問題に対する多項式オーダーの
内点法を提案する.
4. 内点法の性質を使って解ける問題を考える.
5. 区分凸二次計画問題を考える.
6. アフィン関数の最大値関数と最小値関数の差を最
小化問題を考える.
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
1.線形計画問題への変換
• 問題(P)は変数 t   を使うと次の問題に書ける.
min max (ci x  d i )
T
x
i 1,..., l
( P ) s.t. Ax  b
x  0.
min t
s.t. ci x  d i  t i  1,  , l
T
Ax  b
x  0.
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
• 標準形にすると次のようになる.
min t
min t   t
s.t. ci x  d i  t i  1,  , l s.t. Ax  b
T
ci x  t   t  si  d i i  1,, l
Ax  b
T
x  0.
x  0 t  0 t   0 si  0 i  1,, l.
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
• 双対問題は次のようになる.
l
max b y   d i ui
min t   t 
T
i 1
s.t. Ax  b
l
ci x  t   t   si  d i i  1,, l
T
x  0 t   0 t   0 si  0 i  1, , l.
s.t. A y   ci ui  z  0
T
i 1
l
u
i 1
l
u
i 1
i
i
 1
 1
ui  0 i  1,  , l
z  0.
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
• 整理すると次のようになる.
l
l
max b y   d i ui
max b y   d i ui
T
T
i 1
l
i 1
s.t. AT y   ci ui  z  0
i 1
l
u
i 1
l
u
i 1
i
i
 1
l
( D) s.t. AT y   ci ui  z  0
i 1
l
u
i 1
 1
ui  0 i  1, , l
z  0.
i
 1
ui  0 i  1, , l
z  0.
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
2.標準形の問題で解けるような変換
• 内点法を適用するために等式制約を解き代入する
変換を行う.
ul  1   ui ( 0)として目的関数,制約
式に代入すると,
i l
l
b y   d i ui  bT y   d i ui  d l (1   ui )
T
i 1
i l
i l
 bT y   (d l  d i )ui  d l ,
i l
l
A y   ci ui  AT y   ci ui  cl (1   ui )
T
i 1
i l
 AT y   (ci  cl )ui  cl .
i l
i l
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
• 問題(D)は次のように書ける.
max bT y   (d l  d i )ui  d l
i l
s.t. AT y   (ci  cl )ui  v x  cl
i l
  u i  v sl  1
i l
ui  vsi  0 i  1,  , l  1
v x  0 vsl  0 vsi  0 i  1,  , l  1
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
• 対応する主問題は次のようになる.
min cl x  sl  d l
T
s.t. Ax  b
(ci  cl )T x  si  sl  d l  d i i  1,  , l  1
x  0 si  0 i  1,  , l.
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
• 最適条件は次のようになる.
Ax  b,
(ci  cl )T x  si  sl  d l  d i i  1, , l  1,
主実行可能条件
x  0 si  0 i  1,, l ,
AT y   (ci  cl )ui  v x  cl ,
i l
  ui  vsl  1,
双対実行可能条件
i l
ui  vsi  0 i  1, , l  1,
v x  0 vsl  0 vsi  0 i  1,, l  1,
xT vx  0,
si vsi  0 i  1,, l.
相補性条件
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
• 変換後の問題の最適解からもとの問題の最適解
を得ることができる.
• 変換後の主問題の解を ( x* , s1* ,, sl * )として,
もとの主問題の解は
( x, t , s1 ,, sl )  ( x , cl x  sl  dl , s ,, sl )
*
•
T
*
*
*
1
*
*
(
y
変換後の双対問題の解を , u1 ,, ul 1 )として,
*
*
もとの双対問題の解は
( y, u1 ,  , ul )  ( y * , u1 ,  ,1   ui )
*
*
i l
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
3.多項式オーダーの解法
• 問題のサイズから主双対内点法のショートス
テップ法で O ( n  l L) 反復で解ける.
• ただしLは問題のサイズ.
min cl x  sl  d l
T
s.t. Ax  b
( ci  cl )T x  si  sl  d l  d i i  1,, l  1
x  0 si  0 i  1,, l.
変数x  n , si   i  1,, l.
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
• 主双対内点法は,センターパスを近似し,最
適解に近づく反復解法.
センターパス
最適解
実行可能領域
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
と表す.
と表す.
と表す.
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
アルゴリズム
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
0.4 ~ k T ~ k
 (1 
)x s
nl
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
ニュートン方向の計算
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
とする.次の関係がなりたつ.
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
4.内点法の性質を使うと
• 半正定値制約を持つ区分線形凸計画問題
• ただし A  B  Tr ( AT B)
• この問題は変換を使って,内点法で解ける.
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
• 二次錐制約を持つ区分線形凸計画問題
• この問題は変換を使って,内点法で解ける.
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
5.もう少しなめらかな関数
• 目的関数を区分凸二次凸関数とした問題
•
• Qi  o を許すと,区分線形ー凸二次関数を考えら
れる.
• この問題は変数tを使うと次のように書ける.
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
• 凸二次不等式制約は,二次錐制約で書ける
ことより,次の問題と書ける.
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
• 二次錐計画問題であるので内点法で解ける.
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
6.アフィン関数の最大値関数と最小化
関数の差を最小化する問題
• 次のように変形できる.
• 変換を適用後,ショートステップ内点法で
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
今後の課題
• 応用を考える.
• 数値実験を行う.
• 凸多面体や凸二次領域(楕円体の共通部
分)間の距離を最小化する問題を考える.
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学
参考文献
• D.Bertsimas and J.N.Tsitsiklis, Introduction to Linear
Optimization.
• S.Boyd and L.Vandenberghe,
Convex Optimization.
• K.Kobayashi, K.Nakata and M.Kojima,
A Conversion of an SDP Having Free Variables into the
Standard Form SDP.
• S.J.Wright,
Primal-Dual Interior-Point Method.
• F.Alizadeh and D.Goldfarb,
Second-Order Cone Progarmming.
2006 9/13 オペレーションズ・リサー
チ学会 愛知大学