Discovery Sagaサイレントキーワード俯瞰

半正定値計画問題は、錐最適化問題の一つとして内点法など多くの研究がされている。本研究の研究対象である対数行列式半正定値計画問題は半正定値計画問題の拡張である。例えば、統計学のグラフィカルモデリングなどにおける直接的な相関と間接的な相関の差異の検出などにも利用可能な数理モデルである。一方で、大規模なデータにも適用可能にするには高速な計算手法の構築が重要である。研究代表者らは、これまでに対数行列式半正定値計画問題に対して、その双対問題の持つ数理的構造に着目をして双対射影勾配法を提案してきたが、最適解が疎行列となる場合やクラスタ分類情報などを付加した場合などに双対射影勾配法には改良の余地がある。
本年度は、クラスタ分類情報を付加した場合に対する双対射影勾配法の拡張の理論的解析を行った。双対射影勾配法は反復計算手法の一種であるが、各反復で勾配の実行可能集合への射影の計算が必要である。しかし、クラスタ分類情報の場合には双対問題に定式化すると変数の数が著しく増加するため、目的関数の勾配ベクトルに含まれる要素数も増えてしまう。このことから、既存の双対射影勾配法をそのままに適用すると勾配計算自体で長時間の計算時間が必要となり、適用可能範囲が小規模な問題に限定されてしまう。
本研究では、クラスタ分類情報に対応する部分に補助変数を導入することで、目的関数に直接含まれる変数を限定し勾配ベクトルの計算を簡略化する計算手法を開発した。このような簡略化を行っても射影部分を修正することで、生成される点列の目的関数値が元問題の最適値に収束することを理論的に示した。また、射影部分についても主要な計算ボトルネックとならないように計算量削減できるアプローチを採用した。この理論的解析の結果については、日本オペレーションズ・リサーチ学会2022年春季研究発表会で発表を行った。