無約束優化的一個充分下降共軛梯度算法

摘 要 在修正PRP共軛梯度法的基礎上，提出了求解無約束優化問題的一個充分下降共軛梯度算法，證明了算法在Wolfe線搜索下全局收斂，并用數值實驗表明該算法具有較好的數值結果.

關鍵詞 無約束優化；共軛梯度法；Wolfe線搜索；充分下降性；全局收斂性

中圖分類號 O224文獻標識碼 A

A Sufficient Descent Conjugate Gradient Algorithm for Unconstrained Optimization

HUANG Hai

(Department of Mathematics and Computer Science， Guangxi Normal

University for Nationalities， Chongzuo， Guangxi 532200， China)

Abstract A sufficient descent conjugate gradient algorithm for unconstrained optimization was presented on the basis of modified PRP conjugate gradient method. It is proved that the algorithm is globally convergent with the Wolfe line search conditions. The numerical results show that the algorithm is efficient.

Keywords unconstrained optimization; conjugate gradient method; Wolfe line search; Sufficient descent property; global convergence

1引 言

共軛梯度法具有迭代簡單、存儲需求少等特點，是大型無約束優化問題的有效計算方法之一，被廣泛應用于科學、工程、經濟和社會系統等許多領域.本文研究用共軛梯度法求解無約束優化問題

min {f(x)|x∈Rn}，其中x為決策變量，f:Rn→R為連續可微的目標函數，f(x)的梯度

f(x)記為g(x)，fk表示f(xk)，gk表示g(xk).

共軛梯度法的迭代格式為

xk+1=xk+αkdk，(1)

dk=－gk，k=1，－gk+βkdk－1，k≥2.(2)

其中，dk為搜索方向，αk為由線搜索產生的步長因子，βk為標量參數.不同的參數βk對應不同的共軛梯度法，關于βk的著名公式有多種[1]，本文關注其中的兩個公式

βFRk=‖gk‖2‖gk-1‖2，βPRPk=‖gk‖2-gTkgk-1‖gk-1‖2，

它們對應的共軛梯度法分別稱為FR方法和PRP方法.

Al-Baali[2]證明了FR方法在強Wolfe線搜索下具有全局收斂性，然而FR方法的數值結果較差.雖然PRP方法被認為是數值結果最好的共軛梯度法之一，但如Powell[3]指出的，原始PRP方法對一般目標函數不能建立其收斂性，Gilbert和Nocedal[4]對βk取值非負的情形(βPRP+k=max{0，βPRPK})，建立了PRP+方法的全局收斂性.為了得到不但收斂性好而且數值結果優秀的共軛梯度法，人們在經典共軛梯度法的基礎上提出各種βk的改進方案[5-9]，文獻[5]提出基于FR方法的修正參數

βVFRk=μ1‖gk‖2μ2‖gk-1‖2+μ3|gTkdk-1|，μ1，μ2>0，μ3>μ1.

文獻[6]提出基于PRP方法的修正參數：

βNk=‖gk‖2-｜gTkgk-1｜‖gk-1‖2+μ|gTkdk-1|，‖gk‖2≥|gTkgk-1|

0，其他，，（3）

μ>1.文獻[9]提出基于PRP方法的參數修正方案：

βk=max{0，βVNk}，

其中，βVNk=‖gk‖2-｜gTkgk-1｜‖gk-1‖2+μ(gTkdk-1)2，μ>0.

這些相應的修正方法均具有βk≥0的特點， 具有全局收斂性，且取得較好的數值結果.

共軛梯度法的迭代計算過程保持目標函數的充分下降對收斂性有著很重要的作用，要求的充分下降條件為：

gTkdk≤-c‖gk‖2，c>0. (4)

共軛梯度法步長搜索常用的Wolfe線搜索條件為：

f(xk+αkdk)-f(xk)≤δgTkdk，

|g(xk+αkdk)|Tdk≥σgTkdk.(5)

其中，δ∈(0，12)，σ∈(δ，1).式(5)中第二個式子改成|g(xk)+αkdk)Tdk|≤-σgTkdk，即為強Wolfe線搜索條件.

本文在文獻[6]提出的修正PRP方法基礎上，允許βk取負值，擴大參數的取值范圍，考慮采用Wolfe線搜索，提出改進的算法，并分析了算法的全局收斂性，比較算法的數值表現.

