您當前的位置：首頁 > 書法

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

作者：由 一筐鮮橙 發表于 書法時間：2020-09-24

一、定理

區域性最小值點一階必要條件：

\nabla f(x^*)=0

區域性最小值點二階必要條件：

\nabla f(x^*)=0

且

\nabla^2 f(x^*)

正定。

區域性最小值點二階充分條件：

\nabla^2 f(x)

在

x^*

的開鄰域內連續，

\nabla f(x^*)=0

並且

\nabla^2 f(x^*)

正定，那麼

x^*

是

f(x)

的嚴格區域性最小值點。

二、證明

Proof 1

反證法

假設當

x^*

為區域性最小值時

\nabla f(x^*)\neq0

，那麼定義

p = -\nabla f(x^*)

。這樣我們可以得到：

p^T\nabla f(x^*)=-\nabla f(x^*)^T\nabla f(x^*)=-\|\nabla f(x^*)\|<0

（1）

根據函式的連續性，必然可以得到，存在一個足夠小的正數

T

，使得：

p^T\nabla f(x^*+tp)<0

for all

t\in[0,T]

（2）

考慮

\overline{t} \in(0,T]

，並對

f(x)

在

x^*

點處做泰勒展開，我們可以得到：

f(x^*+\overline{t}p) = f(x^*)+\overline{t}p^T\nabla f(x^*+tp)

for some

t\in (0,\overline{t})

（3）

觀察公式（3）的第二項，

\overline{t}

是一個正實數，根據公式（2）我們又可以知道

p^T\nabla f(x^*+tp)

是一個負數。那麼我們可以我們一定可以找到一個正數

\beta

，使得：

f(x^*+\overline{t}p) = f(x^*)-\beta

也就是：

f(x^*+\overline{t}p) < f(x^*)

那麼

x^*

不是區域性最小值點，與假設相反，原結論成立。

Q.E.D

Proof 2：

由Proof 1我們已經證明了前半部分，現在證明後半部分，也就是

\nabla^2 f(x^*)

正定。

反證法

假設

\nabla^2 f(x^*)

不是正定的，那麼肯定可以找到一個向量

p

使得

p^T\nabla^2 f(x^*)p<0

。同樣由連續性，可以得到，存在一個正數

T

使得：

p^T\nabla^2f(x^*+tp)p<0

for all

t\in[0,T]

考慮

\overline{t} \in(0,T]

，並對

f(x)

在

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^*)

同理我們可以得到假設錯誤，原結論成立。

Q.E.D

Proof 3

由於

\nabla^2f(x)

的連續性，我們可以知道，在

x^*

的一個足夠小的鄰域內，

\nabla^2f(x)

可以保持正定性。假設這個鄰域的半徑為

r

，那麼這個鄰域內所有點的集合 為

\mathcal{D} =\{z| \|z-x^*\|<r\}

。我們假設

p

為任意滿足

\|p\|<r

的向量。那麼我們可以得到

x^*+p\in \mathcal{D}

。

（這裡做一點簡要的解釋，在

x^*

附近滿足正定性條件的點不一定都在集合

\mathcal{D}

裡面，之所以引入集合

\mathcal{D}

的概念主要是為了簡化描述。對於單一變數而言，

\mathcal{D}

是一個以

x^*

為中點的線段，這個線段中任何一點都能使二階導正定。這個線段可能不是最長的線段，但是他必須是以

x^*

為中點的，二維的話就是以

x^*

為圓心的圓，三維就是以

x^*

為球心的球。）

同樣我們做泰勒展開：

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

這裡需要解釋的有兩點。1、第二個等式是因為在

x^*

處

\nabla f(x^*) = 0

。2、根據泰勒定理，這裡的

z=x^*+tp

for some

t \in (0,1)

。對於最後一個等式的最後一項，根據正定的定義我們可以知道

p^T f(z) p

是一個正數。

我們可以得到：

f(x^*+p) > f(x^*)

由於

x^*+p

可以認為是一個在超平面上以

x^*

為球心的開球域。這也就是說，在

x^*

附近所有的函式值都比

x^*

點處的大。

Q.E.D

標簽： 最小值  正定  可以  我們  鄰域 

上一篇:閱文霸道合同被那麼多作者討伐，為何只針對免費閱讀作出迴應，而對侵佔作者著作權的事閉口不提？

下一篇：博導催促寫專利有什麼用？

猜你喜歡