数学与应用数学毕业论文（设计）-最优化问题的拟牛顿法.doc

学科分类号 本科生毕业论文(设计)题目（中文）：最优化问题的拟牛顿法（英文）： 学生姓名： 学号： 9 系别：数学系 专业：数学与应用数学系 指导教师：起止日期：2012.032011.042012年 4月1日怀化学院本科毕业论文(设计)诚信声明作者郑重声明：所呈交的本科毕业论文(设计)，是在指导老师的指导下，独立进行研究所取得的成果，成果不存在知识产权争议。除文中已经注明引用的内容外，论文不含任何其他个人或集体已经发表或撰写过的成果。对论文的研究做出重要贡献的个人和集体均已在文中以明确的方式标明。本声明的法律结果由作者承担。本科毕业论文（设计）作者签名：年 月 日目录摘要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 methodabstract(小四号 times new roman 体) 英文摘要应与中文摘要一致，符合英语语法，文字表达自然流畅。key words(小四号 times new roman 体) 英文的关键词应与中文关键词一致231前言首先阐明选题的背景和选题的意义。选题需强调实际背景，说明在计算机研究中或部门信息化建设、管理现代化等工作中引发该问题的原因，问题出现的环境和条件，解决该问题后能起什么作用等。结合问题背景的阐述，使读者感受到此选题确有实用价值和学术价值，确有研究或开发的必要性。 前言部分常起画龙点睛的作用。选题实际又有新意，意味着研究或开发的方向对头，设计工作有价值。对一篇论文来说，前言写好了，就会吸引读者，使他们对你的选题感兴趣，愿意进一步了解你的工作成果。前言应对与选题相关的国内外文献进行综述。主要内容包括：选题的背景及目的；国内外研究状况和相关领域中已有的成果；尚待进一步研究和解决的问题；设计和研究方法等。引言或前言一般不应少于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)一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法(newtons 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结束语要求：这一节篇幅不大。首先对整个论文工作作简单小结，然后将自己在研究开发工作中所作的贡献，或独立研究的成果列举出来，再对自己工作的进展、水平作一个实事求是的评论。但在用“首次提出”、“重大突破”、“重要价值”等自我评语时要慎重。参考文献1 孙发军基于层次型无线传感器网络的密钥管理协议研究d长沙：湖南大学，2007：57-602 william stallings密码编码学与网络安全-原理与实践第4版m北京：电子工业出版社，2006：240-2633 孙发军，吴昊一个基于tossim的异构传感器网络仿真方案j北京：计算机仿真，2007，24(10)：126-1304 haowen chan，adrian perrig，dawn songkey distribution techniques for sensor networksdwashington：carnegie mellon university，2002：1-275 sencun zhu，sanjeev setia，sushil jajodialeap: efficient security mechanisms for large-scale distributed sensor networksaproceedings of the 10th acm conference on computer and communications securitycwashington, usa：acm press，2003：62-726 intel corpintel imotes and wireless sensor networksol /research/downloads/snoverviewcd.pdf，20057 8 9 10 要求如下：中外文的参考文献应按照规范列举在论文最后。这一部分的编写反映作者的学术作风。编写参考文献要注意：（1）要严格按照规范编写，特别是外文文献，不要漏写、错写；（2）论文内容和参考文献要前后对应，正文中凡引用参考文献的地方应加注；（3）列出的文献资料应与论文课题相关，无关的文献只会使读者感到你的研究目标很分散；（4）选择的参考文献应主要是近期的。参考文献的著录应符合国家有关标准（按gb771487文后参考文献著录格式执行）。参考文献的序号左顶格，用数字加方括号表示，如1，2，3，每一参考文献条目的最后均以“.”结束。一篇论著在论文中多处引用时，在参考文献中只应出现一次，序号以第一次出现的为准。各类参考文献条目编排格式及示例如下：（1）期刊文章序号主要责任者文献题名j刊名，出版年份，卷号(期号)：起止页码例如：1毛峡，丁玉宽图像的情感特征分析及其和谐感评价j电子学报，2001，29(12a)：1923-19272mao xia, et a1affective property of image and fractal dimensionjchaos，solitons&fractalsuk，2003：v15905910（2）专著序号主要责任者文献题名m出版地：出版者，出版年：起止页码例如：3刘国钧，王连成图书馆史研究m北京：高等教育出版社，1979：15-18，314tparsons, the social system, new york：free press, 1961,p36-45.（3）会议论文集序号主要责任者文献题名a论文集名c出版地：出版者，出版年：起止页码例如：5毛 峡绘画的音乐表现a中国人工智能学会2001年全国学术年会论文集c北京：北京邮电大学出版社，2001：739740（4）学位论文序号主要责任者文献题名d保存地：保存单位，年份例如：6张和生地质力学系统理论d太原：太原理工大学，1998（5）报告序号主要责任者文献题名r报告地：报告会主办单位，年份例如：7冯西桥核反应堆压力容器的lbb分析r北京：清华大学核能技术设计研究院，1997（6）专利文献序号专利所有者专利题名p专利国别：专利号，发布日期例如：8 姜锡洲一种温热外敷药制备方案p中国专利：881056078，1983-08-12（7）国际、国家标准序号标准代号，标准名称s出版地：出版者，出版年例如：9gbt161591996，汉语拼音正词法基本规则s北京：中国标准出版社，1996（8）报纸文章序号主要责任者文献题名n报纸名，出版日期(版次)例如：10毛峡情感工学破解舒服之迷n光明日报，2000-4-17(bi)（9）电子文献序号主要责