《最速下降法原理及例题实例资料》由会员分享，可在线阅读，更多相关《最速下降法原理及例题实例资料（10页珍藏版）》请在金锄头文库上搜索。
1、最速下降法原理以及其算法的实现最速下降法原理以及其算法的实现 最速下降法又称为梯度法，是 1847 年由著名数学家 Cauchy 给出的，它是解析法中最古老 的一种， 其他解析方法或是它的变形， 或是受它的启发而得到的， 因此它是最优化方法的基础。 作为一种基本的算法，他在最优化方法中占有重要地位。其优点是工作量少，存储变量较少， 初始点要求不高；缺点是收敛慢，效率不高，有时达不到最优解。非线性规划研究的对象是非 线性函数的数值最优化问题。它的理论和方法渗透到许多方面，特别是在军事、经济、管理、 生产过程自动化、工程设计和产品优化设计等方面都有着重要的应用。而最速下降法正是n元 函数的无约束非
2、线性规划问题min( )f x的一种重要解析法，研究最速下降法原理及其算法实 现对我们有着极其重要的意义。 一、最速下降法基本原理 (一)无约束问题的最优性条件 无约束问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据， 为此我们有以下 几个定理。 定理 1 设f : 1n RR在点 n xR处可微。若存在 n pR，使 ( )0 T f xp，令: 0k =； 第 2 步 计算() k f x，若( k f x) ，停止迭代.输出 k x.否则进行第三步； 第 3 步 取() kk pf x= ； 第 4 步 进行一维搜索，求 k t，使得 0 ()min() kkkk k t f
3、 xt pf xtp +=+ 令 1kkk k xxt p + =+，:1kk=+，转第 2 步。 由以上计算步骤可知，最速下降法迭代终止时，求得的是目标函数驻点的一个近似点。 确定最优步长 k t的方法如下： 方法一：采用任一种一维寻优法 此时的() kk f xt f x 已成为步长t的一元函数，故可用任何一种一维寻优法求出 k t，即 1 ()()min() kkkkk k t f xf xtf xf xt f x + = = 方法二：微分法 因为 ()( ) kk tf xt f xt = 所以，一些简单情况下，可令 ( ) 0t= 以解出近似最优步长 k t的值。 (三)最速下降法应
4、用举例 例 1 22 121122 min( )22f xxxxx xx=+给定初始点 ( )1 (0,0)TX= 解：目标函数( )f x的梯度 112 12 2 ( ) ( )142 ( ) 122( ) () f x xxx f x xxf x x + = + (1) 1 () 1 f X = 令搜索方向 (1)(1) 1 () 1 df X = = 再从 (1) X出发，沿 (1) d方向作一维寻优，令 步长变量为，最优步长为 1 ，则有 (1)(1) 01 01 Xd +=+= 故 (1)(1)222 1 ( )()()2()2()2( )f xf Xd =+= += 令 1( )
5、220 =可得 1 1 = (2)(1)(1) 1 011 011 XXd =+=+= 求出 (2) X点之后，与 上类似地，进行第二次迭代： (2) 1 () 1 f X = 令 (2)(2) 1 () 1 df X = = 令步长变量为，最优步长为 2 ，则有 (2)(2) 111 111 Xd +=+= + 故 (2)(2)222 2 ( )()(1)(1)2(1)2(1)(1)(1)521( )f xf Xd =+=+= = 令 2( ) 1020 =可得 2 1 5 = (3)(2)(2) 2 110.8 1 111.25 XXd =+=+= (3) 0.2 () 0.2 f X =
6、 此时所达到的精度 (3) ()0.2828f X 本题最优解 1 1.5 X = ，()1,25f X = 例 2 用最速下降法求解无约束非线性规划问题： 42 112 min()(2)(2)f Xxxx=+ 其中 12 ( ,)TXx x=，要求选取初始点 0 (0,3)TX =，终止误差0.1 =. 解：因 3 11212 ()4(2)2(2), 4(2)Tf Xxxxxx=+ 则 0 ()( 44,24)Tf X= 0 ()50.12f X= 00 ()(44, 24)Tpf X= = 求单变量极小化问题： 00 00 min()min(44 ,324 ) tt f xtpftt +=
7、 42 0 min(442)(926) t tt =+ 的最优解 0 t，由 0.618 法可得 0 0.06t =，于是 1000 (2.70,1.51)TXxt p=+= 1 ()(0.73,1.28)Tf X= 1 ()1.47f X= 令 11 ()pf X= 再求单变量极小化问题 11 0 min() t f Xtp + 的最优解.略去计算步骤，由表 1- 1 给出计算结果.由表 1- 1 可以知道， 7 ()0.09f X=f3) t=t+t;u=u+1; h1=h2;f1=f2;h2=h3;f2=f3;goto pl; elseif(u0) h4=0.5*(h2+h3);h=h4
8、; 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=
9、v*t0;goto p2; p3:h0;fun( ); printf(“OBJ.FUNC F=%fn”,f); for(i=1;in;i+) printf(“X(%d”,I); printf(“)=%fn”,xi); 三、设计总结 接触最速下降法是在学习运筹学时，它是一种重要的无约束最优化方法。是 1847 年由著名数 学家 Cauchy 给出的，它是解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发 而得到的。在进行该题目的毕业设计时，以前学到的知识是远远不够的。我去学校图书馆查阅了大 量的相关书籍，引用了一些比较经典的例题来呈现最速下降法。为了用 C 语言实现最速下降法，重 温
10、了 C 语言，上网查阅了相关资料。经过近半年的努力和辅导老师的大力帮助下，我的论文最速 下降法及其算法实现完成了。详细阐释了最速下降法的基本原理，迭代步骤以及算法的实现，对 最速下降法做了较为深入的研究。 通过这次设计，我重新学习了以前遗忘的知识，加深了记忆和理解。真正做到了理论和实践相 结合，锻炼了自己分析，处理实际问题的能力，也认识到了自己的不足。毕业设计过程中总结到的 经验和教训将指导我未来的工作和学习，我会更加努力，取得更大的成绩。 参 考 文 献 1赵瑞安，吴方.非线性最优化理论和方法.北京:高等教育出版社，1900 2袁亚湘，孙文瑜.最优化理论与方法.北京：科学出版社，1997 3陈开明.非线性规划.上海：复旦大学出版社，1991 4周维，杨鹏飞.运筹学.北京:科学出版社，2008 5张莹，运筹学基础.北京：清华大学出版社.1994 6刘建永，运筹学算法与编程实践.北京：清华大学出版社.2004 7傅鹂，龚劬，刘琼荪，何中市.数学实验.北京：科学出版社.2000
