張一夢，賀祖國

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

一種改進的無導數(shù)共軛梯度法

張一夢1，賀祖國2

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

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

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

0 引言

考慮無約束極小化問題

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

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

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

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

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

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

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

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

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

當gk+1和dk線性相關(guān)時：

當gk+1和dk線性無關(guān)時：

2 改進的無導數(shù)共軛梯度法

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

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

2.1 算法改進思路

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

2.1.1 半徑r的選擇

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

2.2 算法步驟

基于上述改進算法的思想，改進后的算法步驟如下：

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

Step2：檢驗是否滿足收斂性的判別準則：若dk＜ε，則停止迭代，點x*=xk即為極值點；否則進行Step3；

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

Step4：令xk+1=xk+αkdk，計算gk+1=dgk+1，進行Step5；

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

3 數(shù)值試驗

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

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

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

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

我們將一次多項式插值法記為算法 1，有限差商共軛梯度法記為算法 2，有限差商擬牛頓法記為算法3，改進的無導數(shù)共軛梯度法記為算法4。

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

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

4 結(jié)論

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

[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].北京: 科學出版社, 1997: 1-330.YUAN Y, SUN W.Optimization Theory and Algorithm[M].Beijing: Science Press, 1991.1-330.(in Chinese)

[10]陳寶林.最優(yōu)化理論與算法[M].北京: 清華大學出版社, 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]戴彧虹, 袁亞湘.非線性共軛梯度法[M].北京: 科學出版社, 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ù)學建模中的應(yīng)用[M].北京: 國防工業(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

張一夢(1992-)，女，研究生，主要研究方向為最優(yōu)化算法；賀祖國，男，(1972-)，教授，主要研究方向為數(shù)學建模，最優(yōu)化算法。

本文著錄格式：張一夢，賀祖國.一種改進的無導數(shù)共軛梯度法[J].軟件，2017，38（3）：93-96