发布时间 : 星期一 文章最优化Armijo算法确定步长的最速下降法更新完毕开始阅读b826a02cce1755270722192e453610661fd95a53
对于二次函数,由于?f(x)?Qx?q且在x*处 ?f(x*)?Qx*?q?0则 f(x)-f(x*)?112(x-x*)TQ(x-x*)?||x-x*||Q22所以(3.2)可以改写成??-1?* f(xk?1)-f(x)???[f(xk)-f(x)]???1?*2由收敛速度估计式(3.2)看到,最速下降的收敛速度与矩阵Q的条件数?有关,当?接近于1,最速下降收敛很快, 特别, 当??1即Q的所有特征值相等时,算法只需一次迭代即可求出最优解. 而当?较大时(Q接近病态）,算法收敛很慢. 结论：最速下降法的收敛速度比较慢，通常将其用在某些算法的初始阶段求较好的初始点或作为某些算法的间插步. 【实验环境】 Win 7； Matlab7.0 二、实验内容： 【实验方案】 1、求梯度； 2、向梯度相反的方向移动x，其中 为步长。如果步长足够小，则可以保证每一次迭代都在减小，但可能导致收敛太慢，如果步长太大，则不能保证每一次迭代都减少，也不能保证收敛。 3、循环迭代步骤2，直到x的值变化到使得0.00000001，也就是说，直到两次迭代计算出来的达到局部最小值了。 4、此时，输出x，这个x就是使得函数最小时的x的取值 。 在两次迭代之间的差值足够小，比如基本没有变化，则说明此时已经 4
【实验过程】 梯度下降法的计算过程就是沿梯度下降的方向求解极小值（也可以沿梯度上升方向求解极大值）。 其迭代公式为 ,其中 代表梯度负方向， 表示梯度方向上的搜索步长。梯度方向我们可以通过对函数求导得到，步长的确定比较麻烦，太大了的话可能会发散，太小收敛速度又太慢。一般确定步长的方法是由线性搜索算法来确定，即把下一个点的坐标ak+1看做是的函数，然后求满足f(ak+1)的最小值的 即可。 因为一般情况下，梯度向量为0的话说明是到了一个极值点，此时梯度的幅值也为0.而采用梯度下降算法进行最优化求解时，算法迭代的终止条件是梯度向量的幅值接近0即可，可以设置个非常小的常数阈值。 【实验结论】（结果） 梯度下降法处理一些复杂的非线性函数会出现问题，例如Rosenbrock函数： 其最小值在 处，函数值为 。但是此函数具有狭窄弯曲的山谷，最小点 就在这些山谷之中，并且谷底很平。优化过程是之字形的向极小值点靠近，速度非常缓慢。靠近极小值时收敛速度减慢。直线搜索时可能会产生一些问题。可能会“之字形”地下降。 【实验小结】（收获体会） 这次的实验报告，使得我们对这些算法的思想更加了解，在选择线性搜索的方法时，我们深刻体会到各类参数设置对程序效率的重要性，不同的问题要选用合适的参数来求解，这样使得问题求解及程序运行的效率最高。通过不断地翻阅课本，剖析程序，我们最后实现了对程序
5
的修改和完善，对提供的问题作出了较好的解答。总的来说，对无约束最优化的求解，每种方法在解决不同的问题中效果不能都达到最优，所以我们在实际应用中，要根据实际情况选择合适的方法，争取最大可能的尽快的接近最优。 本次实验不仅使我们基本了解了最优化的实用算法的结构及性能，而且也使得我们对matlab的一些编程技巧更加熟悉，收获很大。 三、指导教师评语及成绩： 评语等级 评 语 优 良 中 格 1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强 2.实验方案设计合理 3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻） 4实验结论正确. 及不及格 成 绩： 指导教师签名： 批阅日期： 附录1：源 程 序
Armijo算法实现： [plain] view plaincopy function mk = armijo( fun, xk, rho, sigma, gk ) 6
assert( rho > 0 && rho < 1 ); assert( sigma > 0 && sigma < 0.5 ); mk = 0; max_mk = 100; while mk <= max_mk x = xk - rho^mk * gk; if feval( fun, x ) <= feval( fun, xk ) - sigma * rho^mk * norm( gk )^2 break; end mk = mk + 1; end return; 最速下降法实现： [plain] view plaincopy function [opt_x, opt_f, k] = grad_descent( fun_obj, fun_grad, x0 ) max_iter = 5000; % max number of iterations EPS = 1e-5; % threshold of gradient norm 7