1、 本科毕业论文（设计） （ 20 届） 无约束最优化问题无导数解法 所在学院 专业班级 信息与计算科学 学生姓名 学号 指导教师 职称 完成日期 年 月 摘要 :本文首先 介绍了无约束最优化问题的产生背景和对人们生活的影响，即他的意义 ，例如，经济上、军事上、生产等方面 都有广泛的应用。介绍了无约束最优化问题比较常用的三种无导数解法，即 Powell直接法、 Hookes-Jeeves算法和黄金分割法。其中 Powell直接法和 Hookes-Jeeves算法从某个给定初始点和初始方向开始，通过不断的调整搜索方向来达到最优解，与此不同的是黄金分割法按照黄金分割比例来分割初始区间，从而一步步缩小
2、，最终求得结果。这些算法不仅可以求解无约束的最优化问题，也可以把有约束的最优化问题转化成无约束的问题然后求解。最后利用MATLAB编写三种算法的求解程序，通过数值结果比较方法的优劣。 关键词 :无约束最优化 ； Powell直接法； Hookes-Jeeves算法；黄金分割法 Some Derivative-free Methods of Unconstrained Optimization Problems Abstract： Firstly of all, thesis introduces the background of the unconstrained optimization
3、problems and impact of peoples lives. In practical life, we can find a lot of examples of optimization problems. For example, economic, military, production and other aspects related in this area. We introduce three derivative-free method for unconstrained optimal problems, Powell direct method, Hoo
4、kes-Jeeves method, golden section method. Powell direct method and Hookes-Jeeves method are similar, both have to give an initial point and an initial iterative direction. But the principle of the golden section method is different. The above three algorithms used to solve unconstrained optimal prob
5、lem, but also can solve constrainted optimization problems, constrainted optimization problem can also be transformed into unconstrained problems, then solved by derivative-free methods. Finally, we show the advantages and disadvantages of derivative-free methods by some numerical examples. Keyword:
6、 Unconstrained optimization; Powell direct method; Hookes-Jeeves method; Golden section method 目录 1 绪论 . 1 1 1 问题的背景、意义 . 1 1.1.1 背景 . 1 1.1.2 意义 . 1 2 MATLAB软件介绍 . 4 2.1 MATLAB介绍 . 4 3 无约束最优化问题的无导数解法 . 6 3.1 Powell直接法 . 6 3.2 Hookes-Jeeves 算法 . 6 3.3 黄金分割法 . 7 4 数值算例 . 9 4.1 用黄金分割法解无约束最优化问题 . 9 4.2
7、 用 Powell直接法解无约束最优化问题 . 11 4.3 用 Hookes-Jeeves 算 法解无约束最优化问题 . 12 5 结论 . 14 致 谢 . 16 参考文献 . 17 附录 1 黄金分割法的 Matlab 程序 . 18 附录 2 Powell直接法的 Matlab程序 . 19 附录 3 Hookes-Jeeves算法的 Matlab程序 . 21 1 1 绪论 1 1 问题的背景、意义 1.1.1 背景 在科学研究和工程应用中，涉及到各类工程、军事、生产、管理、经济等领域内最优化算法实用性非常强。已成为许多工程技术人员、管理工作者和研究人员的必备工具。 最优化理论与算法
8、是一个重要的数学分支，它所研究的问题是讨论在众多的设计方案中什么样的方案最优以及怎样找出最优方案。这类 问题普遍从在于实际生活当中，例如，工业设计中怎么样选择设计参数，使得方案满足设计要求，又能降低成本；资源分配中，怎样分配有限资源，才能使得分配方案既能满足各方面的基本要求，又能获得更好的经济效益；生产评价安排中，选择怎样的计划方案才能提高产值和利润；原料配比问题中，怎样确定各种成分的比例，才能提高质量，降低成本；建设规划中，怎样安排工厂、机关、学校、商店、医院、住户和其他单位的合理布局，才能方便群众，有利于城市各行各业的发展；农田规划中，怎样安排各种农作物的合理布局才能保持高产稳产，发挥地区
9、的优势；在军事战 斗指挥中，怎样确定最佳作战方案，才能有效的歼灭敌人，保存自己的实力，而有利于整场战斗的全局，诸如此类，不胜枚举。最优化这一数学分支，正是为这些问题的解决提供理论基础和求解方法，它是一门应用广泛、实用性很强的学科。 1.1.2 意义 最优化理论与算法是一个重要的数学分支，它所研究的问题是讨论在众多的设计方案中什么样的方案最优以及怎样找出最优方案。这类问题普遍从在在实际生活当中，例如，工业设计中怎么样选择设计参数，使得设计方案满足设计要求，又能降低成本；资源分配中，怎样分配有限资源，才能使得分配方案既能满足各 方面的基本要求，又能获得好的经济效益；生产评价安排中，选择怎样的计划方
10、案才能提高产值和利润；原料配比问题中，怎样确定各种成分的比例，才能提高质量，降低成本；建设规划中，怎样安排工厂、机关、学校、商店、医院、住户和其他单位的合理布局，才能方便群众，有利于城市各行各业的发展；农田规划中，怎样安排各种农作物的合理布局才能保持高产稳产，发挥地区的优势；在军事战斗指挥中，怎样确定最佳作战方案，才能有效的歼灭敌人，保存自己的实力，而有利于整场战斗的全局，诸如此类，不胜枚举。最优化这一数学分支，正是为这些问题的解决提供理 论基础和求解方法，它是一门应用广泛、实用性很强的学科。通过运用数值2 分析，数值最优化中算法，再结合现代经济发展的状况以及结合前人所研究的成果，运用科学的方
11、法（ Powell直接法、轴向搜索法、黄金分割法等）来有效的，最优化的解决实际经济当中的问题。先大量的阅读有关资料，熟悉这些算法，并用这些算法来计算实际问题，最后通过 MATLAB 编程实现 在上面的选题背景中，我们可以看出最优化设计在实际生活中的应用非常的广泛，我们可以通过数值最优化中的基础知识和计算方法来解决实际生活中问题，运用科学的计算方法和网络编程来使 我们的工作变得更加效率、科学。下面我们通过以下实例来体会下最优化设计能给我们带哪些方便。 无约束最优化问题的一般数学模型为： )(min xf , nRx 解这两个问题我们要用到以下无约束优化问题的解法： Powell直接法 轴向搜索法
12、 黄金分 割法 在经济中，我们需要将一些很复杂的问题通过无约束最优化无导数算法来实现，显然，在函数)(min xf 中的 x 是不受约束的，并且 )(xf 是很复杂的，没规律的，不能求导数的，那么对于这样的问题的解决，我们可以用上面说的方法来求解。对于一些从在约束条件的，比如 )(min xfnRx ， ,0)( ,0)(xc xcii,ii 我们也可 以把它们化成这种形式来计算。 通过 将 目标函数和 嵌入 约束 条件的罚 函数 相 结合，我们可以通过求解 一个序列的 无约束问题。例如， 只有等式约束条件 ，我们可以定义 罚 函数 为 i i xcuxf )(21)( 2 其中 u 0 作为
13、 罚 参数 ， )(xci 为约束条件。 然后，我们 对这一序列逐渐增加的 u 求解这个无 约束函数 ，直到 能达到 约束优化问题解 的足够精确 。 如果我们 使用一个精确 的罚 函数，可能 只要解一个 无约束最小化 问题就可以求 解 有约束的最优化问题了 。对于等式约束问题， 令 3 i i xcuxf ,)(1)( 其中 u 取某个充分小的正常数 ，就能获得 一个精确 惩罚 函数。然而，精确 惩罚 函数通常是不可微，并 且它们的极小化 需要 求解一个序列的子问题。 在 障碍 方法 中 ，我们 在目标函数中 添加 一项，当 x 在可行域内部时，此项是微不足道的；当 x趋于边界时，它趋于 零
14、。 举例来说，如果 )(min xfnRx中 )(xci 是 只 有 不等式约束 条件时 ， 对数障碍函数有如下形式： i i xcuxf )(lo g)( ， 其中 u 0被称为 障碍 参数。 当 ,0u 时在一定条件下 可 以 证明这个函数的极小 化子趋于 原 来 约束问题的解。同样，通常的策略是 对一个 递减序列 u 求 近似极小 化子 。 在增强拉格朗日方法 中 ，我们定义一个 函数， 当只有等式约束条件时， 所谓的增广拉格朗日函数具有以下的 形式： i i iii xcxcxfx )(21)()(;, 2A ）（ 固定 为最优拉格朗日乘子的某个估计和 为某个正数，然后找到 A 的一个
15、近似极小化子 x ， 这个新的 x 用于更新 ， 可能会降低，并重复这个过程 。 后来我们发现，这种方法避免了以上讨论的 障碍函数方法中求解极小化子的一些数值困难。 在 序列 线性 化 约束方法 中 ， 在每个迭代步 我们 极小化一个带 线性化约束 条件的 拉格朗日函数 ，这种 方法 主要 用于 求 解大 规模 问题 。 这样，我们可以通过加一个罚函数来把有约束的优化问题化成无约束的优化问题，然后运用Powell直接法、轴向搜索法、黄金分割法三种方法解决问题。 4 2 MATLAB 软件介绍 2.1 MATLAB 介绍 MATLAB是一个基本的应用程序， 是一种 面向科学和工程计算的高级语言，
16、通过对现实生活中的问题进行编程，并创建 M文件运行得到结果，整个计算过程和编程过程非常便捷。所以我们的目的就是运用 MATLAB软件对对现实中经济学问题进行编程并得到解。 MATLA有一个称为标准工具箱的巨大程序模块库。 MATLAB工具箱包括解决实际问题的扩展库，如：求根、插值、数值积分、线性和非线性方程组求解以及常微分方程组求解。由于继承了 LINPACK、EISPACK和 LAPACK的特性， MATLAB对数值线性代数来说是一个高可靠的优化系统。许多数值作业能够用线性代数语 言精确地表示。 MATLAB和线性代数的密切关系是程序员能够用很短的 MATLAB语言来解决复杂的数值作业。标准
17、工具箱还包括数据可视化的扩展图形库，有简单的点、线和复杂的三维图形和动画。所有的 MATLAB 程序都可以使用这些函数，这样就可以在所有程序和程序集中分析并生成达到出版质量的图示。对图形的快速访问能有效地提高用户的效率。诊断点有助于调试程序和检验算法是否正确执行。低级的图形函数为自定义图形用户接口的分析代码提供了扩展空间。除了标准工具箱，可以使用其他的工具箱，如：信号处理、图像处理、优化、统计分析、偏微分 方程的求解和许多数值计算的应用。 MATLAB语言的主要特点可概括如下： （ 1） 简单易学，使用方便 MATLAB 被称为 “ 草稿式 ” 语言，这是因为其函数名和表达更接近我们书写计算公
18、式的思维表达方式， 编写 MATLAB程序犹如在草稿纸上排列公式与求解问题 因此可以快速地验证工程技术人员的算法。此外 MATLAB还是一种解释性语言不需要专门的编译器。 （ 2） 强大的图形技术 MATLAB 具有非常强大的以图形化显示矩阵和数组的能力，同时它能给这些图形增加注释并且打印这些图形。 MATLAB 的图形技术既包括一些可以 方便产生二维、三维科技专业图形的高级绘图函数，又包括一些可以让用户灵活控制图形特点的低级绘图命令。另外，用户还可以利用 MATLAB 的句柄图形技术创建图形用户界面。 (3) 编程效率极高 MATLAB 是一种面向科学和工程计算的高级语言。它以矩阵运算为基础
19、，极少的代码即可实现复杂的功能。 5 (4) 可扩充性强，具有方便的应用程序接口 MATLAB 不仅有着丰富的库函数，在进行复杂的数学运算时可以直接调用而且用户还可以根据需要方便地编写和扩充新的函数库。通过混合编程用户可以方便地在 MATLAB 环境中调用其他用 Fortran 或者 C 语言编写的代码，也可以在 C 语言或者 Fortran 语言程序中调用 MATLAB 计算引擎来执行 MATLAB代码。 6 3 无约束最优化问题的无导数解法 3.1 Powell 直接法 取初始点 nRx )0( ，精度 0，给定 n 个线性无关向量 1,.1,0,)( nid i . 令 k ： =0.
20、从 )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 。 由下面算法 )()(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. 依次重复上面的，知道得到满足要求的解。 3.2 Hookes-Jeeves 算法 取初始点 nRx )0( ，初始步长 0，步长缩减因子 )1,0( ，步长加速因子 0 ，精度 0。给定 n 个坐标轴向量 1,1,0,)( nii ，令 )0(y ： = )0(x ， ： =0， j： =0. 若 )( )()( jjyf )( )(jyf
