基于Newton法改進(jìn)的BFGS迭代算法與Newton-CG算法

歐謙寧

（鎮(zhèn)江高等職業(yè)技術(shù)學(xué)校，江蘇鎮(zhèn)江212016）

基于Newton法改進(jìn)的BFGS迭代算法與Newton-CG算法

歐謙寧

（鎮(zhèn)江高等職業(yè)技術(shù)學(xué)校，江蘇鎮(zhèn)江212016）

本文主要研究了數(shù)值分析中數(shù)值優(yōu)化與非線性方程組求解這兩個(gè)重要問題.文中首先概述了數(shù)值優(yōu)化與非線性方程組的關(guān)系，然后對(duì)BFGS法的算法公式進(jìn)行了改進(jìn)，并對(duì)非線性方程組求解問題提出了一種改進(jìn)的算法——Newton-CG算法.

數(shù)值分析；非線性方程組；Newton-CG算法

1 引言

建立合適的模型后，計(jì)算結(jié)果可能求不出來；但是我們可以根據(jù)目標(biāo)函數(shù)和約束條件的特點(diǎn)，設(shè)計(jì)某種算法在計(jì)算機(jī)上給出一個(gè)近似的數(shù)值解.

一個(gè)好的算法應(yīng)至少具備下面的標(biāo)準(zhǔn).首先應(yīng)該是一個(gè)收斂的算法，即該方法從某個(gè)合適的初始點(diǎn)啟動(dòng)，終止于問題的一個(gè)近似解；其次應(yīng)該具有較快的收斂速度，這要求從迭代開始直到一個(gè)滿足精度要求的近似解被找到的過程中，需要的迭代次數(shù)較少且每次迭代的運(yùn)算量不大；最后，應(yīng)具備較好的適用性，即解決同類問題中的大多數(shù)問題的能力.

數(shù)值優(yōu)化和非線性方程組[1-3]的求解是數(shù)值分析的兩個(gè)難點(diǎn)問題.本文介紹了改進(jìn)的BFGS迭代算法，并且對(duì)非線性方程組的求解問題提出了一種新的算法——改進(jìn)的Newton—CG算法.

2 數(shù)值優(yōu)化與非線性方程組的關(guān)系

一般情況下fi=(x1,x2,…，xn)=0，i=(1,2,…,n)是非線性方程，于是無約束優(yōu)化問題便可轉(zhuǎn)化為求解非線性方程組方程組(1.1).

但是，文獻(xiàn)[4]證明了非線性方程組問題通常是無法轉(zhuǎn)化為無約束優(yōu)化問題的.為此，本文的改進(jìn)探討意義重大.

3 改進(jìn)的BFGS迭代算法

算法3.1(新BFGS法)

步1選取初始點(diǎn)x1∈Rn，初始矩陣B1酆0；

步2如果||塄f(xk)||<ε，迭代終止；

步3解方程Bkdk+塄f(xk)=0，得到一個(gè)新的下降方向dk；

步4利用黃金分割法確定步長(zhǎng)αk；

步5計(jì)算新的迭代點(diǎn)xk+1=xk+αkdk，計(jì)算矩陣Ak，Bk+1；

步6令k+1←1，返回步1

可以證明：對(duì)于任何k，考慮由本算法生成的Bk,Ak，只要skTy*'k>0，則矩陣Vk+1一定正定.從而確保得到的dk一定是下降方向.并且可以證明此算法具有全局收斂性，通過此改進(jìn)，使得擬Newton算法——BFGS更加有效.

4 非線性方程組的改進(jìn)Newton-CG法

4.1 Newton法

n個(gè)變量n個(gè)方程的非線性方程組的一般形式為：

其中fi是定義在n維Euclid空間Rn中開域D上的實(shí)值函數(shù).若用向量記號(hào)，令

將非線性映像F：D奐Rn→Rn逐步線性化，在每個(gè)迭代中解一個(gè)線性方程組，這樣的迭代法稱為線性化方法.對(duì)方程(4.1)可構(gòu)造線性方程組Lk(x)=Ak(x-xk)+F(xk)=0，其解為xk+1，并可以作為方程(1.1)的新近似，即xk+1=xk-Ak-1F(xk),k=0,1,…

通常Ak與xk及F，F(xiàn)'等有關(guān)，文獻(xiàn)[3]指出Ak的取法不同對(duì)應(yīng)著不同的方法