2 算法及假設

由式(3)可看出文獻[6]中的參數0≤βNk≤βFRk，下面改進使得-βFRk≤βk≤βFRk，提出求解無約束問題的新共軛梯度算法描述：

算法1

步驟1給定x1∈Rn，δ∈(0，12)，σ∈(σ，1)， ε≥0， d1=-g1，k:=1.若‖gk‖≤ε，停止.

步驟2計算滿足Wolfe線搜索條件(5)的步長αk.

步驟3計算xk+1:=xk+αkdk，gk+1:=g(xk+1). 若‖gk+1‖≤ε，停止.

步驟4由式(2)計算搜索方向dk，其中參數βk為：若2‖gk‖2≥|gTkgk-1|，

βk=‖gk‖2-｜gTkgk-1｜max{‖gk-1‖2，μ|gTkdk-1|}+|gTkdk-1|，μ>0;(6)

否則，βk=0.

步驟5k:=k+1，轉步驟2.

根據算法1的步驟4，對任意給定的μ>0，由式(6)易得如下關系.

引理1 算法1中βk滿足

-βFRk≤βk≤βFRk.(7)

為了分析算法的收斂性，下面給出一般共軛梯度法收斂性分析中常用的基本假設條件:

假設(i) 目標函數f(x)在水平集

Ω={x∈Rn|f(x)≤f(x1)}內有下界.

(ii) 在水平集

Ω內，目標函f連續可微且其導函數g滿足Lipschitz條件，即存在常數L>0，使得

‖g(x)－g(y)‖≤L‖x－y‖，x，y∈Ω.

3 全局收斂性

下面的定理說明算法1滿足充分下降條件(4).

定理1 考慮算法1生成的序列gk和dk，則

-c2‖gk‖2≤gTkdk≤-c‖gk‖2， k≥1. (8)

其中，c1=μ1+μ∈(0，1)，c2=2+μ1+μ∈(1，2).

證明(a) k=1時，d1=－g1，有gTk=-‖gk‖2，顯然滿足式(8).

(b)k>1時，由(2)可得gTkdk=-‖gk‖2+βkgTkdk-1，分兩種情形來討論:

若gTkdk-1=0，顯然gTkdk=-‖gk‖2，式(8)滿足.

若gTkdk-1≠0，由式(6)可得|βk|≤‖gk‖2(1+μ)|gTkdk-1|，從而可得

gTkdk≤-‖gk‖2+|βk‖gTkdk-1|

≤－(1－11+μ)‖gk‖2=－c1‖gk‖2，

gTkdk≥-‖gk‖2-|βk‖gTkdk-1|

≥－(1+11+μ)‖gk‖2=－c2‖gk‖2.

即k>1時，式(8)滿足.綜上即知定理成立.

證畢

根據定理1及文獻[1]的引理1.4.1，易得算法1滿足Zoutendijk條件.

引理2 假設(i)，(ii)成立.考慮算法1生成的序列gk和dk，則

∑k≥1‖gk‖4‖dk‖2<+

. (9)

定理2 假設(i)，(ii)成立.考慮算法產生序列gk，則

lim inf k→

‖gk‖=0. (10)

證明采用反證法，若式(10)不成立，必存在常數γ>0，使得

‖gk‖≥γ，k≥1. (11)

由式(2)可得β2k‖dk-1‖2=‖gk‖2+2gTkdk+‖dk‖2， 進而由式(7)和式(8)，得到

‖dk‖2=β2k‖dk-1‖2-‖gk‖2-2gTkdk

≤(βFRk)2‖dk-1‖2-‖gk‖2+2c2‖gk‖2

=‖gk‖4［‖dk－1‖2‖gk－1‖4+1‖gk‖2(2c2－1)］.

由上式及式(11)，可得

‖dk‖2‖gk‖4≤‖dk－1‖2‖gk－1‖4+c3≤c3k，

其中，c3=max1r2(2c2－1)>1r2>0.

由上式可得

∑k≥1‖gk‖4‖dk‖2≥1c3∑k≥11k=+

.

這與式(9)產生矛盾.從而定理成立.

證畢

4 數值實驗

