An improved dual projected gradient method for log-determinant semidefinite problems

点击翻译按钮获取中文摘要

本研究課題で対象としている対数行列式付き半正定値計画問題は、変数が対称行列であり制約として線形制約を含んでいる数理最適化問題の一種であり、特徴的な構造として目的関数に変数行列の線形項だけでなく対数行列式を持ち合わせいる点が挙げられる。このような数理最適化問題の求解は、例えば疎性を考慮したうえでの多変数の最尤推定などとも関係があり、大規模な問題を短時間で求解する計算手法への需要がある。計算手法を構築する際に最急降下法などをベースとした場合には目的関数の勾配の計算が必要となるが、対数行列式の勾配は変数行列の逆行列で与えられるため計算効率が高い。この性質と双対問題の数理的構造に基づいて、これまでに双対射影勾配法を提案してきた。本研究課題では、クラスタ分類情報を扱うための項を目的関数に追加した場合に双対射影勾配法をどのように改良するべきか、を焦点の一つとして研究を進めている。前年度に改良版の双対射影勾配法の理論的解析を行ったことを引き継いで、本年度は主に以下の３点を行った。(1) 従来の双対射影勾配法と改良した双対射影勾配法を数値実験で比較を行い、改良版が短時間で求解可能であることを確認した。また、求解可能な問題規模についても改良版によって改善されることも確認できた。このことは射影計算の効率化による貢献が大きい。(2) 錐最適化に関する内点法の一つである弦探索型主双対内点法について、各反復で Momentum の項を追加した場合の最適解への収束を解析し、錐最適化問題の計算手法に関する理論的な知見を得た。(3) 国際ワークショップとして International Workshop on Continuous Optimization を共同で開催し、海外研究者や国内の若手研究者との研究交流の機会を設けた。