大規模最適化問題に対するハイブリッド勾配法の提案とその応用

勾配法とは、最適化問題に対する反復解法の1種である。ニュートン法等と比較して、1反復あたりの計算量やメモリ使用量が少ないために、大規模な最適化問題の解法として適している。本研究課題では、勾配法と様々な最適化手法を組合せたハイブリッド勾配法の開発に取り組んでいる。本年度は2つの研究成果を得ることができた。1) 1つ目の成果は、組合せ条件付き２次最適化問題のDNN緩和の定式化に対して、ハイブリッド勾配法に基づく解法を提案したことである。組合せ条件つき2次最適化問題は、最大カット問題や2次割当問題などの組合せ最適化問題を包含する、NP困難な問題クラスである。その最適値の下界を与える凸緩和問題 (比較的解きやすい問題) を構成して解くことは長年研究されている重要なテーマであり、これまで様々な凸緩和問題の定式化が提案されてきた。本研究では、組合せ条件付き２次最適化問題に対して、DNN凸緩和問題を導くフレームワークを提案し、理論・数値実験の両面から解析を行った。その結果、既存の様々なDNN凸緩和問題の最適値が一致する一方で、各問題の数値的な性質は大きく異なることが明らかになった。ハイブリッド勾配法を用いた解法は、数値的性質の悪いDNN凸緩和問題に対しても精度良く解を求められることがわかった。2) 1つ目の研究成果の知見をもとに、ハイブリッド勾配法に様々な高速化の工夫を加え、DNN凸緩和問題に対する実用的な解法を提案した。また、その解法を実装したソフトウェアを公開した。このソフトウェアは、入力された問題のDNN凸緩和問題を構築し、ハイブリッド勾配法を用いて解くものである。組合せ条件付き2次最適化問題だけでなく、より一般的な多項式最適化問題を入力として扱うことができる。様々なベンチマークに対して数値実験を行い、提案ソフトウェアが既存ソフトウェアよりも良い下界を高速に算出できることを示した。

勾配法とは、最適化問題に対する反復解法の1種である。ニュートン法等と比較して、1反復あたりの計算量やメモリ使用量が少ないために、大規模な最適化問題の解法として適している。本研究課題では、勾配法と様々な最適化手法を組合せたハイブリッド勾配法の開発に取り組んでいる。本年度は2つの研究成果を得ることができた。1) 1つ目の成果は、組合せ条件付き２次最適化問題のDNN緩和の定式化に対して、ハイブリッド勾配法に基づく解法を提案したことである。組合せ条件つき2次最適化問題は、最大カット問題や2次割当問題などの組合せ最適化問題を包含する、NP困難な問題クラスである。その最適値の下界を与える凸緩和問題 (比較的解きやすい問題) を構成して解くことは長年研究されている重要なテーマであり、これまで様々な凸緩和問題の定式化が提案されてきた。本研究では、組合せ条件付き２次最適化問題に対して、DNN凸緩和問題を導くフレームワークを提案し、理論・数値実験の両面から解析を行った。その結果、既存の様々なDNN凸緩和問題の最適値が一致する一方で、各問題の数値的な性質は大きく異なることが明らかになった。ハイブリッド勾配法を用いた解法は、数値的性質の悪いDNN凸緩和問題に対しても精度良く解を求められることがわかった。2) 1つ目の研究成果の知見をもとに、ハイブリッド勾配法に様々な高速化の工夫を加え、DNN凸緩和問題に対する実用的な解法を提案した。また、その解法を実装したソフトウェアを公開した。このソフトウェアは、入力された問題のDNN凸緩和問題を構築し、ハイブリッド勾配法を用いて解くものである。組合せ条件付き2次最適化問題だけでなく、より一般的な多項式最適化問題を入力として扱うことができる。様々なベンチマークに対して数値実験を行い、提案ソフトウェアが既存ソフトウェアよりも良い下界を高速に算出できることを示した。