最速下降法原理及例题实例

最速下降法原理以及其算法的实现 最速下降法又称为梯度法，是 1847年由著名数学家 Cauchy给出的，它是解析法中最古老 的一种，其他解析 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。 作为一种基本的算法，他在最优化方法中占有重要地位。其优点是工作量少，存储变量较少， 初始点要求不高；缺点是收敛慢，效率不高，有时达不到最优解。非线性规划研究的对象是非 线性函数的数值最优化问题。它的理论和方法渗透到许多方面，特别是在军事、经济、管理、 生产过程自动化、工程 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 和产品优化设计等方面都有着重要的应用。而最速下降法正是n元 函数的无约束非线性规划问题min ( )f x 的一种重要解析法，研究最速下降法原理及其算法实 现对我们有着极其重要的意义。 一、最速下降法基本原理 (一)无约束问题的最优性条件 无约束问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据，为此我们有以下 几个定理。 定理 1 设 f : 1nR R® 在点 nx RÎ 处可微。若存在 np RÎ ，使 ( ) 0Tf x pÑ < 则向量 p是 f 在点 x 处的下降方向。 定理 2 设 1: nf R R® 在点 nx R* Î 处可微。若 x*是无约束问题的局部最优解，则 ( ) 0f x*Ñ = 由数学 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 中我们已经知道，使 ( ) 0f xÑ = 的点 x为函数 f 的驻点或平稳点。函数 f 的一个驻 点可以是极小点；也可以是极大点；甚至也可能既不是极小点也不是极大点，此时称它为函数 f 的 鞍点。以上定理告诉我们， x*是无约束问题的的局部最优解的必要条件是： x*是其目标函数 f 的 驻点。 现给出无约束问题局部最优解的充分条件。 定理 3 设 1: nf R R® 在点 nx R* Î 处的 Hesse矩阵 2 ( )f x*Ñ 存在。若 ( ) 0f x*Ñ = ，并且 2 ( )f x*Ñ 正定 则 x*是无约束问题的严格局部最优解。 一般而言，无约束问题的目标函数的驻点不一定是无约束问题的最优解。但对于其目标函数是 凸函数的无约束凸规划，下面定理证明了，它的目标函数的驻点就是它的整体最优解。 定理 4 设 1: nf R R® ， nx R* Î ， f 是 nR 上的可微凸函数。若有 ( ) 0f x*Ñ = 则 x*是无约束问题的整体最优解。 (二)最速下降法的基本思想和迭代 步骤 新产品开发流程的步骤课题研究的五个步骤成本核算步骤微型课题研究步骤数控铣床操作步骤 最速下降法又称为梯度法，是 1847年由著名数学家 Cauchy给出的。他是解析法中最古老的一 种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。 设无约束问题中的目标函数 1: nf R R® 一阶连续可微。 最速下降法的基本思想是：从当前点 kx 出发，取函数 ( )f x 在点 kx 处下降最快的方向作为我 们的搜索方向 kp .由 ( )f x 的 Taylor展式知 ( ) ( ) ( ) (k k k k T k kf x f x tp t f x p o tp- + = - Ñ + ‖ ‖) 略去 t的高阶无穷小项不计，可见取 kp = ( )kf x-Ñ 时，函数值下降得最多。于是，我们可以构造 出最速下降法的迭代步骤。 解无约束问题的的最速下降法计算步骤 第 1步 选取初始点 0x ，给定终止误差 0e > ，令 : 0k = ； 第 2步 计算 ( )kf xÑ ，若 ( kf x eÑ £‖ )‖ ，停止迭代.输出 kx .否则进行第三步； 第 3步 取 ( )k kp f x= -Ñ ； 第 4步 进行一维搜索，求 kt ，使得 0 ( ) min ( )k k k kk tf x t p f x tp³+ = + 令 1k k kkx x t p + = + ， : 1k k= + ，转第 2步。 由以上计算步骤可知，最速下降法迭代终止时，求得的是目标函数驻点的一个近似点。 确定最优步长 kt 的方法如下： 方法一：采用任一种一维寻优法 此时的 ( ( ))k kf x t f x- Ñ 已成为步长 t的一元函数，故可用任何一种一维寻优法求出 kt ，即 1( ) ( ( )) min ( ( ))k k k k kk tf x f x t f x f x t f x + = - Ñ = - Ñ 方法二：微分法 因为 ( ( )) ( )k ktf x t f x tj- Ñ = 所以，一些简单情况下，可令 ' ( ) 0tj = 以解出近似最优步长 kt 的值。 (三)最速下降法应用举例 例 1 2 21 2 1 1 2 2min ( ) 2 2f x x x x x x x= - + + + 给定初始点 ( )1 (0,0)TX = 解：目标函数 ( )f x 的梯度 1 1 2 1 2 2 ( ) ( ) 1 4 2 ( ) 1 2 2( ) ( ) f x x x x f x x xf x x ¶é ù ê ú¶ + +é ùê úÑ = = ê ú- + +¶ê ú ë û ê ú¶ë û (1) 1( ) 1 f X é ùÑ = ê ú-ë û 令搜索方向 (1) (1) 1( ) 1 d f X -é ù = -Ñ = ê ú ë û 再从 (1)X 出发，沿 (1)d 方向作一维寻优，令 步长变量为l，最优步长为 1l ，则有 (1) (1) 0 1 0 1 X d l l l l - -é ù é ù é ù + = + =ê ú ê ú ê ú ë û ë û ë û 故 (1) (1) 2 2 2 1( ) ( ) ( ) 2( ) 2( ) 2 ( )f x f X dl l l l l l l l l j l= + = - - + - + - + = - = 令 '1( ) 2 2 0j l l= - = 可得 1 1l = (2) (1) (1) 1 0 1 1 0 1 1 X X dl - -é ù é ù é ù = + = + =ê ú ê ú ê ú ë û ë û ë û 求出 (2)X 点之后，与 上类似地，进行第二次迭代： (2) 1 ( ) 1 f X -é ù Ñ = ê ú-ë û 令 (2) (2) 1 ( ) 1 d f X é ù= -Ñ = ê ú ë û 令步长变量为l，最优步长为 2l ，则有 (2) (2) 1 1 1 1 1 1 X d l l l l - -é ù é ù é ù + = + =ê ú ê ú ê ú+ë û ë û ë û 故 (2) (2) 2 2 2 2( ) ( ) ( 1) ( 1) 2( 1) 2( 1)( 1) ( 1) 5 2 1 ( )f x f X dl l l l l l l l l j l= + = - - + + - + - + + + = - - = 令 '2 ( ) 10 2 0j l l= - = 可得 2 1 5 l = (3) (2) (2)2 1 1 0.81 1 1 1.25 X X dl - -é ù é ù é ù = + = + =ê ú ê ú ê ú ë û ë û ë û (3) 0.2( ) 0.2 f X é ùÑ = ê ú-ë û 此时所达到的精度 (3)( ) 0.2828f XÑ » 本题最优解 1 1.5 X * -é ù = ê ú ë û ， ( ) 1, 25f X * = - 例 2 用最速下降法求解无约束非线性规划问题： 4 2 1 1 2min ( ) ( 2) ( 2 )f X x x x= - + - 其中 1 2( , ) TX x x= ，要求选取初始点 0 (0,3)TX = ，终止误差 0.1e = . 解：因 3 1 1 2 1 2( ) [4( 2) 2( 2 ), 4( 2 )] Tf X x x x x xÑ = - + - - - 则 0( ) ( 44, 24)Tf XÑ = - 0( ) 50.12f X eÑ = > 0 0( ) (44, 24)Tp f X= -Ñ = - 求单变量极小化问题： 0 0 0 0 min ( ) min (44 ,3 24 ) t t f x tp f t t ³ ³ + = - 4 2 0 min(44 2) (92 6) t t t ³ = - + - 的最优解 0t ，由 0.618法可得 0 0.06t = ，于是 1 0 0 0 (2.70,1.51)TX x t p= + = 1( ) (0.73,1.28)Tf XÑ = 1( ) 1.47f X eÑ = > 令 1 1( )p f X= -Ñ 再求单变量极小化问题 1 1 0 min ( ) t f X tp ³ + 的最优解.略去计算步骤，由表 1-1给出计算结果.由表 1-1可以知道， 7( ) 0.09f X eÑ = < ，所以 7 (2.28,1.15)TX = 为近似最优解，原问题的近似最优值为0.007 . 表 1-1 迭代次 数 k kX ( )kf X ( ) kf XÑ ( ) kf XÑ kt 1kX + 0 (0.00,3.00)T 52.00 ( 44, 24) T- 50.12 0.06 (2.70,1.51)T 1 (2.70,1.51)T 0.34 (0.73,1.28) T 1.47 0.24 (2.52,1.20)T 2 (2.52,1.20)T 0.09 (0.80, 0.48) T- 0.93 0.11 (2.43,1.25)T 3 (2.43,1.25)T 0.04 (0.18,0.28) T 0.33 0.31 (2.37,1.16)T 4 (2.37,1.16)T 0.02 (0.30, 0.20) T- 0.36 0.12 (2.33,1.18)T 5 (2.33,1.18)T 0.01 (0.08,0.12) T 0.14 0.36 (2.30,1.14)T 6 (2.30,1.14)T 0.009 (0.15, 0.08) T- 0.17 0.13 (2.28,1.15)T 7 (2.28,1.15)T 0.007 (0.05,0.08) T 0.09 例3 用最速下降法求解无约束问题 2 21 2 1 2 1 3 1min ( ) 2 2 2 f x x x x x x= + - - 取 ( )1 (0,0)TX = ， 210e -= 。 解：计算目标函数的梯度和 Hesse阵 1 2 1 2 1 2 3 2 ( ) x x g f X x x g - -é ù é ù Ñ = =ê ú ê ú-ë û ë û ， 2 3 1( ) 1 1 f X G -é ù Ñ = =ê ú-ë û 设 [ ]( ) 1 2, Tkd d d= ， [ ]( ) 1 2( ) , Tkf X g gÑ = 得到精确一维搜索步长 1 1 2 2 2 2 1 2 1 23 2 k g d g d d d d d a + = + - 取 ( )1 (0,0)TX = ，则 [ ](1)( ) 2,0 Tf XÑ = - ，所以 [ ](1) (1)( ) 2,0 Td f X= -Ñ = ， 2 1 2 2 1 3 2 3 a = = ´ 因此 [ ] [ ](2) (1) (1)1 1 20,0 2,0 ,0 3 3 T T TX X da é ù= + = + = ê úë û 再计算第二轮循环，表 1-2列出了各次迭代的计算结果。共计算了 9个点， (9)( ) 0.025f XÑ = < 210- ，停止计算，所以 [ ](9) 0.988,0.988 TX = 作为问题的最优解。 表 1-2 k ( )kX ( )( )kf X ( )( )kf XÑ ( )kd ka 1 (0.000,0.000) 0.000 ( 2.000,0.000)- (2.000,0.000) 0.333 2 (0.667,0.000) 0.667- (0.000, 0.667)- (0.000,0.667) 1.000 3 (0.667,0.667) 0.889- ( 0.667,0.000)- (0.667,0.000) 0.333 4 (0.889,0.667) 0.963- (0.000, 0.222)- (0.000,0.222) 1.000 5 (0.889,0.889) 0.988- ( 0.222,0.000)- (0.222,0.000) 0.333 6 (0.963,0.889) 0.996- (0.000, 0.074)- (0.000,0.074) 1.000 7 (0.963,0.963) 0.999- ( 0.074,0.000)- (0.074,0.000) 0.333 8 (0.988,0.963) 1.000- (0.000, 0.025)- (0.000,0.025) 1.000 9 (0.988,0.988) 1.000- ( 0.025,0.000)- (四)最速下降法的缺点 由于沿负梯度方向目标函数的最速下降性，很容易使人们误认为负梯度方向是最理想的搜索方 向，最速下降法是一种理想的极小化方法。必须指出的是，某点的负梯度方向，通常只是在该店附 近才具有这种最速下降的性质。 在一般情况下，当用最速下降法寻找极小点时，其搜索路径呈直角锯齿状（图 1-3），在开头 几步，目标函数下降较快；但在接近极小点时，收敛速度长久不理想了。特别适当目标函数的等值 线为比较扁平的椭圆时，收敛就更慢了。 图 1-3 因此，在实用中常将最速下降法和其他方法联合应用，在前期使用最速下降法，而在接近极小 点时，可改用收敛较快的其他方法。 (4)xO (2)x (3)xg 二、最速下降法算法实现 (一)最速下降法程序流程图 最速下降法的程序流程图，如图 1-4所示 图 1-4 (二)最速下降法程序清单 用 C语言编写的最速下降法的程序清单如下。其中 R是梯度模，P是梯度方向的的单位向量，h 是步长，f是目标函数。 #include “math.h” 开始 给定初始点 0 nx EÎ ， 0e > : 0k = 计算 ( )k kp f x= -Ñ kp e£ 求 kl 使其满足 0 min ( ) ( )k k k kkf x p f x pl l l³ + = + 令 1k k k kx x pl + = + 输出： min kx x= 结束 是 #include “stdio.h” float x[10],y[10],p[10],f,h; int n; vod fun( ) {int i; for(i=1,if2) {t=t+t;u=u+1; else{t=-t;h3=h1;f3=f1; h1=h2;f1=f2;h2=h3;f2=f3; p1: h3=h2+t; h=h3; fun( ) f3=f; if(f2>f3) {t=t+t;u=u+1; h1=h2;f1=f2;h2=h3;f2=f3;goto pl;} else{if(u>0) {h4=0.5*(h2+h3);h=h4; fun( );f4=f; if(f4>f2) {h3=h4;f3=f4;} else{h1=h2;f1=f2;h2=h4;f2=f4;} } c1=（f3-f1）/(h3-h1); c2=((f2-f1)/(h2-h1)-c1)/(h2-h3); if(fabs(c2)f2) {h1=h2;f1=f2;} else {h1=h4;f1=f4;} t0=v*t0;goto p2; } } } } p3:h0;fun( ); printf(“OBJ.FUNC F=%f\n”,f); for(i=1;i 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 《最速 下降法及其算法实现》完成了。详细阐释了最速下降法的基本原理，迭代步骤以及算法的实现，对 最速下降法做了较为深入的研究。 通过这次设计，我重新学习了以前遗忘的知识，加深了记忆和理解。真正做到了理论和实践相 结合，锻炼了自己分析，处理实际问题的能力，也认识到了自己的不足。毕业设计过程中总结到的 经验和教训将指导我未来的工作和学习，我会更加努力，取得更大的成绩。 参 考 文 献 ［1］赵瑞安，吴方.非线性最优化理论和方法.北京:高等教育出版社，1900 ［2］袁亚湘，孙文瑜.最优化理论与方法.北京：科学出版社，1997 ［3］陈开明.非线性规划.上海：复旦大学出版社，1991 ［4］周维，杨鹏飞.运筹学.北京:科学出版社，2008 ［5］张莹，运筹学基础.北京：清华大学出版社.1994 ［6］刘建永，运筹学算法与编程实践.北京：清华大学出版社.2004 ［7］傅鹂，龚劬，刘琼荪，何中市.数学实验.北京：科学出版社.2000