最优化Armijo算法确定步长的最速下降法

1、沙理工数学与计算科学学院实验报告实验项目名称使用非精确线搜索 Armjo 算法确定步长的最速下降法所属课程名称最优化方法实验类型算法编程实验日期班 级学 号姓 名成 绩、实验概述:【实验目的】1. 通过实验掌握最速下降法的Matlab算法的基本步骤;2. 通过实验掌握Armijo算法确定步长；3. 掌握最速下降法的思想及迭代步骤。等值线（面）事实上，对任意p Rn且|p |,由Cauchy - Schwarz不等式得 负梯度方向也称为最速下降方向m汗 举当取p厂臂时等号成立，即p的解-| f(Xk)|-f(Xk)是下列问题| f(Xk)|min|p|f(Xk)TP算法步骤：步1给定初始点X。R

2、n,精度0.令k 0;步2若| f(xk)| ，则得解xk,算法终止.否则 计算dk - f (xk),然后转步3；步3由线性搜索计算步长k;步4 令xk 1 xkkdk,k : k 1,转步 2.优点：对于简单的二元二次函 数极小化问题， 最速下降法在有限次迭 代并没有求出其精确最 优解,但能 以较慢的速度无限接近 最优解.最速下降法的收敛性：全局收敛性：由于最速下降法的搜索 方向与负梯度方向一致，即k 0,且II f(xQ| |dk|所以，我们很容易得到最速下 降算法的全局收敛性.的迭采用精确搜索，或Armijo搜索或Wolfe - Powell搜索的最速下降法产生 代序列Xk满足kim

3、| f(Xk)| 0由例子看到，最速下降法的收敛速度至多是线性的，收敛速度估计:设矩阵Q对称正定,q Rn.记max和min分别是Q的最大和最小特征值, maX .考察如下二次函数极小化min 问题：min f(x) 1xTQx qTx2则由米用精确搜索的最 速下降法产生的点列xk满足* 1 *|Xk 1 - X |q, |Xk-x |q(3.2)11 其中x*是问题的惟一解,| x |Q xTQx 2对于二次函数，由于f(x) Qx q且在x*处f (x*) Qx* q 0*1* t*1*2则 f(x)- f(x )2(x-x ) Q(x-x )2|x-x |q所以(3.2)可以改写成2I

4、f(xk 1)- f (x )- f (xk)- f (x )1由收敛速度估计式(3.2)看到,最速下降的收敛速度与 矩阵 Q的条件数 有关，当 接近于1,最速下降收敛很快，特别， 当1即Q的所有特征值相等时，算法只需一次迭代即可求出最优解.而当 较大时(Q接近病态)，算法收敛很慢.结论：最速下降法的收敛速度比较慢，通常将其用在某些算法的初 始阶段求较好的初始点或作为某些算法的间插步.【实验环境】Win7 ；二、实验内容:【实验方案】1、求梯度；2、 向梯度相反的方向移动 x,其中吃|为步长。如果步长足够小，则可以保证每一次迭代都在 减小，但可能导致收敛太慢，如果步长太大，则不能保证每一次迭代

5、都减少，也不能保证收敛。3、 循环迭代步骤 2,直到x的值变化到使得！ 在两次迭代之间的差值足够小，比如，也就 是说，直到两次迭代计算出来的 F2喘基本没有变化，则说明此时 T 诃已经达到局部最小值了。4、 此时，输出x，这个x就是使得函数最小时的x的取值。【实验过程】梯度下降法的计算过程就是沿梯度下降的方向求解极小值（也可以沿梯度上升方向求解极大值）。其迭代公式为 蘇+1=聽+ P话朗,其中副町代表梯度负方向，卩上表示梯度方向上的搜索步长。梯度方向我们可以通过对函数求导得到，步长的确定比较麻烦，太大了的话可能会 发散，太小收敛速度又太慢。一般确定步长的方法是由线性搜索算法来确定，即把下一个点

6、的 坐标ak+1看做是的函数，然后求满足 f（ak+1）的最小值的 即可。因为一般情况下，梯度向量为0的话说明是到了一个极值点， 此时梯度的幅值也为 0.而采用梯度下降算法进行最优化求解时，算法迭代的终止条件是梯度向量的幅值接近0即可，可以设置个非常小的常数阈值。【实验结论】（结果）梯度下降法处理一些复杂的非线性函数会出现问题，例如Rosenbrock函数：其最小值在 （耳丁）二（lH处，函数值为f （xty = 0。但是此函数具有狭窄弯曲的山谷，最小点 就在这些山谷之中，并且谷底很平。优化过程是之字形的向极小值点靠近，速度非常 缓慢。靠近极小值时收敛速度减慢。直线搜索时可能会产生一些问题。可

7、能会“之字形”地下 降。【实验小结】（收获体会）这次的实验报告，使得我们对这些算法的思想更加了解，在选择线性搜索的方法时，我们 深刻体会到各类参数设置对程序效率的重要性，不冋的问题要选用合适的参数来求解，这样使 得问题求解及程序运行的效率最高。通过不断地翻阅课本，剖析程序，我们最后实现了对程序 的修改和完善，对提供的问题作出了较好的解答。总的来说，对无约束最优化的求解，每种方 法在解决不同的问题中效果不能都达到最优，所以我们在实际应用中，要根据实际情况选择合 适的方法，争取最大可能的尽快的接近最优。本次实验不仅使我们基本了解了最优化的实用算法的结构及性能，而且也使得我们对 matlab的一些编

8、程技巧更加熟悉，收获很大。三、指导教师评语及成绩：评语评语等级优良中及格不及格1.实验报告按时完成，字迹清楚，文字叙述流畅，逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细，记录完整，数据合理，分析透彻）4实验结论正确.成绩：指导教师签名：批阅日期：附录1源程序Armijo算法实现：pla in view pla in copyfun cti on mk = armijo( fun, xk, rho, sigma, gk )assert( rho 0 & rho 0 & sigma );mk = 0; max_mk = 100;while mk = max_mkx = xk - rhoA

9、mk * gk;if feval( fun, x ) = feval( fun, xk ) - sigma * rhoAmk * norm( gk )八2 break;endmk = mk + 1;endreturn;最速下降法实现：pla in view pla in copyfun cti on opt_x, opt_f, k = grad_desce nt( fun_obj, fun _grad, x0 )max_iter = 5000;% max nu mber of iterati onsEPS = 1e-5;% threshold of gradie nt n orm% Armij

10、o parametersrho = ; sigma =;% in itializatio nk = 0; xk = xO;while k max_iterk = k + 1;gk = feval( fun _grad, xk ); % gradie nt vectordk = -1 * gk;% search direct ionif norm( dk ) EPSbreak;endyk = feval( fun_obj, xk );fprintf( #iter = %5d, xk = %.5f, F = %.5fn, k, xk, yk );mk = armijo( fun_obj, xk,

11、rho, sigma, gk );xk = xk + rhoAmk * dk;endfprintf( n);if k = max_iterfprintf( P roblem Not solved!n);elsefpri ntf( Problem solved! n);end% record resultsopt_x = xk;opt_f = feval( fun _obj, xk );return;附录2:实验报告填写说明1实验项目名称： 要求与实验教学大纲一致。2 实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。3 实验原理：简要说明本实验项目所涉及的理论知识。4.实验环境：实验用的软、硬件环境。5实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程。对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步 骤来实现其操作。对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设 计思路和设计方法，再