ppt

区分線形凸計画問題に対する
多項式オーダーの内点法
東京工業大学経営工学専攻
小崎敏寛水野眞治中田和秀
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
考える問題
• 区分線形凸計画問題
(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 7/14 モデリングと最適化の理
論京都大学数理解析研究所
発表の構成
1. 区分線形凸計画問題を線形計画問題に変形する．
2. 線形計画問題を標準形の問題で解けるように変
換する．
3. 区分線形凸計画問題に対する多項式オーダーの
内点法を提案する．
4. 凸関数の性質を使って解ける問題を考える．
5. 内点法の性質を使って解ける問題を考える．
6. 区分凸二次計画問題を考える．
7. アフィン関数が無限本ある場合を考える．
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
１．線形計画問題への変換
• 問題(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 7/14 モデリングと最適化の理
論京都大学数理解析研究所
• 標準形にすると次のようになる．
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 7/14 モデリングと最適化の理
論京都大学数理解析研究所
• 双対問題は次のようになる．
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 7/14 モデリングと最適化の理
論京都大学数理解析研究所
• 整理すると次のようになる．
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 7/14 モデリングと最適化の理
論京都大学数理解析研究所
２．標準形の問題で解けるような変換
• 内点法を適用するために等式制約を解き代入する
変換を行う．
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 7/14 モデリングと最適化の理
論京都大学数理解析研究所
• 問題(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 7/14 モデリングと最適化の理
論京都大学数理解析研究所
• 対応する主問題は次のようになる．
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 7/14 モデリングと最適化の理
論京都大学数理解析研究所
• 最適条件は次のようになる．
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 7/14 モデリングと最適化の理
論京都大学数理解析研究所
• 変換後の問題の最適解からもとの問題の最適解
を得ることができる．
• 変換後の主問題の解を ( 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 7/14 モデリングと最適化の理
論京都大学数理解析研究所
３．多項式オーダーの解法
• 問題のサイズから主双対内点法のショートス
テップ法で 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   , si   i  1,, l.
n
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
• 主双対内点法は，センターパスを近似し，最
適解に近づく反復解法．
センターパス
最適解
実行可能領域
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
と表す．
と表す．
と表す．
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
アルゴリズム
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
0.4 ~ k T ~ k
 (1 
)x s
nl
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
ニュートン方向の計算
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
とする．次の関係がなりたつ．
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
4.凸関数の性質を使うと
• 区分線形凸関数の非負結合は凸関数であることか
ら，次の問題も同様に変換を用いて解ける．
• 内点法で O(
q
n   l p L)反復で解ける．
p 1
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
制約式に区分線形凸関数がある問題
• この問題は標準形の線形計画問題に帰着できるの
で，内点法で O( n  l L) 反復で解ける．
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
制約式に区分線形凸関数の
非負結合がある問題
• 区分線形凸関数の非負結合は凸関数．
定数
変数
• この問題は変換を使い内点法で
復で解ける．
p  
q
O( n   l p  1 L)
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
p 1
反
5.内点法の性質を使うと
• 半正定値制約を持つ区分線形凸計画問題
• ただし A  B  Tr ( AT B)
• この問題は変換を使って，内点法で解ける．
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
• 二次錐制約を持つ区分線形凸計画問題
• この問題は変換を使って，内点法で解ける．
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
6.もう少しなめらかな関数
• 目的関数を区分凸二次凸関数とした問題
•
• Qi  o を許すと，区分線形ー凸二次関数を考えら
れる．
• この問題は変数tを使うと次のように書ける．
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
• 凸二次不等式制約は，二次錐制約で書ける
ことより，次の問題と書ける．
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
• 二次錐計画問題であるので内点法で解ける
（はず）．
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
7 アフィン関数が無限本あるとき
ci x  dih
T
ci x  dil
T
min t
min t
s.t. ci x  d i  t d i  [d il , d ih ] s.t. c T x  d  t
i
ih
Ax  b
Ax  b
x  0.
T
x  0.
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
今後の課題
• 応用を考える．
• 自由変数を非負変数の差とあらわす変換を
用いないで，直接ニュートン法を適用する内
点法を考える．
• 区分微分可能凸計画問題を考える．
• 目的関数の係数に区間がある問題を考える．
2006 7/14 モデリングと最適化の理
論京都大学数理解析研究所
参考文献
• 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 7/14 モデリングと最適化の理
論京都大学数理解析研究所

Download Report