線形計画法を用いた非線形方程式の全解探索法

概要

論文の詳細を見る
区間解析は非線形方程式のすべての解を求める代表的な方法として知られている. しかし区間解析は一般に計算効率が非常に悪く, 問題の次元の増加とともに計算時間が指数関数的に増大するという欠点をもつ. 本論文では, 区間解析に線形計画法を導入した, 非線形方程式の新しい全解探索法を提案する. 本手法の基本的なアイデアは次の通りである. まず与えられた領域に対し, 区間拡張を用いて非線形関数の上限と下限を求め, 非線形関数を補助変数と線形不等式で置き換えることにより, 非線形方程式を一旦線形計画問題に定式化する. そのような線形計画問題の実行可能領域は, もとの非線形方程式の与えられた領域におけるすべての解を含むので, 線形計画法 (単体法) を適用して実行可能領域の存在・非存在を判定する. もし実行可能領域が存在しなければ, その領域に解は存在しないので, それを除去し, 次の領域の探索に移る. このような解の非存在判定テストの導入により, 従来の区間解析では全く解くことのできなかった大規模非線形方程式のすべての解 (あるいはすべての解曲線) を非常に効率よく求めることが可能となる.
1997-07-25