最速下降法原理及其算法实现

1、 本科毕业论文（设计）模板本科毕业论文（设计）模板 课程论文课程论文论文题目：论文题目：最速下降法原理及其算法实现最速下降法原理及其算法实现 课程名称：课程名称： 现代信号处理新方法现代信号处理新方法 学学 院：院： 自动化学院自动化学院 专业班级：专业班级： 控制科学与工程控制科学与工程 1 1 班班 学学 号：号： 21113040922111304092 姓姓 名：名： 严春景严春景 任课教师：任课教师： 谢胜利谢胜利 20142014 年年 6 6 月月 2020 日日 最速下降法原理及其算法实现内 容 摘 要摘要：基于最速下降法在解决无约束非线性规划问题中的重要性，对其原理与算法予以

2、讨论。论文主要是参阅大量数学分析和运筹学书籍以及一些学术资料，结合自己在平时学习中掌握的知识，并在指导老师的建议下，针对最速下降法的基本思路和原理进行研究。关键词：运筹学 最速下降法 无约束 梯度法 最优解The steepest descent method, principle and its algorithmAbstractBased on the steepest descent method in solving unconstrained nonlinear programming problem, the importance of the principle and the

3、algorithm is discussed. Paper mainly refer to a mathematical analysis and operations research books and some academic material, usually in the study of knowledge and mastery in teachers suggestion, the steepest descent method according to the basic ideas and principles were studied.Key words：operati

4、onal research steepest descent method Unconstrained gradient method optimal solution序言最速下降法又称为梯度法，是 1847 年由著名数学家 Cauchy 给出的，它是解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。作为一种基本的算法，他在最优化方法中占有重要地位。其优点是工作量少，存储变量较少，初始点要求不高；缺点是收敛慢，效率不高，有时达不到最优解。非线性规划研究的对象是非线性函数的数值最优化问题。它的理论和方法渗透到许多方面，特别是在军事、经济、管理、生产

5、过程自动化、工程设计和产品优化设计等方面都有着重要的应用。而最速下降法正是元函数的无约束非线性规划问题的一种重要解析法，研究最速下降法nmin( )f x原理及其算法实现对我们有着极其重要的意义。一、最速下降法基本原理(一)无约束问题的最优性条件无约束问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据，为此我们有以下几个定理。定理 1 设在点处可微。若存在，使f:1nRRnxRnpR( )0Tf xp则向量是在点处的下降方向。pfx定理 2 设在点处可微。若是无约束问题的局部最优解，则1:nfRRnxRx()0f x由数学分析中我们已经知道，使的点为函数的驻点或平稳点。函数的一个(

6、)0f xxff驻点可以是极小点；也可以是极大点；甚至也可能既不是极小点也不是极大点，此时称它为函数的鞍点。以上定理告诉我们，是无约束问题的的局部最优解的必要条件是：是其目标函数fxx的驻点。f现给出无约束问题局部最优解的充分条件。定理 3 设在点处的 Hesse 矩阵存在。若1:nfRRnxR2()f x，并且正定()0f x2()f x则是无约束问题的严格局部最优解。x一般而言，无约束问题的目标函数的驻点不一定是无约束问题的最优解。但对于其目标函数是凸函数的无约束凸规划，下面定理证明了，它的目标函数的驻点就是它的整体最优解。定理 4 设，是上的可微凸函数。若有1:nfRRnxRfnR()0

7、f x则是无约束问题的整体最优解。x(二)最速下降法的基本思想和迭代步骤最速下降法又称为梯度法，是 1847 年由著名数学家 Cauchy 给出的。他是解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。设无约束问题中的目标函数一阶连续可微。1:nfRR最速下降法的基本思想是：从当前点出发，取函数在点处下降最快的方向作为我kx( )f xkx们的搜索方向.由的 Taylor 展式知kp( )f x()()()(kkkkTkkf xf xtpt f xpotp )略去 的高阶无穷小项不计，可见取时，函数值下降得最多。于是，我们可以构造tkp ()kf

