无约束最优化问题无导数解法[文献综述].doc

1、 毕业论文文献综述 信息与计算科学 无约束最优化问题无导数解法 一、 前言部分 在科学研究和工程应用中，涉及到各类工程、军事、生产、管理、经济等领域内实用性非常强。最优化方法已成为许多工程技术人员、管理工作者和研究人员的必备工具。 最优化理论与算法是一个重要的数学分支，它所研究的问题是讨论在众多的设计方案中什么样的方案最优以及怎样找出最优方案。这类问题普遍从在在实际生活当中，例如，工业设计中怎么样选择设计参数，使得设计方案满足设计要求，又能降低成本；资源分配中，怎样分配有限资源，才能使得分配方案既能满足各方 面的基本要求，又能获得好的经济效益；生产评价安排中，选择怎样的计划方案才能提高产值和利

2、润；原料配比问题中，怎样确定各种成分的比例，才能提高质量，降低成本；建设规划中，怎样安排工厂、机关、学校、商店、医院、住户和其他单位的合理布局，才能方便群众，有利于城市各行各业的发展；农田规划中，怎样安排各种农作物的合理布局才能保持高产稳产，发挥地区的优势；在军事战斗指挥中，怎样确定最佳作战方案，才能有效的歼灭敌人，保存自己的实力，而有利于整场战斗的全局，诸如此类，不胜枚举。最优化这一数学分支，正是为这些问题的解决提供理论 基础和求解方法，它是一门应用广泛、实用性很强的学科。 在上面的选题背景中，我们可以看出最优化设计在实际生活中的应用非常的广泛，我们可以通过数值最优化中的基础知识和计算方法来

