matlab线性搜索确定步长,使用非精最速下降法确线搜索armijo算法确定步长的.doc...

使用非精最速下降法确线搜索armijo算法确定步长的.doc

数学与计算科学学院实验报告实验项目名称使用非精确线搜索ARMIJO算法确定步长的最速下降法所属课程名称最优化方法实验类型算法编程实验日期20班级信学号姓名成绩1一、实验概述【实验目的】1通过实验掌握最速下降法的MATLAB算法的基本步骤；2通过实验掌握ARMIJO算法确定步长；3掌握最速下降法的思想及迭代步骤。【实验原理】1最速下降法最古老的优化方法，十九世纪中叶由CAUCHY提出思想每次沿负梯度方向进行搜索负梯度方向也称为最速下降方向举例算法步骤KX●KXFX●等值线面●1PXFXFPFXPFPXFPFPRTKPKKKKTKNMIN||||||||SCHWARZCAUY,||的解是下列问题时等号成立，即当取不等式得由且事实上，对任意22,1,433,,||20,1K1K0转步令步由线性搜索计算步长步；然后转步计算否则算法终止，则得解若步令精度给定初始点步DXFXXKRKKKN优点,最优解以较慢的速度无限接近但能优解代并没有求出其精确最最速下降法在有限次迭数极小化问题，对于简单的二元二次函最速下降法的收敛性全局收敛性,|||,0,降算法的全局收敛性我们很容易得到最速下所以且即方向与负梯度方向一致由于最速下降法的搜索KKKDXF0||LIM}{POWELWLFARIJO,KKKXFX满足代序列的迭搜索的最速下降法产生搜索或或采用精确搜索,,至多是线性的最速下降法的收敛速度由例子看到收敛速度估计211MINAXIN|,32||||}{21I,QXXXQXFQRQQTKQKKTN是问题的惟一解其中)(满足速下降法产生的点列则由采用精确搜索的最问题化考察如下二次函数极小的最大和最小特征值分别是和记对称正定设矩阵3123||2110,212TXFXFFXQFXQFKKQ可以改写成所以则处且在由于对于二次函数,,1,,,3算法收敛很慢接近病态)较大时而当求出最优解算法只需一次迭代即可的所有特征值相等时即当特别最速下降收敛很快接近于当有关的条件数矩阵最速下降的收敛速度与看到由收敛速度估计式QQ结论最速下降法的收敛速度比较慢，通常将其用在某些算法的初始阶段求较好的初始点或作为某些算法的间插步【实验环境】WIN7；MATLAB70二、实验内容【实验方案】1、求梯度；2、向梯度相反的方向移动X，其中为步长。如果步长足够小，则可以保证每一次迭代都在减小，但可能导致收敛太慢，如果步长太大，则不能保证每一次迭代都减少，也不能保证收敛。3、循环迭代步骤2，直到X的值变化到使得在两次迭代之间的差值足够小，比如000000001，也就是说，直到两次迭代计算出来的基本没有变化，则说明此时已经达到局部最小值了。4、此时，输出X，这个X就是使得函数最小时的X的取值。【实验过程】梯度下降法的计算过程就是沿梯度下降的方向求解极小值(也可以沿梯度上升方向求解极大值)。其迭代公式为,其中代表梯度负方向，表示梯度方向上的搜索步长。梯度方向我们可以通过对函数求导得到，步长的确定比较麻烦，太大了的话可能会发散，太小收敛速度又太慢。一般确定步长的方法是由线性搜索算法来确定，即把下一个点的坐标AK1看做是的函数，然后求满足FAK1的最小值的即可。因为一般情况下，梯度向量为0的话说明是到了一个极值点，此时梯度的幅值也为0而采用梯度下降算法进行最优化求解时，算法迭代的终止条件是梯度向量的幅值接近0即可，4可以设置个非常小的常数阈值。【实验结论】(结果)梯度下降法处理一些复杂的非线性函数会出现问题，例如ROSENBROCK函数其最小值在处，函数值为。但是此函数具有狭窄弯曲的山谷，最小点就在这些山谷之中，并且谷底很平。优化过程是之字形的向极小值点靠近，速度非常缓慢。靠近极小值时收敛速度减慢。直线搜索时可能会产生一些问题。可能会“之字形”地下降。【实验小结】(收获体会)这次的实验报告，使得我们对这些算法的思想更加了解，在选择线性搜索的方法时，我们深刻体会到各类参数设置对程序效率的重要性，不同的问题要选用合适的参数来求解，这样使得问题求解及程序运行的效率最高。通过不断地翻阅课本，剖析程序，我们最后实现了对程序的修改和完善，对提供的问题作出了较好的解答。总的来说，对无约束最优化的求解，每种方法在解决不同的问题中效果不能都达到最优，所以我们在实际应用中，要根据实际情况选择合适的方法，争取最大可能的尽快的接近最优。本次实验不仅使我们基本了解了最优化的实用算法的结构及性能，而且也使得我们对MATLAB的一些编程技巧更加熟悉，收获很大。三、指导教师评语及成绩评语等级评语优良中及格不及格1实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2实验方案设计合理3实验过程(实验步骤详细,记录完整,数据合理,分析透彻)54实验结论正确成绩指导教师签名批阅日期附录1源程序ARMIJO算法实现PLAINVIEWPLAINCOPYFUNCTIONMKARMIJOFUN,XK,RHO,SIGMA,GKASSERTRHO0MK0MAX_MK100WHILEMKMAX_MKXXKRHOMKGKIFFFUN,XFFUN,XKSIGMARHOMKNORMGK2BREAKENDMKMK1ENDRETURN最速下降法实现PLAINVIEWPLAINCOPYFUNCTIONOPT_X,OPT_F,KGRAD_DESCENTFUN_OBJ,FUN_GRAD,X0MAX_ITER5000MAXNUMBEROFITERATIONSEPS1E5THRESHOLDOFGRADIENTNORMARMIJOPARAMETERSRHO05SIGMA02INITIALIZATIONK0XKX0WHILEKMAX_ITERKK16GKFFUN_GRAD,XKGRADIENTVECTORDK1GKSEARCHDIRECTIONIFNORMDKEPSBREAKENDYKFFUN_OBJ,XKFPRINTF ITER5D,XK5F,F5FN ,K,XK,YKMKARMIJOFUN_OBJ,XK,RHO,SIGMA,GKXKXKRHOMKDKENDFPRINTF N IFKMAX_ITERFPRINTF PROBLEMNOTSOLVEDN ELSEFPRINTF PROBLEMSOLVEDN ENDRECORDRESULTSOPT_XXKOPT_FFFUN_OBJ,XKRETURN附录2实验报告填写说明1．实验项目名称要求与实验教学大纲一致。2．实验目的目的要明确，要抓住重点，符合实验教学大纲要求。3．实验原理简要说明本实验项目所涉及的理论知识。4．实验环境实验用的软、硬件环境。5．实验方案(思路、步骤和方法等)这是实验报告极其重要的内容。概括整个实验过程。7对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设计思路和设计方法，再配以相应的文字说明。对于创新性实验，还应注明其创新点、特色。6．实验过程(实验中涉及的记录、数据、分析)写明具体实验方案的