一種充分下降的共軛梯度法及其收斂性

貴竹青+潘軍

摘要：本文提出了一種新的求解無約束優(yōu)化問題的共軛梯度算法。通過構(gòu)造新的[θk]， 及[βk]公式，并由此給出一個具有充分下降性的方向，使得算法能夠滿足下降條件。我們在較弱的條件下證明下算法的全局收斂性。

關(guān)鍵詞：無約束優(yōu)化；共軛梯度法； Armijo線性搜索；全局收斂性

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）14-0191-02

1 概述

考慮無約束優(yōu)化問題

[min f（x） ， x∈Rn] （1）

其中[f（x）：Rn→R]是連續(xù)可微函數(shù).利用共軛梯度法可以有效求解問題（1），尤其對于大規(guī)模無約束優(yōu)化問題。

共軛梯度法的迭代格式為[xk+1=xk+αkdk]，其方向[dk]定義為：

[dk=-gk， k=0 -gk+βkdk-1， k>0]， （2）

步長[αk]由線性搜索得到。

常用的線性搜索有精確線性搜索：求[αk]滿足[f（xk+αkdk）=min α>0f（xk+αdk）]， Armijo線性搜索：給定[ρ∈（0，1）]，求[αk=max{ρi|j=0，1，2，…}]滿足[f（xk+αkdk）≤f（xk）+δαkgTkdk]， Wolf線性搜索：求[αk]滿足[f（xk+αkdk）≤f（xk）+δαkgTkdkdTkg（xk+αkdk）≥σgTkdk]，其中[0<δ≤σ<1].有關(guān)這些線性搜索實(shí)現(xiàn)方式可參看文獻(xiàn)[1]。

迭代式（2）中參數(shù)[βk]較著名的計算公式有：

[βHSk=gTk+1ykdTkyk，βFRk=||gk+1||2||gk||2，βPRPk=gTk+1yk||gk||2，βCDk=||gk+1||2-gTkdk，βLSk=gTk+1yk-gTkdk，βDYk=gTk+1ykdTkyk，]

其中[gk=?f（xk）]是函數(shù)[f]在[xk]點(diǎn)處的梯度，[yk=gk+1-gk]，[||?||]是歐式范數(shù).

Al-Baali在文獻(xiàn)[1]中證明，對于參數(shù)[σ<1/2]，F(xiàn)R方法在強(qiáng)Wolf線性搜索下非凸函數(shù)的全局收斂性，被認(rèn)為數(shù)值效果最好的方法之一是PRP方法，但是對于一般非凸函數(shù)，PRP方法即使在采用精確線性搜索時也不能保證全局收斂，如Powell在文獻(xiàn)[2]中給出的例子. 雖然FR方法有全局收斂性，但是在數(shù)值試驗效果上不如PRP方法，同時HS方法以及文獻(xiàn)[3]中給出的DY方法都有類似的情況.綜合上述方法中的優(yōu)點(diǎn)及剔除缺點(diǎn)，Touati-Ahmed和Storey在文獻(xiàn)[4]中首先提出了混合PRP-FR方法；Gilbert和Nocedal在文獻(xiàn)[5]中進(jìn)一步研究混合PRP-FR方法，使得參數(shù)[βk]允許取負(fù)值. Dai和Yuan在文獻(xiàn)[6]研究了混合DY-HS共軛梯度法，且在Wolf線性搜索下保證算法的收斂性。

我們稱滿足[gTkdk<0]的搜索方向[dk]為下降方向，稱總是產(chǎn)生下降方向的算法為下降算法。本文的目的是構(gòu)造一種具有充分下降性質(zhì)且在較弱條件下保證全局收斂性的算法。

2 算法

本文構(gòu)造一種新的[dk]迭代格式

[dk=-gk， k=0 -θkgk+βTGkdk-1， k>0]， （3）

其中 [θk=2gTkdk-1dTk-1（gk+1-gk），]

[βTGk=2||gk||2dTk-1（gk+1-gk）-||gk||2gTkdk-1]. （4）

引理1假設(shè)方向[dk]由（3）產(chǎn)生，則對任意[k≥0]有

[gTkdk=-||gk||2] （5）

證 （i）當(dāng)[k=0]時，結(jié)論顯然成立。

（ii） 當(dāng)[k>0]時，由式（3）知：

[gTkdk=-θkgk2+βTGkgTkdk-1= -2gTkdk-1dTk-1（gk+1-gk）gk2+（2gk2dTk-1（gk+1-gk）-gk2gTkdk-1）gTkdk-1=-gk2].

引理證明完畢。

下面給出求無約束優(yōu)化問題的共軛梯度法的具體步驟。

算法 A：

步驟0給定常數(shù)[δ2]，[ε>0]，[δ1， α∈（0，1）].任意選取初始點(diǎn)[x0∈Rn]，令[k=0]。

步驟1按公式（3）計算[dk]，其中[θk]，[βTGk]由（4）確定.若[gk≤ε]，則停止；否則轉(zhuǎn)步驟2。

步驟2按照如下線性搜索求步長[σk]，使[σk]為[1， α， α2， … ]中最大值滿足：

