带模式步的梯度法

张　慧，寇彩霞

（北京邮电大学，北京市海淀区　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个坐标轴进行搜索，用以确定新的基点和有利于函数值下降的方向。……