上下限変数制約付き凸計画問題に対する座標軸成分毎最小化法の収束証明

概要

論文の詳細を見る
上下限変数制約付き凸計画問題は次のように定式化される。Q : min f(x) xεS ここで、 S={ x | l≦x≦u } x、l、u ε E_n (l、uの成分は±∞を許す) f : E_n → E_1 (一階微分可能かつ凸) 上記問題Qに対して、座標軸成分毎最小化法(CM法)を適用する際、f(x)が次の性質をもつならば、最適解への収束が証明されている。(性質A)任意の座標軸成分方向に対して最小値を与える点が唯一に定まる。しかし、f(x)が性質Aを持たない場合、収束の保証は得られていない。本論文では、問題Qにおいて、f(x)が性質Aを持たない一般の微分可能凸関数の時にも、CM法が最適解に収束する事を証明する。問題Qは上下限変数制約をもつ特殊な凸計画問題であるとともに、より一般的な次の凹計画問題のラグランジェ双対問題でもある。 P : max g(x) sub。to h(x)≦0xεS ここで、8⊆E_n g:E_n→E_1 (一階微分可能かつ強凹) h:E_n→E_m (一階微分可能かつ凸) 問題Pを双対法で解く際、すべての制約式をラグランンジェ関数に埋めこむことにより双対関数に性質Aを持たせる事ができるが、式の数に等しい双対変数が必要となる。一方、制約式の一部をラグランジェ関数に埋めこむ(ラグランジェ緩和法)ことにより双対変数を減らせるが、この場合双対関数が性質Aを持つとは限らない。本論文中の証明により、この場合にも最適解への収束が保証されるので、CM法とラグランジェ緩和法を組み合わせたアルゴリズムの効率をあげることができる。
社団法人日本オペレーションズ・リサーチ学会の論文

上下限変数制約付き凸計画問題に対する座標軸成分毎最小化法の収束証明

スポンサーリンク

概要

著者

関連論文

スポンサーリンク