非精確線搜索條件下共軛梯度法的收斂性分析

鞠靜潔，龐德艷，杜守強

（青島大學 數(shù)學科學學院，山東 青島 266071）

0 引言

討論無約束最優(yōu)化問題

其中f為RN上的可微函數(shù).本文中‖·‖為歐幾里得范數(shù).

共軛梯度法自創(chuàng)立以來就被廣泛應用于解無約束最優(yōu)化問題，是求解大規(guī)模無約束優(yōu)化問題的一種很有效的方法［1－11］，原因在于它在計算過程中只需要目標函數(shù)值和梯度函數(shù)值，不需要矩陣存儲，卻比最速下降法有更好的數(shù)值效果，如由Hideaki與Yasushi提出的使用目標函數(shù)值的共軛梯度法.

傳統(tǒng)的求解問題（1）的共軛梯度法的迭代公式為

其中g(shù)k＝▽f（xk），αk＞0是步長，dk是搜索方向，βk是一個參數(shù).

本文將介紹兩種改進的共軛梯度法，它們的步長都是由一種新的Wolfe線搜索方法［5］

與

本文結(jié)構(gòu)為：在第1、2部分中將分別給出在新的Wolfe型線搜索條件下的兩種算法，并詳細介紹其收斂性質(zhì)；第3部分給出這兩種算法在其它的非精確線搜索條件下的一些討論；最后，分別給出這幾種算法的數(shù)值實例以說明它們的有效性.

1 算法Ⅰ及其收斂性分析

算法Ⅰ

步驟0：選取初始點x1∈RN，給定參數(shù)0＜ρ＜，0＜σ＜1且ρ＜σ，容許誤差0＜ε?1，令d1＝－g1，k＝1.

步驟1：給定xk，dk∈RN，計算滿足不等式（4），（5）的αk＞0.由（2）式計算xk＋1∈RN.

步驟2：若gk＋1＝0，停止.否則轉(zhuǎn)第3步.

步驟3：由（6）式計算βk＋1∈R，計算搜索方向

步驟4：令k＝k＋1.轉(zhuǎn)到步驟1.

為了建立算法Ⅰ的全局收斂性，先給出如下假設及引理.

假設1 A1）f：RN→R在水平集Γ＝｛x∈RN：f（x）≤f（x1）｝中有下界，x1∈RN為初始點.A2）▽f：RN→RN在Γ的某個鄰域N中是Lipsichitz連續(xù)的，即存在L＞0滿足

引理1 若假設1成立，則Wolfe型線搜索方法（4）和（5）可行.

引理1的證明見文獻［5］.

引理2 算法Ⅰ中的序列（dk）k∈N滿足下降條件，即gkTdk＜0（k∈N）.

證 顯然d＝－g∈RN滿足gTd＜0.設gTd ＜0對……