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

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

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