帶模式步的梯度法

張　慧，寇彩霞

（北京郵電大學(xué)，北京市海淀區(qū)　100876）

帶模式步的梯度法

張慧，寇彩霞

（北京郵電大學(xué)，北京市海淀區(qū)100876）

本文通過把經(jīng)典模式搜索法中模式步的思想融入到梯度法中，提出了帶模式步的梯度法（Pattern Steepest Descent），克服了梯度法收斂速度變慢的缺陷。通過計算CUTEst中的測試問題對PSD算法和SD算法進行了比較。數(shù)值實驗表明，對絕大數(shù)測試問題，PSD算法的計算效率優(yōu)于SD算法。最后，我們對該PSD算法的理論分析做了一定的探索。

梯度法；帶模式步的梯度法；Wolfe準(zhǔn)則

本文著錄格式：張慧，寇彩霞. 帶模式步的梯度法［J］. 軟件，2016，37（8）：16-19

0　引言

梯度法［1］，又稱最速下降法（Steepest Descent，簡稱SD），由法國科學(xué)家Cauchy于1847年首先提出。算法在每次迭代中取負(fù)梯度為搜索方向，在該方向上里利用線搜索確定搜索步長。由于梯度法在靠近最優(yōu)點時，其步長變得越來越小，收斂速度越來越慢，即：梯度法出現(xiàn)鋸齒現(xiàn)象（ZigZag現(xiàn)象）。鋸齒現(xiàn)象的存在使得梯度法的計算效率很低，實用性減弱。

模式步最早是在經(jīng)典的模式搜索法［2，3］中采用的一種搜索方向。模式搜索法是求解無約束優(yōu)化問題的無導(dǎo)數(shù)方法，即，算法在迭代的過程中不需要計算目標(biāo)函數(shù)的導(dǎo)數(shù)。該法用于求解目標(biāo)函數(shù)不可導(dǎo)以及求導(dǎo)耗時的無約束最優(yōu)化問題。該法最早是由Hooke-Jeeves在1961年提出的，因此該法又稱Hooke-Jeeves方法。后續(xù)產(chǎn)生了修正的Hooke-Jeeves方法［2］。模式搜索法的基本思想是從初始基點開始，包括兩種類型的移動，即：探測移動和模式移動。探測移動依次沿n個坐標(biāo)軸進行搜索，用以確定新的基點和有利于函數(shù)值下降的方向。模式移動沿相鄰兩個基點連線方向進行搜索?？梢宰C明該方法有全局收斂性［4-9］。

本文提出了帶模式步的梯度法［10］（Pattern Steepest Descent，簡稱PSD），將經(jīng)典模式搜索法中模式步的思想融入到梯度法中，使得梯度法在迭代過程中每N步進行一次模式步的搜索。有效地避免了梯度法收斂慢的缺陷。本文結(jié)構(gòu)如下：第一節(jié)介紹了梯度法及Wolfe準(zhǔn)則；第二節(jié)介紹了帶模式步的梯度法（PSD）的算法框架；第三節(jié)通過計算CUTEst中的測試問題，詳細(xì)的給出了PSD算法同SD算法的數(shù)值結(jié)果比較；第四節(jié)進行總結(jié)與展望，探索PSD算法的全局收斂性，展望PSD算法的進一步發(fā)展。

1　梯度法（SD）

梯度法在每次迭代中以負(fù)梯度為搜索方向，在該方向上進行線搜索確定步長。最早的梯度法是由Cauchy提出的采用精確步長的梯度算法。后來Curry等人對梯度法作了進一步的研究，設(shè)計了一系列該方法的變種。梯度法由于計算簡單、存儲需求小的特點，被認(rèn)為是最優(yōu)化理論中的基礎(chǔ)和優(yōu)化算法設(shè)計中的基本方法。理論可以證明該法在適當(dāng)?shù)木€搜索下是全局收斂的，但數(shù)值實驗顯示算法在迭代接近極小值點時，會收斂變慢，產(chǎn)生鋸齒現(xiàn)象。本文提出的對梯度法的改進算法就是為了克服該數(shù)值缺陷。

最優(yōu)化算法在每步確定搜索方kd后，要計算該搜索方向上的步長kα。常常要求步長kα滿足下面的Wolfe條件［11，12］：

上述不等式（1）要求新點處的函數(shù)值有一定的下降；不等式（2）通過對函數(shù)梯度的比較要求步長kα不要取得太小。本文提出的新算法就是采用該Wolfe線搜索。

2　帶模式步的梯度法（PSD）

本節(jié)主要介紹一種帶模式步的梯度法（PSD）。該方法的基本思路是將梯度法與經(jīng)典的模式搜索方法相結(jié)合，在算法開始的時候采用負(fù)梯度方向迭代，從某個時刻開始每N步負(fù)梯度迭代后進行一次模式步迭代。具體的算法框架如下：

