局所最適解と大域最適解

大域最適解は実行可能領域全体で最も良い点。 局所最適解は「その近くでは最も良い」だけの点。

$$x^{\star }\text{ が局所最適}⟺\exists \epsilon >0,\forall x\in ℱ\cap B(x^{\star },\epsilon ),f(x^{\star })\le f(x)$$

なぜこの区別が効くのか#

ほとんどのアルゴリズムは近くしか見ていない。勾配降下法は現在地の傾きしか 知らないし、山登り法は近傍しか調べない。だから停止したときに得られるのは 原則として局所最適解であって、大域最適解である保証はない。

ここで効いてくるのが凸性で、 目的関数と実行可能領域が凸なら、局所最適解は自動的に大域最適解になる。 凸性が保証されないなら、複数の初期点から始める、 悪化も一定確率で受け入れる、 集団で探すといった工夫で、局所解から抜け出す仕掛けを入れることになる。

論文を読むときの注意

「収束した」は多くの場合「局所最適解に到達した」あるいは 「更新量が閾値を下回った」を意味する。大域最適性の主張かどうかは、 凸性の仮定が置かれているかで見分けるのが早い。

参考文献#

• Stephen Boyd, Lieven Vandenberghe. Convex Optimization, §4.2.2. Cambridge University Press, 2004. https://web.stanford.edu/~boyd/cvxbook/
• Jorge Nocedal, Stephen J. Wright. Numerical Optimization, §2.1. Springer, 2006. https://doi.org/10.1007/978-0-387-40065-5