超大規模な最適化問題に対する行列補完を用いた準ニュートン法に関する研究

正定値行列補完を用いた準ニュートン法(MCQN法)は,目的関数のヘッセ行列において0とならない成分を既存の準ニュートン法で更新し,0となる成分を正定値行列補完で構成することによって,正定値行列となる疎な近似ヘッセ行列を生成するする手法である.これまでに,既存の準ニュートン法としてDFP法を用いた場合,MCQN法が超1次収束することが示されていた.本年度は,国科学院のDai教授と共に,DFP法よりもより実用度が高いBFGS法と組み合わせたMCQN法が超1次収束することを証明した.また,アルゴリズムに含まれるパラメータを自動的に更新する手法を複数考案した.さらに,疎構造を工夫することによって,理論的には超1次収束性を保証することができないが,計算時間,必要メモリーを減少させる手法を開発した.さらに,数値実験を通してその有効性を確認した.一方,制約つき最小化問題に対する逐次2次計画法にMCQN法を組み込む手法を開発したが,逐次2次計画法では,部分問題で2次計画法を解かなければならないため,不等式で表された制約条件を含むときにはMCQN法を用いると計算効率が非常に悪くなり,既存の手法よりもよい結果が得られなかった.内点法とMCQN法を組み合わせることが今後の課題である.

正定値行列補完を用いた準ニュートン法(MCQN法)は,目的関数のヘッセ行列において0とならない成分を既存の準ニュートン法で更新し,0となる成分を正定値行列補完で構成することによって,正定値行列となる疎な近似ヘッセ行列を生成するする手法である.これまでに,既存の準ニュートン法としてDFP法を用いた場合,MCQN法が超1次収束することが示されていた.本年度は,国科学院のDai教授と共に,DFP法よりもより実用度が高いBFGS法と組み合わせたMCQN法が超1次収束することを証明した.また,アルゴリズムに含まれるパラメータを自動的に更新する手法を複数考案した.さらに,疎構造を工夫することによって,理論的には超1次収束性を保証することができないが,計算時間,必要メモリーを減少させる手法を開発した.さらに,数値実験を通してその有効性を確認した.一方,制約つき最小化問題に対する逐次2次計画法にMCQN法を組み込む手法を開発したが,逐次2次計画法では,部分問題で2次計画法を解かなければならないため,不等式で表された制約条件を含むときにはMCQN法を用いると計算効率が非常に悪くなり,既存の手法よりもよい結果が得られなかった.内点法とMCQN法を組み合わせることが今後の課題である.