張一夢(mèng)，賀祖國(guó)

（1.北京郵電大學(xué)理學(xué)院，北京 100876；2.北京郵電大學(xué)，北京 100876）

一種改進(jìn)的無(wú)導(dǎo)數(shù)共軛梯度法

張一夢(mèng)1，賀祖國(guó)2

（1.北京郵電大學(xué)理學(xué)院，北京 100876；2.北京郵電大學(xué)，北京 100876）

本文基于共軛梯度法的子空間研究，針對(duì)無(wú)約束優(yōu)化問(wèn)題提出了一種改進(jìn)的無(wú)導(dǎo)數(shù)共軛梯度法。新算法不僅能有效彌補(bǔ)經(jīng)典共軛梯度法要求線(xiàn)搜索為精確搜索的局限性，而且可適用于導(dǎo)數(shù)信息不易求得甚至完全不可得的問(wèn)題。實(shí)驗(yàn)結(jié)果表明：相比于一次多項(xiàng)式插值法、有限差商共軛梯度法以及有限差商擬牛頓法，新算法的效率有很大的提高。

無(wú)約束最優(yōu)化；無(wú)導(dǎo)數(shù)優(yōu)化；子空間；共軛梯度法

0 引言

考慮無(wú)約束極小化問(wèn)題

其中f:Rn→R二次連續(xù)可微。

目標(biāo)函數(shù)的導(dǎo)數(shù)信息（梯度和 Hessian矩陣）在優(yōu)化過(guò)程有著非常重要的作用。例如，對(duì)一個(gè)目標(biāo)函數(shù)連續(xù)可微的無(wú)約束優(yōu)化問(wèn)題來(lái)說(shuō)，由一階最優(yōu)性條件確定的穩(wěn)定點(diǎn)處，其梯度為零。導(dǎo)數(shù)信息不僅能提供簡(jiǎn)單有效的停止準(zhǔn)則，并且能有效的指引對(duì)試探點(diǎn)的選取。然而，很多來(lái)源于實(shí)際應(yīng)用的優(yōu)化問(wèn)題的導(dǎo)數(shù)信息不易求得甚至完全無(wú)法得到，因此解決這類(lèi)問(wèn)題需要用無(wú)導(dǎo)數(shù)優(yōu)化方法，也稱(chēng)為直接方法。

早期的無(wú)導(dǎo)數(shù)方法例如單純形法，簡(jiǎn)單直觀并且易于實(shí)現(xiàn)。發(fā)展到現(xiàn)在，無(wú)導(dǎo)數(shù)優(yōu)化方法有直接搜索法[1-3]，線(xiàn)搜索法[4-6]，隨機(jī)性算法，有限差商共軛梯度法和擬牛頓法[7]，基于差值模型逼近的信賴(lài)域方法等。

本文基于共軛梯度法的子空間研究[8]，將其運(yùn)用于多項(xiàng)式插值算法中得到一種改進(jìn)的無(wú)導(dǎo)數(shù)共軛梯度法。新算法不使用導(dǎo)數(shù)，實(shí)驗(yàn)結(jié)果表明，新算法提高了效率，是有效可行的。

1 共軛梯度法的子空間研究

共軛梯度法[9-12]是求解非線(xiàn)性無(wú)約束極小化問(wèn)題[13]的一種經(jīng)典算法，其基本思想是將最速下降方向與共軛性相結(jié)合構(gòu)造一組共軛方向，在已知點(diǎn)處沿著這組共軛方向進(jìn)行精確線(xiàn)搜索，求出目標(biāo)函數(shù)的極小值和極小點(diǎn)。標(biāo)準(zhǔn)的共軛梯度法具有如下迭代形式：

其中dk+1迭代形式如下：

根據(jù)以上形式可知，由于不同的kβ將會(huì)產(chǎn)生不同的搜索方向dk，因而得到的共軛梯度算法也不一樣。

共軛梯度法的子空間研究，彌補(bǔ)了經(jīng)典共軛梯度法要求線(xiàn)搜索為精確搜索的局限性。當(dāng)線(xiàn)搜索為非精確搜索時(shí)，可在由 gk+1和dk張成的子空間span｛gk+1,dk｝中求dk。下面我們給出dk+1的迭代形式：

當(dāng)gk+1和dk線(xiàn)性相關(guān)時(shí)：

當(dāng)gk+1和dk線(xiàn)性無(wú)關(guān)時(shí)：

2 改進(jìn)的無(wú)導(dǎo)數(shù)共軛梯度法

多項(xiàng)式插值法[13-16]屬于無(wú)導(dǎo)數(shù)優(yōu)化方法，其主要思想是用插值方法來(lái)構(gòu)造目標(biāo)函數(shù)的多項(xiàng)式逼近模型，計(jì)算過(guò)程中使用差商來(lái)近似梯度，不需要目標(biāo)函數(shù)的導(dǎo)數(shù)信息。本文使用一次多項(xiàng)式插值模型來(lái)近似目標(biāo)函數(shù)。本文將差商記為dg，設(shè)當(dāng)前迭代點(diǎn)為xk，則此點(diǎn)處的梯度可由差商來(lái)近似，其中：

