最优化问题的拟牛顿法本科毕业论文.doc
学科分类号 输入专业代码 本科生毕业论文(设计)题目(中文):最优化问题的拟牛顿法(英文): 怀化学院本科毕业论文(设计)诚信声明作者郑重声明:所呈交的本科毕业论文(设计),是在指导老师的指导下,独立进行研究所取得的成果,成果不存在知识产权争议。除文中已经注明引用的内容外,论文不含任何其他个人或集体已经发表或撰写过的成果。对论文的研究做出重要贡献的个人和集体均已在文中以明确的方式标明。本声明的法律结果由作者承担。本科毕业论文(设计)作者签名:年 月 日毕业设计(论文)原创性声明和使用授权说明原创性声明本人郑重承诺:所呈交的毕业设计(论文),是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知,除文中特别加以标注和致谢的地方外,不包含其他人或组织已经发表或公布过的研究成果,也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体,均已在文中作了明确的说明并表示了谢意。作 者 签 名: 日 期: 指导教师签名: 日期: 使用授权说明本人完全了解 大学关于收集、保存、使用毕业设计(论文)的规定,即:按照学校要求提交毕业设计(论文)的印刷本和电子版本;学校有权保存毕业设计(论文)的印刷本和电子版,并提供目录检索与阅览服务;学校可以采用影印、缩印、数字化或其它复制手段保存论文;在不以赢利为目的前提下,学校可以公布论文的部分或全部内容。作者签名: 日 期: 学位论文原创性声明本人郑重声明:所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名: 日期: 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定,同意学校保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名:日期: 年 月 日导师签名: 日期: 年 月 日指导教师评阅书指导教师评价:一、撰写(设计)过程1、学生在论文(设计)过程中的治学态度、工作精神 优 良 中 及格 不及格2、学生掌握专业知识、技能的扎实程度 优 良 中 及格 不及格3、学生综合运用所学知识和专业技能分析和解决问题的能力 优 良 中 及格 不及格4、研究方法的科学性;技术线路的可行性;设计方案的合理性 优 良 中 及格 不及格5、完成毕业论文(设计)期间的出勤情况 优 良 中 及格 不及格二、论文(设计)质量1、论文(设计)的整体结构是否符合撰写规范? 优 良 中 及格 不及格2、是否完成指定的论文(设计)任务(包括装订及附件)? 优 良 中 及格 不及格三、论文(设计)水平1、论文(设计)的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意?设计是否有创意? 优 良 中 及格 不及格3、论文(设计说明书)所体现的整体水平 优 良 中 及格 不及格建议成绩: 优 良 中 及格 不及格(在所选等级前的内画“”)指导教师: (签名) 单位: (盖章)年 月 日评阅教师评阅书评阅教师评价:一、论文(设计)质量1、论文(设计)的整体结构是否符合撰写规范? 优 良 中 及格 不及格2、是否完成指定的论文(设计)任务(包括装订及附件)? 优 良 中 及格 不及格二、论文(设计)水平1、论文(设计)的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意?设计是否有创意? 优 良 中 及格 不及格3、论文(设计说明书)所体现的整体水平 优 良 中 及格 不及格建议成绩: 优 良 中 及格 不及格(在所选等级前的内画“”)评阅教师: (签名) 单位: (盖章)年 月 日教研室(或答辩小组)及教学系意见教研室(或答辩小组)评价:一、答辩过程1、毕业论文(设计)的基本要点和见解的叙述情况 优 良 中 及格 不及格2、对答辩问题的反应、理解、表达情况 优 良 中 及格 不及格3、学生答辩过程中的精神状态 优 良 中 及格 不及格二、论文(设计)质量1、论文(设计)的整体结构是否符合撰写规范? 优 良 中 及格 不及格2、是否完成指定的论文(设计)任务(包括装订及附件)? 优 良 中 及格 不及格三、论文(设计)水平1、论文(设计)的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意?设计是否有创意? 优 良 中 及格 不及格3、论文(设计说明书)所体现的整体水平 优 良 中 及格 不及格评定成绩: 优 良 中 及格 不及格(在所选等级前的内画“”)教研室主任(或答辩小组组长): (签名)年 月 日教学系意见:系主任: (签名)年 月 日目录摘要I关键词IAbstractIKey wordsI1前言12第二章牛顿法32.1第二章牛顿法原理32.1.1第二章牛顿法算法步骤33第三章拟牛顿法93.1第三章拟牛顿法原理93.1.1第三章拟牛顿法步骤和条件94第四章收敛性原理174.1第四章二级标题174.1.1第四章三级标题175第五章标题175.1第五章二级标题175.1.1第五章三级标题176第六章标题176.1第六章二级标题176.1.1第六章三级标题177结束语18参考文献18致谢21附录A22最优化问题的拟牛顿法摘要对一般无约束优化问题提出了一类在修正的DFP算法下的广义拟牛顿算法,证明了该算法对函数在Goldste in非精确线搜索下具有全局收敛性.(小四号仿宋体)摘要是对全文内容的高度概括,反映出毕业设计论文的目的、方法、成果和结论。摘要中不宜使用公式、图表、不标注引用文献编号。中文摘要以200400字为宜。关键词输入关键词拟牛顿法 DFP算法 全局收敛性The optimization problem to Newton methodAbstractInsert the Abstract of Thesis(小四号 Times New Roman 体) 英文摘要应与中文摘要一致,符合英语语法,文字表达自然流畅。Key wordsInsert the Key Words(小四号 Times New Roman 体) 英文的关键词应与中文关键词一致1前言单击输入前言内容,4号仿宋体首先阐明选题的背景和选题的意义。选题需强调实际背景,说明在计算机研究中或部门信息化建设、管理现代化等工作中引发该问题的原因,问题出现的环境和条件,解决该问题后能起什么作用等。结合问题背景的阐述,使读者感受到此选题确有实用价值和学术价值,确有研究或开发的必要性。 前言部分常起画龙点睛的作用。选题实际又有新意,意味着研究或开发的方向对头,设计工作有价值。对一篇论文来说,前言写好了,就会吸引读者,使他们对你的选题感兴趣,愿意进一步了解你的工作成果。前言应对与选题相关的国内外文献进行综述。主要内容包括:选题的背景及目的;国内外研究状况和相关领域中已有的成果;尚待进一步研究和解决的问题;设计和研究方法等。引言或前言一般不应少于1500字。从第2节开始,为论文主体 前面部分的篇幅大约占论文的五分之一,主体部分要占五分之四左右。在这部分中,要将整个研究开发工作的内容,包括理论分析、总体设计、模块划分、实现方法等进行详细论述。 主体部分的写法,视选题的不同可以多样化,研究型论文和技术开发型论文的写法就有明显的不同。 研究型论文,主体部分一般应包括:理论基础、数学模型、算法推导、形式化描述、求解方法、计算程序的编制及计算结果的分析和结论。 要强调的是,研究型论文绝不是从推理到推理的空洞文章。研究型论文也应有实际背景,也应有到企业和实际部门调研的过程,并在实际调查研究中获取信息、发现问题、收集数据和资料。在研究分析的基础上,提出解决实际问题的、富有创建性的结论。 技术开发型论文,主体部分应包括:总体设计、模块划分、算法描述、编程模型、数据结构、实现技术、实例测试及性能分析。 以上内容根据任务所处的阶段不同,可以有所侧重。在任务初期的论文,可侧重于设计实现,在任务后期的论文可侧重于应用。但作为一篇完整的论文应让读者从课题的原理设计、问题的解决方法、关键技术以及性能测试都有全面的了解,以便能准确地评判论文的质量。 论文主体部分的内容一般要分成几个章节来描述。在写作上,除了用文字描述外,还要善于利用各种原理图、流程图、表格、曲线等来说明问题,一篇条理清晰、图文并茂的论文才是一篇好的论文。主体是毕业论文(设计)正文的主要部分,包括以下各方面:(1)毕业论文(设计)总体方案设计与论证。(2)毕业论文(设计)各部分的设计计算及试验数据的处理及分析。(3)对本研究内容及成果应进行较全面的阐述,应着重指出本研究内容中的创新、改进与实际应用之处。凡引用、转述、参考他人的成果或资料,均须注明出处。(4)自然科学论文应推理正确,结论清晰。2第二章牛顿法2.1第二章牛顿法原理2.1.1第二章牛顿法算法步骤牛顿法基本原理:设是二次可微实函数,.又设是的极小点的一个估计,我们把在展成Taylor级数,并取二阶近似:其中是在处的Hessian矩阵.为求的平稳点,令,即。设可逆,可得到牛顿法的迭代公式:其中是Hessian矩阵的逆矩阵. 这样, 知道后,算出在这一点处目标函数的梯度和Hessian矩阵的逆,代人,便得到后继点,用代替,再用计算,又得到的后继点.依此类推,产生序列.在适当的条件下,这个序列收敛.定理 设为二次连续可微函数, ,满足,且 存在.又设初点充分接近,使得存在,满足,且对每一个成立。有以下关系式成立则牛顿法产生的序列收敛于.我们现在来考虑牛顿法的步骤问题,首先考虑.由于已知 .那么由最优性条件,当正定时,存在,立即可得,而且由的正定性,知即为最优解.于是对于的一般函数,在的局部 ,当正定时,形成套用公式,设想能取得好的效果,这就是牛顿法,其步骤为1、 任取;2、 计算,若,则停,否则计算,令 ;3、. 正文中的相关要求如下:1)、名词术语科技名词术语及设备、元件的名称,应采用国家标准或部颁标准中规定的术语或名称。标准中未规定的术语要采用学科通用术语或名称。一些特殊名词或新名词应在适当位置加以说明或注解。采用英语缩写词时,文中第一次出现的缩写词应该用括号注明英文全文。2)、数字按国家语言文字工作委员会等七单位1987年发布的关于出版物上数字用法的试行规定,除习惯用中文数字表示的以外,一般均采用阿拉伯数字。年份一概写全数,如2005年不能写成05年。3)、表格表序一般按章编排,如第一章第一个插表的序号为“表1.1”等。表序与表名之间空一格,表名中不允许使用标点符号,表名后不加标点。表序与表名置于表上居中。数字空缺的格内加“一”字线(占2个数字),不允许用“”或“同上”之类的写法;表内文字一律用5号仿宋体。表中若有附注时,用5号仿宋体写在表的下方,句末加标点。仅有一条附注时写成:注:;有多条附注时,附注各项的序号一律用阿拉伯数字,例如:注1:。表3.1 示例表一项目1项目2项目3项目4项目5内容1内容2内容3内容4内容5内容1内容2内容3内容4内容5注1:注释1;4)、图毕业论文(设计)的插图应与文字紧密配合,文图相符,内容正确。选图要力求精练。(1)制图标准插图应符合国家标准及专业标准。机械工程图:采用第一角投射法,严格按照GB44574460-84,GB131-83机械制图标准规定。电气图:图形符号、文字符号等应符合有关标准的规定。流程图:原则上应采用结构化程序并正确运用流程框图。对无规定符号的图形应采用该行业的常用画法。(2)图题及图中说明图号按章编排,如第一章第一图的图号为“图1.1”等。图题置于图下居中,用5号宋体。有图注或其他说明时应置于图题之上,用5号仿宋体。图名在图号之后空一格排写。引用图应说明出处,在图题右上角加引用文献号。图中若有分图时,分图号用(a)、(b)等置于分图之下。图中各部分说明应采用中文(引用的外文图除外)或数字项号,各项文字说明置于图题之上(有分图题者,置于分图题之上)。示例如图2.1所示。注:此图用于说明问题,这一行的缩进可自己调节图2.1 示例图(3)插图编排插图与其图题为一个整体,不得拆开排写于两页。插图处的该页空白不够排写该图整体时,可将其后文字部分提前排写,将图移至次页最前面。(4)论文原件中照片图及插图毕业论文(设计)原件中的照片图应是数码相机拍照的照片,或是原版照片粘贴,不得采用复印方式。照片可为黑白或彩色,采用光面相纸,不宜用布纹相纸。显微组织照片必须注明放大倍数。(5)坐标与坐标单位对坐标轴必须进行说明,有数字标注的坐标图,必须注明坐标单位。5)、物理量名称、符号与计量单位(1)物理量的名称和符号物理量的名称和符号应符合GB31003102-86的规定。论文中某一量的名称和符号应统一。(2)物理量计量单位物理量计量单位及符号应按国务院1984年发布的中华人民共和国法定计量单位及GB31003102执行,不得使用非法计量单位及符号。计量单位符号,除用人名命名的单位第一个字母用大写之处,一律用小写字母。表达时刻时应采用中文计量单位,如“上午8点3刻”,不能写成“8h45min”。6)、外文字母的正、斜体用法物理量符号、物理常量、变量符号、生物拉丁文用斜体,计量单位等符号均用正体。7)、公式公式应另起一行写在稿纸中央,公式和编号之间不加虚线。公式较长时最好在等号“=”处转行,如难以实现,则可在、×、÷运算符号处转行,运算符号应写在转行后的行首,公式的编号用圆括号括起来放在公式右边行末。公式序号按章编排,如第一章第一个公式序号为“(1.1)”,附录A中的第一个公式为“(A1)”等。文中引用公式时,一般用“见式(1.1)”或“由公式(1.1)”。8)、注释毕业设计(论文)中有个别名词或情况需要解释时,可加注说明。注释一律用页末注,即将注文放在加注页稿纸的下端,而不用行中注(夹在正文中的注)和 篇末注(将全部注文集中在文章末尾)。若在同一页中有两个以上的注时,按各注出现的先后,须按序编列注号。注释的注号左顶格,并用数字加圆表示,如,应与正文中的指示序号和格式一致。注释只限于写在注释符号出现的同页,不得隔页。3第三章拟牛顿法条件3.1第三章拟牛顿法原理3.1.1第三章拟牛顿法步骤前面介绍了牛顿法,它的突出优点是收敛很快.但是,运用牛顿法需要计算二阶便导数,而且目标函数的Hessian矩阵可能非正定.为了克服牛顿法的缺点,人们提出了拟牛顿法.它的基本思想是用不包含二阶导数的矩阵近似牛顿法中的Hessian矩阵的逆矩阵.由于构造近似矩阵的方法不同,因而出现不同的拟牛顿法.经理论证明和实践检验,拟牛顿法已经成为一类公认的比较有效的算法.下面分析怎样构造近似矩阵并用它取代牛顿法中的Hessian矩阵的逆.前面已经给出牛顿发的迭代公式,即其中是在点处的牛顿方向:是从出发沿牛顿方向搜索的最优步长.为构造的近似矩阵,先分析与一阶导数的关系.设在第k次迭代后,得到点,我们将目标函数在点 展成Taylor级数,并取二阶近似,得到由此可知,在附近有令,则记作,则有又设Hessian矩阵可逆,则这样,计算出后,可以根据,估计在处的Hessian矩阵的逆.因此,为了用不包含二阶导数的矩阵取代牛顿法中的Hessian矩阵 的逆矩阵,有理由令满足这个式子有时称为拟牛顿条件. 拟牛顿法(Quasi-Newton Methods)是求解非线性优化问题最有效的方法之一,于20世纪50年代由美国Argonne国家实验室的物理学家W. C. Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R. Fletcher和M. J. D. Powell证实了这种新的算法远比其他方法快速和可靠,使得非线性优化这门学科在一夜之间突飞猛进。在之后的20年里,拟牛顿方法得到了蓬勃发展,出现了大量的变形公式以及数以百计的相关论文。 拟牛顿法和最速下降法(Steepest Descent Methods)一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化,构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法,尤其对于困难的问题。另外,因为拟牛顿法不需要二阶导数的信息,所以有时比牛顿法(Newton's Method)更为有效。如今,优化软件中包含了大量的拟牛顿算法用来解决无约束,约束,和大规模的优化问题。 现在确定的一种自然想法,是将 作为的近似来构造.于是注意到的对称矩阵,且有近似关系式 即 若记,因此要求满足条件1、 对称;2、 满足拟牛顿方程 . 另外,再设想是由经过简单修正而得到的,即设 校正矩阵自然应是对称矩阵,由满足 满足这个式子的对称矩阵有无穷多个,因此拟牛顿算法是一族算法,最简单的算法DFP算法是目前无约束极小问题最有效的方法之一.DFP算法设校正矩阵的形式为 (1)其中为待定参数,为待定向量.这种形式显然是对称的。于是再利用你牛顿方程来确定.把(1)代入有 (2)简单的做法是取 (3)就能使(2)式成立.注意到和为数,因此为使(3)成立的简单做法是取 , ,因此DFP算法中的公式为 (4)DFP算法的步骤为1、 任取;2、 若,则停;否则令 ,由线搜索求得;3、 计算 4、例1 用DFP算法求解,取.解:取时,DFP法的第一步与最速下降法相同,以下作第二次迭代 , ,所以 , .令 ,利用,求得,所以 .因,于是停,即为最优解.例2 用DFP方法求解下列问题: 初始点及初始矩阵分取为 解:第一次迭代在处的梯度及搜索方向为 从出发沿作一维搜索,求最优步长: 得到,因此沿方向搜索得到的点及在此点目标函数的梯度为 , 第二次迭代:令 计算矩阵及搜索方向: 从出发沿作一维搜索 得到,经第2次迭代得到的点及在此点目标函数的梯度分别为 因此,为最优解.对于正定二次函数,可以证明,DFP方法中构造出来的搜索方向是一组共轭方向,因此DFP方法具有正定性和二次终止性.那么,我们知道了,拟牛顿法集中了许多算法的长处,它的主要缺点就是所需存储量较大.例3 用DFP算法求解,取,给定解:1、 求迭代点,令得的最小值点=0.02, 由DFP修正公式有=下一个搜索方向:2、 求迭代点,令得的最小值 所以, 表1 最速下降法结果表02.005224100100.0810411.8501.920-0.0033.84-0.1543.8433.68720.0710.0710.0710.1423.53.5470.13130.0660.068-0.0000.136-0.0050.1360.00046340.0030.0030.0030.0050.1260.1260.000164从表1计算结果可以看出,最速下降法在迭代的开始几步,步长较大,自变量的改变和函数值的下降速度大,本题最优点的精确值,.经过三次迭代以后已基本接近最优点,但是当接近最优点时,步长、自变量的改变越来越小,目标函数值的下降也越来越慢. 表2 DFP法结果表00.02224100100.210410.51.9203.8403.843.6862000.07750.00150.075754第四章收敛性原理4.1第四章二级标题4.1.1第四章三级标题单击输入正文内容5第五章标题5.1第五章二级标题5.1.1第五章三级标题单击输入正文内容6第六章标题6.1第六章二级标题6.1.1第六章三级标题单击输入正文内容对工程技术专业的毕业设计论文,测试数据是不可缺少的。通过测试数据,论文工作的成效就可一目了然。根据课题的要求,可以在实验室环境下测试,也可以在工作现场测试。 在论文中,要将测试时的环境和条件列出,因为任何测试数据都与测试的环境和条件相关,不说明测试条件的数据是不可比的,因此也是无意义的。 测试一般包括功能测试和性能测试。功能测试是将课题完成的计算机软硬件系统(子系统)或应用系统所要求达到的功能逐一进行测试。性能测试一般是在系统(子系统)的运行状态下,记录实例运行的数据,然后,归纳和计算这些数据,以此来分析系统运行的性能。 测试实例可以自己设计编写,也可以选择学科领域内公认的、有一定权威性的测试实例或测试集。原则是通过所选择(设计)的实例的运行,既能准确反映系统运行的功能和性能,与同类系统又有可比性。只有这样,论文最后为自己工作所作的结论才有说服力。7结束语单击插入结束语内容要求:这一节篇幅不大。首先对整个论文工作作简单小结,然后将自己在研究开发工作中所作的贡献,或独立研究的成果列举出来,再对自己工作的进展、水平作一个实事求是的评论。但在用“首次提出”