梯度的方向與等值面垂直，并且指向函數(shù)值提升的方向。
二次收斂是指一個(gè)算法用于具有正定二次型函數(shù)時(shí)，在有限步可達(dá)到它的極小點(diǎn)。二次收斂與二階收斂沒(méi)有盡然聯(lián)系，更不是一回事，二次收斂往往具有超線性以上的收斂性。一階收斂不一定是線性收斂。
解釋一下什么叫正定二次型函數(shù)：
n階實(shí)對(duì)稱矩陣Q，對(duì)于任意的非0向量X，如果有XTQX>0，則稱Q是正定矩陣。
對(duì)稱矩陣Q為正定的充要條件是：Q的特征值全為正。
二次函數(shù)
黃金分割法適用于任何單峰函數(shù)求極小值問(wèn)題。
求函數(shù)在[a,b]上的極小點(diǎn)，我們?cè)赱a,b]內(nèi)取兩點(diǎn)c,d，使得a<c<d<b。并且有
1）如果f(c)<f(d)，則最小點(diǎn)出現(xiàn)在[a,d]上，因此[a,d]成為下一次的搜索區(qū)間。
2）如果f(c)>f(d)，則[c,b]成為下一次的搜索區(qū)間。
假如確定了[a,d]是新的搜索區(qū)間，我們并不希望在[a,d]上重新找兩個(gè)新的點(diǎn)使之滿足(1)式，而是利用已經(jīng)抗找到有c點(diǎn)，再找一個(gè)e點(diǎn)，使?jié)M足：
可以解得r=0.382，而黃金分割點(diǎn)是0.618。
練習(xí)：求函數(shù)f(x)=x*x-10*x+36在[1,10]上的極小值。
泰勒級(jí)數(shù)告訴我們：
其中Δx可正可負(fù)，但必須充分接近于0。
X沿D方向移動(dòng)步長(zhǎng)a后，變?yōu)閄+aD。由泰勒展開(kāi)式：
目標(biāo)函數(shù)：
a確定的情況下即最小化：
向量的內(nèi)積何時(shí)最小？當(dāng)然是兩向量方向相反時(shí)。所以X移動(dòng)的方向應(yīng)該和梯度的方向相反。
接下來(lái)的問(wèn)題是步長(zhǎng)a應(yīng)該怎么定才能使迭代的次數(shù)最少？
若f(X)具有二階連續(xù)偏導(dǎo)，由泰勒展開(kāi)式可得：
H是f(X)的Hesse矩陣。
可得最優(yōu)步長(zhǎng)：
g是f(X)的梯度矩陣。
此時(shí)：
可見(jiàn)最速下降法中最優(yōu)步長(zhǎng)不僅與梯度有關(guān)，而且與Hesse矩陣有關(guān)。
練習(xí)：求函數(shù)f(x1,x2)=x1*x1+4*x2*x2在極小點(diǎn)，以初始點(diǎn)X0=(1,1)T。
梯度下降法開(kāi)始的幾步搜索，目標(biāo)函數(shù)下降較快，但接近極值點(diǎn)時(shí)，收斂速度就比較慢了，特別是當(dāng)橢圓比較扁平時(shí)，收斂速度就更慢了。
另外最速下降法是以函數(shù)的一次近似提出的，如果要考慮二次近似，就有牛頓迭代法。
在點(diǎn)Xk處對(duì)目標(biāo)函數(shù)按Taylar展開(kāi)：
令
得
即
可見(jiàn)X的搜索方向是
練習(xí)：求
牛頓法是二次收斂的，并且收斂階數(shù)是2。一般目標(biāo)函數(shù)在最優(yōu)點(diǎn)附近呈現(xiàn)為二次函數(shù)，于是可以想像最優(yōu)點(diǎn)附近用牛頓迭代法收斂是比較快的。而在開(kāi)始搜索的幾步，我們用梯度下降法收斂是比較快的。將兩個(gè)方法融合起來(lái)可以達(dá)到滿意的效果。
收斂快是牛頓迭代法最大的優(yōu)點(diǎn)，但也有致命的缺點(diǎn)：Hesse矩陣及其逆的求解計(jì)算量大，更何況在某個(gè)迭代點(diǎn)Xk處Hesse矩陣的逆可能根本就不存在（即Hesse矩陣奇異），這樣無(wú)法求得Xk+1。
Hesse矩陣在擬牛頓法中是不計(jì)算的，擬牛頓法是構(gòu)造與Hesse矩陣相似的正定矩陣，這個(gè)構(gòu)造方法，使用了目標(biāo)函數(shù)的梯度（一階導(dǎo)數(shù)）信息和兩個(gè)點(diǎn)的“位移”（Xk-Xk-1）來(lái)實(shí)現(xiàn)。有人會(huì)說(shuō)，是不是用Hesse矩陣的近似矩陣來(lái)代替Hesse矩陣，會(huì)導(dǎo)致求解效果變差呢？事實(shí)上，效果反而通常會(huì)變好。
擬牛頓法與牛頓法的迭代過(guò)程一樣，僅僅是各個(gè)Hesse矩陣的求解方法不一樣。
在遠(yuǎn)離極小值點(diǎn)處，Hesse矩陣一般不能保證正定，使得目標(biāo)函數(shù)值不降反升。而擬牛頓法可以使目標(biāo)函數(shù)值沿下降方向走下去，并且到了最后，在極小值點(diǎn)附近，可使構(gòu)造出來(lái)的矩陣與Hesse矩陣“很像”了，這樣，擬牛頓法也會(huì)具有牛頓法的二階收斂性。
對(duì)目標(biāo)函數(shù)f(X)做二階泰勒展開(kāi)：
兩邊對(duì)X求導(dǎo)
當(dāng)X=Xi時(shí)，有
這里我們用Hi來(lái)代表在點(diǎn)Xi處的Hesse矩陣的逆，則
(5)式就是擬牛頓方程。
下面給出擬牛頓法中的一種--DFP法。
令
我們希望Hi+1在Hi的基礎(chǔ)上加一個(gè)修正來(lái)得到：
給定Ei的一種形式：
m和n均為實(shí)數(shù)，v和w均為N維向量。
(6)(7)聯(lián)合起來(lái)代入(5)可得：
下面再給一種擬牛頓法--BFGS算法。
(8)式中黑色的部分就是DFP算法，紅色部分是BFGS比DFP多出來(lái)的部分。
BFGS算法不僅具有二次收斂性，而且只有初始矩陣對(duì)稱正定，則BFGS修正公式所產(chǎn)生的矩陣Hk也是對(duì)稱正定的，且Hk不易變?yōu)槠娈?，因此BFGS比DFP具有更好的數(shù)值穩(wěn)定性。
最速下降法有鋸齒現(xiàn)像，收斂速度慢；而牛頓法需要計(jì)算Hesse矩陣而計(jì)算量大。共軛方向法收斂速度界于兩者之間，具有二次收斂性。共軛方向法屬于效果好而又實(shí)用的方法。
由于一般目標(biāo)函數(shù)在最優(yōu)點(diǎn)附近呈現(xiàn)為二次函數(shù)，因此可以設(shè)想一個(gè)算法對(duì)于二次函數(shù)比較有效，就可能對(duì)一般函數(shù)也有較好效果。共軛方向法是在研究對(duì)稱正定二次函數(shù)的基礎(chǔ)上提出來(lái)的。
則稱兩個(gè)向量P0和P1為Q的共軛向量。當(dāng)Q為單位向量時(shí)，有
對(duì)于二次正定函數(shù)，從任意點(diǎn)X0出發(fā)，沿任意下降方向P0作直線搜索得到X1，再?gòu)腦1出發(fā)，沿與P0共軛的方向P1作直線搜索，即可得到f(X)的極小點(diǎn)。
當(dāng)一組向量Pi（i=1,2,...,n-1）為Q共軛時(shí)，從任意點(diǎn)出發(fā)，依次沿P0,P1,P2,...,Pn-1方向作下述算法的直線搜索，經(jīng)過(guò)n次迭代必定收斂于正定二次函數(shù)的極小點(diǎn)。
為確定最優(yōu)步長(zhǎng)tk,令
現(xiàn)在問(wèn)題是如何產(chǎn)生一組關(guān)于Q共軛的向量？這里一種叫作Gram-Schmidt的方法。
取線性無(wú)關(guān)的向量組V0,V1,...,Vn-1，例如取n個(gè)坐標(biāo)軸的單位向量。
取P0=V0.
上面的方法都是針對(duì)目標(biāo)函數(shù)為正定二次函數(shù)的，對(duì)于一般非二次函數(shù)，可以通過(guò)二次近似。
這就是f(X)在極小點(diǎn)X*處的近似，
理論與實(shí)踐證明，將二次收斂算法用于非二次的目標(biāo)函數(shù)，亦有很好的效果，但迭代次數(shù)不一定保證有限次，即對(duì)非二次n維目標(biāo)函數(shù)經(jīng)n步共軛方向一維搜索不一定就能達(dá)到極小點(diǎn)。在這種情況下，為了找到極小點(diǎn)，可用泰勒級(jí)數(shù)將該函數(shù)在極小點(diǎn)附近展開(kāi)，略去高于二次的項(xiàng)之后即可得該函數(shù)的二次近似。實(shí)際上很多的函數(shù)都可以用二次函數(shù)很好地近似，甚至在離極小點(diǎn)不是很近的點(diǎn)也是這樣。故用二次函數(shù)近似代替非二次函數(shù)來(lái)處理的方法不僅在理論分析上是重要的，而且在工程實(shí)際應(yīng)用中也是可取的。
共軛梯度法是共軛方向法的一種延伸，初始共軛向量P0由初始迭代點(diǎn)X0處的負(fù)梯度-g0來(lái)給出。以后的Pk由當(dāng)前迭代點(diǎn)的負(fù)梯度與上一個(gè)共軛向量的線性組合來(lái)確定：
對(duì)于非二次函數(shù)的優(yōu)化問(wèn)題，迭代次數(shù)不止n次，但共軛方向只有n個(gè)。當(dāng)?shù)鷑次后，可以把Pn重新置為最開(kāi)始的P0，其他的變量按原方法更新。
聯(lián)系客服