3、解决实际生活中问题，运用科学的计算方法和网络编程来使我们的工作变得更加效率、科学。下面我们通过以下实例来体会下最优化设计能给我们带哪些方便。 无约束最优化问题的一般数学模型为： )(min xf , nRx 解 这两个问题我们要用到以下无约束优化问题的解法： Powell直接法 轴向搜索法， 黄金分割法 在经济中，我们需要将一些很复杂的问题通过无约束最优化无导数算法来实现，显然，在函数 )(min xf 中的 x 是不受约束的，并且 )(xf 是很复杂的，没规律的，不可能求导数的 ，那么对于这样的问题的解决，我们可以用上面说的方法来解。对于一些从在约束条件的，比如 )(min xfnRx ，

4、,0)( ,0)(xc xcii,ii 我们也可以把它们化成这种形式来计算。 通过 将 目标函数和 嵌入 约束 条件的罚 函数 相 结合，我们可以通过求解 一个序列的 无约束问题。例如， 只有等式约束条件 ，我们可以定义 罚 函数 为 i i xcuxf )(21)( 2 其中 u 0作为 罚 参数 ， )(xci 为约束条件。 然后，我们 对这一序列逐渐增加的 u求解这个无 约束 函数 ，直到 能达到 约束优化问题解 的足够精确 。 如果我们使用一个精确 的罚 函数，可能 只要解一个 无约束最小化 问题就可以求 解 有约束的最优化问题了 。对于等式约束问题， 令 i i xcuxf ,)(1

5、)( 其中 u 取某个充分小的正常数 ，就能获得 一个精确 惩罚 函数。然而，精确 惩罚 函数通常是不可微，并 且它们的极小化 需要 求解一个序列的子问题。 在 障碍 方法 中 ，我们 在目标函数中 添加 一项，当 x 在可行域内部时，此项是微不足道的；当 x 趋于边界时，它趋于零 。 举例来说，如果 )(min xfnRx中 )(xci 是 只有 不等式约束 条件时 ， 对数障碍函数有如下形式 i i xcuxf )(lo g)( ， 其中 u 0 被称为 障碍 参数。 当 ,0u 时在一定条件下 可 以 证明这个函数的极小化子趋于 原 来 约束问题的解。同样，通常的策略是 对一个 递减序列

6、 u 求 近似极小化子 。 在增强拉格朗日方法 中 ，我们定义一个函数， 当只有等式约束条件时， 所谓的增广拉格朗日函数具有以下的 形式： i i iii xcxcxfx )(21)()(;, 2A ）（ 固定 为最优拉格朗日乘子的某个估计和 为某个正数，然 后找到 A 的一个近似极小化子 x ， 这个新的 x 用于更新 ， 可能会降低，并重复这个过程 。 后来我们发现，这种方法避免了以上讨论的 障碍函数方法中求解极小化子的一些数值困难。 在 序列 线性 化 约束方法 中 ， 在每个迭代步 我们 极小化一个带 线性化约束 条件的 拉格朗日函数 。这种 方法 主要 用于 求 解大 规模 问题 这

7、样，我们可以通过加 一个罚函数来把有约束的优化问题化成无约束的优化问题来解决。 主题部分 2.1 MATLAB 软件简介 MATLAB是一个基本的应用程序， 是一种面向科学和工程计算的高级语言，通过对现实生活中的问题进行编程，并创建 M文件运行得到结果，整个计算过程和编程过程非常便捷。所以我们的目的就是运用 MATLAB 软件对对现实中经济学问题进行编程并得到解。 MATLA有一个称为标准工具箱的巨大程序模块库。 MATLAB工具箱包括解决实际问题的扩展库，如：求根、插值、数值积分、线性和非线性方程组求解以及常微分方程组求解。由于 继承了 LINPACK、 EISPACK 和 LAPACK 的

8、特性， MATLAB 对数值线性代数来说是一个高可靠的优化系统。许多数值作业能够用线性代数语言精确地表示。 MATLAB 和线性代数的密切关系是程序员能够用很短的 MATLAB语言来解决复杂的数值作业。标准工具箱还包括数据可视化的扩展图形库，有简单的点、线和复杂的三维图形和动画。所有的 MATLAB 程序都可以使用这些函数，这样就可以在所有程序和程序集中分析并生成达到出版质量的图示。对图形的快速访问能有效地提高用户的效率。诊断点有助于调试程序和检验算法是否正确执行。低级 的图形函数为自定义图形用户接口的分析代码提供了扩展空间。除了标准工具箱，可以使用其他的工具箱，如：信号处理、图像处理、优化、

9、统计分析、偏微分方程的求解和许多数值计算的应用。 MATLAB语言的主要特点可概括如下： （ 1） 简单易学，使用方便 MATLAB 被称为 “ 草稿式 ” 语言，这是因为其函数名和表达更接近我们书写计算公式的思维表达方式， 编写 MATLAB 程序犹如在草稿纸上排列公式与求解问题 因此可以快速地验证工程技术人员的算法。此外 MATLAB 还是一种解释性语言不需要专门的编译器。 （ 2） 强大的图形技术 MATLAB 具有非常强大的以图形化显示矩阵和数组的能力，同时它能给这些图形增加注释并且打印这些图形。 MATLAB 的图形技术既包括一些可以方便产生二维、三维科技专业图形的高级绘图函数，又包

10、括一些可以让用户灵活控制图形特点的低级绘图命令。另外，用户还可以利用 MATLAB 的句柄图形技术创建图形用户界面。 (3) 编程效率极高 MATLAB 是一种面向科学和工程计算的高级语言。它以矩阵运算为基础，极少的代码即可实现复杂的功能。 (4) 可扩充性强，具有方便的应用程序接口 MATLAB 不仅有着丰富的库函数， 在进行复杂的数学运算时可以直接调用而且用户还可以根据需要方便地编写和扩充新的函数库。通过混合编程用户可以方便地在 MATLAB 环境中调用其他用 Fortran 或者 C 语言编写的代码，也可以在 C 语言或者 Fortran 语言程序中调用 MATLAB 计算引擎来执行 M

11、ATLAB 代码。 2.2 现实经济当中的问题分析 现实社会中，比如经济领域，军事领域，生产领域等等，最优化问题则是我们经常会见到的，也是非常棘手的问题。怎样处理问题才能设计出最优化的方案来，这也是很多投资者，职权这，厂家所关心的问题。为此本论文将 讨论无约束最优化中最为常见的无导数算法，并以经济实例来说明他的优点。 我们都知道，对于一项工程，一次生产等经济运行中，成本的控制非常重要的，也受到了管理者的高度重视，因为成本的控制直接的很明显的影响着利润的高低，那么我们看看下面这个问题： 在一个生产项目中，一年的机器折旧费用、机器维护费、工人薪水等为 8万元支出，项目期间对于没用材料的变卖的利润与

12、总的材料量的比例为 5，材料的费用和材料的量 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 ，各次循环迭代的计算结果如下图： 区间缩

13、短次数 a 0.382 0.618 b 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.5

14、44 2.495 2.514 6.6253 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 。

15、2.3 无约束最优化问题无导数的几种方法 （ 1） Powell 直接法 取初始点 nRx )0( ，精度 0，给定 n 个线性无关向量 1,.1,0,)( nid i . 令 k ： =0. 从 )0(x 出发，一次沿 )1()1()0( , nddd 进行精确线性搜索得 , )()2()1( nxxx 即 ),(m in)( )()()()( iiRaiii adxfdaxf .1,1,0,)()()1( nidaxx iiii 令 .)0()()( xxd nn 若 )(nd ，则得解 )(nx ，否则，从 )(nx 出发，沿 )(nd 进行精度线性搜索得 )1(nx 。 由下面算法 )