[f（xk+αkdk）≤f（xk）+δ1σkgTkdk-δ2σkdk2] （6）

步驟3令[xk+1=xk+σkdk]，[k=k+1]，轉(zhuǎn)步驟1。

3 算法的良定分析和收斂性證明

在算法分析中需要假設(shè)[Ω]：

（a）水平集[L={x∈Rn|f（x）≤f（x0）}]有界，其中[x0]為初始點(diǎn)。

（b）存在[L]的一個鄰域[B]。使[f]在[B]上連續(xù)可微，且梯度[g]滿足Lipschitz條件，即存在常數(shù)

[L1>0]，對任意[x， y∈B]有不等式成立[g（x）-g（y）≤L1x-y]，[?x， y∈B].由假設(shè)[Ω]知，存在常數(shù)

[N>0]，[M>0]，對[?x∈B]下列不等式成立[x≤N]，[gk≤M]。

引理2存在常數(shù)[η>0]，使得下面不等式對任意充分大的[k]都成立

[σk≥ηgk2dk2] （8）

證 由（6）及假設(shè)[Ω]知[k≥0-δ1σkgTkdk+δ2σkdk2<∞].由此及（5）可知[k≥0σ2kdk2<∞]，和

[k≥0αkgk2=-k≥0αkgTkdk<∞] （9）

特別地，[limk→∞δ2σkdk=0]，[limk→∞αkgk2=0]。

下面分兩種情形證明（8）成立。

（i）當(dāng)[σk=1].由（5），有[gk≤dk]，令[η=1]，則不等式（8）成立。

（ii）當(dāng)[σk<1].由步驟2知[α-1σk]不滿足不等式（6），那么就有下面不等式成立。

[f（xk+α-1αkdk）>f（xk）+δ1α-1σkgTkdk-δ2α-1σkdk2] （10）

由微積分中值定理和假設(shè)[Ω]知，存在[lk∈（0， 1）]使得：

[f（xk+α-1αkdk）-f（xk）=α-1σkg（xk+lkα-1σkdk）Tdk = α-1σkgTkdk+α-1σk（g（xk+lkα-1σkdk）-gk）Tdk ≤ α-1σkgTkdk+L1α-2σ2kdk2]

將最后一個不等式代入式（10），得[σk>（1-δ1）αgk2（L1+δ2）dk2]

取[η=min{1， （1-δ1）αgk2（L1+δ2）dk2}]，則可知不等式（8）成立，引理證明完畢。

那么有引理2和式（9），即可得Zoutendijk..

引理3設(shè)目標(biāo)函數(shù)滿足假設(shè)[Ω]，序列[{xk}]由算法A產(chǎn)生，則[k≥0gk4dk2<+∞]

下面證明算法的全局收斂性。

定理1若假設(shè)[Ω]成立，[{xk}]和[{dk}]由算法A產(chǎn)生，則[limk→∞inf||gk||=0]。

證 利用反證法，假設(shè)結(jié)論不成立，則存在常數(shù)[c>0]，使得[||gk||≥][c]，[?k≥0].由式（3）知[gTkdk=-θkgk2+βTGkgTkdk-1]，因此有

[gTkdk-1=θk-1βTGkgk2] （11）

由式（3）和式（11）有

[dk2=θ2kgk2-2θkβTGkgTkdk-1+（βTGk）2dk-12= （2θk-θ2k）gk2+（βTGk）2dk-12]

因此有：

[dk2gk4=（βTGk）2dk-12gk4+（2θk-θ2k）1gk2= dk-12gk4-（θk-1）gk2+1gk2≤ dk-12gk4+1gk2 ≤ j=0k1gj2≤kc2].

上式等價于[gk4dk2≥c2k=+∞]，這與引理3矛盾，定理證明完畢。

參考文獻(xiàn)：

[1] M.Al-Baali， Descent property and global convergence of the Fletcher-Reeves method with inexact line search. IMAJ. Number. Anal.， 1985（5）：121-124.

[2] Powell M J D. Nonconex Minimization calculations and the conjugate gradient method. Lecture Notes in Math.， 1984， 1066： 121-141.

[3] Dai Y H， Yuan Y X. A nonlinear conjugate gradient with a strong alobal convergence property. SIAM Journal of Optimization， 2000（10）： 177-182.

[4] Touati-Ahmed D， Storey C. Efficient hybrid conjugate gradient techniques. J. Optim. Theory Appl.， 1990，64： 379-397.

[5] Gilbert J C， Nocedal J. Global convergence properties of conjugate gradient method for optimization. SIAM. J. Optim.， 1992（2）： 21-42.

[6] Dai Y H， Yuan Y. An efficient hybrid conjugate gradient method for unconstrained optimization. Annals of Operations Research， 2001（103）： 33-47.

[7] 袁亞湘，孫文瑜. 最優(yōu)化理論與方法[M]. 北京： 科學(xué)出版社，1995.

[9] 張麗.求解最優(yōu)化問題的非線性共軛梯度法[D].湖南：湖南大學(xué)，2006.