《最速下降法原理及其算法实现》由会员分享，可在线阅读，更多相关《最速下降法原理及其算法实现（16页珍藏版）》请在金锄头文库上搜索。
1、 本科毕业论文（设计)模板 课程论文论文题目：最速下降法原理及其算法实现 课程名称: 现代信号解决新措施 学 院: 自动化学院 专业班级: 控制科学与工程班 学 号： 姓 名: 严春景 任课教师: 谢胜利 6月2日 最速下降法原理及其算法实现内 容 摘 要摘要：基于最速下降法在解决无约束非线性规划问题中的重要性，对其原理与算法予以讨论。论文重要是参阅大量数学分析和运筹学书籍以及某些学术资料，结合自己在平时学习中掌握的知识,并在指引教师的建议下,针对最速下降法的基本思路和原理进行研究。核心词:运筹学 最速下降法 无约束 梯度法 最优解The stepst dscentmthod,prncplea
2、n islgorihmAbstrcBase nhesepest esce methodn solvng unonsraied onlear roramng problm, the ipornc ofhe prnple n h algorithm isice. Papermainy refr to amahatcal analis and opratios reserh os nd some academicmatera,uuallinte stud of knowede and mastery inteahs sugston， hesteepest deentmhod aording the
3、ac ide dpricipleswertudied.Key words:oeratial rsearch steeest esceethod Unonsained raint method ptial solution前言最速下降法又称为梯度法,是87年由出名数学家Cuchy给出的,它是解析法中最古老的一种,其她解析措施或是它的变形,或是受它的启发而得到的，因此它是最优化措施的基本。作为一种基本的算法,她在最优化措施中占有重要地位。其长处是工作量少,存储变量较少,初始点规定不高；缺陷是收敛慢，效率不高，有时达不到最优解。非线性规划研究的对象是非线性函数的数值最优化问题。它的理论和措施渗入到许
4、多方面，特别是在军事、经济、管理、生产过程自动化、工程设计和产品优化设计等方面均有着重要的应用。而最速下降法正是元函数的无约束非线性规划问题的一种重要解析法，研究最速下降法原理及其算法实现对我们有着极其重要的意义。一、最速下降法基本原理(一)无约束问题的最优性条件无约束问题的最优解所要满足的必要条件和充足条件是我们设计算法的根据,为此我们有如下几种定理。定理 设在点处可微。若存在,使则向量是在点处的下降方向。定理 设在点处可微。若是无约束问题的局部最优解，则由数学分析中我们已经懂得，使的点为函数的驻点或平稳点。函数的一种驻点可以是极小点;也可以是极大点;甚至也也许既不是极小点也不是极大点,此时
5、称它为函数的鞍点。以上定理告诉我们，是无约束问题的的局部最优解的必要条件是:是其目的函数的驻点。现给出无约束问题局部最优解的充足条件。定理 设在点处的Hesse矩阵存在。若，并且正定则是无约束问题的严格局部最优解。一般而言，无约束问题的目的函数的驻点不一定是无约束问题的最优解。但对于其目的函数是凸函数的无约束凸规划,下面定理证明了,它的目的函数的驻点就是它的整体最优解。定理4 设，是上的可微凸函数。若有则是无约束问题的整体最优解。(二)最速下降法的基本思想和迭代环节最速下降法又称为梯度法，是147年由出名数学家Cucy给出的。她是解析法中最古老的一种,其她解析措施或是它的变形，或是受它的启发而
6、得到的，因此它是最优化措施的基本。设无约束问题中的目的函数一阶持续可微。最速下降法的基本思想是：从目前点出发,取函数在点处下降最快的方向作为我们的搜索方向.由的Talr展式知略去的高阶无穷小项不计，可见取时，函数值下降得最多。于是，我们可以构造出最速下降法的迭代环节。解无约束问题的的最速下降法计算环节第步 选用初始点,给定终结误差，令；第2步 计算，若，停止迭代.输出.否则进行第三步;第步 取；第4步 进行一维搜索,求,使得令,，转第步。由以上计算环节可知,最速下降法迭代终结时,求得的是目的函数驻点的一种近似点。拟定最优步长的措施如下:措施一：采用任一种一维寻优法此时的已成为步长的一元函数,故
7、可用任何一种一维寻优法求出,即措施二：微分法由于因此,某些简朴状况下,可令以解出近似最优步长的值。(三)最速下降法应用举例例1 给定初始点解:目的函数的梯度令搜索方向再从出发，沿方向作一维寻优，令步长变量为，最优步长为，则有故令可得 求出点之后，与上类似地,进行第二次迭代: 令令步长变量为,最优步长为,则有故令可得 此时所达到的精度本题最优解,例2用最速下降法求解无约束非线性规划问题:其中，规定选用初始点，终结误差解:因 则 求单变量极小化问题：的最优解，由08法可得,于是令 再求单变量极小化问题的最优解略去计算环节，由表-1给出计算成果.由表-可以懂得，因此为近似最优解，原问题的近似最优值为
8、.表1-1迭代次数例3 用最速下降法求解无约束问题 取，。解：计算目的函数的梯度和Hese阵,设,得到精确一维搜索步长取,则，因此,因此 再计算第二轮循环，表1-列出了各次迭代的计算成果。合计算了9个点，停止计算，因此作为问题的最优解。表1(四)最速下降法的缺陷由于沿负梯度方向目的函数的最速下降性,很容易使人们误觉得负梯度方向是最抱负的搜索方向,最速下降法是一种抱负的极小化措施。必须指出的是,某点的负梯度方向,一般只是在该店附近才具有这种最速下降的性质。在一般状况下，当用最速下降法寻找极小点时,其搜索途径呈直角锯齿状(图1-)，在开头几步,目的函数下降较快；但在接近极小点时,收敛速度长期不抱负
9、了。特别合适目的函数的等值线为比较扁平的椭圆时,收敛就更慢了。图1-因此，在实用中常将最速下降法和其她措施联合应用,在前期使用最速下降法，而在接近极小点时，可改用收敛较快的其她措施。二、最速下降法算法实现(一）最速下降法程序流程图最速下降法的程序流程图,如图1-4所示开始给定初始点，计算是求使其满足令输出：结束图-4（二）最速下降法程序清单用C语言编写的最速下降法的程序清单如下。其中R是梯度模,P是梯度方向的的单位向量,h是步长,f是目的函数。#clde “mat.”#ince “stdi.”flotx0,y0,p10,f,;n n;vofu（ ）in i;for(1,in;+） x=yii;
10、=x*x+2x2-1*20*1-4*2；f=f+60;rern;min（ )flot g0，d0,r,e,1,2，3,h4,，t0,c1,c2,f1,f2，f3,f4,f,v;int i,k,u;rinf（“inputn,en”)；canf(“%d,%f”,&n,&e);1=;x2=；: g1=2*x1x10；g2=2x-1-4;q=0;for(=1;n；i+) qgi+q；sqrt(q);r(i=1；f3) tt+t;uu+1；h1=h2;1=f2；h2=h3;f2=3;oto l； esi()h4=.（h2+h3);h=h4;un（ ）;4=;if(f4f2)3=4;f3=f4;elseh1=h2；f1=2;h2h4；f=f4;c1=（f-f)/(h-h);c2=(f2-f1)(h2-h1)-c1)/(h2h)；if(abs(2)e) h1=2;1=f;0=v*t;goto p;elseh40.5*（+3-(c1/c2）)；=h4;fun（ )；4=f;if（f21) f1;el f5f2；(（fa(f42）/f5)for(i=；in;i+) iyi-hi；go p4;eli(4f2) h1h2;f1=2;lse 1h4；f=f；0