上述算法的搜索方向在S2中確定，具體的是在第一步迭代取負(fù)梯度方向，然后每隔N步負(fù)梯度迭代進行一次模式迭代。模式迭代的搜索方向是以當(dāng)前迭代點kx和前N步迭代點Nkx-的連線方向。這也是該方法和傳統(tǒng)的梯度法最根本的差別。正是這樣的差別能夠使梯度法的效率得到很大的提升，具體數(shù)值實驗結(jié)果參見下一節(jié)。算法在達到最大迭代步數(shù)maxit或者梯度的模小于等于給定的精度時終止。maxit和N的具體取值見數(shù)值實驗部分。

3　數(shù)值實驗

本文的測試問題來自于CUTEst［13］，它的早期版本CUTEr［13］是由Nicholas I.M.Gould，Dominique Orban和Philippe L.Toint在2001年開發(fā)的。CUTEst（Constraint and Unconstraint Test Enviroment）是一種測試無約束和有約束優(yōu)化算法的測試環(huán)境。它包含了諸多類型的無約束和約束優(yōu)化測試問題。測試問題均采用其標(biāo)準(zhǔn)輸入格式（SIF）編寫。

算法是在Matlab（R 2014a），Windows7操作系統(tǒng)上實現(xiàn)。下面是算法中所有參數(shù)的取值：實驗允許誤差ε=10-3；如果維數(shù)n小于10，最大迭代步數(shù)maxit取10000*n，否則就取1000*n；如果問題的維數(shù)n小于10，N取5*n，如果問題維數(shù)n介于10到1000之間，N取n/2，否則，N取n/20。

我們在CUTEst中隨機選取了80個無約束優(yōu)化問題，問題的維數(shù)為2至5000維。對這些問題分別使用PSD方法和SD方法進行求解。其中兩種算法均求解失敗的有18個問題。剩余的62個問題中，SD算法在15步迭代內(nèi)求解成功的有27個問題，這些問題我們認(rèn)為較容易求解。因此比較法時候我們只比較剩余35個較難問題。

表1給出剩余的35個問題的數(shù)值比較結(jié)果。表1中，iter表示問題求解成功時迭代步數(shù)；nf表示問題求解成功時目標(biāo)函數(shù)值的計算次數(shù)；ng表示問題求解成功時梯度的計算次數(shù)；time表示問題求解成功所用時間；表中每行依次表示測試問題的名字，測試問題的維數(shù)，PSD算法求解該測試問題的iter/nf/ng計數(shù)結(jié)果以及SD算法求解該測試問題的iter/nf/ng計數(shù)結(jié)果，哪個算法計算效率高就用加黑標(biāo)注。

具體的，兩種算法PSD算法和SD算法有5個測試問題求解效果一樣；有26個問題（占測試問題總數(shù)74.2%）PSD算法所用函數(shù)值和梯度求解次數(shù)遠小于SD算法，有4個問題（占測試問題總數(shù)11.4%）PSD算法所用函數(shù)值和梯度求解次數(shù)略多于SD算法。

4　總結(jié)與探索

本文提出了一個帶模式步的梯度法（PSD算法），數(shù)值實驗顯示該算法有效地提高了經(jīng)典梯度法的計算效率，但是該算法的收斂性還需要我們進一步探索。

表1　PSD算法與SD算法數(shù)值比較Tab.1　The numerical results of PSD method and SD method

經(jīng)典模式搜索法已經(jīng)證明是全局收斂的［14］：

定理［14］：設(shè)L（x0）是初始點x0的某個小鄰域，L（x0）是緊集，f在L（x0）上連續(xù)可微，經(jīng)典模式搜索法產(chǎn)生的迭代點｛xk｝滿足，

其證明過程是通過定義基本矩陣B∈Rn×n以及生成矩陣Ck∈Zn×p，得到一個一般的模式法的算法框架，并證明了該法的全局收斂性。通過矩陣B和Ck的特殊取值，證明了經(jīng)典的模式搜索算法正是該一般算法框架下的一個特殊算法，從而經(jīng)典模式搜索算法收斂性得證。

具體的，定義任意非奇異的基本矩陣B∈Rn×n，生成矩陣Ck∈Zn×p（p＞2n，R和Z分別表示實數(shù)集和整數(shù)集），可以得出一般模式法在第k次迭代的試探步：是Ck的第i列，αk表示步長，BCk的所有列表示了第k次迭代所有可能的迭代方向。通過該方式可以將經(jīng)典模式搜索法中的所有迭代方向，包括沿坐標(biāo)的n個方向和每N步的模式方向都可以寫成上述迭代格式。接著更新迭代點為

其中，kx表示當(dāng)前迭代點。滿足函數(shù)值下降的試探點作為下一個迭代點x。

