リーマン多様体上の最適化理論の展開とその大規模問題への応用

黎曼流形优化理论的发展及其在大规模问题中的应用

基本信息

批准号：
20K14359
负责人：
佐藤寛之
金额：
$ 2.66万
依托单位：
Kyoto University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Early-Career Scientists
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

令和4年度は，リーマン多様体上の最適化問題に対するアプローチとして，特に共役勾配法に関する2編の論文を発表した．一つは，リーマン多様体上の共役勾配法の一般的な枠組みについての研究である．この研究では，これまで様々に研究されてきたユークリッド空間やリーマン多様体上の共役勾配法を統一するような一般的な枠組みを与え，適切かつ自然な仮定の下で提案アルゴリズムの大域的収束性を詳細に解析した．また，数値実験においては，2つのグラスマン多様体の直積により構成される500万次元を超える多様体上の最適化問題や，リヤプノフ方程式の解法として一定サイズの正定値対称行列全体からなる多様体上の最適化問題を扱い，大規模問題に対する提案手法の有効性の実証も行った．もう一つの研究では，ユークリッド空間上の共役勾配法の中でも注目を集めている Hager-Zhang (HZ) 型の共役勾配法について，そのリーマン多様体への拡張を詳しく議論した．先述の共役勾配法の一般的な枠組みについての研究では，多様体上の点列の更新の際にレトラクションと呼ばれる写像を用い，探索方向の計算の際にはある接空間から別の接空間への一般的な写像を用いた．一方，この研究ではそれらの特別な場合として，点列の更新では指数写像を用い，探索方向の計算ではその微分を用いる手法を提案した．また，リーマン幾何学におけるガウスの補題を効果的に用いることで提案手法の大域的収束性を証明した．さらに，レイリー商最小化問題や無向グラフの安定数を求める問題を超球面上の最適化問題と捉え，数値実験によりこれらの問題を解くことで，提案手法が既存手法より優れた性能を発揮することを実証した．これら2つの研究はいずれも，リーマン多様体上の大規模な最適化問題の求解に大きく貢献するものである．

2020 年，我们发表了两篇关于共轭梯度法作为黎曼流形优化问题的方法的论文。一是黎曼流形共轭梯度法总体框架的研究。在这项研究中，我们提供了一个统一了欧几里得空间和黎曼流形上的共轭梯度方法的通用框架，这些方法迄今为止已经得到了各种研究，并详细分析了所提出算法在适当和自然的假设下的全局收敛性。此外，在数值实验中，我们解决了超过500万维的流形上的优化问题，这些流形是由两个格拉斯曼流形的直接乘积构造的，并解决了由恒定大小的正定对称矩阵组成的流形上的问题作为解我们处理了上述优化问题，并证明了该方法对于大规模问题的有效性。在另一项研究中，我们详细讨论了欧几里得空间上的共轭梯度法中备受关注的 Hager-Zhang (HZ) 型共轭梯度法到黎曼流形的扩展。在前面提到的共轭梯度法总体框架的研究中，在更新流形上的点序列时，使用了一种称为回缩的映射，而在计算搜索方向时，需要从一个切空间变换到另一个切空间我们使用通用映射到 .另一方面，在本研究中，作为这些的特例，我们提出了一种使用指数映射来更新点序列及其导数来计算搜索方向的方法。我们还通过有效利用黎曼几何中的高斯引理证明了该方法的全局收敛性。此外，通过将瑞利商最小化问题和寻找稳定数的无向图问题视为超球面上的优化问题，并通过数值实验解决这些问题，所提出的方法表现出了优于现有方法的性能。。这两项研究都对解决黎曼流形上的大规模优化问题做出了巨大贡献。