對梯度迭代法與牛頓法求解極值問題的討論

1、梯度下降算法發(fā)散舉例0=0, 1=0, 2=0, h(x(i)=0, x0=1y(1)=400, y(2)=330, y(3)=369, y(4)=232, y(5)=540 x1(1)=2104, x1(2)=1600, x1(3)=2400, x1(4)=1416, x1(5)=3000 x2(1)=3, x2(2)=3, x2(3)=3, x2(4)=2, x2(5)=40=0+0.01(y(1)-h(x(1)x0(1)+.+(y(5)-h(x(5)x0(5)1=0+0.01(y(1)-h(x(1)x1(1)+.+(y(5)-h(x(5)x1(5)2=0+0.01(y(1)-h(x(1)

2、x2(1)+.+(y(5)-h(x(5)x2(5)x1yx20=0+0.01(y(1)-h(x(1)x0(1)+.+(y(5)-h(x(5)x0(5)=0.01（400+330+369+232+540）=18.711=0+0.01(y(1)-h(x(1)x1(1)+.+(y(5)-h(x(5)x1(5)=0.01（400*2104+330*1600+540*3000)=42037.122=0+0.01(y(1)-h(x(1)x2(1)+.+(y(5)-h(x(5)x2(5)=0.01(400*3+330*3+369*3+540*4)=59.21得到 ，和matlab一次迭代結果一致。據此計算再

3、次代入迭代公式得到：用matlab程序迭代兩次結果如圖：發(fā)現(xiàn)第二次迭代和手工算也沒有什么區(qū)別，當迭代150次時，結果都是NaN，已經發(fā)散了，于是用矩陣法求求解結果如下：用矩陣法求解線性回歸問題依照公式得到 即其實這里，即為X的廣義逆矩陣，如果X為方陣且可逆的話，則可得到，矩陣法誤差分析絕對誤差向量，計算相對誤差（采用第二范數）得這里看似是比較好的擬合結果，但其實這個結果并不穩(wěn)定，也就是說如果每次觀測的數據都有偏差，這個用最小二乘法的矩陣解法求出的解的差別可能千差萬別，或者隨著數據的不斷輸入，求的結果相差非常大，以至于感覺不能取得一個好的擬合結果，這就涉及到下面病態(tài)矩陣與條件數的知識了。病態(tài)矩陣

4、與條件數那么為什么用梯度下降算法迭代出現(xiàn)了發(fā)散呢？這里就涉及到了病態(tài)矩陣的概念了，而判斷矩陣是否病態(tài)的準則就是條件數！求解方程組時如果對數據進行較小的擾動，則得出的結果具有很大波動，這樣的矩陣稱為病態(tài)矩陣。求解方程組時對數據的小擾動很敏感的矩陣。解線性方程組Ax=b時，若對于系數矩陣A及右端項b的小擾動A、b,方程組(A+A)=b+b的解與原方程組Ax=b的解差別很大，則稱矩陣A為病態(tài)矩陣。下面給出一個病態(tài)矩陣的例子：病態(tài)矩陣實例可見非常小的擾動能引起解的非常大的變化，這樣的矩就被稱為病態(tài)矩陣。解決病態(tài)矩陣的解的問題也是現(xiàn)在研究的一個熱點，在求解任何反問題的過程中通常會遇到病態(tài)矩陣問題，而且病

5、態(tài)矩陣問題還未有很好的解決方法，尤其是長方形、大型矩陣。目前主要有Tikhonov、奇異值截斷、奇異值修正、迭代法等方法。得到定義1：設 ，|.|是Cnxn上的一個矩陣范數.矩陣A的條件數定義為條件數的定義與計算 -條件數：1-條件數：2-條件數：常用的條件數條件數的計算對于條件數的計算matlab給出了很好的支持，在matlab中可以用cond（X，p）函數來計算，X表示要計算條件數的矩陣，p表示p條件數，p如果不給出的話matlab默認值為2，即計算2條件數。下面用matlab計算上面矩陣條件數從以上實驗結果可以看出矩陣不可逆的化條件數為無窮，且不可逆性約強的話（其實這個時候就是各個分量之

6、間的平行性越強）矩陣的條件數越大。以該矩陣為參數的線性方程解的波動性也就會越大。最小二乘法梯度迭代法與矩陣求解比較回到最初房屋價格問題，計算矩陣的條件數可以得到如下結果：可見該矩陣條件數非常之大，也就是該矩陣方程病態(tài)很嚴重，用矩陣解法雖然可以解出方程的解，但是該解是極不穩(wěn)定的。下面給出梯度迭代法與矩陣求解最小二乘問題的異同：對于用梯度迭代法，結果是慢慢迭代而出的，如果出現(xiàn)了結果的不穩(wěn)定性非常嚴重（原因就是矩陣病態(tài)，條件數過大），則可能出現(xiàn)迭代不收斂的情況（本例就是一個很好的例子），求不出最小二乘的參數。對于矩陣法，給出數據就可以得到結果，不論矩陣是否病態(tài)，但如果矩陣病態(tài)的話，數據小的波動會引起

7、解非常大的改變，如果數據在增加，則可能連續(xù)得出的解千差萬別以至于得不到好的解。牛頓法求解極值存在的問題給定初值重復直到收斂其中H為海森矩陣， 為梯度向量稱為海森矩陣(Hessian matrix)NxN維矩陣，N為特征變量數量，若考慮0，則實際上是(N+1)x(N+1)維簡單二維向量例子求 的極值。按照推到公式第一步求出海森矩陣H海森矩陣H=代入迭代公式，令得到此時已將收斂，所以極值點為 ，極值為 3 如果將前面的系數改為2，則海森矩陣不可逆，此時牛頓迭代法不可用，因為此時只要滿足 都可以是方程的解，方程欠定，有無窮解，牛頓迭代法只能解決適定方程，即解是唯一固定的，且不能直接得出是極大值還是極

8、小值。這是它的缺陷。對結果進行反思該方程實際上是沒有極值點的，理由如下：令兩個x相等，則3是極小值，令兩個x相反，則3是極大值。實際上，0點只是梯度為零的點而不是極值點，牛頓迭代法求出的點是梯度為0即認為是極值點，這在一般情況下成立，但這種情況不成立，函數陷入了扁平化區(qū)域。畫出函數的三維圖發(fā)現(xiàn)，在0點附近一三象限取值為正，二四象限取值為負，這時候牛頓迭代法也不適用了。Matlab繪圖如下：用matlab驗證f=x(1)2+3*x(1)*x(2)+x(2)2;x,fval,exitflag,output=fminsearch(f,1 1);運行程序結果如下：可以發(fā)現(xiàn)exitflag為0，也就標志著極值不存在，畫圖也可看出極值不存在對梯度下降算法與牛頓法的理解梯度下降算法與牛頓法其實是一本同根的，用他們求極值其實都是找出梯度為0的點即認為是極值點，這在凸優(yōu)化問題中是合適的，當處理扁平問題時是有bug的，即在這類問題中梯度為0的點不一定是極值點，這是這兩大算法的致命缺點。隨機梯度下降算法的迭代法與矩陣解法也是各有優(yōu)劣，在矩陣非病態(tài)的情況下兩者都能得到較好的結果，數據較少時采用矩陣法可以很快的得到結果，數據較多時求逆運算耗時不方便，多用梯度迭代法，而且迭代結果收斂。當矩陣病態(tài)時，梯度迭代法可能出現(xiàn)發(fā)散，矩陣求解法可以得出結果但隨著數據的波動變化太大，得不到好的估計，但是矩