大域的最適化

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

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

       \begin{array}{ll}
               \mbox{min.} & f(\x) \\
               \mbox{s. t.} & \x := (x_1, \ldots, x_n) \in D, 
       \end{array}

の大域的最適解，つまり

       f(\x^*) \leq f(\x), \quad \forall\, \x \in D,

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

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

       \begin{array}{ll}
               \mbox{min.} & f(\x) \\
               \mbox{s. t.} & \x \in D := \{\x \in \R^n \mid \A \x \geq \b\}.
       \end{array}

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

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

       V := \{\x' + \theta_i \u^i \mid \theta_i \geq 0,\;  i = 1, \ldots, n\} \cap 

\{\x \in \R^n \mid f(\x) = f^\circ\}

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

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

       S' := S \cap \{\x \in \R^n \mid \a_i^{\T} \x \geq b_i\}

に更新して$\x'$と共に実行不可能な領域を切除する．実行可能集合$D$が$S$の部分集合なので$f(\x')$は大域的最適値の下界値を与えるが，以上の操作を繰り返して $\x' \in D$となれば，$\x'$が大域的最適解である．

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

       f(\x) := \sum_{j=1}^n f_j(x_j).

ただし，$f_j$はすべて凹関数である．実行可能集合$D$を含む矩形$M := \{\x \in \R^n \mid l_j \leq x_j \leq u_j,\; j = 1, \ldots, n\}$を定義し，これを複数の小さな矩形

       M^k := \{\x \in \R^n \mid l_j^k \leq x_j \leq u_j^k\}, \quad
       k = 1, \ldots, K,

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

\begin{description}

       \item[限定操作\ ] $D \cap M^k$上における$f$の下界値$f'$を計算し，その値がそれまでに得られた最も

小さな目的関数値$f^\circ$以上ならば$M^k$を考察の対象から外す;

       \item[分枝操作\ ] $f' < f^\circ$ならば，$M^k$を2つの矩形 $M^{k_1}$,
       $M^{k_2}$に分割する

\end{description}

を繰り返す．効率の鍵を握る下界値$f'$には，通常$(l_j^k, f_j(l_j^k))$と$(u_j^k, f_j(u_j^k))$を通るアフィン関数

       g_j(x_j) := \frac{f(u_j^k) - f(l_j^k)}{u_j^k - l_j^k} x_j +
       \frac{u_j^k f(l_j^k) - l_j^k f(u_j^k)}{u_j^k - l_j^k},
       \quad j = 1, \ldots, n,

を定義し，その和$g(\x) := \sum_{j=1}^n g_j(x_j)$の$D \cap M^k$上における最小値が用いられる．関数$g$は$M^k$上における$f$の最も大きな下界値を与える凸関数で，凸包絡関数 (convex envelope function)と呼ばれる．しかし，アフィン関数であるので単体法や内点法を使って容易に最小値$f'$を計算することができる．

　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.