Continuous Optimization

連続最適化

Theorem (Necessity)

$f:{\mathbb{R}}^n\to \mathbb{R}$とする。 $x^{\ast }\in {\mathbb{R}}^n$が局所的最小解とする。 $f$が$x^{\ast }$の近傍で微分可能とする。 このとき以下が成立。

$$\begin{array}{}\text{(1)}& \mathrm{\nabla }f(x^{\ast })=0\end{array}$$

さらに、$f$が$x^{\ast }$の近傍で2回連続微分可能ならば、${\mathrm{\nabla }}^{2}f(x^{\ast })$は半正定値行列になる。

proof.

$\mathrm{\nabla }f(x^{\ast })\ne 0$とする。 $d:=-\mathrm{\nabla }f(x^{\ast })$とおくと、

$$\begin{array}{}\text{(2)}& d^{\mathrm{T}}\mathrm{\nabla }f(x^{\ast })=-\Vert \mathrm{\nabla }f(x^{\ast })\Vert <0\end{array}$$

となる。 $f$が連続より、ある$\overline{t}>0$が存在して

$$\begin{array}{}\text{(3)}& \mathrm{\forall }t\in [0,\overline{t}],d^{\mathrm{T}}\mathrm{\nabla }f(x^{\ast }+td)<0\end{array}$$

とできる。 また、平均値の定理よりある$0<\xi <1$が存在して

$$\begin{array}{}\text{(4)}& f(x^{\ast }+td)=f(x^{\ast })+t{d}^{\mathrm{T}}f(x^{\ast }+\xi td)\end{array}$$

$◻$

Theorem (sufficiency)

$f:{\mathbb{R}}^n\to \mathbb{R}$が二階微分可能とする。 $x^{\ast }$が

$$\begin{array}{}\text{(5)}& \mathrm{\nabla }f(x^{\ast })=0\end{array}$$

かつ、$\nabla^{2} f(x^{})$が正定値行列ならば$x^{}$は局所的最小解になる。

proof.

$◻$

Reference

• primal-dual.pdf