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

解决对数行列式半定问题的改进对偶投影梯度法

基本信息

批准号：
21K11767
负责人：
山下真
金额：
$ 2.5万
依托单位：
Tokyo Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

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

本研究项目的目标是对数行列式半定规划问题，它是一种数学优化问题，其中变量是对称矩阵，并且包含线性约束作为约束。矩阵也是一个对数行列式。解决此类数学优化问题还涉及例如考虑稀疏性的多变量的最大似然估计，并且需要能够在短时间内解决大规模问题的计算方法。在构造基于最速下降等的计算方法时，需要计算目标函数的梯度，但由于对数行列式的斜率是由变量矩阵的逆矩阵给出，因此计算效率较高。基于这个性质和对偶问题的数学结构，我们提出了对偶投影梯度法。在这个研究项目中，我们关注的是当目标函数中添加处理聚类分类信息的项时如何改进对偶投影梯度方法。延续去年对双投影梯度法改进版的理论分析，今年我们主要关注以下三点。 (1)通过数值实验比较了传统的对偶投影梯度法和改进的对偶投影梯度法，并证实改进的版本可以在短时间内解决问题。我们还确认改进版本提高了可解决的问题规模。这很大程度上归功于投影计算效率的提高。 (2) 对于锥优化内点法之一的串搜索原对偶内点法，我们分析了在每次迭代中添加动量项时对最优解的收敛性，并获得了有关计算方法的理论知识。（3）联合举办持续优化国际研讨会作为国际研讨会，为海外研究人员和国内青年研究人员提供研究交流的机会。