線形計画法を用いた非線形システムの全解探索アルゴリズム開発とLSI設計への応用

点击翻译按钮获取中文摘要

区間解析は非線形方程式のすべての解を求める代表的な方法として知られている.しかし区間解析は一般に計算効率が非常に悪く,問題の次元の増加とともに計算時間が指数関数的に増大するという欠点をもつ.本研究では,区間解析に線形計画法を導入した,非線形方程式の新しい全解探索法を提案した.この方法の基本的なアイデアは,「非線形問題を線形計画問題に置き換えて解く」,すなわち非線形方程式という曲がりくねった世界の問題を平坦な世界に引きずり込んで料理しようというものである.具体的には,非線形方程式を線形等式と線形不等式で置き換え(幾何学的には関数曲線を多角形で囲み),非線形方程式を一旦線形計画問題に定式化してから,それに線形計画法を適用するというものである.この方法の導入により,従来の区間解析では全く解くことのできなかった100変数方程式をはじめとする様々な非線形方程式の全解探索に成功した.この成果については,既に国際会議や外国論文誌等で発表している.また上記のアイデアを区分的線形回路の全解探索問題にも応用し,線形領域数10^<100>の超大規模問題を世界で初めて実用時間内で解くことに成功した.この成果も国際会議や外国論文誌等で発表を行っている.さらに回路シミュレーションと関連して,「非線形回路の安定解に収束するホモトピー法」を開発した.一般に回路方程式の解は安定解とは限らないため,シミュレーションにより得られた解が実際の回路では観測されないという混乱が生じていたが,この方法は大域的収束性をもつと同時に,高い確率で実用上重要な安定解に収束する.その他,高分子化学の研究者との共同研究により,上記のアルゴリズムを用いた高分子溶液の多相平衡の研究に取り組み,実験では測定が困難な様々な興味深いメカニズム(高圧力下での共存曲線の対称性の変化など)を解明することに成功した.