山川栄樹,松原康博
2次計画問題に対する主双対内点法とその数値実験
Abstract:2次計画問題はポートフォリオ選択問題などの重要な応用分野を持つだけでなく、一般の非線形問題の反復解法における部分問題としてもしばしば用いられている。2次計画問題に対しては、Lemke法[4]やGoldfarb - Idnaniの方法[3]など、これまでに数多くの解法が提案されている。ここでは、大規模な問題に対する応用を想定して、Path Following タイプの内点法の一種であるPrimal-Dual Interior Point Method [2]を適用することを考える。この方法は、元の2次計画問題とその双対問題の双方について、それらに含まれる不等式制約条件を古典的なLogarithmic Barrier ペナルティ関数を利用して目的関数に組込み、等式制約条件のみを含む問題に変換した上で、それらの最適性の1次の条件の方程式系をNewton法を用いて解くというものである。本稿では、その具体的な計算法について検討を加えると共に、並列計算機Connection Machine Model CM-5上への実現について述べ、数値実験の結果を報告する。