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

区分線形凸計画問題に対する
内点法
東京工業大学経営工学専攻
小崎敏寛
2006 5/28 S@CO 筑波大学
考える問題
• 区分線形凸計画問題
(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 5/28 S@CO 筑波大学
発表の構成
1. 区分線形凸計画問題を線形計画問題に変
形する．
2. 線形計画問題を標準形の問題で解ける用
に変換する．
3. 区分線形凸計画問題に対する多項式オー
ダーの内点法を提案する．
4. 凸関数の性質を使って解ける問題を考える．
5. 内点法の性質を使って解ける問題を考える．
2006 5/28 S@CO 筑波大学
１．線形計画問題への変換
• 問題(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 5/28 S@CO 筑波大学
• 標準形にすると次のようになる．
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 5/28 S@CO 筑波大学
• 双対問題は次のようになる．
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 5/28 S@CO 筑波大学
• 整理すると次のようになる．
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 5/28 S@CO 筑波大学
２．標準形の問題で解けるような変換
• 内点法を適用するために等式制約を解き代入する
変換を行う．
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 5/28 S@CO 筑波大学
• 問題(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 5/28 S@CO 筑波大学
• 対応する主問題は次のようになる．
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 5/28 S@CO 筑波大学
• 最適条件は次のようになる．
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 5/28 S@CO 筑波大学
• 変換後の問題の最適解からもとの問題の最適解
を得ることができる．
• 変換後の主問題の解を ( 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 5/28 S@CO 筑波大学
３．多項式オーダーの解法
• 問題のサイズから主双対内点法のショートス
テップ法で O ( n  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 5/28 S@CO 筑波大学
• 主双対内点法は，センターパスを近似し，最
適解に近づく反復解法．
センターパス
最適解
実行可能領域
2006 5/28 S@CO 筑波大学
と表す．
sl
と表す．
と表す．
2006 5/28 S@CO 筑波大学
アルゴリズム
2006 5/28 S@CO 筑波大学
2006 5/28 S@CO 筑波大学
2006 5/28 S@CO 筑波大学
4.凸関数の性質を使うと
• 区分線形凸関数の非負結合は凸関数である
ことから，次の問題も同様に解ける．
2006 5/28 S@CO 筑波大学
制約式に区分線形凸関数がある問題
• この問題は標準形の線形計画問題に帰着で
きるので，内点法で解ける．
2006 5/28 S@CO 筑波大学
制約式に区分線形凸関数の
非負結合がある問題
• 区分線形凸関数の非負結合は凸関数．
• この問題は変換を使い内点法で解ける．
2006 5/28 S@CO 筑波大学
5.内点法の性質を使うと
• 半正定値制約を持つ区分線形凸計画問題
• この問題は変換を使って，内点法で解ける．
2006 5/28 S@CO 筑波大学
• 二次錐制約を持つ区分線形凸計画問題
• この問題は変換を使って，内点法で解ける．
2006 5/28 S@CO 筑波大学
今後の課題
• 応用を考える．
• 変換を用いないで，直接ニュートン法を適用
する内点法を考える．
• 自由変数を持つ線形計画問題に対する内点
法を考える．
2006 5/28 S@CO 筑波大学
参考文献
• 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.
2006 5/28 S@CO 筑波大学

Download Report