超大規模な半正定値計画の数値計算に関する研究

超大规模半定规划数值计算研究

基本信息

批准号：
12780326
负责人：
中田和秀
金额：
$ 1.09万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
2000
资助国家：
日本
起止时间：
2000 至 2001
项目状态：
已结题

项目摘要

半正定値計画問題に対する主双対内点法の変数行列に対し、行列補完理論を導入することにより、この密となる変数行列にある種の疎構造が存在することを証明した。そして、この疎構造を主双対内点法に応用する方法として、conversion版とcompletion版の2通りの方法を提案した。この方法により、変数の個数が多くなる半正定値計画問題を非常に効率よく解くことが可能となった。その結果、変数の数が1千万程度の大規模半正定値計画問題を解くことに成功した。主双対内点法の各反復で解く係数行列が大規模で密となる線形方程式系に対し、クリロフ部分空間法などに代表される様々な反復解法を適用する枠組みを提案した。また、係数行列の構造を活かすため、対称逐次過剰緩和法などの定常反復法を前処理として用いた。そして、その効率性を理論的・実験的に検証した。この方法により、線形制約の個数が多くなる半正定値計画問題を非常に効率よく解くことが可能となった。その結果、制約の数が20万以上の大規模半正定値計画問題を解くことに成功した。さらに、それらの結果を拡張することにより、係数行列が大規模で密となる一般の線形方程式系に対し、クリロフ部分空間法や前処理としての定常反復法を適用する枠組みを構築した。以上の成果を日本応用数理学会やSWoPPで発表することにより、専門分野の研究者に紹介した。さらに、半正定値計画問題に対する主双対内点法を量子化学分野に応用することにより、従来のアルゴリズムでは解くことが困難であった最適化問題を解くことに成功し、それらも論文としてまとめた。

将矩阵补全理论引入到半定规划问题的原对偶内点法的变矩阵中，证明了该稠密变矩阵中存在某种稀疏结构。然后，我们提出了两种将这种稀疏结构应用于原始对偶内点方法的方法：转换版本和完成版本。该方法可以非常有效地解决具有大量变量的半定规划问题。结果，我们成功解决了一个包含约 1000 万个变量的大规模半定规划问题。我们提出了一个框架，将各种迭代解决方案（例如 Krylov 子空间方法）应用于线性方程组，其中原对偶内点法每次迭代求解的系数矩阵又大又密。此外，为了利用系数矩阵的结构，采用对称序贯过松弛法等稳态迭代方法作为预处理。然后，从理论上和实验上验证了其效率。该方法可以非常有效地解决具有大量线性约束的半定规划问题。结果，我们成功解决了一个具有超过 200,000 个约束的大规模半定规划问题。此外，通过扩展这些结果，我们构建了一个框架，将 Krylov 子空间方法和稳定迭代方法应用于具有大且稠密系数矩阵的一般线性方程组的预处理。我们通过在日本应用数学学会和SWoPP上展示上述结果，向专业领域的研究人员介绍了这些结果。此外，我们将半定规划问题的原对偶内点法应用到量子化学领域，成功地解决了传统算法难以解决的优化问题，并在论文中进行了总结。