非凸計画法のアルゴリズムとその応用に関する研究

最適化問題を定義する関数のうち少なくとも一つが凸ではない非凸計画問題は、多数の局所的最小解が存在するため、大域的に最小な解を見つけることは困難とされてきた。しかし、非凸型関数がある種の合成関数として表される場合には、凸計画問題を解く場合と遜色のない手間で大域的最小解が得られることを解明した。また、そのためのアルゴリズムを開発し、計算機上での実験で有効性を確認した。このクラスの合成関数の代表例は、複数の凸関数の積であり、これは凸関数にも凹関数にもならない。2つの凸関数の積を含む凸乗法計画問題が効率的に解けることは既に知られているが、k(≧2)個の積を含む問題に対しても効率よく大域的最小解を求めることができた。開発したアルゴリズムは、問題の実行可能領域を凸多面体などで近似し、その精度を逐次高めてゆくことで、近似解を大域的最小解に収束させている。この方法が効果的に機能するのは、次元nの問題を次元kの問題に変換できる場合であり、一般にはk個の凸関数を引数とする準凹関数に対してこれが可能である。他の合成関数の場合でも、例えば凸関数の積の和の最小化などに対しては、わずかな変更でアルゴリズムを適用することができる。変換された問題の目的関数値の計算に従来の凸最小化手法を利用することで、k<<nであればかなり大規模な問題まで解くことが可能となった。ワークステーション上での実験では、kが5未満であれば、nが100を越える問題まで解くことができたが、これは非凸計画問題としてはきわめて大規模なものである。また、同様な方法は、凸集合を囲む矩形面積の最小化や、凸集合に含まれる矩計面積の最大化など、非凸構造を有する計算幾何学問題に対しても有効なことが分かり、パラメトリック単体法と組み合わせてこれらを効率的に解くアルゴリズムの開発も行った。

最適化問題を定義する関数のうち少なくとも一つが凸ではない非凸計画問題は、多数の局所的最小解が存在するため、大域的に最小な解を見つけることは困難とされてきた。しかし、非凸型関数がある種の合成関数として表される場合には、凸計画問題を解く場合と遜色のない手間で大域的最小解が得られることを解明した。また、そのためのアルゴリズムを開発し、計算機上での実験で有効性を確認した。このクラスの合成関数の代表例は、複数の凸関数の積であり、これは凸関数にも凹関数にもならない。2つの凸関数の積を含む凸乗法計画問題が効率的に解けることは既に知られているが、k(≧2)個の積を含む問題に対しても効率よく大域的最小解を求めることができた。開発したアルゴリズムは、問題の実行可能領域を凸多面体などで近似し、その精度を逐次高めてゆくことで、近似解を大域的最小解に収束させている。この方法が効果的に機能するのは、次元nの問題を次元kの問題に変換できる場合であり、一般にはk個の凸関数を引数とする準凹関数に対してこれが可能である。他の合成関数の場合でも、例えば凸関数の積の和の最小化などに対しては、わずかな変更でアルゴリズムを適用することができる。変換された問題の目的関数値の計算に従来の凸最小化手法を利用することで、k<<nであればかなり大規模な問題まで解くことが可能となった。ワークステーション上での実験では、kが5未満であれば、nが100を越える問題まで解くことができたが、これは非凸計画問題としてはきわめて大規模なものである。また、同様な方法は、凸集合を囲む矩形面積の最小化や、凸集合に含まれる矩計面積の最大化など、非凸構造を有する計算幾何学問題に対しても有効なことが分かり、パラメトリック単体法と組み合わせてこれらを効率的に解くアルゴリズムの開発も行った。