基于Newton法改進的BFGS迭代算法與Newton-CG算法

歐謙寧

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

基于Newton法改進的BFGS迭代算法與Newton-CG算法

歐謙寧

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

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

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

1 引言

建立合適的模型后，計算結果可能求不出來；但是我們可以根據目標函數和約束條件的特點，設計某種算法在計算機上給出一個近似的數值解.

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

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

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

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

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

3 改進的BFGS迭代算法

算法3.1(新BFGS法)

步1選取初始點x1∈Rn，初始矩陣B1酆0；

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

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

步4利用黃金分割法確定步長αk；

步5計算新的迭代點xk+1=xk+αkdk，計算矩陣Ak，Bk+1；

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

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

4 非線性方程組的改進Newton-CG法

4.1 Newton法

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

其中fi是定義在n維Euclid空間Rn中開域D上的實值函數.若用向量記號，令

將非線性映像F：D奐Rn→Rn逐步線性化，在每個迭代中解一個線性方程組，這樣的迭代法稱為線性化方法.對方程(4.1)可構造線性方程組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'等有關，文獻[3]指出Ak的取法不同對應著不同的方法

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

Newton法(4.2)式當n很大時計算比較困難，常采用下面形式

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

算法4.1(Newton法)[3]

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

步2假定已進行了k次迭代，已求出xk及F (xk)，計算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，轉步2；

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

4.2 改進的Newton-CG法

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

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

算法4.2(改進的Newton-CG法)

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

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

步3對線性方程組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，轉步2.

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

〔1〕馮果枕.非線性方程組迭代解法[M].上海:上海科學技術出版社,1986.

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

〔3〕李慶揚,莫孜中,祈力群.非線性方程組的數值解法[M].北京:科學出版社,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