📂最適化理論

数学における最適化技術

定義

1. 関数$f : \mathbb{R}^{n} \to \mathbb{R}$の関数値を最小にする$x^{ \ast } = \argmin_{x} f(x)$を見つける問題を最適化問題^{optimization Problem}と呼び、その問題を解くアルゴリズムを最適化技法と呼ぶ。最適化問題で与えられた関数$f$は特に目的関数^{objective function}と言う。
2. 全ての$x$に対して$f(x^{ \ast }) \le f(x)$を満たす$x^{ \ast }$を全域最適解^{global Optimizer}と呼ぶ。
3. 全ての$x \in \mathcal{N}$に対して$f(x^{ \ast }) \le f(x)$を満たす$x^{ \ast }$の近傍$\mathcal{N}$が存在する場合、その$x^{ \ast }$を局所最適解^{local Optimizer}と呼ぶ。

これらの定義では、不等式の向きが逆でも、つまり最大化について説明されても、それらは総じて最適化と呼ばれる。

説明

最適化技法を使用する人々は「利益を最大化」または「コストを最小化」と言うことができるが、数学者にとっては最大か最小かは重要な問題ではない。最小化が最適化とほぼ同義とされる理由は、最小化問題で使用されるアルゴリズムが、$-1$を単に乗じることで最大化問題にも適用できるからであり、数学的に非常に重要な関数であるメトリックやノルムが$0$以上の実数の集合を値域に持つから、つまり最小値が存在するという理由からである。

近年、ディープラーニングが流行しているが、目的関数（またはコスト関数、損失関数）は通常、スムーズであると想定されているが、必ずそうであるとは限らない。したがって、それを克服するためのアルゴリズムとメソッドも研究されてきた。目的関数の定義域が必ずしも$\mathbb{R}^{n}$でなければならないわけではない。

全域最適解

最適解の存在性は、数々の条件によって示すことができるかもしれないが、局所最適解が全域最適解であることを示す定理はない。理想的には誰もが最適解を見つけたいと思うが、実際に見つけた解が最適解であることを心から期待することはほとんどない。最適化問題は多くあるが、すべての問題にピッタリ合う「最適化された」最適化技法はないため、数多くの改善アルゴリズムが開発されてきた。

最適解の厳密さと孤立性

通常は以下の定義は無意味であるが、一応言及しておく。

4. 全ての$x \in \mathcal{N}$に対して$f(x^{ \ast }) < f(x)$を満たす$x^{ \ast }$の近傍$\mathcal{N}$が存在する場合、その$x^{ \ast }$を厳密な局所最適解^{strict Local Optimizer}と呼ぶ。
5. 全ての$x \in \mathcal{N}$に対して$f(x^{ \ast }) < f(x)$を満たす$x^{ \ast }$の唯一の近傍$\mathcal{N}$が存在する場合、その$x^{ \ast }$を孤立した局所最適解^{isolated Local Optimizer}と呼ぶ。