其中r為半徑，ei∈Rn表示除第i個(gè)分量等于1外，其余分量均等于0的向量。

2.1 算法改進(jìn)思路

本文的改進(jìn)思路是將對(duì)共軛梯度法的子空間研究運(yùn)用于多項(xiàng)式插值算法中，得到改進(jìn)的無(wú)導(dǎo)數(shù)共軛梯度法。具體實(shí)現(xiàn)過(guò)程為：公式（1）和公式（2）求解搜索方向 dk+1時(shí)，用差商來(lái)近似梯度，然后沿此搜索方向進(jìn)行搜索，求得目標(biāo)函數(shù)的極小值點(diǎn)。

2.1.1 半徑r的選擇

關(guān)于半徑r的選取，本文令初始半徑r0=1。在之后的迭代時(shí)，若當(dāng)前迭代點(diǎn)函數(shù)值與上一個(gè)迭代點(diǎn)函數(shù)值的距離小于α?xí)r，選取半徑為當(dāng)前迭代點(diǎn)函數(shù)值與上一個(gè)迭代點(diǎn)函數(shù)值距離的α倍，即。根據(jù)大量的數(shù)值實(shí)驗(yàn)，得出當(dāng)α=0.01時(shí)實(shí)驗(yàn)結(jié)果較好，故本文中選取α=0.01。

2.2 算法步驟

基于上述改進(jìn)算法的思想，改進(jìn)后的算法步驟如下：

Step1：給定初始點(diǎn) x0∈Rn，允許誤差ε＞0，初始搜索方向d0=-dg0，k=0；

Step2：檢驗(yàn)是否滿(mǎn)足收斂性的判別準(zhǔn)則：若dk＜ε，則停止迭代，點(diǎn)x*=xk即為極值點(diǎn)；否則進(jìn)行Step3；

Step3：從當(dāng)前迭代點(diǎn)xk出發(fā)，沿dk進(jìn)行一維搜索，求kα ，使其滿(mǎn)足，其中，一維搜索使用wolfe-Powell非精確線(xiàn)搜索，進(jìn)行Step4；

Step4：令xk+1=xk+αkdk，計(jì)算gk+1=dgk+1，進(jìn)行Step5；

Step5：構(gòu)造搜索方向dgk+1：

3 數(shù)值試驗(yàn)

此次數(shù)值實(shí)驗(yàn)，所用電腦系統(tǒng)為Windows 10，內(nèi)存為4.00 GB，處理器主頻為2.30 GHz，編程環(huán)境為Mathematics10.1[17]。用Mathematic語(yǔ)言分別編寫(xiě)了一次多項(xiàng)式插值法、有限差商共軛梯度法、有限差商擬牛頓法和改進(jìn)的無(wú)導(dǎo)數(shù)共軛梯度法的算法程序。在程序中，線(xiàn)搜索步長(zhǎng)的選取均采用 Wolfe-Powell非精確線(xiàn)條件來(lái)進(jìn)行，終止條件為dk＜10-8。

3.1 選用的測(cè)試函數(shù)

本文選取兩個(gè)可變維數(shù)的測(cè)試函數(shù)：

3.2 數(shù)值結(jié)果

我們將一次多項(xiàng)式插值法記為算法 1，有限差商共軛梯度法記為算法 2，有限差商擬牛頓法記為算法3，改進(jìn)的無(wú)導(dǎo)數(shù)共軛梯度法記為算法4。

表1 Wolfe-Powell準(zhǔn)則下四種算法的運(yùn)行結(jié)果Tab.1 The results for the four algorithms at Wolfe-Powell

根據(jù)表1和表2中結(jié)果分析可得：不管是對(duì)于一些次數(shù)較高的函數(shù)，還是對(duì)于維數(shù)較大的函數(shù)而言，相比一次多項(xiàng)式插值法、有限差商共軛梯度法和有限差商擬牛頓法，改進(jìn)的無(wú)導(dǎo)數(shù)共軛梯度法不僅迭代次數(shù)少，運(yùn)行時(shí)間短，并且能收斂到很高的精度，具有良好的計(jì)算效能。

4 結(jié)論

大多數(shù)優(yōu)化方法都依賴(lài)問(wèn)題的導(dǎo)數(shù)信息，但在實(shí)際應(yīng)用中，大量問(wèn)題的導(dǎo)數(shù)信息都不可用，本文改進(jìn)的算法可以很好的解決導(dǎo)數(shù)信息不易求得的無(wú)約束優(yōu)化問(wèn)題。在數(shù)值實(shí)驗(yàn)中，通過(guò)四種算法從迭代次數(shù)，運(yùn)行時(shí)間，誤差等方面的對(duì)比，數(shù)值結(jié)果也表明本文改進(jìn)的算法是一種有效可行的方法。

