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

基于计算统计的高效全局优化方法的开发

• 批准号: 12J04020
• 负责人: 合田 隆
• 金额: $ 1.41万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2012
• 资助国家: 日本
• 起止时间: 2012 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-12J04020/
• 关键词: 計算統計学; 大域的最適化; 準モンテカルロ法; 一様分布列

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

今年，我们研究了（1）准蒙特卡洛方法的理论用于平滑函数的数值集成，以及（2）准蒙特卡carlo方法在退火（一种全局优化方法）中的应用。关于（1），我们进一步开发了去年的结果，并研究了一组关键点的构建，这些点根据整体的平滑度来达到最佳收敛速率。常规已知的构造方法称为高阶多项式晶格规则，但是点集的构造需要指数计算，具体取决于平滑度。因此，我们提出了一种称为“交错的多项式晶格规则”的方法，以证明可以达到最佳收敛速率，并证明可以根据平滑度来用线性计算复杂性构建点集。此外，为了使用高阶多项式晶格规则减少点集的计算量，我们考虑了一种方法，在该方法中，以称为帐篷转换的方法更改了点集的排列，这表明可以减少构建良好点所需的计算量。上述结果汇编为论文，目前正在提交学术期刊。另一方面，在研究（2）中，我们考虑了在提出候选解决方案并在称为退火的全球最佳解决方案搜索算法中接受和拒绝它们的过程中使用准蒙特卡洛方法。进行了理论分析，结果表明，如果用于输入的一组点有足够的条件，即使是确定的输入也可以获得全局最佳解决方案。但是，目前的尝试并未成功，因为文献发现没有一组满足这种足够条件的要点。因此，有必要进行更详细的分析，并考虑是否削弱应满足的足够条件。

项目成果

被積分関数の滑らかさに応じた準モンテカルロ法

取决于被积函数平滑度的拟蒙特卡罗方法

• 发表时间: 2013
• 作者: Takuya Niikawa;Riichiro Hira;Toshihiro Kotani;takuya niikawa;takuya niikawa;Takuya Niikawa;Takashi Goda;Takashi Goda;合田 隆
• 通讯作者: 合田 隆

Construction of interlaced scrambled polynomial lattice rules

交错置乱多项式格规则的构造

• 发表时间: 2013
• 作者: Takuya Niikawa;Riichiro Hira;Toshihiro Kotani;takuya niikawa;takuya niikawa;Takuya Niikawa;Takashi Goda;Takashi Goda
• 通讯作者: Takashi Goda