📂最適化理論

多変数関数の極値に対する2階の必要/十分条件

要旨¹

関数 $f : \mathbb{R}^{n} \to \mathbb{R}$ が与えられたとしよう。$\nabla f$, $\nabla^{2}f$ をそれぞれ $f$の勾配とヘシアンとする。

• 2次必要条件

  $x^{\ast}$ が 局所最適解であり、$x^{\ast}$ の近傍で $\nabla^{2}f$ が存在し、連続であれば、

  $$ \nabla f(x^{\ast}) = 0 $$

  であり、$\nabla^{2} f(x^{\ast})$ は 半正定行列である。

  ここで $0$ は数値のゼロではなく、ゼロベクトルであることに注意。

• 2次十分条件

  $x^{\ast}$ の近傍で $\nabla^{2}f$ が連続であり、$\nabla f (x^{\ast}) = 0$、そして $\nabla f(x^{\ast})$ が正定であるとする。すると $x^{\ast}$ は 厳密な 局所最適解である。

解説

必要条件は $x^{\ast}$ が極値であるときの $f$ が持つ性質について述べる。十分条件は $f$ がある性質を持つときに $x^{\ast}$ が極値であるかどうかについて述べる。

証明

2次必要条件

1次必要条件により $\nabla f(x^{\ast})$ が成立するのは事実だ。

残りは背理法で証明する。$\nabla^{2} f(x^{\ast})$ が半正定でないと仮定する。そして $p^{t} \nabla^{2}f(x^{\ast}) p \lt 0$ を満たすあるベクトル $p$ を選ぶ。ここで $p^{t}$ は転置行列である。したがって、$\nabla^{2}f$ が $x^{\ast}$ の近傍で連続であるため、ある $s \gt 0$ について次が成立する。

$$ \begin{equation} p^{t} \nabla^{2}f(x^{\ast} + \xi p) p \lt 0,\quad \forall \xi \in [0, s] \end{equation} $$

また、多変数関数のテイラー展開公式により、

$$ \begin{equation} f(x^{\ast} + \xi p) = f (x^{\ast}) + \xi p^{t} \nabla f(x^{\ast}) + \dfrac{1}{2}\xi^{2} p^{t} \nabla^{2} f(x^{\ast} + \bar{\xi} p)p,\quad \text{for some } \bar{\xi} \in (0, \xi) \end{equation} $$

すると、$\nabla f(x^{\ast}) = 0$ であり、$(1)$ と $(2)$ により次を得る。

$$ f(x^{\ast} + \xi p) \lt f (x^{\ast}), \qquad \forall \xi \in [0, s] $$

これは $x^{\ast}$ が局所最小値である事実に矛盾する。したがって、仮定が間違っており、$\nabla^{2} f (x^{\ast})$ は半正定行列である。

■

2次十分条件

$x^{\ast}$ でのヘシアン $\nabla^{2}f$ が連続で正定であるため、すべての $x \in B$ に対して $\nabla^{2}f (x)$ が正定となるような開球 $B_{r} = \left\{ x : \left\| x - x^{\ast} \right\| \lt r \right\}$ を選べる。

$$ p^{t}\nabla^{2} f(x) p \gt 0,\quad \forall p \in \mathbb{R}^{n} $$

今、$0$ ではなく $\left\| p \right\| \lt r$ を満たすあるベクトル $p$ について、多変数関数のテイラー展開公式により、次を得る。

$$ \begin{align*} f(x^{\ast} + p) &= f(x^{\ast}) + p^{t}\nabla f(x^{\ast}) + \dfrac{1}{2}p^{t} \nabla^{2} f(x + \xi p) p,\quad \xi \in (0, 1) \\ &= f(x^{\ast}) + \dfrac{1}{2}p^{t} \nabla^{2} f(x + \xi p) p \end{align*} $$

ここで、$x^{\ast} + \xi p \in B$ であるため、

$$ f(x^{\ast} + p) \gt f(x^{\ast}) $$

したがって、$x^{\ast}$ は局所最小値である。

■

参照

• 1次必要条件