數值最優化—優化問題的解(二)

一、定理

區域最小值點一階必要條件： ? f ( x ? ) = 0 \nabla f(x^*)=0 ?f(x?)=0
區域最小值點二階必要條件： ? f ( x ? ) = 0 且 ? 2 f ( x ? ) \nabla f(x^*)=0 且 \nabla^2 f(x^*) ?f(x?)=0且?2f(x?) 正定，
區域最小值點二階充分條件： ? 2 f ( x ) \nabla^2 f(x) ?2f(x) 在 x ? x^* x?的開鄰域內連續， ? f ( x ? ) = 0 \nabla f(x^*)=0 ?f(x?)=0并且 ? 2 f ( x ? ) \nabla^2 f(x^*) ?2f(x?) 正定，那么 x ? x^* x?是 f ( x ) f(x) f(x) 的嚴格區域最小值點，

二、證明

Proof 1
反證法
假設當 x ? x^* x? 為區域最小值時 ? f ( x ? ) ≠ 0 \nabla f(x^*)\neq0 ?f(x?)?=0 ，那么定義 p = ? ? f ( x ? ) p = -\nabla f(x^*) p=??f(x?) ，這樣我們可以得到：
p T ? f ( x ? ) = ? ? f ( x ? ) T ? f ( x ? ) = ? ∥ ? f ( x ? ) ∥ < 0 p^T\nabla f(x^*)=-\nabla f(x^*)^T\nabla f(x^*)=-\|\nabla f(x^*)\|<0 pT?f(x?)=??f(x?)T?f(x?)=?∥?f(x?)∥<0 （1）
根據函式的連續性，必然可以得到，存在一個足夠小的正數 T T T ，使得：
p T ? f ( x ? + t p ) < 0 p^T\nabla f(x^*+tp)<0 pT?f(x?+tp)<0 for all t ∈ [ 0 , T ] t\in[0,T] t∈[0,T] （2）
考慮 \overline{t} \in(0,T] ，并對 f(x)$ 在 x ? x^* x? 點處做泰勒展開，我們可以得到：
f ( x ? + t ￣ p ) = f ( x ? ) + t ￣ p T ? f ( x ? + t p ) f o r s o m e t ∈ ( 0 , t ￣ ) f(x^*+\overline{t}p) = f(x^*)+\overline{t}p^T\nabla f(x^*+tp) for some t\in (0,\overline{t}) f(x?+tp)=f(x?)+tpT?f(x?+tp)forsomet∈(0,t) （3）
觀察公式(3)的第二項， t ￣ \overline{t} t 是一個正實數，根據公式(2)我們又可以知道 p T ? f ( x ? + t p ) p^T\nabla f(x^*+tp) pT?f(x?+tp) 是一個負數，那么我們可以我們一定可以找到一個正數 β \beta β ，使得：
f ( x ? + t ￣ p ) = f ( x ? ) ? β f(x^*+\overline{t}p) = f(x^*)-\beta f(x?+tp)=f(x?)?β
也就是：
f ( x ? + t ￣ p ) < f ( x ? ) f(x^*+\overline{t}p) < f(x^*) f(x?+tp)<f(x?)
那么 x^* 不是區域最小值點，與假設相反，原結論成立，
Q.E.D
Proof 2：
由Proof 1我們已經證明了前半部分，現在證明后半部分，也就是 ? 2 f ( x ? ) \nabla^2 f(x^*) ?2f(x?) 正定，
反證法
假設 ? 2 f ( x ? ) \nabla^2 f(x^*) ?2f(x?) 不是正定的，那么肯定可以找到一個向量 p p p 使得 p T ? 2 f ( x ? ) p < 0 p^T\nabla^2 f(x^*)p<0 pT?2f(x?)p<0 ，同樣由連續性，可以得到，存在一個正數 T T T 使得：
p T ? 2 f ( x ? + t p ) p < 0 p^T\nabla^2f(x^*+tp)p<0 pT?2f(x?+tp)p<0 for all t ∈ [ 0 , T ] t\in[0,T] t∈[0,T]
考慮 t ￣ ∈ ( 0 , T ] \overline{t} \in(0,T] t∈(0,T] ，并對 f ( x ) f(x) f(x) 在 x ? x^* x? 點處做二階泰勒展開，我們可以得到：
f ( x ? + t ￣ p ) = f ( x ? ) + t ￣ p T ? f ( x ? + t p ) + 1 2 t ￣ 2 p T ? 2 f ( x ? + t p ) p < f ( x ? ) f(x^*+\overline{t}p) = f(x^*)+\overline{t}p^T\nabla f(x^*+tp)+\frac{1}{2}\overline{t}^2p^T\nabla^2f(x^*+tp)p<f(x^*) f(x?+tp)=f(x?)+tpT?f(x?+tp)+21?t2pT?2f(x?+tp)p<f(x?)
同理我們可以得到假設錯誤，原結論成立，
Q.E.D
Proof 3
由于 ? 2 f ( x ) \nabla^2f(x) ?2f(x) 的連續性，我們可以知道，在 x ? x^* x? 的一個足夠小的鄰域內， ? 2 f ( x ) \nabla^2f(x) ?2f(x) 可以保持正定性，假設這個鄰域的半徑為 r r r ，那么這個鄰域內所有點的集合 為 D = { z ∣ ∥ z ? x ? ∥ < r } \mathcal{D} =\{z| \|z-x^*\|<r\} D={z∣∥z?x?∥<r} ，我們假設 p p p 為任意滿足 ∥ p ∥ < r \|p\|<r ∥p∥<r 的向量，那么我們可以得到 x ? + p ∈ D x^*+p\in \mathcal{D} x?+p∈D ，
（這里做一點簡要的解釋，在 x ? x^* x? 附近滿足正定性條件的點不一定都在集合 D \mathcal{D} D 里面，之所以引入集合 D \mathcal{D} D 的概念主要是為了簡化描述，對于單一變數而言， D \mathcal{D} D是一個以 x ? x^* x?為中點的線段，這個線段中任何一點都能使二階導正定，這個線段可能不是最長的線段，但是他必須是以 x ? x^* x?為中點的，二維的話就是以 x ? x^* x? 為圓心的圓，三維就是以 x ? x^* x? 為球心的球，）
同樣我們做泰勒展開：
f ( x ? + p ) = f ( x ? ) + p T ? f ( x ? ) + 1 2 p T ? 2 f ( z ) p = f ( x ? ) + 1 2 p T f ( z ) p f(x^*+p) = f(x^*) +p^T \nabla f(x^*) + \frac{1}{2}p^T\nabla^2 f(z) p\\=f(x^*) + \frac{1}{2} p^T f(z) p f(x?+p)=f(x?)+pT?f(x?)+21?pT?2f(z)p=f(x?)+21?pTf(z)p
這里需要解釋的有兩點，1、第二個等式是因為在 x ? x^* x? 處 ? f ( x ? ) = 0 \nabla f(x^*) = 0 ?f(x?)=0 ，2、根據泰勒定理，這里的 z = x ? + t p z=x^*+tp z=x?+tp for some t ∈ ( 0 , 1 ) t \in (0,1) t∈(0,1) ，對于最后一個等式的最后一項，根據正定的定義我們可以知道 p T f ( z ) p p^T f(z) p pTf(z)p 是一個正數，
我們可以得到：
f ( x ? + p ) > f ( x ? ) f(x^*+p) > f(x^*) f(x?+p)>f(x?)
由于 x ? + p x^*+p x?+p 可以認為是一個在超平面上以 x ? x^* x? 為球心的開球域，這也就是說，在 x ? x^* x? 附近所有的函式值都比 x ? x^* x? 點處的大，
Q.E.D