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

非凸规划算法及其应用研究

基本信息

批准号：
04832010
负责人：
久野誉人
金额：
$ 0.96万
依托单位：
University of Tsukuba
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1992
资助国家：
日本
起止时间：
1992 至无数据
项目状态：
已结题

项目摘要

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

对于定义优化问题的至少一个函数不是凸的非凸规划问题，存在许多局部最小解，并且一直认为很难找到全局最小解。然而，我们发现，当非凸函数表示为一种复合函数时，可以用与解决凸规划问题相同的工作量来获得全局最小解。我们还为此开发了一种算法，并通过计算机实验证实了其有效性。这类复合函数的典型例子是多个凸函数的乘积，它既不是凸函数也不是凹函数。已知涉及两个凸函数的乘积的凸乘法规划问题可以被有效地求解，但是对于涉及k(≥2)个乘积的问题也可以有效地找到全局最小解。所开发的算法利用凸多面体等近似问题的可行区域，并逐步提高其精度，使近似解收敛于全局最小解。当 n 维问题可以转化为 k 维问题时，该方法有效，这对于以 k 个凸函数为参数的拟凹函数来说通常是可能的。该算法只需稍作修改即可应用于其他复合函数，例如最小化凸函数的乘积之和。通过使用传统的凸最小化方法来计算变换问题的目标函数值，只要k<<n，就可以解决相当大规模的问题。在工作站上的实验中，只要 k 小于 5，我们就能够解决 n 超过 100 的问题，这对于非凸规划问题来说是非常大的。人们还发现，类似的方法对于非凸结构的计算几何问题是有效的，例如最小化凸集周围的矩形的面积以及最大化凸集内包含的矩形的总面积。还开发了一种算法，通过与参数单纯形法相结合来有效地解决这些问题。