一種新的無優化約束問題的混合FR和PRP共軛梯度算法

何曉旭, 殷守林, 趙志剛

(沈陽師范大學 科信軟件學院, 沈陽 110034)

?

一種新的無優化約束問題的混合FR和PRP共軛梯度算法

何曉旭, 殷守林, 趙志剛

(沈陽師范大學 科信軟件學院, 沈陽 110034)

混合共軛梯度法; 線性搜索; 收斂性分析

0 引 言

對于無優化問題,混合共軛梯度法在尋找最優解方面起著很大的作用。問題可以描述為

(1)

其中,f:Rn→R是連續可微的目標函數。對于解決大規模無優化問題,混合梯度法是首選的一種方法,因為不像牛頓或者擬牛頓法[1-2],它們只需要一階導數,因此只需要較少的存儲容量。而且他們也相對很容易編程。給定一個初始值x0∈Rn,混合梯度法產生對于式(1)的一個序列{xk},用下述方式表示:

(2)

其中,αk是線性搜索確定的一個步長,dk是在xk位置目標函數的下降方向。αk可以由執行一個確切或者不確切的一維線性搜索過程獲得。如果對于一個確切的線性搜索,那么αk可以是

(3)

如果對于不確切的線性搜索,在Amirjo條件下,需要αk滿足條件

(4)

和標準的Wolfe條件,也需要滿足公式(4)和曲率條件

(5)

其中,0<μ<σ<1。強Wolfe條件用于很多文章,由式(4)和式(6)給出。

(6)

混合梯度法的搜索方向dk可以由式(7)得到。

(7)

其中,gk=f(xk)是f的梯度在xk位置,βk是一個標量,被稱為共軛梯度系數。不同的共軛梯度系數選擇導致不同的共軛梯度法。一些應用比較廣泛的共軛梯度法包括)共軛算法[3-4],Polak-Ribiè)共軛算)共軛算)共軛算法[9],conjugate)共軛算法,)共軛算法[10]。所列文獻展示了二元函數是等價的,但是它們的性能還是依靠系數βk。共軛梯度法和擁有強大的全局收斂性性[11-12],但是它們有更少的計算性能;另一方面,和方法不總是收斂,但是表現出良好的計算性能[13-14]。

1 新的混合共軛梯度算法

(8)

(9)

(10)

第2步 使用任意一個線性搜索方法計算αk>0,并找到下一個迭代。xk+1=xk+αkdk,計算f(xk+1),gk+1=f(xk+1),如果‖gk+1‖≤ε,算法停止。

第4步 令k=k+1,返回執行第二步。

2 收斂性分析

為驗證新方法的收斂性,做如下關于在很多混合梯度算法中的應用分析收斂性目標函數的基本假設。

假設1f在水平集合S={x∈Rn:f(x)≤f(x0)}上有下界,x0是初始點。

假設2 在一些S的鄰居點N,函數f是連續可微的梯度函數。g(x)=f(x)是利普希茨連續,也就是說存在一個常數L>0,對于所有的x,y∈N使‖g(x)-g(y)‖≤L‖x-y‖。

引理 上述兩點假設存在的條件下,以xk+1=xk+αkdk此格式和式(7)為基礎,并且在dk時下降方向,步長αk滿足標準Wolfe條件(4)、(5)情況下,混合共軛梯度算法可以得到

(11)

3 數值結果

表1 4種方法數值結果

圖1 函數評價次數性能概況

為了更好地比較4種算法的數值效果,使用性能配置屬性,在圖1中有展示,其中的功能評估性能由曲線繪制。令P={p1,…,p14}是所有問題的集合,S={s1,s2,s3,s4}是4種算法集合。令ap,s代表性能測量次數,所以可以得出一個性能比值公式:rp,s=ap,s/min{ap,s:s∈S}。

4 結 論

在未來研究中將進一步開發更多混合共軛梯度法解決大規模無約束優化問題。雖然低維的測試問題主要用于測試本文新的算法,未來會在算法中向更高維層面延伸。另一個方向是擴展共軛梯度法來約束優化問題以及最優控制問題。

[1]馮冬冬. 一類精細修正牛頓法和擬牛頓法研究[D]. 長沙:中南大學, 2012.

[2]ANTNIOU A,LU W S. Practical optimization, algorithms and engeneering applications[M]. New York:Springer, 2007.

[3]WEI Zengxin, HUANG Haidong, TAO Yanrong. A modified hestenes-stiefel conjugate gradient method and its convergence[J]. 數學研究與評論, 2010,30(2):297-308.

[4]戚后鐸,韓繼業,劉光輝. 修正Hestenes-Stiefel共軛梯度算法[J]. 數學年刊A輯:中文版, 1996(3):277-284.

[5]A Globally Convergent Polak-Ribiere-Polyak Conjugate Gradient Method with Armijo-Type Line Search[J]. Numerical Mathematics A Journal of Chinese Universities(English Series), 2006,04(15):357-366.

[6]段俠彬,袁功林,王曉亮,等. 一種含參數的修正HS共軛梯度法及其收斂性[J]. 廣西大學學報(自然科學版), 2015,40(3):750-757.

[7]馬國棟,簡金寶,江羨珍. 一個具有下降性的改進Fletcher-Reeves共軛梯度法[J]. 應用數學學報, 2015,1(38):89-97.

[8]張靜. 一類新的修正Fletcher-Reeves算法[J]. 安徽大學學報(自然科學版), 2009,33(3):31-35.

[9]胡亞萍. 非線性單調方程組和非光滑優化問題的算法研究[D]. 上海：華東理工大學, 2015.

[10]張勁松,李紅. 含參數Dai-Yuan共軛梯度法及其收斂性[J]. 華東交通大學學報, 2008,1(25):127-129.

[11]BAAIE-KAFAKI S. A hybrid conjugate gradient method based on a quadratic relaxation of the Dai-Yuan Hybrid conjugate gradient parameter[J]. Optimization, 2013,62(7):929-941.

[12]DAI Y H. Convergence of conjugate gradient methods with constant step sizes[J]. Optimization Methods and Software, 2011,26(6):895-909.

[13]HAGER W, ZHANG H. A survey of nonlinear conjugate gradient methods[J]. Pacific Journal of Optimization, 2006(2):35-58.

[14]GILBET J, NOCEDAL J. Global convergence properties of conjugate gradient methods for optimization[J]. SIAM Journal on Optimization, 1992,2(1):21-42.

A new hybrid conjugate gradient FR and PRP method for unconstrained optimization problems

HEXiaoxu,YINShoulin,ZHAOZhigang

(Software College, Shenyang Normal University, Shenyang 110034, China)

hybrid conjugate gradient; line search; convergence analysis

2015-08-27。

國家自然科學基金資助項目(60970112)。

何曉旭(1989-),女,遼寧本溪人,沈陽師范大學碩士研究生; 通信作者:趙志剛(1971-),男,遼寧鐵嶺人,沈陽師范大學副教授,博士。

1673-5862(2016)01-0092-04

TP391.9

A

10.3969/ j.issn.1673-5862.2016.01.021