1、 毕业论文 开题报告 信息与计算科学 无约束最优化问题无导数解法 一、选题的背景、意义 1.选题的背景 在科学研究和工程应用中，涉及到各类工程、军事、生产、管理、经济等领域内实用性非常强。最优化方法已成为许多工程技术人员、管理工作者和研究人员的必备工具。 最优化理论与算法是一个重要的数学分支，它所研究的问题是讨论在众多的设计方案中什么样的方案最优以及怎样找出最优方案。这类问题普遍从在在实际生活当中，例如，工业设计中怎么样选择设计参数，使得设计方案满足设计要求，又能降低成本；资源分配中，怎样分配有限资源，才能使得分配方案既能满足各方面的基本要求，又能获得好的经济效益；生产评价安排中，选择怎样的计
2、划方案才能提高产值和利润；原料配比问题中，怎样确定各种成分的比例，才能提高质量，降低成本；建设规划中，怎样安排工厂、机关、学校、商店、医院、住户和其他单位的合理布局，才能方便群众，有利于城市各行各业的发展；农田规划中，怎样安排各种农作物的合理布局才能保持高产稳产，发挥地区的优势；在军事战斗指挥中，怎样确定最佳作战方案，才能有效的歼灭敌人，保存自己的实力，而有利于整场战斗的全局，诸如此类，不胜枚举。最优化这一数学分支， 正是为这些问题的解决提供理论基础和求解方法，它是一门应用广泛、实用性很强的学科。 2.选题的意义 在上面的选题背景中，我们可以看出最优化设计在实际生活中的应用非常的广泛，我们可以
3、通过数值最优化中的基础知识和计算方法来解决实际生活中问题，运用科学的计算方法和网络编程来使我们的工作变得更加效率、科学。下面我们通过以下实例来体会下最优化设计能给我们带哪些方便。 无约束最优化问题的一般数学模型为： )(min xf , nRx 解这两个问题我们要用到以下无约束优化问题的解法： Powell直接法 轴向搜索法 黄金分割法 这 3种方法是针对无约束的最优化求解，分析问题，写出求解过程，再利用MATLAB 软件编程计算结果，但是对于有约束的一类问题，我们也可以化成无约束问题来解决，例如 )(min xfnRx ， ,0)( ,0)(xc xcii,ii我们加入一个罚函数， 通过 将
4、 目标函数和 嵌入 约束 条件的罚 函数 相 结合，我们可以通过求解 一个序列的 无约束问题。例如， 只有等式约束条件 ，我们可以定义 罚 函数 为 i i xcuxf )(21)( 2 对于等式约束问题，则定义罚函数为 i i xcuxf ,)(1)( 然后用开始介绍的 3种方法来计算，这样我们就拓展了最优化算法的范围，使得实际运用时更加方便。 二、 研究的基本内容与拟解决的主要问题 2.1 MATLAB 软件 简介和经济问题分析 2.1.1 MATLAB 软件 简介 MATLAB是一个基本的应用程序， 是一种面向科学和工程计算的高级语言，通过对现实生活中的问题进行编程，并创建 M文件运行得
5、到结果，整个计算过程和编程过程非常便捷。所以我们的目的就是运用 MATLAB 软件对对现实中经济学问题进行编程并得到解。 MATLA有一个称为标准工具箱的巨大程序模块库。 MATLAB工具箱包括解决实际问题的扩展库，如：求根、插值、数值积分、线性和非线性方程组求解以及常微分 方程组求解。由于继承了 LINPACK、 EISPACK 和 LAPACK 的特性， MATLAB 对数值线性代数来说是一个高可靠的优化系统。许多数值作业能够用线性代数语言精确地表示。 MATLAB 和线性代数的密切关系是程序员能够用很短的 MATLAB语言来解决复杂的数值作业。标准工具箱还包括数据可视化的扩展图形库，有简
6、单的点、线和复杂的三维图形和动画。所有的 MATLAB 程序都可以使用这些函数，这样就可以在所有程序和程序集中分析并生成达到出版质量的图示。对图形的快速访问能有效地提高用户的效率。诊断点有助于调试程序和检验算法是 否正确执行。低级的图形函数为自定义图形用户接口的分析代码提供了扩展空间。除了标准工具箱，可以使用其他的工具箱，如：信号处理、图像处理、优化、统计分析、偏微分方程的求解和许多数值计算的应用。 MATLAB 不仅有着丰富的库函数，在进行复杂的数学运算时可以直接调用而且用户还可以根据需要方便地编写和扩充新的函数库。通过混合编程用户可以方便地在 MATLAB 环境中调用其他用 Fortran
7、 或者 C 语言编写的代码，也可以在 C 语言或者 Fortran 语言程序中调用 MATLAB 计算引擎来执行 MATLAB 代码。 2.1.2 现实经济当中的问题分析 现实社会中，比如经济领域，军事领域，生产领域等等，最优化问题则是我们经常会见到的，也是非常棘手的问题。怎样处理问题才能设计出最优化的方案来，这也是很多投资者，职权这，厂家所关心的问题。为此本论文将讨论无约束最优化中最为常见的无导数算法，并以经济实例来说明他的优点。现在我们来看在一个生产项目中，一年的机器折旧费用、机器维护费、工人薪水等为 8万元支出，项目期间对于没用材料的变卖的利润与总的材料量的比例为 5，材料的费用和材料的
8、量 x 的关系 为 2x ，合同规定 x 的范围为 71， （吨），计算 x 为多少时，成本最低。 分析：通过题目我们可以得到成本和 x 的关系为 85-)( 2 xxxf ，此问题我们可以写成： )(min xf ，其中 x 的搜索区间为 71， ，如果给出一个精度 ，我们就可以运用黄金分割法来计算此问题，解题过程如下： 解： 我们取精度为 0.1 ，那么要达到这个精度要求，区间缩短次数必须满1.0)(0 .6 1 8 abk 得 51.8618.0 )/( n abnk 取 9k ，则计算点数应为 101kn ，各次循环迭代的计算结果如下图： 区间缩短次数 a 0.382 0.618 b
9、b-a 节点坐标 函数值 节点坐标 函数值 初始区间 1 2 3 4 5 6 7 8 9 1.000 1.000 1.000 1.875 1.875 2.210 2.416 2.416 2.416 2.465 3.292 2.416 1.875 2.416 2.210 2.416 2.544 2.495 2.465 2.495 2.3773 1.7570 2.1402 1.7570 1.8343 1.7570 1.7519 1.7500 1.7512 1.7500 4.708 3.292 2.416 2.751 2.416 2.544 2.623 2.544 2.495 2.514 6.625
10、3 2.3773 1.7570 1.8128 1.7570 1.7519 1.7651 1.7519 1.7500 1.7512 7.000 4.708 3.292 3.292 2.751 2.751 2.751 2.623 2.544 2.544 6 3.708 2.292 1.417 0.876 0.541 0.335 0.207 0.128 0.079 从上表中可以看出经过 9次迭代计算后 079.0ab 小于 0.1 ，所以当 x 的取 值为 505.2)544.2465.2(21)(21 bax ， )(xf 的最优化结果为 7500.1 。 设 f ： RRn 连续可微，我们要想得
11、到如下无约束最优化问题： .),(min nRxxf 。 为了得到上面无约束问题的最优化条件，我们介绍一下几种算法： 2.2.1 Powell 直接法 对于无约束最优化问题的无导数算法中，什么是无约束了，很直观就是对函数的自变量 x 没有限制，而且对于 x 的函数是很难或者不能求解的。在这种情况下 Powell 直接法很容易的解 决了问题，那么 Powell 直接法的主要步骤如下： 取初始点 nRx )0( ，精度 0，给定 n 个线性无关向量 1,.1,0,)( nid i . 令 k ： =0. 从 )0(x 出发，一次沿 )1()1()0( , nddd 进行精确线性搜索得 , )()2
12、()1( nxxx 即 ),(m in)( )()()()( iiRaiii adxfdaxf .1,1,0,)()()1( nidaxx iiii 令 .)0()()( xxd nn 若 )(nd ，则得解 )(nx ，否则，从 )(nx 出发，沿 )(nd 进行精度线性搜索得 )1(nx 。 由下面算法 )()(m a x)()( )1()(10)1()( iiniii yfyfyfyf计算最大下降量所确定的指标 t 如果 ）（）（ )()(2)2()(2)( )1()(0)()()0( itnn yfyfyyfyfyf 成立，则 )0(x ： = kxn ,)1( ： = 1k ，转步
13、2. 令 )( itd ： = )1( itd ， )0(,1,1,0 xtni ： = kxn ,)1( ： = 1k 。转步 2. 2.2.2 轴向搜索法 轴向搜索法有 Hooke-Jeeves(1961)提出，故又 称为 Hooke-Jeeves 算法，该算法的基本思想是从某个初始点 )0(x 出发，采用固定的步长 0，依次沿坐标轴nii ,1,0,)( 的正向或反向进行试探，产生列点 )()2()1( , nyyy . 若 )( )(nyf )( )0(xf ， 则称该轮试探成功，若试探成功，则算法转入下一轮试探，即从 )()1( nyx 出发，采用固定步长 0，再依次沿坐标轴 nii
14、 ,1,0,)( 的正向或反向进行试探，若试探不成功，即 ),()( )0()( xfyf n （ 0） 则缩小试探长度 ，即令 ： = ），（ 10 ，重新进行试探，重复上述过程，知道该轮试探成功，算法的细节如下： 从初始点 )0(x 出发，沿坐标轴 )0( （的正方向）进行试探得点 )0()0()1( xy ， 若 )( )1(yf )( )0(xf （ 1） 不成立，则从 )0(x 出发沿 )0( 的反方向重新试探得点 )0()0()1( xy ，若（ 1）式不成立，则再重新赋值 )0()1( xy ，然后从 )1(y 点出发沿 )1( 的正方向或负方向得新的试探点 )1()1()2(
15、yy 。重复上述过程直至沿所有坐标的正方向或反方向都进行 一次试探。此时得点列 )()2()1( , nyyy 。 若（ 0）式成立，则该轮试探成功，令 )0(x ： = )(ny ，转入下一轮的试探，若（ 0）不成立，则令 ： = ，其中 ），（ 10 。从初始点 )0(x 出发，重复上述试探过 程，得新的点列： )()2()1( , nyyy 若（ 0）式还是不成立，则再令 ： = 。重复上述试探过程，直至该轮试探成功。 总结上述过程，轴向搜索法的具体算法步骤如下： 取初始点 nRx )0( ，初始步长 0，步长缩减因子 )1,0( ，步长加速因子 0 ，精度 0。给定 n个坐标轴向量 1
16、,1,0,)( nii ，令 )0(y ： = )0(x ， ： =0， j： =0. 若 )( )()( jjyf )( )(jyf 则令 )()()1( jjj yy 转到第 4步，否则转到第 3步。 若 )( )()( jjyf )( )(jyf 则令 )()()1( jjj yy 转到步 4，否则，令 )()1( : jj yy ，转步 4. 若 j n-1,令 j:=j+1并转步 2.否则转步 5. 若 )( )(nyf )( )(kxf ，令 ,0:,1:),(:,: )()1()1()0()()1( jkkxxxyyx kkknk 并转步 2，否则，转步 6. 若 ，则得解 )(
17、kx ，否则，令 0:,1:,:,:,: )()1()()0( jkkxxxy kkk 转向步 2.则依次循环，直到得到最优解。 2.2.3 黄金分割法 黄金分割法是优化计算中的经典算法 , 以算法简单、效果显著而著称 , 是许多优化算法的基础 ,但它只适用于一维区间 ba, 上的凸函数 。 其基本思想是 : 依照“去坏留好”原则、对称原则、以及等比收缩原则来逐步缩小搜索范围 。 具体地说 , 就是在区间 ba, 中取点 )(6 1 8.0),(3 8 2.0 21 abaxabax 。 如果)(1xf )(2xf 则令 1xa , 重新开始 。 如果 )()( 21 xfxf 则令 2xb
18、, 重新开始 。这样每次可将搜索区间缩小 0. 382倍或 0. 618倍 。 直至缩为一点。这是一个收敛速度很快的一维搜索方法 。 正是受这一算法的启发我们这里将这一方法推广到二维和三维空间 。 本法 是受黄金分割法的启发而产生的 , 简单地说 , 是黄金分割法在平面上推广 , 正因为如此 , 它和黄金分割法一样 , 具有简单、快捷的特点 , 当然本法同样也只适用于单峰凸 (或凹 )函数 。 其基本思想是 : 将可行的平面矩形区域 dycbxayx ,D ）（ 在纵横两个方向分别以 0. 382 和 0. 618 将其分割 , 如图 1所示 , 将 D 分为九个小矩形 。 逐个判断各小矩形形
19、心的函数值 , 如果该点函数值小于四角的函数值 , 则将该小矩形作为新的搜索区重新开始 。 如果各小矩形形心的函数值均不能小于四角的函数值则 , 选十 六个节点中函数值最小者为新的形心构造一个面积大约为原矩形五分之二大的矩形 , 重新开始 。 当然这里我们要求新矩形的顶点必须保证不超出原矩形所界定的区域 , 即 : 都保持在可行区域之内 。 如果超出可行区 , 则以该矩形与边界线的交点为相应的顶点 。 如果最小点在角上 , 一样办理 。 只是如果新矩形的某一角超出可行区的角则以可行区的角为相应的角 。 具体地说 , 如果 1a 处最小 , 则新的矩形区域为 : 以 1a 点为心 , 水平长为
20、a , 2p 之间距离 , 垂直高为 a , 7p 之间距离的矩形 。 如果 1b 处最小 , 则新的矩形区域为 : 以 1b 点为心 , 水平长为 2p , b 之间距离 , 垂直高为 b , 4p 之间距离 。 如果a 处最小则新矩形为 a , 2p , 1c , 7p 等等 。 如此类推 ， 如此一直做去直至矩形收缩到所需的范围之内 。 如果不幸 , 恰好 16个节点处的函数值都相等 ， 那我们就将这九个矩形都再做一次分割 , 找出一个最小点 ， 如果还是不幸 , 第二次分割后所有节点处的 函数值仍然都相等 , 我们继续进行分割 , 直到每个矩形的直径都小于某个给定的数 (或规定达到某一
21、个分割次数 )， 则我们可以断定该函数是一个平行于 yx0 坐标面的平面 , 即可结束运算 。 对于上述做法也许有人会提出这样的疑问 : 如果目标函数出现一道深沟怎么办 , 这样一来有可能四角 的函数值虽然大于中心的函数值 , 但真正的最小值实际上在所讨论的矩形之外 。 对于这一疑问 , 我们也考虑到了 。 实际上 , 我们这里的矩形是可以在可行区内移动的 , 所以当上述情况出现时 , 我们依然缩小矩形 ,当矩形 小到一定程度时 , 矩形中的最小值就一定会移到边上的 (否则最小值就在矩形中 ) , 这时我们再做出的下一级矩形就会向边上移动 , 直至最小值重新回到矩形中 。 三、研究的方法与技术
22、路线、研究难点，预期达到的目标 1、研究内容 （ 1）掌握 MATLAB 的基本语法、基本命令、 MATLAB函数及程序设计，学习使用 MATLAB编程来解决实际当中的最优化问题； （ 2）熟悉无约束最优化问题无导数解法的几种算法，比如 Powell直接法、轴向搜索法、黄金分割法等 ; (3)通过编程实现问题的最优解计算并进行结果的比较，选择出效 果好，跟加实用的算法。 2、研究方法及技术路线 通过运用数值分析，数值最优化中算法，再结合现代经济发展的状况以及结合前人所研究的成果，运用科学的方法（ Powell 直接法、轴向搜索法、黄金分割法等）来有效的，最优化的解决实际经济当中的问题。先大量的
23、阅读有关资料，熟悉这些算法，并用这些算法来计算实际问题，最后通过 MATLAB编程实现。 3、研究难点 （ 1）熟悉 MATLAB 和熟练的运用 MATLAB 进行编程； （ 2）要通过有创新的思维，科学的思想来相处独到的算法，来更有效的解决问题； （ 3）无约束最优化问题的 解法非常多，本论文只针对很难求导或不能求导的问题 4、预期达到的目标 通过这篇论文的撰写更加熟悉无约束最优化问题的无导数的概念和解法，掌握 MATLAB 的基本语法、基本命令和 MATLAB 函数程序设计，并能够熟练的运用MATLAB编程来解决实际当中的问题 四、论文详细工作进度和安排 第一阶段： 2010年 11月 5
24、号至 2011年 1月 10号 完成毕业论文文献检索、文献综述、外文文献翻译及开题报告。 第二阶段： 2011 年 1 月 10 号至 2011 年 3 月 11 号 完成毕业论文的数据收集，论文初稿。 第三阶段： 2011 年 3 月 11 号至 2011 年 5 月 3 号 （ 1） 进入实习单位进行毕业实习，对论文进行修改 ; （ 2） 2011 年 5 月 3 号前必须返校，完成毕业实习返校，并递交毕业实习报告，进一步完善毕业论文。 第四阶段： 2011 年 5 月 23 号至 2011 年 5 月 28 号 完成第一轮毕业论文答辩。 第五阶段： 2011 年 5 月 28 号之 20
25、11 年 6 月 3 号 第一轮答辩没通过的学生完成第二轮答辩，并随机抽取部分完成较好的毕业论文进行校级答辩。 五、主要参考文献： 1 李董辉 ,童小娇，万中编 .数值最优化 M.北京 :科学出版社 ,2005.5. 2 易大义 ,陈道琦 .数值分析引论 M. 浙江：浙江大学出版社 ,1998.9. 3汪卉琴，刘目楼 .数值分析 M.冶金工业出版社， 2003. 4陈宝林编著 最优化理论与算法 M 北京 : 清华大学出版社， 1999. 5何坚勇编著 最优化方法 M 北京 : 清华大学出版社， 1999. 6唐焕文，秦学志 .编著 M 大连 : 大连理工大学出版社， 2004. 7曹卫华，郭正
26、 最优化技术方法及 MATLAB 的实现 M 北京： 化学工业出版社， 2005. 8朱德通 最优化模型与试验 M 上海 : 同济大学出版社， 2003. 9阳明盛，罗长童 最优化原理及求解软件 M 科学出版社， 2988. 10邓扬 无约束最优化计算方法 M 北京 : 科学出版社， 1982. 11杨冰 实用最优化方法及计算机程序 M，西安 : 西安交通大学出版社，1988. 12R.K.AHUJA,T.L.MAGNANTI,J.B.Orln,NetworkFlows:Theory,Algorithms,and ApplicationsM,Prentice-Hall,Englewood Cl
27、iffs,N.J.,1993. 13 Richard L.Burden and J.Douglas, Numerical AnalysisM.Wadsworth Group. Brooks,2001. 14 Jorge Nocedal,Stephen J.Wright. Numerical OptimizationM. 影印版 .北京：科学出版社 , 2006. 15J.E.Dennis,Jr. Robert B. Schnabel. Numeical methods for unconstrained optimization and nonlinear equationsM. 影印版 .北京：科学出版社 , 2009.
