基于Hooke-Jeeves方法和最速下降法的组合最优化方法研究

刘亮 叶佳驹

摘 要 在解决优化问题时，最速下降法是常用的最优化方法之一，但其越接近目标值，步长越小，前进越慢，使迭代次数增多。而对于另外一种Hooke-Jeeves最优化方法而言，初值的选择对它的收敛速度有着很大的影响。因此，本文将最速下降法与Hooke-Jeeves方法进行组合，先利用最速下降法得到一个较接近目标值的解，然后利用这个解作为初始解代入Hooke-Jeeves方法中，以此得到规定误差内的最优解，从而达到提高收敛速度的目的。最后，通过实例验证了本文提出的组合最优化方法的优越性。

关键词 最速下降法;Hooke-Jeeves方法;组合最优化方法

1 最速下降法和Hooke-Jeeves方法

1.1 最速下降法

最速下降法是以负梯度方向作为下降方向的极小化算法，所以又称梯度下降法，特别适合于低维空间的无约束最优化求解问题[9]。

它的算法基本流程如下：

2 組合最优化方法

将最速下降法和Hooke-Jeeves方法进行组合，即先利用最速下降法得到一个较接近目标值的解，然后将这个解作为初始解代入Hooke-Jeeves方法中。在本文提出的组合最优化方法中，一个关键问题就是利用最速下降法得到的解，怎样才算是接近目标值的解，应该有一个标准去衡量。本文通过大量实验知道对于不同的优化问题，这个标准是不一样的，即设置最速下降法停止迭代的误差是不同的。

3 实例验证

为了验证本文提出的组合最优化方法的优越性，通过下列优化问题进行数值实验：

.

设置初始解x0=[7;7]，表1表示设置不同的误差值时，最速下降法、Hooke-Jeeves方法、组合最优化方法的迭代次数。针对此优化问题，在组合最优化方法中，设置最速下降法停止迭代的误差。

从表1我们可以看出，最速下降法的迭代次数随着误差值的减小增加得很快，这也印证了最速下降法有越接近目标值时下降得越慢的缺点，Hooke-Jeeves方法和本文提出的组合最优化方法的迭代次数则比较稳定，但组合最优化方法的迭代次数明显小于最速下降法、Hooke-Jeeves方法的迭代次数，这说明了本文提出的组合最优化方法有着良好的收敛效率[1-8]。

4 结束语

本文从最速下降法以及Hooke-Jeeves方法的缺点出发，将两者进行组合，从而提出一种组合最优化方法。该组合最优化方法能有效避免最速下降法越接近目标值，前进越慢的缺点，也能够保证无论最开始选的初始解为多少，最后的收敛速率都比较稳定。最后，本文通过测试函数，验证了组合最优化方法相比于最速下降法、Hooke-Jeeves方法有着更好的收敛效率。

参考文献

[1] 孙文瑜，袁亚湘.最优化理论与方法[M].北京：科学出版社，1997：79.

[2] 经红霞.无约束最优化问题的算法研究与实现[D].北京：北京邮电大学，2013.

[3] 梁昔明，赵旭芳.基于最速下降法改进的人工蜂群算法[J].北京建筑大学学报，2018，34（3）：49-56，62.

[4] 于海艳，杜晓燕，卫佩佩.粒子群算法结合最速下降法的混合算法[J].信息工程大学学报，2018，19（1）：39-41，56.

[5] 李文，梁昔明.基于混沌优化和最速下降法的一种混合算法[J].计算技术与自动化，2003（2）：12-14.

[6] 简金宝，罗雁，徐庆娟.Hooke-Jeeves方法在简单约束优化中的推广[J].广西科学，2005（2）：81-84.

[7] W. R. Klingman，D. M. Himmelblau. Nonlinear Programming with the Aid of a Multiple-Gradient Summation Technique[M]. ACM，1964：51.

[8] Glass H，Cooper L . Sequential Search：A Method for Solving Constrained Optimization Problems[J]. Journal of the Acm，1965，12（1）：71-82.

[9] 李廷锋.基于最速下降法的平面选址问题应用研究[J].科技资讯，2011（36）：14，16.

[10] Hooke R，Jeeves T A .Direct SearchSolution of Numerical and Statistical Problems[J]. Journal of the ACM，1961，8（2）：212-229.