山川栄樹,松原康博
大規模2次計画問題に対する内点法とその数値計算について -- 逐次線形化法の部分問題への適用を目指して --
Abstract:大規模非線形計画問題に対する逐次線形化法[1]では，各反復で凸2次計画問題を解かなければならない．大規模問題を取扱う場合には，逐次線形化法の実行時間の大半が2次計画部分問題の処理に費やされるため，これを高速に解くことが要求される[5]．そこで本実習では，計算量が理論的に多項式時間で抑えられることで最近注目を集めている内点法の一種であるPotential Reduction Algorithm[3]を適用し，実際の数値計算においてどのような工夫が必要か，またこれにより，実際にどの程度の性能を引き出せるかについて実証的に検討を行うことにした内点法のアルゴリズムでは，一般にその計算量の大半が連立一次方程式の処理で占められる．ここでは，元の問題の疎な構造を生かしつつ，これを高速に解くための改良を試みた．また，内点法の実装においてしばしば問題にされるステップサイズの選択方法についても数値実験により検証を行ったので，その結果を報告する．