【研究領域課題番号】21K11767 (KAKENデータベースで見る）

【研究キーワード】

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

【研究成果の概要】

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

【研究種目】基盤研究(C)

【研究期間】2021-04-01 - 2024-03-31

【配分額】3,900千円 (直接経費: 3,000千円、間接経費: 900千円)

【研究領域課題番号】18K11176 (KAKENデータベースで見る）

【研究キーワード】

応用数学 / 数理最適化 / 錐最適化 / 混合整数計画問題 / 半整数制約 / 育種学 / 種別構成問題

【研究成果の概要】

本研究課題では、種別構成問題において各変数が半整数となるような制約を付加した最適化問題に対する効率的な計算手法の開発を行った。錐分割手法では、切除平面の計算が解析的に行えるようにし、半整数制約と合わせて混合整数計画問題を解く反復解法を構築した。また、別の手法として、半整数制約と錐制約をそれぞれの子問題に分解する方法を改良し、一部の制約を含ませることで良好な解を生成可能とした。

【研究の社会的意義】

半整数制約は、変数が 0 あるいは一定の範囲の整数となっているような制約である。例えばポートフォリオ構築などであれば、資産をポートフォリオに組み込む場合に手数料などから最低限組み込むべき量が決まっている場合などが想定される。本研究で構築した計算手法は半整数制約を伴うような錐最適化問題に特に効果が高いと考えられる。また、数理最適化問題が複雑になったときに子問題への分解は良く行われる手法であり、特定の制約を含ませる本研究の方法は多くの手法の改善に利用できる可能性がある。

【研究種目】基盤研究(C)

【研究期間】2018-04-01 - 2022-03-31

【配分額】4,030千円 (直接経費: 3,100千円、間接経費: 930千円)

【研究分野】数理情報学

【研究領域課題番号】15K00032 (KAKENデータベースで見る）

【研究キーワード】

応用数学 / 数理最適化 / 錐最適化 / 育種学 / 種別構成問題 / 錐最適化理論 / 畜産学

【研究成果の概要】

種別構成問題は混合整数二次錐最適化問題として定式化できる。本研究では、錐最適化アプローチに基づいて効率的なアルゴリズムを構築し、高速な計算手法を開発した。二次錐分割による線形近似では、最適解が得られる理論的枠組みの中で、従来提案されてきた計算手法の10分の1程度に計算時間を短縮した。また、steep ascent method は、最適解の保証はないものの良質な解を数秒程度という短時間で得ることを可能とした。

【研究の社会的意義】

種別構成問題は、育種学などから生じる数理最適化問題である。例えば「数千種の遺伝子から割合を決めて樹木園を作るときに、遺伝子の多様性を維持できる範囲で利益を最大にする割合の算出」の計算などを数理モデル化したものである。この計算時間が短縮されることで、遺伝子のパラメータなどを変えての複数回のシミュレーションの実施が容易になる。また、混合整数二次最適化問題は種別構成問題以外にも多くの応用を持っていることが知られており、本研究で開発した高速な計算解法は、それらの応用にも適用可能な範囲があると考えられる。

【研究種目】基盤研究(C)

【研究期間】2015-04-01 - 2019-03-31

【配分額】3,510千円 (直接経費: 2,700千円、間接経費: 810千円)

【研究分野】社会システム工学・安全システム

【研究領域課題番号】24710161 (KAKENデータベースで見る）

【研究キーワード】

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

【研究成果の概要】

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

【研究種目】若手研究(B)

【研究期間】2012-04-01 - 2015-03-31

【配分額】2,990千円 (直接経費: 2,300千円、間接経費: 690千円)

【研究分野】社会システム工学・安全システム

【研究領域課題番号】21710148 (KAKENデータベースで見る）

【研究キーワード】

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

【研究成果の概要】

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

【研究種目】若手研究(B)

【研究期間】2009 - 2011

【配分額】2,860千円 (直接経費: 2,200千円、間接経費: 660千円)

【研究分野】社会システム工学・安全システム

【研究領域課題番号】18710141 (KAKENデータベースで見る）

【研究キーワード】

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

【研究成果の概要】

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

【研究種目】若手研究(B)

【研究期間】2006 - 2008

【配分額】430千円 (直接経費: 400千円、間接経費: 30千円)