最適性条件

関数\(f: \mathbb{R}^n \to \mathbb{R}\)に対する無制約最適化問題

\[ \newcommand{\R}{\mathbb{R}} \newcommand{\b}[1]{ \boldsymbol{#1} } \min_{\b{x}\in\R} f(\b{x}) \tag{1} \]

について考える。

凸とは限らない関数の最適化では、局所最適解を求めることが現実的な目標になる

Note

最適解 実行可能領域（feasible region）\(S\)における\(\b{x}^* \in S\)が任意の\(\b{x} \in S\)に対して

\[ f(\b{x}^*) \leq f(\b{x}) \]

を満たすとき、\(\b{x}^*\)をその問題の最適解（optimal solution）、あるいは**大域的最適解（global optimal solution）**という。

Note

局所最適解 \(\b{x}^* \in S\)に対して\(\varepsilon > 0\)が存在し、

\[ \b{x} \in B(\b{x}^*, \varepsilon) \cap S \implies f(\b{x}^*) \leq f(\b{x}) \]

が成り立つとき、\(\b{x}^* \in S\)を**局所最適解（local optimal solution）**という。

ただし

\[ B(\b{x}^*, \varepsilon) = \{ \b{y} \in \R^n | \|\b{x} - \b{y} \| < \varepsilon \} \]

は点\(\b{x}\)の\(\varepsilon\)近傍

目的関数が微分可能なら、局所最適解における勾配はゼロベクトルとなる

Note

1次の必要条件 関数\(f: \R^n \to \R\)は1回微分可能とし、\(\b{x}^* \in \R^n\)を問題(1)の局所最適解とする。このとき

\[ \nabla f(\b{x}^*) = \b{0} \]

が成り立つ

ここで\(\nabla f(\b{x})\)は勾配（gradient）

\[ \nabla f(\b{x}) = \left( \frac{\partial f}{\partial x_1} (\b{x}), \dots, \frac{\partial f}{\partial x_n} (\b{x}) \right)^T \in \R^n \]

である

ヘッセ行列の情報で局所最適解かどうかを判定することができる

2回微分可能な関数\(f\)のヘッセ行列（Hessian）\(\nabla^2 f(\b{x}) \in \R^{n\times n}\)は

\[ (\nabla^2 f(\b{x}))_{ij} = \frac{\partial^2 f}{\partial x_i \partial x_j} (\b{x}), \hspace{1em} i, j = 1, \dots, n \]

である

Note

2次の必要条件 \(\b{x}^* \in \R^n\)が問題\((1)\)の局所最適解のとき、

\[ \nabla^2 f(\b{x}^*) \succeq \b{O} \]

となる（\(\succeq \b{O}\)は非負正定値行列（non-negative definite matrix）の意味）