《大域的最適化》

提供: ORWiki
ナビゲーションに移動 検索に移動

【たいいきてきさいてきか (global optimization)】

 ユークリッド空間上で定義された連続な実数値関数目的関数とし,の閉部分集合実行可能集合とする最適化問題:



に対して,その大域的最適解,つまり



を満足するを求める方法を大域的最適化という.目的関数と実行可能集合が共に凸性を満たす凸計画問題であれば,局所的な最適化によってを求めることができる.また,凸性を満たさなくとも,分数計画問題(fractional programming problem)や幾何計画問題(geometric programming problem)の一部は任意の局所的最適解で大域的にも最適となる.したがって,大域的最適化が本質的な意味をもつのは,目的関数値が異なる複数の局所的最適解をもつ非凸計画問題に対してであり,これを多極値大域的最適化問題(multiextremal global optimization problem)と呼ぶ.例えば,が凹関数でが凸多面体の凹最小化問題(concave minimization problem)の場合,局所的最適解は一般にの複数の端点に現われる.しかし,端点の数は膨大であり,その中から大域的に最適なものを見つけだすのは容易な作業でない.実際,この単純な例でさえ最悪計算量の上ではNP困難であることが知られている.そのため,現段階で一般の多極値大域的最適化問題を解決する有効な手段はなく,モンテカルロ法(Monte Carlo method)などのヒューリスティクスが唯一現実的なアプローチとなっている [2].

 このように困難な問題クラスではあるが,個々の問題の中には,その構造を利用することで現実的な計算時間のうちに大域的最適解の求められるものも少なくない [1].その代表例が,実は上にも述べた凹最小化問題である:



ここで,行列で次ベクトル,は凹関数(concave function),つまり凸関数である.この非凸計画問題を大域的に最適化するアルゴリズムとして,凹性カット法(concavity-cut method),外部近似法(outer approximation method),分枝限定法(branch-and-bound method)などがある [3].

 凹性カット法は,以下の操作を繰り返し,から大域的最適解以外の実行可能解をすべて除去しようとする方法である.局所的最適解を与えるの端点を見つけ,から出る本の稜線ベクトルと,それまでに得られた最も小さな目的関数値によって集合



を定義する.端点におけるの値がよりも悪ければ,は丁度個の点から構成されるが,それらを通る次元超平面によってと一緒に見込のない実行可能解もから切除する.目的関数が2次の凹関数である双線形計画問題 (bilinear programming problem)に対しては,より大きな領域を切除する方法も考案されている.

 外部近似法も超平面による切除を行うが,凹性カット法と違って実行可能解は1つも失わない.まず,次元単体や矩形などの単純な凸多面体で近似し,上で最小化する.これも凹最小化問題であるが,は端点の数が少ないので,それらの列挙で最小点は比較的容易に求められる.このが満たさないの制約式の1つを選び,



に更新してと共に実行不可能な領域を切除する.実行可能集合の部分集合なのでは大域的最適値の下界値を与えるが,以上の操作を繰り返して となれば,が大域的最適解である.

 分枝限定法には多くのバリエーションが存在するが,最も効力を発揮するのは目的関数が1変数凹関数の和に分離可能な場合である:



実行可能集合を含む矩形を定義し,これを複数の小さな矩形



に分割していく.基本となる操作は,組合せ最適化問題に使われる分枝限定法と同様で,まず を選んで


限定操作 上におけるの下界値を計算し,その値がそれまでに得られた最も小さな目的関数値以上ならばを考察の対象から外す;

分枝操作 ならば,を2つの矩形 , に分割する


を繰り返す.効率の鍵を握る下界値には,通常を通るアフィン関数



を定義し,その和上における最小値が用いられる.関数上におけるの最も大きな下界値を与える凸関数で,凸包絡関数 (convex envelope function)と呼ばれる.しかし,アフィン関数であるので単体法内点法を使って容易に最小値を計算することができる.

 DC計画問題(d.c. programming problem)や逆凸計画問題(reverse convex programming problem)などのより一般的な多極値大域的最適化問題も,凹最小化問題を逐次解くことで処理することができる [2, 3].



参考文献

[1] H. Konno, P.T. Thach and H. Tuy, Optimization on Low Rank Nonconvex Structures, Kluwer Academic Publishers, 1997.

[2] R. Horst and P.M. Pardalos (eds.), Handbook of Global Optimization, Kluwer Academic Publishers, 1995.

[3] R. Horst and H. Tuy, Global Optimization - Deterministic Approaches, 3rd ed., Springer-Verlag, 1996.