词条 | 最速下降法 |
释义 | 最速下降法又称为梯度法,是1847 年由著名数学家Cauchy 给出的,它是解析法中最古老的一种,其他解析方法或是它的变形,或是受它的启发而得到的,因此它是最优化方法的基础。作为一种基本的算法,他在最优化方法中占有重要地位。其优点是工作量少,存储变量较少,初始点要求不高;缺点是收敛慢,效率不高,有时达不到最优解。非线性规划研究的对象是非线性函数的数值最优化问题。它的理论和方法渗透到许多方面,特别是在军事、经济、管理、生产过程自动化、工程设计和产品优化设计等方面都有着重要的应用。而最速下降法正是n元函数的无约束非线性规划问题min f (x)的一种重要解析法,研究最速下降法原理及其算法实现对我们有着极其重要的意义。 一、最速下降法基本原理 (一)无约束问题的最优性条件 无约束问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据,为此我们有以下 几个定理。 定理1 设 f : Rn ® R1在点x ÎRn处可微。若存在pÎRn,使 Ñf (x)T p < 0 则向量p是f 在点x 处的下降方向。 定理2 设 f : Rn ® R1在点x* Î Rn处可微。若x*是无约束问题的局部最优解,则 Ñf (x* ) = 0 由数学分析中我们已经知道,使Ñf (x) = 0的点x为函数f 的驻点或平稳点。函数f 的一个驻 点可以是极小点;也可以是极大点;甚至也可能既不是极小点也不是极大点,此时称它为函数f 的 鞍点。以上定理告诉我们,x*是无约束问题的的局部最优解的必要条件是:x*是其目标函数f 的 驻点。 现给出无约束问题局部最优解的充分条件。 定理3 设 f : Rn ® R1在点x* Î Rn处的Hesse矩阵Ñ2 f (x* )存在。若 Ñf (x* ) = 0,并且Ñ2 f (x* )正定 则x*是无约束问题的严格局部最优解。 一般而言,无约束问题的目标函数的驻点不一定是无约束问题的最优解。但对于其目标函数是 凸函数的无约束凸规划,下面定理证明了,它的目标函数的驻点就是它的整体最优解。 定理4 设 f : Rn ® R1,x* ÎRn, f 是Rn上的可微凸函数。若有 Ñf (x* ) = 0 则x*是无约束问题的整体最优解。 (二)最速下降法的基本思想和迭代步骤 最速下降法又称为梯度法,是1847年由著名数学家Cauchy 给出的。他是解析法中最古老的一 种,其他解析方法或是它的变形,或是受它的启发而得到的,因此它是最优化方法的基础。 设无约束问题中的目标函数f : Rn ® R1一阶连续可微。 最速下降法的基本思想是:从当前点xk出发,取函数f (x)在点xk处下降最快的方向作为我 们的搜索方向pk .由f (x)的Taylor 展式知 f (xk ) - f (xk + tpk ) = -tÑf (xk )T pk + o‖( tpk‖) 略去t的高阶无穷小项不计,可见取pk = -Ñf (xk )时,函数值下降得最多。于是,我们可以构造 出最速下降法的迭代步骤。 解无约束问题的的最速下降法计算步骤 第 1 步选取初始点x0,给定终止误差e > 0,令k := 0; 第 2 步计算Ñf (xk ),若‖Ñf (xk )‖£ e ,停止迭代.输出xk .否则进行第三步; 第 3 步取 pk = -Ñf (xk ); 第 4 步进行一维搜索,求k t ,使得 0 ( k k ) min ( k k ) k t f x tp f x tp 3 + = + 令 k 1 k k k x + = x + t p ,k := k +1,转第2 步。 由以上计算步骤可知,最速下降法迭代终止时,求得的是目标函数驻点的一个近似点。 确定最优步长k t 的方法如下: 方法一:采用任一种一维寻优法 此时的f (xk - tÑf (xk ))已成为步长t的一元函数,故可用任何一种一维寻优法求出k t ,即 ( k 1) ( k ( k )) min ( k ( k )) k t f x + = f x - t Ñf x = f x -tÑf x 方法二:微分法 因为 tf (xk - tÑf (xk )) = j(t) 所以,一些简单情况下,可令 j' (t) = 0 以解出近似最优步长k t 的值。 (三)最速下降法应用举例 例 1 2 2 1 2 1 1 2 2 min f (x) = x - x + 2x + 2x x + x 给定初始点X (1) = (0,0)T 解:目标函数f (x)的梯度1 1 2 1 2 2 ( ) ( ) 1 4 2 ( ) ( ) 1 2 2 ( ) f x x x x f x f x x x x é¶ ù ê ¶ ú é + + ù Ñ = ê ú = ê ú ê¶ ú ë- + + û ê ¶ ú ë û (1) 1 ( ) 1 f X é ù Ñ = ê ú ë- û 令搜索方向(1) (1) 1 ( ) 1 d f X é- ù = -Ñ =ê ú ë û 再从X (1)出发,沿d(1)方向作一维寻优,令 步长变量为l ,最优步长为1 l ,则有(1) (1) 0 1 0 1 X d l l l l é ù é- ù é- ù + = ê ú + ê ú = ê ú ë û ë û ë û 故 (1) (1) 2 2 2 1 f (x) = f (X + ld ) = (-l) - l + 2(-l) + 2(-l)l + l = l - 2l = j (l) 令 ' 1 ( j l) = 2l - 2 = 0可得1 l =1 (2) (1) (1) 1 0 1 1 0 1 1 X X l d é ù é- ù é- ù = + = ê ú + ê ú = ê ú ë û ë û ë û 求出 X (2)点之后,与 上类似地,进行第二次迭代: (2) 1 ( ) 1 f X é- ù Ñ = ê ú ë- û 令 (2) (2) 1 ( ) 1 d f X é ù = -Ñ =ê ú ë û 令步长变量为l ,最优步长为2 l ,则有 (2) (2) 1 1 1 1 1 1 X d l l l l é- ù é ù é - ù + = ê ú + ê ú = ê ú ë û ë û ë + û 故 (2) (2) 2 2 2 2 f (x) = f (X + ld ) = (l -1) - (l +1) + 2(l -1) + 2(l -1)(l +1) + (l +1) = 5l - 2l -1 = j (l) 令' 2 j (l) =10l - 2 = 0可得2 1 5 l = (3) (2) (2) 2 1 1 1 0.8 1 5 1 1.2 X X l d é- ù é ù é- ù = + = ê ú + ê ú = ê ú ë û ë û ë û (3) 0.2 ( ) 0.2 f X é ù Ñ = ê ú ë- û 此时所达到的精度Ñf (X (3) ) » 0.2828 本题最优解 1 1.5 X * é- ù =ê ú ë û , f (X * ) = -1, 25 例2 用最速下降法求解无约束非线性规划问题: 4 2 1 1 2 min f (X ) = (x - 2) + (x - 2x ) 其中 1 2 X = (x , x )T,要求选取初始点X 0 = (0,3)T ,终止误差e = 0.1. 解:因3 1 1 2 1 2 Ñf (X ) = [4(x - 2) + 2(x - 2x ),-4(x - 2x )]T 则 Ñf (X 0 ) = (-44, 24)T Ñf (X 0 ) = 50.12 > e p0 = -Ñf (X 0 ) = (44,-24)T 求单变量极小化问题: 0 0 0 0 min ( ) min (44 ,3 24 ) t t f x tp f t t 3 3 + = - 4 2 0 min(44 2) (92 6) t t t 3= - + - 的最优解t0,由0.618 法可得t0 = 0.06,于是 X1 = x0 + t0 p0 = (2.70,1.51)T Ñf (X1) = (0.73,1.28)T Ñf (X1) =1.47 > e 令 p1 = -Ñf (X1) 再求单变量极小化问题 1 1 0 min ( ) t f X tp 3 + 的最优解.略去计算步骤,由表1-1 给出计算结果.由表1-1 可以知道, Ñf (X 7 ) = 0.09 < e ,所以 X 7 = (2.28,1.15)T 为近似最优解,原问题的近似最优值为0.007 . 表1-1 迭代次 数k X k f (X k ) Ñf (X k ) Ñf (X k ) tk X k +1 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 2 1 2 12 1 min ( ) 3 1 2 2 2 f x = x + x - x x - x 取 ( X 1) = (0,0)T ,e =10-2 。 解:计算目标函数的梯度和Hesse阵 1 2 1 2 1 2 3 2 ( ) x x g f X x x g é - - ù é ù Ñ = ê ú = ê ú ë - û ë û , 2 3 1 ( ) 1 1 fX G é - ù Ñ = ê ú = ë- û 设 ( ) [ ] 1 2 , d k = d d T , ( ) [ ] 1 2 ( ) , Ñf X k = g g T 得到精确一维搜索步长 1 1 2 2 2 2 1 2 1 2 3 2 k gd g d d d d d a + = + - 取 ( X 1) = (0,0)T ,则( (1) ) [ 2,0]T Ñf X = - ,所以(1) ( (1) ) [2,0]T d = -Ñf X = , 2 1 2 2 1 3 2 3 a= = ′ 因此 (2) (1) (1) [ ] [ ] 1 0,0 1 2,0 2 ,0 3 3 T T T X = X +a d = + = éê ùú ë û 再计算第二轮循环,表1-2 列出了各次迭代的计算结果。共计算了9 个点, Ñf (X (9) ) = 0.025 < 10-2,停止计算,所以(9) [0.988,0.988]T X = 作为问题的最优解。 表 1-2 k X ( k ) f (X ( k ) ) Ñf (X (k ) ) d( k ) k a 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 因此,在实用中常将最速下降法和其他方法联合应用,在前期使用最速下降法,而在接近极小 点时,可改用收敛较快的其他方法。 x(4) O x(2) g x(3) 二、最速下降法算法实现 (一)最速下降法程序流程图 最速下降法的程序流程图,如图1-4 所示 图 1-4 (二)最速下降法程序清单 用 C 语言编写的最速下降法的程序清单如下。其中R 是梯度模,P是梯度方向的的单位向量,h 是步长,f 是目标函数。 #include “math.h” 开始 给定初始点0 x ÎEn,e > 0 k := 0 计算pk = -Ñf (xk ) pk £ e 求 k l 使其满足 0 min ( k k ) ( k k ) k f x p fx p l l l 3 + = + 令 k 1 k k k x + = x + l p 输出: min x = xk 结束 是 #include “stdio.h” float x[10],y[10],p[10],f,h; int n; vod fun( ) {int i; for(i=1,i<n;i++) x[i]=y[i]-h*p[i]; f=x[1]*x[1]+x[2]*x[2]-x[1]*x[2]-10*x[1]-4*x[2]; f=f+60; return; } main( ) {float g[10],d[10],q,r,e,h1,h2,h3,h4,t,t0,c1,c2,f1,f2,f3,f4,f5,v; int i,k,u; printf(“input n,e\”); scanf(“%d,%f”,&n,&e); x[1]=0;x[2]=0; p4: g[1]=2*x[1]-x[2]-10; g[2]=2*x[2]-x[1]-4; q=0; for(i=1;i<n;i++) q=g[i]*g[i]+q; r=sqrt(q); for(i=1;i<n;i++) {y[i]=x[i];p[i]=g[i]/r;} if(r<e)go to p3; else {t0=1;v=0.1;h1=0;h=h1 fun( );f1=f; p2: u=0;t=t0; h2=h1+t;h=h2; fun( );f2=f; if(f1>f2) {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)<e) {h1=h2;f1=f2;t0=v*t0;goto p2;} else{h4=0.5*(h1+h3-(c1/c2));h=h4; fun( );f4=f; if(f2<1) f5=1; else f5=f2; if((fabs(f4-f2)/f5)<e) {for(i=1;i<n;i++) x[i]=y[i]-h4*p[i]; goto p4; } else {if(f4>f2) {h1=h2;f1=f2;} else {h1=h4;f1=f4;} t0=v*t0;goto p2; } } } } p3:h0;fun( ); printf(“OBJ.FUNC F=%f\”,f); for(i=1;i<n;i++) {printf(“X(%d”,I); printf(“)=%f\”,x[i]); } } 三、设计总结 接触最速下降法是在学习运筹学时,它是一种重要的无约束最优化方法。是1847 年由著名数 学家Cauchy 给出的,它是解析法中最古老的一种,其他解析方法或是它的变形,或是受它的启发 而得到的。在进行该题目的毕业设计时,以前学到的知识是远远不够的。我去学校图书馆查阅了大 量的相关书籍,引用了一些比较经典的例题来呈现最速下降法。为了用C 语言实现最速下降法,重 温了C 语言,上网查阅了相关资料。经过近半年的努力和辅导老师的大力帮助下,我的论文《最速 下降法及其算法实现》完成了。详细阐释了最速下降法的基本原理,迭代步骤以及算法的实现,对 最速下降法做了较为深入的研究。 通过这次设计,我重新学习了以前遗忘的知识,加深了记忆和理解。真正做到了理论和实践相 结合,锻炼了自己分析,处理实际问题的能力,也认识到了自己的不足。毕业设计过程中总结到的 经验和教训将指导我未来的工作和学习,我会更加努力,取得更大的成绩。 参考 文献 [1]赵瑞安,吴方.非线性最优化理论和方法.北京:高等教育出版社,1900 [2]袁亚湘,孙文瑜.最优化理论与方法.北京:科学出版社,1997 [3]陈开明.非线性规划.上海:复旦大学出版社,1991 [4]周维,杨鹏飞.运筹学.北京:科学出版社,2008 [5]张莹,运筹学基础.北京:清华大学出版社.1994 [6]刘建永,运筹学算法与编程实践.北京:清华大学出版社.2004 [7]傅鹂,龚劬,刘琼荪,何中市.数学实验.北京:科学出版社.2000 |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。