8、 x出最速下降法的迭代步骤。解无约束问题的的最速下降法计算步骤第 1 步 选取初始点，给定终止误差，令；0 x0: 0k 第 2 步 计算，若，停止迭代.输出.否则进行第三步；()kf x(kf x)kx第 3 步 取；()kkpf x 第 4 步 进行一维搜索，求，使得kt0()min()kkkkktf xt pf xtp令，转第 2 步。1kkkkxxt p:1kk由以上计算步骤可知，最速下降法迭代终止时，求得的是目标函数驻点的一个近似点。确定最优步长的方法如下：kt方法一：采用任一种一维寻优法此时的已成为步长 的一元函数，故可用任何一种一维寻优法求出，即()kkf xt f x tkt1

9、()()min()kkkkkktf xf xtf xf xt f x 方法二：微分法因为()( )kktf xt f xt 所以，一些简单情况下，可令( )0t以解出近似最优步长的值。kt(三)最速下降法应用举例例 1 给定初始点22121122min( )22f xxxxx xx 1(0,0)TX解：目标函数的梯度( )f x112122( )()142( )122( )()f xxxxf xxxf xx 令搜索方向再从出发，沿方向作一维寻优，(1)1()1f X(1)(1)1()1df X (1)X(1)d令步长变量为，最优步长为，则有1(1)(1)0101Xd 故(1)(1)2221(

10、)()()2()2()2( )f xf Xd 令可得 求出点之后，与1( )220 11(2)(1)(1)1011011XXd (2)X上类似地，进行第二次迭代： 令(2)1()1f X(2)(2)1()1df X 令步长变量为，最优步长为，则有2(2)(2)111111Xd 故(2)(2)2222( )()(1)(1)2(1)2(1)(1)(1)521( )f xf Xd 令可得 2( )1020 215(3)(2)(2)2110.81111.25XXd 此时所达到的精度(3)0.2()0.2f X(3)()0.2828f X本题最优解，11.5X()1,25f X 例 2 用最速下降法求解

11、无约束非线性规划问题：42112min()(2)(2)f Xxxx其中，要求选取初始点，终止误差.12( ,)TXx x0(0,3)TX0.1解：因 311212()4(2)2(2), 4(2)Tf Xxxxxx则 0()( 44,24)Tf X 0()50.12f X00()(44, 24)Tpf X 求单变量极小化问题：0000min()min(44 ,324 )ttf xtpftt420min(442)(926)ttt的最优解，由 0.618 法可得，于是0t00.06t 1000(2.70,1.51)TXxt p1()(0.73,1.28)Tf X1()1.47f X令 11()pf

12、X 再求单变量极小化问题110min()tf Xtp的最优解.略去计算步骤，由表 1-1 给出计算结果.由表 1-1 可以知道，所7()0.09f X以为近似最优解，原问题的近似最优值为.7(2.28,1.15)TX0.007表 1-1迭代次数kkX()kf X()kf X()kf Xkt1kX0(0.00,3.00)T52.00( 44,24)T50.120.06(2.70,1.51)T1(2.70,1.51)T0.34(0.73,1.28)T1.470.24(2.52,1.20)T2(2.52,1.20)T0.09(0.80, 0.48)T0.930.11(2.43,1.25)T3(2.4

13、3,1.25)T0.04(0.18,0.28)T0.330.31(2.37,1.16)T4(2.37,1.16)T0.02(0.30, 0.20)T0.360.12(2.33,1.18)T5(2.33,1.18)T0.01(0.08,0.12)T0.140.36(2.30,1.14)T6(2.30,1.14)T0.009(0.15, 0.08)T0.170.13(2.28,1.15)T7(2.28,1.15)T0.007(0.05,0.08)T0.09例 3用最速下降法求解无约束问题 221212131min( )222f xxxx xx取，。 1(0,0)TX210解：计算目标函数的梯度和

14、Hesse 阵，12121232()xxgf Xxxg231()11f XG设，得到精确一维搜索步长( )12,Tkdd d( )12(),Tkf Xg g112222121232kg dg dddd d取，则，所以， 1(0,0)TX(1)()2,0Tf X (1)(1)()2,0Tdf X 212213 23因此 (2)(1)(1)1120,02,0,033TTTXXd再计算第二轮循环，表 1-2 列出了各次迭代的计算结果。共计算了 9 个点，(9)()0.025f X，停止计算，所以作为问题的最优解。210(9)0.988,0.988TX表 1-2k( )kX( )()kf X( )()

