帶模式步的梯度法

張　慧，寇彩霞

（北京郵電大學，北京市海淀區　100876）

帶模式步的梯度法

張慧，寇彩霞

（北京郵電大學，北京市海淀區100876）

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

梯度法；帶模式步的梯度法；Wolfe準則

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

0　引言

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

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

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

1　梯度法（SD）

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

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

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

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

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

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

3　數值實驗

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

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

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

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

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

4　總結與探索

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

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

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

定理［14］：設L（x0）是初始點x0的某個小鄰域，L（x0）是緊集，f在L（x0）上連續可微，經典模式搜索法產生的迭代點｛xk｝滿足，

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

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

其中，kx表示當前迭代點。滿足函數值下降的試探點作為下一個迭代點x。

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

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

5　致謝

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

［1］ 袁亞湘. 非線性優化計算方法［M］. 北京: 科學出版社. 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］ 陳寶林. 最優化理論與算法［M］. 北京: 清華大學出版社. 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］. 宋士吉，張玉利， 賈慶山. 北京: 清華大學出版社， 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］ 袁亞湘. 非線性優化計算方法［M］. 北京. 科學出版社. 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

中國國家自然科學基金（11401038，11471052）. 中央高?；究蒲袠I務費專項資金資助，北京郵電大學青年科研創新專項014RC0904

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