計算統計学に基づく効率的な大域的最適化アプローチの開発

今年度は(1)滑らかな関数の数値積分を目的とした準モンテカルロ法の理論と(2)大域的最適化手法である焼きなまし法への準モンテカルロ法の応用について研究した。(1)については、昨年度の成果をさらに発展させ、被積分関数の滑らかさに応じて最適な収束レートを達成するような決定的な点集合の構成法について研究した。従来知られていた構成法にhigher order polynomial lattice ruleというものがあったが、点集合の構成には滑らかさに応じて指数的な計算量が要求されるものであった。そこで、interlaced polynomial lattice ruleという方法を考え、最適な収束レートを達成できることを証明するとともに、この方法を用いれば滑らかさに応じて線形な計算量で点集合が構成できることを示した。また、higher order polynomial lattice ruleを用いた点集合の構成に要する計算量そのものを低減するために、tent変換と呼ばれる方法で点集合の配置を変えるというアプローチを考え、これによって良い点集合を構成するのに必要な計算量を減らせることを示した。以上の結果は、それぞれ論文にまとめ学術雑誌に投稿中である。一方、(2)に関する研究では、焼きなまし法と呼ばれる大域的最適解の探索アルゴリズムにおいて、解候補の提案ならびに受理・棄却の過程に準モンテカルロ法を用いることを考えた。理論的な解析を行い、入力に用いられる点集合がある十分条件を満たせば、決定的な入力によっても大域的最適解が得られる、という結果を得た。しかし、そのような十分条件を満たす点集合は存在しないことが文献上分かったため、現時点の試みでは成功していない。したがって、より詳細な解析を行い、満たすべき十分条件を弱められないか、といった検討が今後必要である。

今年度は(1)滑らかな関数の数値積分を目的とした準モンテカルロ法の理論と(2)大域的最適化手法である焼きなまし法への準モンテカルロ法の応用について研究した。(1)については、昨年度の成果をさらに発展させ、被積分関数の滑らかさに応じて最適な収束レートを達成するような決定的な点集合の構成法について研究した。従来知られていた構成法にhigher order polynomial lattice ruleというものがあったが、点集合の構成には滑らかさに応じて指数的な計算量が要求されるものであった。そこで、interlaced polynomial lattice ruleという方法を考え、最適な収束レートを達成できることを証明するとともに、この方法を用いれば滑らかさに応じて線形な計算量で点集合が構成できることを示した。また、higher order polynomial lattice ruleを用いた点集合の構成に要する計算量そのものを低減するために、tent変換と呼ばれる方法で点集合の配置を変えるというアプローチを考え、これによって良い点集合を構成するのに必要な計算量を減らせることを示した。以上の結果は、それぞれ論文にまとめ学術雑誌に投稿中である。一方、(2)に関する研究では、焼きなまし法と呼ばれる大域的最適解の探索アルゴリズムにおいて、解候補の提案ならびに受理・棄却の過程に準モンテカルロ法を用いることを考えた。理論的な解析を行い、入力に用いられる点集合がある十分条件を満たせば、決定的な入力によっても大域的最適解が得られる、という結果を得た。しかし、そのような十分条件を満たす点集合は存在しないことが文献上分かったため、現時点の試みでは成功していない。したがって、より詳細な解析を行い、満たすべき十分条件を弱められないか、といった検討が今後必要である。