連続と離散の融合によるロバストアルゴリズム構築

通过连续和离散融合构建鲁棒算法

• 批准号: 16092204
• 负责人: 杉原 厚吉
• 金额: $ 18.5万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas
• 财政年份: 2004
• 资助国家: 日本
• 起止时间: 2004 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-16092204/
• 关键词: 厳密計算法; 離散凸解析; カット凸多面体; パーフェクトサンプリング; 符号可解性; ロバスト線形不等式; 長方形詰込み問題; ロバスト構造設計; ロバスト計算; ハブ空港設計問題; 独立偶因子; 四面体メッシュ; ボート航行距離方程式; 行列拡大法; カッターパス生成法; 細分割曲面; パーフェクトグラフ分解; 符号行列; チャンネル割当; ジャンプシステム; 離散凸; ディジタルトポロジー; ディジタル近似; 最適化; 最適航路; マルコフサンプリン

従来は連続計算の分野と離散計算の分野に分かれてそれぞれ独立になされてきたアルゴリズム研究の知見を融合し,両者の手法の長所を補完し合うことによって,諸計算のロバスト性を確保するための計算原理を開拓することが本研究の目的であった.本年度もこの目的に沿って研究を行い,次のような成果を得た.幾何計算の分野では,2次元および3次元の球ボロノイ図のロバストな計算法を開発した.これは,位相構造をいつも正しく判定できる高精度計算を用いるもので,必要な精度をもとの入力データの2d+4倍に置き換えることに成功した.また,流れの中でのボートの最短経路を求めるロバスト解法を高次元と曲面上とへ拡張した.さらに長方形詰込み問題の実用的解法を構成するとともに,一般の形の図形詰込み結果に基づいてハードメタルを切り取るためのカッターパス生成法を構成した.離散凸解析の分野では,定パリティジャンプシステム上のM凸関数が,合成積やグラフによる変換によってM凸性を保存することを示した.量子計算の分野では,カット凸多面体とベル不等式の関係を明らかにし,量子状態を記述するより強力な不等式を得た.サンプリングの分野では,マルコフ連鎖を用いたモンテカルロ法のためのパーフェクトサンプリング方法を開発した.組合せ最適化の分野では,数理計画問題の符号情報のみから最適解の性質を調べる方法を開発した.制御計算の分野では,制御対象パラメータのとり得る区間の中で常に安定性が保証されるロバスト制御法を,ロバスト線形不等式を条件とする半正定値問題に帰着させて解く方法を与えた.構造設計の分野では,不確定な外力に対する構造物の解析法を開発した.これらの諸成果を通じて,「連続計算における知見と離散計算における知見の交流によって,計算の安定化をはかることができる」というロバストな計算を確保するための一つの原理の有効性を確認することができた.

我们的目标是通过结合传统上在连续计算和离散计算领域独立进行的算法研究知识，并通过探索计算原理来补充两种方法的优势，以确保各种计算的鲁棒性。这就是本次研究的目的。今年，我们本着这个目的进行了研究，得到了以下成果。在几何计算领域，我们开发了2维和3维球面Voronoi图的鲁棒计算方法我们开发了一种始终能够准确确定拓扑结构的方法。该方法采用可确定的高精度计算，成功地用原始输入数据的2d+4倍代替了所需的精度。此外，在扩展到曲面。此外，矩形。除了构造堆积问题的实用解决方案外，我们还基于一般形状 M 凸函数的图形堆积结果构造了一种切削硬质合金的刀具路径生成方法。我们证明了通过使用乘积和图进行变换可以保留 M 凸性。在量子计算领域，我们阐明了割凸多面体与贝尔不等式之间的关系，并获得了描述量子态的更强大的不等式。的领域我们开发了一种使用链链的蒙特卡罗方法的完美采样方法。在组合优化领域，我们开发了一种仅从数学规划问题的符号信息来研究最优解的属性的方法。在该领域在控制计算中，我们开发了一个目标参数提出了一种求解鲁棒控制方法的方法，该方法通过将鲁棒控制方法简化为受鲁棒线性不等式影响的正半定问题，保证在数据可能的范围内始终保持稳定性。在结构设计领域，不确定性我们开发了一种方法分析结构对抗外力的影响。通过这些结果，我们确认了确保鲁棒计算的一个原则的有效性：“连续计算的知识和离散计算的知识的交换可以稳定计算。”我能够做到这一点。

项目成果

A general construction method for mixed-level supersaturated design

• DOI: 10.1016/j.csda.2004.07.018
• 发表时间: 2006-01
• 期刊: Comput. Stat. Data Anal.
• 作者: S. Yamada;M. Matsui;Tomomi Matsui;D. Lin;Takenori Takahashi

Submodular function minimization

• DOI: 10.1007/s10107-006-0084-2
• 发表时间: 2008-03-01
• 期刊: MATHEMATICAL PROGRAMMING
• 影响因子: 2.7
• 作者: Iwata, Satoru

流れの中の航行シミュレーションと最適経路の探索

流动中的导航模拟并搜索最佳路线

• 发表时间: 2007
• 期刊: シミュレーション 26・2
• 作者: Y. Kanno;I. Takewaki;西田 徹志
• 通讯作者: 西田 徹志

Proximity Theorems of Discrete Convex Functions

离散凸函数的邻近定理

• 发表时间: 2004
• 期刊: Mathematical Programming A99・3
• 作者: Kazuo Murota;Akihisa Tamura
• 通讯作者: Akihisa Tamura

疎性の利用によるロバスト半正定値計画法の効率化

利用稀疏性提高鲁棒半定规划的效率

• 发表时间: 2007
• 期刊: 計測自動制御学会論文集 43・2
• 作者: N. Kakimura;S. Iwata;S. Iwata;猪阪・大石
• 通讯作者: 猪阪・大石