最速下降法原理及其算法实现课程论文


     本科毕业论文(设计)模板 课程论文 论文题目:最速下降法原理及其算法实现 课程名称: 现代信号处理新方法 学 院: 自动化学院 专业班级: 控制科学与工程班 学 号: 姓 名: 任课教师: 2014年X月X日 最速下降法原理及其算法实现 内 容 摘 要 摘要:基于最速下降法在解决无约束非线性规划问题中的重要性,对其原理与算法予以讨论。论文主要是参阅大量数学分析和运筹学书籍以及一些学术资料,结合自己在平时学习中掌握的知识,并在指导老师的建议下,针对最速下降法的基本思路和原理进行研究。 关键词:运筹学 最速下降法 无约束 梯度法 最优解 The steepest descent method, principle and its algorithm Abstract Based on the steepest descent method in solving unconstrained nonlinear programming problem, the importance of the principle and the 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 teacher's suggestion, the steepest descent method according to the basic ideas and principles were studied. Key words:operational research steepest descent method Unconstrained gradient method optimal solution 序言 最速下降法又称为梯度法,是1847年由著名数学家Cauchy给出的,它是解析法中最古老的一种,其他解析方法或是它的变形,或是受它的启发而得到的,因此它是最优化方法的基础。作为一种基本的算法,他在最优化方法中占有重要地位。其优点是工作量少,存储变量较少,初始点要求不高;缺点是收敛慢,效率不高,有时达不到最优解。非线性规划研究的对象是非线性函数的数值最优化问题。它的理论和方法渗透到许多方面,特别是在军事、经济、管理、生产过程自动化、工程设计和产品优化设计等方面都有着重要的应用。而最速下降法正是元函数的无约束非线性规划问题的一种重要解析法,研究最速下降法原理及其算法实现对我们有着极其重要的意义。 一、最速下降法基本原理 (一)无约束问题的最优性条件 无约束问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据,为此我们有以下几个定理。 定理1 设在点处可微。若存在,使 则向量是在点处的下降方向。 定理2 设在点处可微。若是无约束问题的局部最优解,则 由数学分析中我们已经知道,使的点为函数的驻点或平稳点。函数的一个驻点可以是极小点;也可以是极大点;甚至也可能既不是极小点也不是极大点,此时称它为函数的鞍点。以上定理告诉我们,是无约束问题的的局部最优解的必要条件是:是其目标函数的驻点。 现给出无约束问题局部最优解的充分条件。 定理3 设在点处的Hesse矩阵存在。若 ,并且正定 则是无约束问题的严格局部最优解。 一般而言,无约束问题的目标函数的驻点不一定是无约束问题的最优解。但对于其目标函数是凸函数的无约束凸规划,下面定理证明了,它的目标函数的驻点就是它的整体最优解。 定理4 设,,是上的可微凸函数。若有 则是无约束问题的整体最优解。 (二)最速下降法的基本思想和迭代步骤 最速下降法又称为梯度法,是1847年由著名数学家Cauchy给出的。他是解析法中最古老的一种,其他解析方法或是它的变形,或是受它的启发而得到的,因此它是最优化方法的基础。 设无约束问题中的目标函数一阶连续可微。 最速下降法的基本思想是:从当前点出发,取函数在点处下降最快的方向作为我们的搜索方向.由的Taylor展式知 略去的高阶无穷小项不计,可见取时,函数值下降得最多。于是,我们可以构造出最速下降法的迭代步骤。 解无约束问题的的最速下降法计算步骤 第1步 选取初始点,给定终止误差,令; 第2步 计算,若,停止迭代.输出.否则进行第三步; 第3步 取; 第4步 进行一维搜索,求,使得 令,,转第2步。 由以上计算步骤可知,最速下降法迭代终止时,求得的是目标函数驻点的一个近似点。 确定最优步长的方法如下: 方法一:采用任一种一维寻优法 此时的已成为步长的一元函数,故可用任何一种一维寻优法求出,即 方法二:微分法 因为 所以,一些简单情况下,可令 以解出近似最优步长的值。 (三)最速下降法应用举例 例1 给定初始点 解:目标函数的梯度 令搜索方向再从出发,沿方向作一维寻优,令步长变量为,最优步长为,则有 故 令可得 求出点之后,与上类似地,进行第二次迭代: 令 令步长变量为,最优步长为,则有 故令可得 此时所达到的精度 本题最优解, 例2 用最速下降法求解无约束非线性规划问题: 其中,要求选取初始点,终止误差. 解:因 则 求单变量极小化问题: 的最优解,由0.618法可得,于是 令 再求单变量极小化问题 的最优解.略去计算步骤,由表1-1给出计算结果.由表1-1可以知道,,所以 为近似最优解,原问题的近似最优值为. 表1-1 迭代次数 例3 用最速下降法求解无约束问题 取,。 解:计算目标函数的梯度和Hesse阵 , 设,得到精确一维搜索步长 取,则,所以, 因此 再计算第二轮循环,表1-2列出了各次迭代的计算结果。共计算了9个点, ,停止计算,所以作为问题的最优解。 表1-2 (四)最速下降法的缺点 由于沿负梯度方向目标函数的最速下降性,很容易使人们误认为负梯度方向是最理想的搜索方向,最速下降法是一种理想的极小化方法。必须指出的是,某点的负梯度方向,通常只是在该店附近才具有这种最速下降的性质。 在一般情况下,当用最速下降法寻找极小点时,其搜索路径呈直角锯齿状(图1-3),在开头几步,目标函数下降较快;但在接近极小点时,收敛速度长久不理想了。特别适当目标函数的等值线为比较扁平的椭圆时,收敛就更慢了。 图1-3 因此,在实用中常将最速下降法和其他方法联合应用,在前期使用最速下降法,而在接近极小点时,可改用收敛较快的其他方法。 二、最速下降法算法实现 (一)最速下降法程序流程图 最速下降法的程序流程图,如图1-4所示 开始 给定初始点, 计算 是 求使其满足 令 输出: 结束 图1-4 (二)最速下降法程序清单 用C语言编写的最速下降法的程序清单如下。其中R是梯度模,P是梯度方向的的单位向量,h是步长,f是目标函数。 #include “math.h” #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\n”); 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\n”,f); for(i=1;i<n;i++) {printf(“X(%d”,I); printf(“)=%f\n”,x[i]); } } 三、设计总结 接触最速下降法是在学习运筹学时,它是一种重要的无约束最优化方法。是1847年由著名数学家Cauchy给出的,它是解析法中最古老的一种,其他解析方法或是它的变形,或是受它的启发而得到的。在进行该题目的毕业设计时,以前学到的知识是远远不够的。我去学校图书馆查阅了大量的相关书籍,引用了一些比较经典的例题来呈现最速下降法。为了用C语言实现最速下降法,重温了C语言,上网查阅了相关资料。经过近半年的努力和辅导老师的大力帮助下,我的论文《最速下降法及其算法实现》完成了。详细阐释了最速下降法的基本原理,迭代步骤以及算法的实现,对最速下降法做了较为深入的研究。 通过这次设计,我重新学习了以前遗忘的知识,加深了记忆和理解。真正做到了理论和实践相结合,锻炼了自己分析,处理实际问题的能力,也认识到了自己的不足。毕业设计过程中总结到的经验和教训将指导我未来的工作和学习,我会更加努力,取得更大的成绩。 参 考 文 献 [1]赵瑞安,吴方.非线性最优化理论和方法.北京:高等教育出版社,1900 [2]袁亚湘,孙文瑜.最优化理论与方法.北京:科学出版社,1997 [3]陈开明.非线性规划.上海:复旦大学出版社,1991 [4]周维,杨鹏飞.运筹学.北京:科学出版社,2008 [5]张莹,运筹学基础.北京:清华大学出版社.1994 [6]刘建永,运筹学算法与编程实践.北京:清华大学出版社.2004 [7]傅鹂,龚劬,刘琼荪,何中市.数学实验.北京:科学出版社.2000 本文档由香当网(https://www.xiangdang.net)用户上传

    下载文档到电脑,查找使用更方便

    文档的实际排版效果,会与网站的显示效果略有不同!!

    需要 2 香币 [ 分享文档获得香币 ]

    下载文档

    相关文档

    操作系统课程设计银行家算法的模拟实现

    操作系统课程设计报告专业计算机科学与技术学生姓名班级学号指导教师完成日期信息工程学院题目: 银行家算法的模拟实现 一、设计目的本课程设计是学习完“操作系统原理”课程后进...

    7个月前   
    280    0

    粒子群算法(优化算法)毕业设计论文

     毕 业 论 文 题 目 粒子群算法及其参数设置 专 业 信息与计算科学 班 级 ...

    2年前   
    928    0

    编译原理课程设计报告 简单编译器的设计与实现

     编译原理课程设计 ——简单编译器的设计与实现 班 级: 组长: 组员: 指导教师: 设计时间: ...

    2年前   
    976    0

    线索二叉树算法的设计与实现

    随着时代的不断进步,计算机技术也随之得到发展。数据结构在计算机技术的发展中起到巨大的作用。数据结构为构建出高效的计算机算法打下了坚实的基础。良好的数据结构能够提高算法效率的同时也能减少对系统资源的占用[

    8个月前   
    612    0

    大数据处理算法研究与实现

    因为要适应不同的人的上网要求,提供一些企业的一些网络地址,是网上比较重要的一部分、成套动力设备中起主要作用的机器、寄件系统、系统控制在内的完整的网络平台服务。我们有一个自己的平台,现如今数据发展...

    1年前   
    446    0

    算法实践与创新论文

    XX大学算法实践与创新论文题目 回溯法的分析与应用学生姓名: 学号: 摘...

    10个月前   
    383    0

    眼图形成及其原理总结

    1眼图基本概念1.1 眼图的形成原理眼图是一系列数字信号在示波器上累积而显示的图形,它包含了丰富的信息,从眼图上可以观察出码间串扰和噪声的影响,体现了数字信号整体的特征,从而估计系统优劣程度,...

    6个月前   
    155    0

    论文课程马克思主义基本原理

      论文课程:马克思主义基本原理 论文题目:       学    院  管理学院   专    业  市场营销   学生姓名  梁**   学    号  201**...

    5年前   
    5105    0

    《马克思主义基本原理》课程论文

    《马克思主义基本原理概论》课程论文 通过《马克思主义基本原理概论》学习,我从中学到了很多科学的世界观和方法论,潜移默化地扩大了视野,加深了思想的深度。在老师的教导下,正确地运用马克思主义基本...

    2年前   
    1695    0

    课程论文

    **南师范学院2013-2014学年第一学期 《食用菌栽培技术》课程论文 行政班级:2011级园艺技术         学号:110920010         姓名:廖文昭   任课...

    2年前   
    975    0

    《编译原理》课程实验报告

    《编译原理》课程实验报告题 目: 词法分析器实验 专 业: 计算机科学与技术 班 级: 1班 学 号: ...

    2个月前   
    68    0

    基于视觉的车道线识别算法研究毕业论文

    毕业设计基于视觉的车道线识别算法研究Research on Algorithms of Vision-basedLane Recognition 2009 届 电气与电子工程 分...

    1年前   
    519    0

    毕业论文:TIPTOP双档算法设计与分析

    为了进一步完善现有的TIPTOP系统,针对工程部需求对企业设备进行有效登记管理,本人通过编写TIPTOP双档程序cfar222初步完成了对设备仪器的数据采集。在cfar281双档项目实施后,工程...

    2年前   
    1082    0

    浮选柱分类及其工作原理

    第三节 浮选柱一、概述浮选柱研究最早出现于上世纪六十年代,但由于气泡发生器的结垢与堵塞、浮选尾矿得不到保证、设备运行不稳定等原因,该项研究与应用很快进入了低潮。自上世纪八十年代以来,浮选柱...

    10个月前   
    413    0

    课程论文写作要求

    课程论文写作要求《 国际贸易》课程论文题目:年级、专业: 09级国际经济与贸易学生姓名:学号:完成时间:成绩:指导教师陈钦福建.福州.福建农林大学金山学院论文写作相关要求一、课程论文写作要求1...

    8年前   
    153    0

    **大学课程论文

     **大学课程论文     题目:安全行为影响因素分析研究         作者:  刘 文 港           班级:  安全1502班          时间:...

    4年前   
    1472    0

    论文写作课程要点

    论文写作课程要点论文写作课程总结—论文的结构分类总结“ 昨夜西风凋碧树。独上高楼,望尽天涯路。”“衣带渐宽终不悔,为伊消得人憔悴。”“众里寻他千百度,暮然回首,那人却在灯火阑珊处。” 推荐参考...

    8年前   
    139    0

    新课程教育论文

        目   录   摘要……………………………………………………………………1 关键字………………………………………………………………………1 引言……………………………………...

    7年前   
    8055    0

    操作系统实验报告C语言实现银行家算法

    实 验 报 告题 目名 称C语言实现银行家算法院 系信息科学与工程学院班 级完成时间指导老师本次实验成绩组长联系电话邮件地址组员(姓名,学号)主要任务程序算法的编写、实现、运行调...

    4周前   
    43    0

    操作系统实验三磁盘调度算法的实现

    XX大学计算机与通信工程学院实验报告2013 至 2014 学年 第 一 学期课程名称操作系统学号 学生姓名 年级 专业 教学班号 实验地点 实验时间 2013年 月 日 ...

    4周前   
    34    0

    文档贡献者

    文***品

    贡献于2021-06-15

    下载需要 2 香币 [香币充值 ]
    亲,您也可以通过 分享原创文档 来获得香币奖励!
    下载文档

    该用户的其他文档