logo

多変数関数の極値に対する2階の必要/十分条件 📂最適化理論

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

要旨1

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

  • 2次必要条件

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

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

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

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

  • 2次十分条件

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

解説

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

証明

2次必要条件

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

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

pt∇2f(x∗+ξp)p<0,∀ξ∈[0,s] \begin{equation} p^{t} \nabla^{2}f(x^{\ast} + \xi p) p \lt 0,\quad \forall \xi \in [0, s] \end{equation}

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

f(x∗+ξp)=f(x∗)+ξpt∇f(x∗)+12ξ2pt∇2f(x∗+ξˉp)p,for some ξˉ∈(0,ξ) \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}

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

f(x∗+ξp)<f(x∗),∀ξ∈[0,s] f(x^{\ast} + \xi p) \lt f (x^{\ast}), \qquad \forall \xi \in [0, s]

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

■

2次十分条件

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

pt∇2f(x)p>0,∀p∈Rn p^{t}\nabla^{2} f(x) p \gt 0,\quad \forall p \in \mathbb{R}^{n}

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

f(x∗+p)=f(x∗)+pt∇f(x∗)+12pt∇2f(x+ξp)p,ξ∈(0,1)=f(x∗)+12pt∇2f(x+ξp)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∗+ξp∈Bx^{\ast} + \xi p \in B であるため、

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

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

■

参照

  1. J. Nocedal and Stephen J. Wright, Numerical Optimization (2nd), p14-15 ↩︎