[1]R.Hooke and T.A.Jeeves, Direct search solution of numerical and statistical problems, Journal of the Association forComputing Machinery, 8(1961), pp.212–229.

[2]E.Fermi and N.Metropolis, Tech.Report, Los Alamos Unclassifled Report LA–1492, Lo s Alamo s Na tional Laboratory, Los Alamos, NM, 1952.

[3]J.A.Nelder and R.Mead, A simplex method for function minimization, The Computer Journal, 7(1965), pp.308–313.

[4]H.H.Rosenbrock, An automatic method for flnding the greatest or least value of a function, Comput.J., 3(1960), pp.175–184.

[5]M.J.D.Powell, An e–cient method for flnding the minimum of a function of several variables without calculating derivatives, Comput.J., 7(1964), pp.155–162.

[6]W.H.Swann, Report on the development of a new direct search method of optimization, Tech.Rep.Research Note 64/3, I.C.I.Central Instrument Lab, 1964.

[7]G.W.Stewart, A modiflcation of Davidon’s minimization method to accept difierence approximations of derivatives, Journal of the ACM, 14(1967), pp.72–83.

[8]Yuan Y X, Stoer J.A Subspace Study on Conjugate Gradient Algorithms[J].Zamm Journal of Applied Mathematics & Mechanics Zeitschrift Für Angewandte Mathematik Und Mechanik, 1995, 75(1): 69-77.

[9]袁亞湘, 孫文瑜.最優(yōu)化理論與算法[M].北京: 科學(xué)出版社, 1997: 1-330.YUAN Y, SUN W.Optimization Theory and Algorithm[M].Beijing: Science Press, 1991.1-330.(in Chinese)

[10]陳寶林.最優(yōu)化理論與算法[M].北京: 清華大學(xué)出版社, 2005.1-358.CHEN B, Optimization Theory and Algorithm[M].Beijing: Tsinghua University Press, 2005.1-358.(in Chinese)

[11]M.J.D.Powell, Nonconvex minimization calculations and the conjugate gradient method, in: Lecture Notes in Mathematics vol 1066, Berlin: Springer-Verlag, 1984.122-141.

[12]戴彧虹, 袁亞湘.非線(xiàn)性共軛梯度法[M].北京: 科學(xué)出版社, 1982.DAI Y H, YUAN Y X.Nonlinear conjugate gradient method[M].Beijing: Science Press, 1982.(in Chinese)

[13]M.J.D.Powell, Direct search algorithms for optimization calculations, Acta Numerica, pages 288-336, Cambridge University Press, Cambridge, 1998.

[14]M.J.D.Powell, UOBYQA: unconstrained optimization by quadratic approximation, Report No.DAMTP 2000/NA14, University of Cambridge.

[15]M.J.D.Powell, On the Lagrange functions of quadratic models that are defined by interpolation, Opim.Methods Software, 2001(16), 289-309.

[16]M.J.D.Powell, Least Frobenius norm updating of quadratic models that satisfy interpolation conditions, Report No.DAMTP 2002/NA08, University of Cambridge.李漢龍, 繆淑賢, 韓婷.Mathematica基礎(chǔ)及其在數(shù)學(xué)建模中的應(yīng)用[M].北京: 國(guó)防工業(yè)出版社, 2013.

[17]LI H L, MIU S X, HAN T.Mathematica basis and its application in Mathematical Modeling[M].Beijing: Naional Defense Industry Press, 2013.(in Chinese)

An Improved Conjugate Gradient Method without Derivatives

ZHANG Yi-meng1,2, HE Zu-guo1,2
(1.Beijing University of Posts and Telecommunications, College of Science, Beijing 100876, China; 2.Beijing University of Posts and Telecommunications , Beijing 100876, China)

Based on the study of subspace of conjugate gradient method, an improved conjugate gradient method without derivatives is proposed for unconstrained optimization problem.The new algorithm can not only make up for the classical conjugate gradient method, but also can be applied to the problem that the derivative information is not easy to obtain or even completely unavailable.The experimental results show that the efficiency of the new algorithm is greatly improved compared with the linear polynomial interpolation method, the finite difference conjugate gradient method and the finite difference quasi-Newton method.

Unconstrained optimization; Optimization without derivative; Subspace; Conjugate gradient method

O221.2

A

10.3969/j.issn.1003-6970.2017.03.019

張一夢(mèng)(1992-)，女，研究生，主要研究方向?yàn)樽顑?yōu)化算法；賀祖國(guó)，男，(1972-)，教授，主要研究方向?yàn)閿?shù)學(xué)建模，最優(yōu)化算法。

本文著錄格式：張一夢(mèng)，賀祖國(guó).一種改進(jìn)的無(wú)導(dǎo)數(shù)共軛梯度法[J].軟件，2017，38（3）：93-96