大域的最適化

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

　ユークリッド空間構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathbf{R}^n\, } 上で定義された連続な実数値関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } を目的関数とし，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathbf{R}^n\, } の閉部分集合$D\,$を実行可能集合とする最適化問題:

${\begin{array}{ll}{\mbox{min.}}&f({x})\\{\mbox{s. t.}}&x:=(x_{1},\ldots ,x_{n})\in D,\end{array}}\,$

の大域的最適解，つまり

構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f(x^{*})\leq f(x),\quad \forall \,x\in D,\,}

を満足する$x^{*}\in D\,$を求める方法を大域的最適化という．目的関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } と実行可能集合構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle D\, } が共に凸性を満たす凸計画問題であれば，局所的な最適化によって構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x^{*}\,} を求めることができる．また，凸性を満たさなくとも，分数計画問題(fractional programming problem)や幾何計画問題(geometric programming problem)の一部は任意の局所的最適解で大域的にも最適となる．したがって，大域的最適化が本質的な意味をもつのは，値が異なる複数の局所的最適解をもつ非凸計画問題に対してであり，これを多極値大域的最適化問題(multiextremal global optimization problem)と呼ぶ．例えば，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } が凹関数で構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle D\, } が凸多面体の凹最小化問題(concave minimization problem)の場合，局所的最適解は一般に$D\,$の複数の端点に現われる．しかし，端点の数は膨大であり，その中から大域的に最適なものを見つけだすのは容易な作業でない．実際，この単純な例でさえ最悪計算量の上ではNP困難であることが知られている．そのため，現段階で一般の多極値大域的最適化問題を解決する有効な手段はなく，モンテカルロ法(Monte Carlo method)などのヒューリスティクスが唯一現実的なアプローチとなっている [2]．

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

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \begin{array}{ll} \mbox{min.} & f(x) \\ \mbox{s. t.} & x \in D := \{x \in \mathbf{R}^n \mid \mbox{A} x \geq b\}. \end{array}\, }

ここで，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{A}\, } は$m\times n\,$行列で$b\,$は構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m\, } 次ベクトル，$f\,$は凹関数(concave function)，つまり構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle -f\, } が凸関数である．この非凸計画問題を大域的に最適化するアルゴリズムとして，凹性カット法(concavity-cut method)，外部近似法(outer approximation method)，分枝限定法(branch-and-bound method)などがある [3]．

　凹性カット法は，以下の操作を繰り返し，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle D\, } から大域的最適解以外の実行可能解をすべて除去しようとする方法である．局所的最適解を与える構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle D\, } の端点$x'\,$を見つけ，$x'\,$から出る$n\,$本の稜線ベクトル$u^{1},\ldots ,u^{n}\,$と，それまでに得られた最も小さな目的関数値$f^{\circ }\,$によって集合

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V := \{x' + \theta_i u^i \mid \theta_i \geq 0,\; i = 1, \ldots, n\} \cap \{x \in \mathbf{R}^n \mid f(x) = f^\circ\}\, }

を定義する．端点構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x'\, } における構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } の値が構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f^\circ\, } よりも悪ければ，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V\, } は丁度構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } 個の点から構成されるが，それらを通る$n\,$次元超平面によって構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x'\, } と一緒に見込のない実行可能解も構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle D\, } から切除する．目的関数$f\,$が2次の凹関数である双線形計画問題 (bilinear programming problem)に対しては，より大きな領域を切除する方法も考案されている．

　外部近似法も超平面による切除を行うが，凹性カット法と違って1つの実行可能解も失わない．まず，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle D\, } を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } 次元単体や矩形などの単純な凸多面体構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S \supseteq D\, } で近似し，$f\,$を$S\,$上で最小化する．これも凹最小化問題であるが，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S\, } は端点の数が少ないので，それらの列挙で最小点$x'\,$は比較的容易に求められる．この構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x'\, } が満たさない構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle D\, } の制約式の1つ構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a_i^{\top} x \geq b_i\, } を選び，$S\,$を

構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle S':=S\cap \{x\in \mathbf {R} ^{n}\mid a_{i}^{\top }x\geq b_{i}\}\,}

に更新して構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x'\, } と共に実行不可能な領域を切除する．実行可能集合$D\,$が$S\,$の部分集合なので構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f(x')\,} は大域的最適値の下界値を与えるが，以上の操作を繰り返して 構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x'\in D\,} となれば，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x'\, } が大域的最適解である．

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

$f(x):=\sum _{j=1}^{n}f_{j}(x_{j}).\,$

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

$M^{k}:=\{x\in \mathbf {R} ^{n}\mid l_{j}^{k}\leq x_{j}\leq u_{j}^{k}\},\quad k=1,\ldots ,K,\,$

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

限定操作　$D\cap M^{k}\,$上における$f\,$の下界値$f'\,$を計算し，その値がそれまでに得られた最も小さな目的関数値$f^{\circ }\,$以上ならば$M^{k}\,$を考察の対象から外す;

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

を繰り返す．効率の鍵を握る下界値$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.