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

応用数学 / 数理最適化 / 半正定値計画問題 / 錐最適化 / 双対問題 / 射影勾配法

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

数理最適化 / 非線形最適化 / 半正定値計画問題 / 数値計算 / 応用数学

非線形半正定値計画問題は、変数行列の固有値に関する制約を課した数理最適化問題であり、金融工学や不確実なデータなどを扱う最適化などに利用できる。
本研究では、上下限制約付き非線形半正定値計画問題に対して、現在の反復点と半正定値行列のなす錐の境界までの間の距離情報を探索方向に取り込むことにより、効率的に求解する反復計算手法を提案した。
数値実験を通して、本研究の提案手法は３次以上の項を含むような非線形関数に対して実行可能方向法より短時間での求解を達成しており、錐の境界までの情報の有効性が示された。

応用数学 / ハイパフォーマンスコンピューティング / 数理最適化 / 並列計算 / 半正定値計画問題 / センサーネットワーク

半正定値計画問題の計算時間短縮は、センサネットワーク問題や多項式計画問題など様々な問題にとって重要である。本研究では並列計算で計算時間短縮を行うが、その計算時間の多くを占めるSchur補完行列が疎行列となる特徴を注目し、行列要素ごとの計算時間を見積もることで計算負荷分散を行い、効率的な並列計算手法の提案を行った。数値実験を通して、提案手法により大幅な計算時間短縮が達成されることを確認した。

数理計画法 / 並列計算 / 半正定値計画問題 / 応用数学 / ハイパフォーマンス・コンピューティング / 数理最適化 / 量子化学 / 大規模

半正定値計画問題は、量子化学や制御理論など幅広い応用を持つ重要な数理計画問題である。しかしながら、量子化学などから発生する半正定値計画問題は大規模になる傾向が強く、一台の計算機では求解が難しい。本研究では、Schur補完行列にかかる計算に並列計算を適用することで、既存ソフトウェアでは不可能であった大規模な半正定値計画問題の求解を実現した。さらに行列の特徴を活用し、高い並列効果を得ることに成功した。