當(dāng)Ak=F'(x0)，xk+1=xk-[F'(x0)]-1F(xk)，稱為簡(jiǎn)化Newton法；kk+1kk-1k

Newton法(4.2)式當(dāng)n很大時(shí)計(jì)算比較困難，常采用下面形式

這樣每步解一個(gè)n階線性方程組，稱(4.3)為Newton方程組，并且可以證明Newton法是局部二階收斂的.

算法4.1(Newton法)[3]

步1給出初始近似x0及其計(jì)算精度ε1,ε2；

步2假定已進(jìn)行了k次迭代，已求出xk及F (xk)，計(jì)算Ak=F'(xk)；

步3解線性方程組F'(xk)△xk+F(xk)=0，得到△xk；

步4求xk+1=xk+△xk及F(xk+1)；

步5若||xk+1-xk||≤ε1或||F(xk+1)||≤ε2，x*=xk+1；否則，k+1→k，轉(zhuǎn)步2；

從上面算法可以看出，Newton法具有收斂快，自校正的優(yōu)點(diǎn)；它的缺點(diǎn)是(1)局部收斂，要求初試近似x0與x*充分靠近；(2)當(dāng)n較大時(shí)，每步都計(jì)算Jacobi陣，工作量大；(3)解(4.3)線性方程組時(shí)，F(xiàn)' (xk)可能非奇異或者病態(tài).

4.2 改進(jìn)的Newton-CG法

用Newton法求解Newton方程組時(shí)，常用的方法是Newton-SOR迭代法和非線性SOR-N方法.本文提出一種改進(jìn)的Newton法，即方程組F'(xk)△xk+F (xk)=0是關(guān)于△xk的線性方程組，當(dāng)F'(xk)對(duì)稱正定時(shí)，可以用共軛梯度法求此方程，但一般情況下F' (xk)不能達(dá)到如此高的要求，故必須對(duì)Newton方程組改進(jìn),對(duì)(4.3)式兩邊同時(shí)做矩陣乘法運(yùn)算，即得到新的Newton方程：

記A=(F'(xk))TF'(xk)·b=-(F'(xk))TF(xk)，可以證明A是對(duì)稱正定矩陣，故滿足共軛梯度法的條件，可以使用共軛梯度法，避免求逆運(yùn)算，提高算法的有效性.

算法4.2(改進(jìn)的Newton-CG法)

步1給出初始近似x0及其計(jì)算精度ε1,ε2；

步2假定已進(jìn)行了k次迭代，已求出xk及F (xk)，計(jì)算Ak=F'(xk)；

步3對(duì)線性方程組F'(xk)△xk+F(xk)=0變形，得到新的Newton方程(F'(xk))TF'(xk)△xk+(F'(xk))TF(xk)=0，用共軛梯度法得到△xk；

步4求xk+1=xk+△xk及F(xk+1)；

步5若||xk+1-xk||≤ε1||xk||或||F(xk+1)||≤ε2，x*=xk+1；否則，k+1→k，轉(zhuǎn)步2.

可以證明，改進(jìn)的Newton-CG法總體上仍然具有Newton法的二階斂速，每步迭代計(jì)算2n個(gè)分量函數(shù)值和n2個(gè)函數(shù)乘法，但避免了矩陣求逆，計(jì)算量相對(duì)減少，存儲(chǔ)空間也隨之減少，與N—SOR法相比，不需要進(jìn)行矩陣分解，因此很大程度上提高了算法的有效性.

〔1〕馮果枕.非線性方程組迭代解法[M].上海:上?？茖W(xué)技術(shù)出版社,1986.

〔2〕晁玉翠.求解非線性方程組的修正牛頓法研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),2007.

〔3〕李慶揚(yáng),莫孜中,祈力群.非線性方程組的數(shù)值解法[M].北京:科學(xué)出版社,1987.

〔4〕王德人.非線性方程組解法與最優(yōu)化方法[M].北京:人民教育出版社,1979.

〔5〕Z Wei,G Li,L Qi.Newton quasi-Newton method for unconstrained optimization problem [J],AppliedMathematicsandComputation, 2006,175:1156-1188

〔6〕Y Dai.Convergence properities of the BFGS algorithm[J].SIMA journal on optimization, 2003,13:693-701.

O29

A

1673-260X（2010）11-0006-02