区分線形凸計画問題に対する 主双対内点法 東京工業大学経営工学専攻 小崎 敏寛 水野 眞治 中田 和秀 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 mn , 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 オペレーションズ・リサー チ学会 愛知大学 １．線形計画問題への変換 • 問題(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 オペレーションズ・リサー チ学会 愛知大学 ２．標準形の問題で解けるような変換 • 内点法を適用するために等式制約を解き代入する 変換を行う． 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 オペレーションズ・リサー チ学会 愛知大学 ３．多項式オーダーの解法 • 問題のサイズから主双対内点法のショートス テップ法で 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 nl 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 オペレーションズ・リサー チ学会 愛知大学
© Copyright 2024 ExpyDoc