如果上述一般模式搜索法中的基本矩陣B取單位陣I，生成矩陣kC的前3n均由｛1， 0， -1｝組成，表示坐標(biāo)搜索的所有方向，這3n列是固定不變的；在前3n的基礎(chǔ)上再添加3n列（也是由｛1， 0， -1｝組成），后3n列在迭代的過程中不斷變化，包含著成功模式搜索方向的變化。這樣的取值正是經(jīng)典的模式搜索法。故經(jīng)典的模式搜索法滿足一般模式搜索法的定義，從而具有全局收斂性。

我們嘗試將本文提出的PSD算法統(tǒng)一在該一般算法框架下，但是發(fā)現(xiàn)一般的模式法收斂性的證明過程中要求矩陣的元素為整數(shù)，而PSD算法不具備這一點。因此PSD算法的收斂性分析不能簡單地套用該一般模式法的收斂性結(jié)論。對PSD算法收斂性分析將是我們今后進一步的工作。

5　致謝

感謝編輯和審稿人的幫助和建議。

［1］ 袁亞湘. 非線性優(yōu)化計算方法［M］. 北京: 科學(xué)出版社. 2008.

［2］ Chen Jing， Du Xue wu. A modified Hook-Jeeves method［J］. Journal of ChongQing Normal University （Natural Science），Jul. 2013， 30（4）: 6-9.

［3］ 陳寶林. 最優(yōu)化理論與算法［M］. 北京: 清華大學(xué)出版社. 2005， 332～336.

［4］ Elizabeth D. Dolan. Pattern search behavior in nonlinear optimization［D］. Williamsburg: Department of Computer Science， College of William & Mary， 1999.

［5］ R. M. Lewis， V. J. Torczon. Rank ordering and positive bases in pattern search algorithms［R］. NASA Langley Research Center， Hampton， Virginia: Institute for Computer Applications in Science and Engineering， Tech. Rep. 96-71， 1999.

［6］ R. M. Lewis and V. J. Torczon. Pattern search algorithms for bound constrained minimization［J］， SIAM Journal on Optimization， 1999， 9（4）: 1082-1099.

［7］ R. M. Lewis， V. Torczon. Pattern Search Methods for Linearly Constrained Minimization［J］， SIAM Journal on Optimization，2000， 10（3）: 917-941.

［8］ R. M. Lewis， V. Torczon. A Globally Convergent Augmented Lagrangian Pattern Search Algorithm for Optimization with General Constraints and Simple Bounds ［J］， SIAM Journal on Optimization， 2002， 12（4）: 1075-1089

［9］ E. D. Dolan， R. M. Lewis， V. Torczon.On the local convergence of pattern search［J］， SIAM Journal on Optimization， 2003，14（2）: 567-583.

［10］ Dimitri P. Bertsekas. Nonlinear Programming［M］. 宋士吉，張玉利， 賈慶山. 北京: 清華大學(xué)出版社， 2013.

［11］ Wei Zeng-xin， Li Yan-jun， Tao Yan-rong. Global convence of a modifiedNK（）βμ method with stand wolfe conditions［J］. Journal of Guangxi Teachers Education University， 2008，25（2）: 4-8.

［12］ 袁亞湘. 非線性優(yōu)化計算方法［M］. 北京. 科學(xué)出版社. 2008. 38-43.

［13］ Gould N I M， Orban D， Toint Ph L. CUTEr （and SifDec）， a constrained and unconstrained testing environment， revisited. Technical Report TR/PA/01/04. CERFACS， Toulouse， France，2001 ［14］ Torczon， V. On the convergence of pattern search algorithms［J］. SIAM Journal on optimization， 1997. 7（1）: p. 1-25.

［14］ Torczon， V. On the convergence of pattern search algorithms［J］. SIAM Journal on optimization， 1997. 7（1）: p. 1--25.

Gradient Method with Pattern Step

ZHANG Hui， KOU Cai-xia
（Beijing University of Posts and Telecommunications, Beijing 100876， China）

This paper proposes the gradient method with pattern step（Pattern Steepest Descent） by adding the pattern step in classical pattern search method to the steepest descent method ， which overcomes deficiency of the SD’s slower convergence rate. The paper compares the PSD algorithm and SD algorithm by computing test problems in CUTEst，numerical experiments show that the calculation efficiency of PSD algorithm is faster than that of SD algorithm for most problems.

Steepest descent method； Gradient method with pattern step； Wolfe criterion

TN925+.3

A

10.3969/j.issn.1003-6970.2016.08.004

中國國家自然科學(xué)基金（11401038，11471052）. 中央高校基本科研業(yè)務(wù)費專項資金資助，北京郵電大學(xué)青年科研創(chuàng)新專項014RC0904

張慧（1990-），女，碩士研究生，主要研究：非線性最優(yōu)化；寇彩霞，主要研究方向：最優(yōu)化理論及其應(yīng)用。