16、()(m a x)()( )1()(10)1()( iiniii yfyfyfyf计算最大下降量所确定的指标 t 如果 ）（）（ )()(2)2()(2)( )1()(0)()()0( itnn yfyfyyfyfyf 成立，则 )0(x ： = kxn ,)1( ： = 1k ，转步 2. 令 )( itd ： = )1( itd ， )0(,1,1,0 xtni ： = kxn ,)1( ： = 1k 。转步 2. 依次重复上面的，知道得到满足要求的解。 （ 2）轴向搜索法 取初始点 nRx )0( ，初始步长 0，步长 缩减因子 )1,0( ，步长加速因子 0 ，精度 0。给定 n个坐标

17、轴向量 1,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. 若 ，则

18、得解 )(kx ，否则，令 0:,1:,:,:,: )()1()()0( jkkxxxy kkk 转向步 2.则依次循环，直到得到最优解。 （ 3）黄金分割法 黄金分割法是优化计算中的经典算法 , 以算法简单、效果显著而著称 , 是许多优化算法的基础 ,但它只适用于一维区间 ba, 上的凸函数 。 其基本思想是 : 依照“去坏留好”原则、对称原则、以及等比收缩原则来逐步缩小搜索范围 。 具体地说 , 就是在区间 ba, 中取点 )(6 1 8.0),(3 8 2.0 21 abaxabax 。 如果)(1xf )(2xf 则令 1xa , 重新开始 。 如果 )()( 21 xfxf 则令 2

19、xb , 重新开始 。这样每次可将搜索区间缩小 0. 382倍或 0. 618倍 。 直至缩为一点。这是一个收敛速度很快的一维搜索方法 。 正是受这一算法的启发我们这里将这一方法推广到二维和三维 空间 。 本法是受黄金分割法的启发而产生的 , 简单地说 , 是黄金分割法在平面上推广 , 正因为如此 , 它和黄金分割法一样 , 具有简单、快捷的特点 , 当然本法同样也只适用于单峰凸 (或凹 )函数 。 其基本思想是 : 将可行的平面矩形区域 dycbxayx ,D ）（ 在纵横两个方向分别以 0. 382 和 0. 618 将其分割 , 如图 1所示 , 将 D 分为九个小矩形 。 逐个判断各小

20、矩形形心的函数值 , 如果该点函数值小于四角的函数值 , 则将该小矩形作为新的搜索区重新开始 。 如果各小矩形形心的函数值均不能小于四角的函数 值则 , 选十六个节点中函数值最小者为新的形心构造一个面积大约为原矩形五分之二大的矩形 , 重新开始 。 当然这里我们要求新矩形的顶点必须保证不超出原矩形所界定的区域 , 即 : 都保持在可行区域之内 。 如果超出可行区 , 则以该矩形与边界线的交点为相应的顶点 。 如果最小点在角上 , 一样办理 。 只是如果新矩形的某一角超出可行区的角则以可行区的角为相应的角 。 具体地说 , 如果 1a 处最小 , 则新的矩形区域为 : 以 1a 点为心 , 水平

21、长为 a , 2p 之间距离 , 垂直高为 a , 7p 之间距离的矩形 。 如果 1b 处最小 , 则新的矩形区域为 : 以 1b 点为心 , 水平长为 2p , b 之间距离 , 垂直高为 b , 4p 之间距离 。 如果a 处最小则新矩形为 a , 2p , 1c , 7p 等等 。 如此类推 ， 如此一直做去直至矩形收缩到所需的范围之内 。 如果不幸 , 恰好 16个节点处的函数值都相等 ， 那我们就将这九个矩形都再做一次分割 , 找出一个最小点 ， 如果还是不幸 , 第二次分割后 所有节点处的函数值仍然都相等 , 我们继续进行分割 , 直到每个矩形的直径都小于某个给定的数 (或规定达

22、到某一个分割次数 )， 则我们可以断定该函数是一个平行于 yx0 坐标面的平面 , 即可结束运算 。 对于上述做法也许有人会提出这样的疑问 : 如果目标函数出现一道深沟怎么办 , 这样一来有可能四角 的函数值虽然大于中心的函数值 , 但真正的最小值实际上在所讨论的矩形之外 。 对于这一疑问 , 我们也考虑到了 。 实际上 , 我们这里的矩形是可以在可行区内移动的 , 所以当上述情况出现时 , 我们依然缩小 矩形 ,当矩形小到一定程度时 , 矩形中的最小值就一定会移到边上的 (否则最小值就在矩形中 ) , 这时我们再做出的下一级矩形就会向边上移动 , 直至最小值重新回到矩形中 。 总结部分 本论

23、文首先讨论了无约束最优化问题无导数解法在实际生活中的重要性，初步对最优化问题到底表现在那些方面作了简单的介绍，然后又介绍了最优化算法的基本形式。它 涉及到各类工程、军事、生产、管理、经济等领域内，实用性非常强，也理所当然的成为许多工程技术人员、管理工作者和研究人员的必备工具。接着我们又介绍了 MATLAB软件的特点和使用方法，初步 了解了 MATLAB的基本情况， MATLAB一开始 是 专门用于矩阵数值计算的软件，随着 MATLAB 主见市场化，MATLAB不仅具有了数值计算功能，而且具有了数据可视化功能。下来我们具体的用一个例子来说明 无约束最优化问题无导数解法在实际生活中具体的表现和我们

24、怎么运用这些方法来解决他，初步分析并列出方程，然后运用具体方法来得出最后的最优化的方案。 最后，我们非常具体的说明了无约束最优化问题无导数解法的三种方法，Powell直接法、轴向搜索法、黄金分割法。最优化方法是应用数学的一个分支，又是现代工程分析最佳设计四种 主要方法之一，最优化方法能获得明显的经济意义、技术价值和管理效益。 参考文献 1 李董辉 ,童小娇，万中编 .数值最优化 M.北京 :科学出版社 ,2005.5. 2 易大义 ,陈道琦 .数值分析引论 M. 浙江：浙江大学出版社 ,1998.9. 3汪卉琴，刘目楼 .数值分析 M.冶金工业出版社， 2003. 4陈宝林编著 最优化理论与算

25、法 M 北京 清华大学出版社， 1999. 5何坚勇编著 最优化方法 M 北京 清华大学出版社， 1999. 6唐焕文，秦学志 .编著 M 大 连 大连理工大学出版社， 2004. 7曹卫华，郭正 最优化技术方法及 MATLAB 的实现 北京 化学工业出版社， 2005. 8朱德通 最优化模型与试验 上海 同济大学出版社， 2003. 9阳明盛，罗长童 最优化原理及求解软件 科学出版社， 2988. 10邓扬 无约束最优化计算方法 北京 科学出版社， 1982. 11杨冰 实用最优化方法及计算机程序， 西安 西安交通大学出版社， 1988. 12R.K.AHUJA,T.L.MAGNANTI,J

26、.B.Orln,NetworkFlows:Theory,Algorithms,and Applications,Prentice-Hall,Englewood Cliffs,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.