線形計画問題に対する乗法的罰金関数法の拡張

概要

論文の詳細を見る
本論文では、伊理〔論文中参考文献4〕により導入された線形計画問題に対する乗法的罰金関数法(multiplicative penalty function method)の種々の拡張について論じる。まず、元の方法では目的関数の最小値が既知であるという条件が必要であった点について、ここでは目的関数の最小値の下界を更新しながら、その下界に関する乗法的罰金関数を最小化することを考え、それにより最適解が効率よく求められることを示す。すなわち、目的関数のある下界が所与の場合、その下界に関する乗法的罰金関数を最小化する過程で、より良い下界を与える双対変数が構成でき、下界を必ず更新できること、及びそのようにして下界を更新したとき、それが線形目的関数の最適値に収束することを示す。これらを証明する過程で、乗法的罰金関数に関する新たな双対定理を示す。この双対性は、内点に関するものであり、この双対性自身も興味深い。また、全ての最適解で有効でない制約を、この算法の過程で求めることができることを示す。計算効率を高めるための種々の技法についても述べる。さらに、本論文で提案する算法とSonnevend、Renegar〔論文中参考文献10、11〕の算法との関連について言及する。目的関数値の下界が十分最適値に近いときには、その下界とそれに関する乗法的罰金関数の最小解から線形目的関数の最適解値が良く評価できることも示す。そして、ランダム線形計画問題に対する計算機実験を通して、拡張された算法の有効性を示す。
社団法人日本オペレーションズ・リサーチ学会の論文

線形計画問題に対する乗法的罰金関数法の拡張

スポンサーリンク

概要

著者

関連論文

スポンサーリンク