一種非線性擴展混合共軛梯度算法的全局收斂性

陳元媛， 高 巖

（1.上海理工大學 管理學院，上海 200093；2.青島大學 數學科學學院，青島266071）

1 問題的提出

共軛梯度法起源于Hestenes和Stiefel在1952年提出的求解線性方程組的方法，是著名的共軛方向法.由于解非線性方程組等價于極小化一個正定二次函數，故1964年Fletcher和Reeves提出了無約束優化的共軛梯度法.共軛梯度法由于計算過程中只要目標函數值和梯度函數值，不要矩陣存儲，卻比最速下降算法有好的數值效果，一直為一種廣泛應用的無約束優化算法［1－8］.本文主要對大規模的無約束優化問題給出了一種非線性擴展混合共軛梯度法.考慮求解的無約束優化問題為

式中，f（x）為Rn上的連續可微函數，梯度f（x）記為g（x）.算法的一般迭代形式為

式中，｛xk｝為迭代點列；αk為步長因子；dk為搜索方向，即

式中，gk為f（xk）；βk 為標量，常用式為

關于上述方法的文章可以參見文獻［5－12］.步長因子αk一般由Wolfe線搜索、Armijo線搜索等非精確線搜索得到［3－6］.最近，文獻［13］中給出了一種新的βk，即

在文獻［13］的基礎上，結合一種新的Wolfe型線搜索，給出了一種新的非線性擴展混合共軛梯度法.在下文中對這種共軛下降算法的全局收斂性進行理論分析，在一般假設條件下給出全局收斂性定理，并且給出了該算法的數值實驗結果與討論.

2 非線性擴展混合共軛梯度法

2.1 假設條件

a.f（x）在水平集L0＝｛x∈Rn｜f（x）≤f（x0）｝有界.

b.f（x）在L0的一個鄰域U 內連續可微，且其導數g（x）滿足Lipschitz條件，即 存在常數L＞0使得 g（x）－g（y）≤L x－y ，?x，y∈U.

另外，給出Wolfe型線搜索，此線搜索在文獻［14］中用過.選取αk＞0，滿足

其中，0＜ρ＜σ＜1.

2.2 計算步驟

a.給出x1∈Rn，ε＞0，d1＝－g1，k：＝1.若g1≤ε，停.

b.求αk＞0 滿足Wolfe型線搜索式（6）和式（7），由式（2）得xk＋1，若gk＋1≤ε，則停，否則轉c.

c.由式（4）和式（5）計算βk＋1，dk＋1的計算為

d.k：＝k＋1，轉b.

為建立非線性擴展混合共軛梯度算法的全局收斂結果，給出引理：

引理1［14］若假設條件滿足，則算法中線搜索式（6）和式（7）可行.

引理2［13］若dk由式（8）產生，則對k≥1有充分下降條件

引理3 若假設條件滿足，步長αk由式（6）和式（7）得到，則

證明 由式（6）和式（7）和假設條件，得到

則

對其兩邊平方，得到

由式（6），得

即得到式（9），結論成立.

引理4 若假設條件滿足，dk由式（8）產生，步長αk由式（6）和式（7）得到，則

證明 由引理2和引理3，得到式（10）.

3 全局收斂結果

定理1 若假設條件滿足，｛xk｝由算法產生，則

證明 反證法.若結論不成立，則?ε＞0，使gk≥ε，由式（8）和引理2，得

對上式兩邊同時除gk4，得到

即

與式（10）矛盾，定理成立.

4 數值實驗與討論

給出了該算法的數值實驗與相關的討論，數值問題取自文獻［15］，αk由式（6）和式（7）得到，其中ρ＝0.001，σ＝0.01.gk≤10－6為停止規則.利用Matlab7.0在CPU1.60GHZ上對測試函數進行了計算，具體的數值結果見表1，其中NI表示迭代的次數，NF表示計算函數值的次數，NG表示計算函數梯度值的次數.

表1 數值結果Tab.1 Numerical results

由非線性擴展混合共軛梯度算法的全局收斂分析知，只要dk滿足充分下降條件，在Wolfe型線搜索式（6）和式（7）下結合式（3），不需其它條件就可得到該算法的全局收斂結果.如最近文獻［16］中

［1］Fletcher R，Reeves C.Function minimization by conjugate gradients［J］.J Comput，1964，7（2）：149－154.

［2］Polyak B T.The conjugate gradient method in extreme problems［J］.USSR Comp Math Physk，1969，9（4）：94－112.

［3］Dai Y H，Yuan Y X.A nonlinear conjugate gradient method with nice global convergence properties［J］.SIAM J Optim，1999，10（1）：177－182.

［4］Wei Z，Li G，Qi L.New quasi－Newton methods for unconstrained optimization problems［J］.Appl Math Comput，2006，175（2）：1156－1188.

［5］Fletcher R. Practical methods of optimization，unconstrained optimization［M］.New York：Wiley，1987.

［6］Liu Y，Storey C.Efficient generalized conjugate gradient algorithms，Part 1：Theory［J］.J Optim Theory Appl，1991，69（1）：129－137.

［7］Raydan M.The Barzilain and Borwein gradient method for the large unconstrained minimization problem［J］.SIAM J Optim，1997，7（1）：26－33.

［8］Birgin E G，Martinez J M.A spectral conjugate gradient method for unconstrained optimization［J］.Appl Math Optim，2001，43（2）：117－128.

［9］Gilbert J C，Nocedal J.Global convergence properties of conjugate gradient methods for optimization［J］.SIAM J Optim，1992，2（1）：21－24.

［10］Sun J，Zhang J.Convergence of conjugate gradient methods without line search［J］.Annals Operations Research，2001，103（1）：161－173.

［11］Zhang L，Zhou W，Li D.Global convergence of a modified fletcher－reeves conjugate gradient method with Armijo－type line search［J］.Numer Math，2006，104（4）：561－572.

［12］Hager W W，Zhang H.A new conjugate gradient method with guaranteed descent and an efficient line search［J］.SIAM J Optim，2005，16（1）：170－192.

［13］Hui Y，Chen L P.Extended AS－GN hybrid conjugate gradient method［J］.OR Transactions，2010，14（3）：122－128.

［14］Wang C，Chen Y，Du S.Further insight into the Shamanskii modification of Newton method［J］.Appl Math Comput，2006，18（1）：46－52.

［15］More J J，Garbow B S，Hillstrom K E.Testing unconstrained optimization software［J］.ACM Trans Math Software，1981，7（1）：17－41.

［16］Wu C Y.A modified PRP conjugate gradient algorithm for unstrained optimization problems［J］.Mathematica Applicata，2011，24（1）：25－29.