一般化固有値計算による大域最適化手法の展開
【研究分野】数理情報学
【研究キーワード】
数理最適化 / 大域最適化 / 一般化固有値 / アルゴリズム / 機械学習 / 一般化固有値計算
【研究成果の概要】
一般に効率的なアルゴリズムの設計が原理的に不可能であると言われている非凸最適化問題の中でも幾何的な背景を有する問題に焦点を絞り，その構造を利用して, 大域最適解を見出す効率的なアルゴリズムを設計する手法を発展させた．特に，1本の制約式のみを含む非凸2次制約2次計画問題(QCQP)に対して，一般化固有値問題に帰着することによって，効率的に最適解を得る手法を開発した．さらに，一般の非凸QCQPに対して， Lagrange 双対問題を考え，子問題としての 1制約非凸QCQPを繰り返し解くことによってLagrange乗数を逐次改善して，緩和解を高速に得る手法を新たに開発した．
【研究の社会的意義】
これまで厳密な最適解を効率的に計算することは殆ど不可能だろうと思われていた非凸最適化問題に対して，幾何的な背景を有する特殊な問題であれば，一般化固有値計算を用いて，大域最適化を得られることを明らかにした．特に，一般の非凸無制約最適化問題の解法として広く使われている信頼領域法の中で繰り返し解く必要が生じる信頼領域部分問題(TRS)の高速解法を発表した論文は，比較的多くの研究に引用されている．その中には，３次正則化に対して手法を拡張したドイツの研究者による論文など，興味深い後続研究が現れている．
【研究代表者】
【研究分担者】 |
| 武田 朗子 | 東京大学 | 大学院情報理工学系研究科 | 教授 | (Kakenデータベース) |
| 中務 佑治 | 国立情報学研究所 | 情報学プリンシプル研究系 | 准教授 | (Kakenデータベース) |
|
【研究種目】基盤研究(B)
【研究期間】2017-04-01 - 2022-03-31
【配分額】7,280千円 (直接経費: 5,600千円、間接経費: 1,680千円)