15、kf X( )kdk1(0.000,0.000)0.000( 2.000,0.000)(2.000,0.000)0.3332(0.667,0.000)0.667(0.000, 0.667)(0.000,0.667)1.0003(0.667,0.667)0.889( 0.667,0.000)(0.667,0.000)0.3334(0.889,0.667)0.963(0.000, 0.222)(0.000,0.222)1.0005(0.889,0.889)0.988( 0.222,0.000)(0.222,0.000)0.3336(0.963,0.889)0.996(0.000, 0.074)(0

16、.000,0.074)1.0007(0.963,0.963)0.999( 0.074,0.000)(0.074,0.000)0.3338(0.988,0.963)1.000(0.000, 0.025)(0.000,0.025)1.0009(0.988,0.988)1.000( 0.025,0.000)(四)最速下降法的缺点由于沿负梯度方向目标函数的最速下降性，很容易使人们误认为负梯度方向是最理想的搜索方向，最速下降法是一种理想的极小化方法。必须指出的是，某点的负梯度方向，通常只是在该店附近才具有这种最速下降的性质。在一般情况下，当用最速下降法寻找极小点时，其搜索路径呈直角锯齿状（图 1-3）

17、，在开头几步，目标函数下降较快；但在接近极小点时，收敛速度长久不理想了。特别适当目标函数的等值线为比较扁平的椭圆时，收敛就更慢了。(4)xO(2)x(3)x图 1-3因此，在实用中常将最速下降法和其他方法联合应用，在前期使用最速下降法，而在接近极小点时，可改用收敛较快的其他方法。二、最速下降法算法实现(一)最速下降法程序流程图最速下降法的程序流程图，如图 1-4 所示开始给定初始点，0nxE0: 0k 计算()kkpf x kp求使其满足k0min()()kkkkkf xpf xp令1kkkkxxp输出：minkxx结束是图 1-4(二)最速下降法程序清单 用 C 语言编写的最速下降法的程序清

18、单如下。其中 R 是梯度模，P 是梯度方向的的单位向量，h 是步长，f 是目标函数。#include “math.h”#include “stdio.h”float x10,y10,p10,f,h;int n;vod fun( )int i;for(i=1,in;i+) xi=yi-h*pi;f=x1*x1+x2*x2-x1*x2-10*x1-4*x2;f=f+60;return;main( )float g10,d10,q,r,e,h1,h2,h3,h4,t,t0,c1,c2,f1,f2,f3,f4,f5,v;int i,k,u;printf(“input n,en”)；scanf(“%d,

19、%f”,&n,&e);x1=0;x2=0;p4: g1=2*x1-x2-10;g2=2*x2-x1-4;q=0;for(i=1;in;i+) q=gi*gi+q;r=sqrt(q);for(i=1;in;i+) yi=xi;pi=gi/r;if(rf2) t=t+t;u=u+1;elset=-t;h3=h1;f3=f1;h1=h2;f1=f2;h2=h3;f2=f3;p1: h3=h2+t; h=h3;fun( ) f3=f;if(f2f3) t=t+t;u=u+1;h1=h2;f1=f2;h2=h3;f2=f3;goto pl; elseif(u0)h4=0.5*(h2+h3

20、);h=h4;fun( );f4=f;if(f4f2) h3=h4;f3=f4;elseh1=h2;f1=f2;h2=h4;f2=f4;c1=（f3-f1）/(h3-h1);c2=(f2-f1)/(h2-h1)-c1)/(h2-h3);if(fabs(c2)e) h1=h2;f1=f2;t0=v*t0;goto p2;elseh4=0.5*(h1+h3-(c1/c2);h=h4;fun( );f4=f;if(f21) f5=1;else f5=f2;if(fabs(f4-f2)/f5)e)for(i=1;if2) h1=h2;f1=f2;else h1=h4;f1=f4;t0=v*t0;goto p2; p3:h0;fun( );printf(“OBJ.FUNC F=%fn”,