在這一部分中，測試算法1的數值表現，并與PRP方法及文獻[6]方法進行比較，數值實驗結果如表1，計算效能比較結果見表2.所用的算例來自文獻[10]，數學軟件為Matlab7.3，運行環境為1.60GHz CPU，1G RAM，Windows XP系統，算法線搜索參數δ=0.01，σ=0.1，精度參數ε=10－5.表中相關的符號表示為:

PRPSWP:算法參數為βPRPk，采用強Wolfe線搜索；

NCGWWP：算法參數為βNk，μ=1.25，采用Wolfe線搜索；

VCGWWP：算法1，μ=1.4.

Problem：測試問題的名稱；Dim：目標函數的維數；“-”：算法對算例計算失效；

NI/NF/NG：迭代次數/目標函數計算次數/目標梯度函數計算次數.

為比較算法的計算效能，采用文獻[5]中數值迭代的估計辦法.具體為，利用公式（12）計算測試函數及其梯度估計的總次數

Ntotal=NF+5*NG.(12)

對第i個測試函數，利用算法j(記為EM(j))及PRPSWP算法求解，式(12)對應的結果分別記為Ntotal，i(EM(j))和Ntotal，i(PRPSWP)，然后計算比值

ri(EM(j))=Ntotal，i(EM(j))Ntotal，i(PRPSWP)，

r(EM(j))=(∏i∈Sri(EM(j)))1/|S|，

其中，S表示測試問題集，S表示集合S的元素個數， S1={i:算法j或PRPSWP算法對第i個算例失效，i∈S}.對問題i，若算法j計算成功，而PRPSWP算法計算失效，則取ri(EM(j))=

min {ri(EM(j)):iS1}；若算法j計算失效，而PRPSWP算法計算成功，則取ri(EM(j))=

max {ri(EM(j)):iS1}；若算法j及PRPSWP算法均計算失效，則取ri(EM(j))=1.

最后以幾何平均數r(EM(j))作為算法j與PRPSWP算法的總體計算效能的關系.r(EM(j))>1時說明算法j不比PRPSWP算法的數值結果好，r(EM(j))=1則說明兩個算法數值結果相當，r(EM(j))<1說明算法j的數值結果優于PRPSWP算法，且越小越好.根據以上規則，顯然有r(PRPSWP)=1，r(NCGWWP)，r(VCGWWP)的值列表2.

從表2可以看出，相對于表1中所測試的問題集合，在實驗中給定的這些測試參數下，算法1的數值結果優于PRPSWP算法及文獻[6]中的算法.說明算法1是有效的.

參考文獻

［1］ 戴彧虹，袁亞湘. 非線性共軛梯度法[M]. 上海:上海科學技術出版社， 2001.

[2] M AL-BAALI. Descent property and global convergence of Flecher-Reeves method with inexact line search[J]. IMA J Numer Anal， 1985，5:121-124.

[3] M J D POWELL. Nonconvex minimization calculations and the conjugate gradient method[J]. Lecture Notes in Mathematics， 1984， 1066: 122-141.

[4] J C GILBERT， J NOCEDAL. Global convergence properties of conjugate gradient methods for optimization[J]. SIAM J Optim 1992， 2: 21-42.

[5] Z X WEI， G Y LI， L Q QI. New nonlinear conjugate gradient formulas for large-scale unconstrained optimization problems[J]. Appl Math Comput， 2006， 179: 407-430.

[6] G H YU， Y L ZHAO， Z X WEI. A descent nonlinear conjugate gradient method for large-scale unconstrained optimization[J]. J Appl Math Comput， 2007， 187: 636-643.

[7] 賀戰兵，向昭紅. 一類帶參數的修改Fletcher-Reeves共軛梯度法[J]. 經濟數學， 2009，26(3):79-84.

[8] 劉金魁，王開榮. 一種改進的共軛梯度法及全局收斂性[J]. 經濟數學， 2008， 25(3): 309-315.

[9] 洪玲，莫利柳. 一個新的全局收斂的共軛梯度法[J]. 運籌學報， 2009， 13(1):95-106.

[10]J J MOR，B S GARBOW， K E HILLSTROM. Testing unconstrained optimization software[J]. ACM Trans Math Software， 1981， 7: 17-41.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文