最適性条件

最適性条件#

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

\begin{matrix} (1) & min_{x \in R} f (x) \end{matrix}

について考える。

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

Note

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

f (x^{*}) \leq f (x)

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

Note

局所最適解 $x^{*} \in S$ に対して $ε > 0$ が存在し、

x \in B (x^{*}, ε) \cap S ⟹ f (x^{*}) \leq f (x)

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

ただし

B (x^{*}, ε) = {y \in R^{n} | ‖ x - y ‖ < ε}

は点 $x$ の $ε$ 近傍

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

Note

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

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

が成り立つ

ここで $\nabla f (x)$ は勾配（gradient）

\nabla f (x) = {(\frac{\partial f}{\partial x_{1}} (x), \dots, \frac{\partial f}{\partial x_{n}} (x))}^{T} \in R^{n}

である

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

Note

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

\nabla^{2} f (x^{*}) ⪰ O

となる（ $⪰ O$ は非負正定値行列（non-negative definite matrix）の意味）