最优化方法及其应用.ppt

《最优化方法及其应用.ppt》由会员分享，可在线阅读，更多相关《最优化方法及其应用.ppt（289页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最优化（一）最优化（一）一 最优化问题总论二二 一维搜索法一维搜索法三 常用无约束最优化方法四 常用约束最优化方法五 程序设计及其他优化方法一一 最优化问题总论最优化问题总论无论做任何一件事，人们总希望以最少的代价取得最大的效益，也就是力求最好，这就是优化问题最优化就是在一切可能的方案中选择一个最好的方案以达到最优目标的学科例如，从甲地到乙地有公路、水路、铁路、航空四种走法，如果我们追求的目标是省钱，那么只要比较一下这四种走法的票价，从中选择最便宜的那一种走法就达到目标这是最简单的最优化问题，实际优化问题一般都比较复杂概括地说，凡是追求最优目标的数学问题都属于最优化问题作为最优化问题，一般要有

2、三个要素：第一是目标；第二是方案；第三是限制条件而且目标应是方案的“函数”如果方案与时间无关，则该问题属于静态最优化问题；否则称为动态最优化问题本书只讨论静态最优化问题一一 最优化问题总论最优化问题总论 最简单的最优化问题实际上在高等数学中已遇到，这就是所谓函数极值，我们习惯上又称之为经典极值问题例1.1 对边长为a的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？一一 最优化问题总论最优化问题总论解 设剪去的正方形边长为设剪去的正方形边长为x x，由题意易知，与，由题意易知，与此相应的水槽容积为此相应的水槽容积为 令令 得两个驻点：得两个驻点：一一 最优

3、化问题总论最优化问题总论 第一个驻点不合实际，这是因为剪去第一个驻点不合实际，这是因为剪去4 4个边个边 长为长为的正方形相当于将铁板全部剪去现在来判断第的正方形相当于将铁板全部剪去现在来判断第二个驻点是否为极大点二个驻点是否为极大点 因为因为 所以所以 是极大点是极大点 结论是：每个角剪去边长为的正方形可使所制成结论是：每个角剪去边长为的正方形可使所制成的水槽容积最大的水槽容积最大一一 最优化问题总论最优化问题总论例例1.21.2 求侧面积为常数体积最大的长方体体积求侧面积为常数体积最大的长方体体积解解 设长方体的长、宽、高分别为，体积设长方体的长、宽、高分别为，体积为，则依题意知体积为为，

4、则依题意知体积为限制条件为限制条件为 由拉格朗日乘数法，考虑函数由拉格朗日乘数法，考虑函数1.1 1.1 最优化问题数学模型最优化问题数学模型 令 由题意可知 应是正数，由此，将上面三个等式分别乘以 ，并利用已知条件得到1.1 1.1 最优化问题数学模型最优化问题数学模型 比较以上三式可得 从而x=y=z=a，右侧面积固定的长方体的最大体积客观存在，因此侧面积固定的长方体中以正方体体积最大一一 最优化问题总论最优化问题总论例1.3 某单位拟建一排四间的停车房，平面位置如图1.1所示由于资金及材料的限制，围墙和隔墙的总长度不能超过40m，为使车房面积最大，应如何选择长、宽尺寸？x1x2一一 最优

5、化问题总论最优化问题总论解 设四间车房长为，宽为由题意可 知面积为 且变量，应满足 即求，一一 最优化问题总论最优化问题总论最优化问题的数学模型包含有三个要求：即最优化问题的数学模型包含有三个要求：即变量（又称设计变量）、目标函数、约束条件一、变量一、变量二、目标函数二、目标函数三、约束条件三、约束条件四、带约束条件的优化问题数学模型表示形式四、带约束条件的优化问题数学模型表示形式一一 最优化问题总论最优化问题总论综上所述，全书所要讨论的问题是如下的（静态）综上所述，全书所要讨论的问题是如下的（静态）最优化问题，其表示形式有三种：最优化问题，其表示形式有三种：第一种最优化问题表示形式为第一种最

6、优化问题表示形式为 第二种最优化问题表示形式为第二种最优化问题表示形式为 一一 最优化问题总论最优化问题总论第三种最优化问题表示形式为第三种最优化问题表示形式为（1.11.1）其中其中一一 最优化问题总论最优化问题总论 上述三种表示形式中，称为集约束在所讨论的最优上述三种表示形式中，称为集约束在所讨论的最优化问题中，集约束是无关紧要的这是因为一般，不化问题中，集约束是无关紧要的这是因为一般，不然的话，通常也可用不等式约束表达出来因此今后然的话，通常也可用不等式约束表达出来因此今后一般不再考虑集约束一般不再考虑集约束 满足所有约束的点称为容许点或可行点容许点的集满足所有约束的点称为容许点或可行点

7、容许点的集合称为容许集或可行域可用合称为容许集或可行域可用 表示表示一一 最优化问题总论最优化问题总论 一般地，对于最优化问题（一般地，对于最优化问题（1.11.1）的求解，是指在）的求解，是指在可行域内找一点，使得目标函数在该点取得极小可行域内找一点，使得目标函数在该点取得极小值，即值，即 这样的称为问题（这样的称为问题（1.11.1）的最优点，也称极小点，）的最优点，也称极小点，而相应的目标函数值而相应的目标函数值 称为最优值；称为最优值；合起来称为最优解，但习惯上把本身称为最优合起来称为最优解，但习惯上把本身称为最优解最优点的各分量和最优值必须是有限数解最优点的各分量和最优值必须是有限数

8、一一 最优化问题总论最优化问题总论一、二维最优化问题的图解法 讨论二维最优化问题为 一一 最优化问题总论最优化问题总论（一）约束集合（一）约束集合l当约束函数为线性时，等式约束在坐标平面上为当约束函数为线性时，等式约束在坐标平面上为一条直线，不等式约束在坐标平面上为一半平面；一条直线，不等式约束在坐标平面上为一半平面；l 当约束函数为非线性时，等式约束条件在坐标平当约束函数为非线性时，等式约束条件在坐标平面上为一条曲线（如图），不等式约束把坐标平面面上为一条曲线（如图），不等式约束把坐标平面分成两部分当中的一部分（如图）分成两部分当中的一部分（如图）一一 最优化问题总论最优化问题总论综上所述，

9、当把约束条件中的每一个等式所确定的曲线，以及每一个不等式所确定的部分在坐标平面上画出之后，它们相交的公共部分即为约束集合D一一 最优化问题总论最优化问题总论例例1.41.4 在坐标平面上画出约束集合解解:满足的区域为以原点为圆心，半径为1的圆；满足的区域为第一象限的扇形（如图所示）一一 最优化问题总论最优化问题总论（二）等高线（二）等高线 我们知道我们知道 在三维空间中表示一在三维空间中表示一张曲面张曲面 其中其中 为常数）在三维空间中为常数）在三维空间中表示平行于表示平行于 平面的一个平面，这个平面平面的一个平面，这个平面上任何一点的高度都等于常数上任何一点的高度都等于常数 （如图）（如图）

10、在三维空间中曲面在三维空间中曲面 与平面与平面 有一条交线有一条交线 交线在平面上的投影曲线是交线在平面上的投影曲线是 ，可见曲线上的点到平面，可见曲线上的点到平面 的高度都等于的高度都等于常数常数C C，也即曲线上的的函数值都具有相同的，也即曲线上的的函数值都具有相同的值值一一 最优化问题总论最优化问题总论 当常数取不同的值当常数取不同的值时，重复上面的讨论，时，重复上面的讨论，在平面上得到一族曲线在平面上得到一族曲线等高线等高线.等高线的形状完全由等高线的形状完全由曲面的形状所决定；反曲面的形状所决定；反之，由等高线的形状也之，由等高线的形状也可以推测出曲面的形状可以推测出曲面的形状一一

11、最优化问题总论最优化问题总论例例1.51.5 在坐标平面在坐标平面 上画出目标函数上画出目标函数的等高线的等高线 解解:因为当因为当 取时，曲线表示是以原点为圆心，取时，曲线表示是以原点为圆心，半径为的圆因此等高线是一族以原点为圆半径为的圆因此等高线是一族以原点为圆心的同心圆（如图所示）心的同心圆（如图所示）一一 最优化问题总论最优化问题总论例例1.61.6 用图解法求解二维最优化问题用图解法求解二维最优化问题解解:如图，目标函数的等高线是以为圆如图，目标函数的等高线是以为圆心的同心圆，并且这族同心圆的外圈比内圈心的同心圆，并且这族同心圆的外圈比内圈的目标函数值大因此，该问题为在约束集的目标函

12、数值大因此，该问题为在约束集中找一点中找一点,使其落在半径最小的那个同心圆使其落在半径最小的那个同心圆上。问题的最优解为：上。问题的最优解为：一一 最优化问题总论最优化问题总论二、最优化问题的迭代解法（一）迭代方法 在经典极值问题中，解析法虽然具有概念简明在经典极值问题中，解析法虽然具有概念简明,计算精确等优点，但因只能适用于简单或特殊问计算精确等优点，但因只能适用于简单或特殊问题的寻优题的寻优,对于复杂的工程实际问题通常无能为力，对于复杂的工程实际问题通常无能为力，所以极少使用。所以极少使用。最优化问题的迭代算法是指：从某一选定的初最优化问题的迭代算法是指：从某一选定的初始点出发，根据目标函

13、数、约束函数在该点的某始点出发，根据目标函数、约束函数在该点的某些信息，确定本次迭代的一个搜索方向和适当的些信息，确定本次迭代的一个搜索方向和适当的步长，从而到达一个新点，用式子表示即为步长，从而到达一个新点，用式子表示即为(1.2)(1.2)一一 最优化问题总论最优化问题总论 式中式中,前一次已取得的迭代点，在前一次已取得的迭代点，在 开始计算时为迭代初始点开始计算时为迭代初始点 ；新的迭代点；新的迭代点；第第k k次迭代计算的搜索方向；次迭代计算的搜索方向；第第k k次迭代计算的步长因子次迭代计算的步长因子 一一 最优化问题总论最优化问题总论 按照式（按照式（1.21.2）进行一系列迭代计

14、算所根据）进行一系列迭代计算所根据的思想是所谓的的思想是所谓的“爬山法爬山法”，就是将寻求函数极，就是将寻求函数极小小点（无约束或约束极小点）的过程比喻为向点（无约束或约束极小点）的过程比喻为向“山山”的顶峰攀登的过程，始终保持向的顶峰攀登的过程，始终保持向“高高”的方向前的方向前进，直至达到进，直至达到“山顶山顶”当然当然“山顶山顶”可以理解可以理解为目为目标函数的极大值，也可以理解为极小值，前者称标函数的极大值，也可以理解为极小值，前者称为上升算法，后者称为下降算法这两种算法都为上升算法，后者称为下降算法这两种算法都有一个共同的特点，就是每前进一步都应该使目有一个共同的特点，就是每前进一步

15、都应该使目标函数有所改善，同时还要为下一步移动的搜索标函数有所改善，同时还要为下一步移动的搜索方向提供有用的信息如果是下降算法，则序列方向提供有用的信息如果是下降算法，则序列迭代点的目标函数值必须满足下列关系迭代点的目标函数值必须满足下列关系一一 最优化问题总论最优化问题总论 如果是求一个约束的极小点，则每一次迭代的新如果是求一个约束的极小点，则每一次迭代的新点都应该在约束可行域内，即点都应该在约束可行域内，即 下图为迭代过程下图为迭代过程一一 最优化问题总论最优化问题总论（二）收敛速度与计算终止准则（二）收敛速度与计算终止准则（1 1）收敛速度）收敛速度作为一个算法作为一个算法A A，能够收

16、敛于问题的最优解当然，能够收敛于问题的最优解当然是必要的，但光能收敛还不够，还必须能以较快是必要的，但光能收敛还不够，还必须能以较快的速度收敛，这才是好的算法的速度收敛，这才是好的算法定义定义1.1 1.1 设由算法设由算法A A产生的迭代点列产生的迭代点列 在某种在某种“|”|”的意义下收敛于点的意义下收敛于点 ，即，即 ,若存在实数若存在实数 及一个与迭代次数及一个与迭代次数 无关的无关的常数常数 使得使得 则算法则算法A A产生的迭代点列叫做具有产生的迭代点列叫做具有 阶收敛速阶收敛速度度,或算法或算法A A叫做是叫做是 阶收敛的，特别地阶收敛的，特别地 :一一 最优化问题总论最优化问题

17、总论 当当 ，迭代点列，迭代点列 称为具有线性收敛称为具有线性收敛速度或算法速度或算法A A称为线性收敛的称为线性收敛的 当当 ，或，或 时，迭代点列时，迭代点列 叫做具有超线性收敛速度或称算法叫做具有超线性收敛速度或称算法A A是超线性是超线性收敛收敛 当当 时，迭代点列时，迭代点列 叫做具有二阶收敛速叫做具有二阶收敛速度或算法度或算法A A是二阶收敛的是二阶收敛的 一般认为，具有超线性收敛或二阶收敛的算法一般认为，具有超线性收敛或二阶收敛的算法是较快速的算法是较快速的算法 一一 最优化问题总论最优化问题总论 (2)(2)计算终止准则计算终止准则 用迭代方法寻优时，其迭代过程总不能无限制地进

18、行用迭代方法寻优时，其迭代过程总不能无限制地进行下去，那么什么时候截断这种迭代呢？这就是迭代什下去，那么什么时候截断这种迭代呢？这就是迭代什么时候终止的问题么时候终止的问题 从理论上说，当然希望最终迭代点到达理论极小点，从理论上说，当然希望最终迭代点到达理论极小点，或者使最终迭代点与理论极小点之间的距离足够小时或者使最终迭代点与理论极小点之间的距离足够小时才终止迭代但是这在实际上是办不到的因为对于才终止迭代但是这在实际上是办不到的因为对于一个待求的优化问题，其理论极小点在哪里并不知道一个待求的优化问题，其理论极小点在哪里并不知道所知道的只是通过迭代计算获得的迭代点列，因此所知道的只是通过迭代计

19、算获得的迭代点列，因此只能从点列所提供的信息来判断是否应该终止迭代只能从点列所提供的信息来判断是否应该终止迭代 对于无约束优化问题通常采用的迭代终止准则有以下对于无约束优化问题通常采用的迭代终止准则有以下几种：几种：一一 最优化问题总论最优化问题总论点距准则点距准则相邻两迭代点之间的距离已达到充分小，即相邻两迭代点之间的距离已达到充分小，即式中式中 是一个充分小正数，代表计算精度是一个充分小正数，代表计算精度函数下降量准则函数下降量准则相邻两迭代点的函数值下降量已达到充分小当相邻两迭代点的函数值下降量已达到充分小当 时，时，可用函数绝对下降量准则可用函数绝对下降量准则当当 时，可用函数相对下降

20、量准则时，可用函数相对下降量准则梯度准则梯度准则目标函数在迭代点的梯度已达到充分小，即目标函数在迭代点的梯度已达到充分小，即这一准则对于定义域上的凸函数是完全正确的若是非凸函数，有这一准则对于定义域上的凸函数是完全正确的若是非凸函数，有可能导致误把驻点作为最优点。可能导致误把驻点作为最优点。对于约束优化问题，不同的优化方法有各自的终止准则对于约束优化问题，不同的优化方法有各自的终止准则一一 最优化问题总论最优化问题总论综上所述，优化算法的基本迭代过程如下：综上所述，优化算法的基本迭代过程如下：选定初始点选定初始点 ，置，置 按照某种规则确定搜索方向按照某种规则确定搜索方向 按某种规则确定按某种

21、规则确定 使得使得 计算计算 判定判定 是否满足终止准则若满足，则打印是否满足终止准则若满足，则打印 和和 ,停机；否则置停机；否则置 ,转转一一 最优化问题总论最优化问题总论NYX是否满足终止准则输出X，f(X)开始结束选定X0确定P确定t，使得f(X0+t P)0，加步系数1，令k=00=(t0)，比较目标函数值tk+1=tk+hk,k+1=(tk+1)a=mint，tk+1b=maxt，tk+1结束NYNY k+1khk+1=hk,t=tk,tk=tk+1,k=k+1,k=k+1k=0hk=hk,k=k+1 在加步探索法中，一般建议 若能估计问题（4.3）的最优解的大体位置的话，初始点要

22、尽量取接近于问题（4.3）的最优解.在具体运用上述加步探索法时，有时还要考虑一些细节问题例如，当探索得到新点处的目标函数值和出发点处相同时，以及初始步长应如何选取等，都需作适当处理搜索区间及其确定方法搜索区间及其确定方法 三、单谷区间与单谷函数 由于以后要介绍的一些维搜索方法，主要适用于问题（4.3）在搜索区间中只有唯一的最优解的情况，为此，我们再给出下面单谷区间与单谷函数概念 定义定义4.2 设 闭区间 若存在点 使得 在 上严格递减，在 上严格递增，则称 是函数 的单谷区间单谷区间，是 上单谷函数单谷函数 搜索区间及其确定方法搜索区间及其确定方法由定义4.2易知，一个区间是某函数的单谷区间

23、意味着，在该区间中函数只有一个“凹谷”（极小值）例如，左图中的 是 的单谷区间，也即 是 上的单谷函数右图中的 不是 的单谷区间，即 不是 上的单谷函数 搜索区间及其确定方法搜索区间及其确定方法 另外，从定义4.2还可知，某区间上的单谷函数在该区间上不一定是连续函数，而凸函数在所给区间上必然是单谷函数（如左图所示）由定义4.1和定义4.2知，函数的单谷区间总是相应问题（4.3）的一个搜索区间（如左图所示），但反之不然（如右图所示）搜索区间及其确定方法搜索区间及其确定方法单谷区间和单谷函数有如下有用的性质：定理4.1 设 是的单谷区间，任取 并且 （1）若有 ，则 是 的单谷区间（2）若有 ，则

24、 是 的单谷区间定理4.1说明，经过函数值的比较可以把单谷区间缩短为一个较小的单谷区间换句话说利用这个定理可以把搜索区间无限缩小，从而求到极小点.以下介绍的几种一维搜索方法都是利用这个定理通过不断地缩短搜索区间的长度，来求得一维最优化问题的近似最优解搜索区间及其确定方法搜索区间及其确定方法一、对分法基本原理求解一维最优化问题 一般可先确定它的一个有限搜索区间 ，把问题化为求解问题 ，然后通过不断缩短区间的长度，最后求得最优解对分法对分法设 在已获得的搜索区间 内具有连续的一阶导数因为 在 上可微，故 在 上连续，由此知 在 上有最小值令 ，总可求得极小点 不妨设 在 上是单减函数；在 上是单增

25、函数所以 时，故 ；当 时，亦即 对分法的原理如图 对分法对分法二、对分法迭代步骤已知 ，表达式，终止限 (1)确定初始搜索区间 ，要求(2)计算 的中点 (3)若 ，则 ，转(4)；若 ，则 ，转(5)；若 ，则 ，转(4)(4)若 ，则 ，转(5)；否则转(2)(5)打印 ，停机对分法对分法Y开始确定a b,要求c=(a+b)/2b=ct*=(a+b)/2输出t*结束T*=cNa=cNYNY对分法的计算流程如图所示三、对分法有关说明 对分法每次迭代都取区间的中点 a.若这点的导数值小于零，说明的根位于右半区间中，因此去掉左半区间；b.若中点导数值大于零，则去掉右半区间；c.若中点导数值正好

26、等于零，则该点就是极小点 因为每次迭代都使原区间缩短一半，所以称为对分法或二分法对分法对分法NewtonNewton切线法切线法一、Newton切线法基本原理 设 在已获得的搜索区间 内具有连续二阶导数，求 因为 在 上可微，故 在 上有最小值，令 下面不妨设在区间 中经过 次迭代已求得方程 的一个近似根 过 作曲线 的切线,其方程是然后用这条切线与横轴交点的横坐标 作为根的新的近似（如图）它可由方程（4.4）在令 的解出来，即 这就是Newton切线法迭代公式 NewtonNewton切线法切线法二、二、NewtonNewton切线法迭代步骤切线法迭代步骤已知 ，表达式，终止限 (1)确定初

27、始搜索区间 ，要求(2)选定 (3)计算 (4)若 ，则 ，转（3）；否则转（5）(5)打印 ，停机NewtonNewton切线法切线法Newton切线法的计算流程如图所示 三、Newton切线法有关说明这种方法一旦用好，收敛速度是很高的如果初始点选得适当，通常经过几次迭代就可以得到满足一般精度要求的结果.但是它也有缺点：第一，需要求二阶导数如果在多维最优化问题的一维搜索中使用这种方法，就要涉及Hesse矩阵，一般是难于求出的NewtonNewton切线法切线法第二，当曲线 在 上有较复杂的弯曲时，这种方法也往往失效如图(a)所示的迭代：结果 跳出 .迭代或者发散，或者找到的根并不是我们想要的

28、结果第三，即使曲线比较正常，在 中或者上凹或者下凹，初始点的选取也必须适当在图（b）的情况下，曲线上凹，应选点b作为初始点；而在图（c）的情况下，曲线下凹，应选点a为初始点否则都可能失败NewtonNewton切线法切线法黄金分割法黄金分割法一、黄金分割法基本原理 要介绍黄金分割法有必要回顾一下古老的黄金分割问题所谓黄金分割就是将一线段分为二段的方法这样分后，要求整段长L与较长段x的比值正好等于较长段x与较短段 的比值(如图)于是则解得由此可见长段的长度应为全长的0.618倍，而短段的长度应为全长的0.382倍因为古代的人们认为按0.618的比率来分割线段是最协调，胜似黄金，故称之为黄金分割黄

29、金分割法黄金分割法 用黄金分割法进行一维搜索，其基本思想是在单谷区间内适当插入两点，由此把区间分为三段，然后再通过比较这两点函数值大小，就可以确定是删去最左段还是最右段，或者同时删去左右两段保留中间段如此继续下去可将单谷区间无限缩小黄金分割法黄金分割法二、黄金分割法迭代步骤二、黄金分割法迭代步骤 现在提出一个问题，就在 上如何选取二点使得迭代次数最小而区间缩短最快？要解决这个问题，人们想到对区间 选二点 等价于将区间长度 进行黄金分割，也就是将第一个搜索点 取在 的0.618处，第二个搜索点 取成 的对称点即 的0.382处（如图所示）黄金分割法黄金分割法即要求接着计算 与 的值，并根据 与

30、的值的大小关系分情况讨论：（1）若 ,说明 是好点，于是把区间 划掉，保留 ，则 内有一保留点 ，置新的区间 ；（2）若 ，说明 是好点，于是应将 划掉，保留 ,则 内有保留点 ,置新的区间 .黄金分割法黄金分割法(3)若 则应具体分析,看极小点可能在哪一边再决定取舍，在一般情况下，可同时划掉 和 仅保留中间的 重置新的区间 接下来是在留下的区间 内找好点重复上面的步骤，直到搜索区间 小于给定的允许误差 为止。这样就得到黄金分割法迭代算法：黄金分割法黄金分割法已知 ，常数 0.382，终止限 (1)确定 的初始搜索区间 (2)计算 (3)计算 (4)若 ,则打印 ，停机；否则，转(5)(5)判

31、别是否满足 ：若满足，则置 ，然后转(3)；否则，置 ，然后转(4)黄金分割法黄金分割法黄金分割法算法流程如图所示 三、黄金分割法有关说明 黄金分割法是通过所选试点的函数值而逐步缩短单谷区间来搜索最优点该方法适用于单谷区间上的任何函数，甚至可以是不连续函数，因此这种算法属于直接法，适用相当广泛 黄金分割法黄金分割法 抛物线插值法抛物线插值法一、抛物线插值法基本原理 考虑一维搜索问题 假设其中 是定义在区间 上的单峰函数首先用试探法在 上找一点 ，使之满足 通过目标函数曲线上的三个点 作它的二次拟合曲线（如图所示）图4.14 抛物线插值法抛物线插值法 由于上述三个点既是目标函数曲线 上的点，又是

32、二次拟合曲线 上的点，故有方程组 将方程组（4.5）中的 消去，得 抛物线插值法抛物线插值法 从方程组（4.6）可解出待定系数 对于二次拟合函数 ，我们很容易求得它的极小值点令 即 ，从中解出 即为二次拟合函数 的极小值点 抛物线插值法抛物线插值法将式（4.7）与式（4.8）代入式（4.9）得用区间 上二次拟合函数 的这个极小值点 作为目标函数 在该区间极小值点的一个估计值若 和 已充分接近，即对给定的允许误差 使 成立时，就可被看作是 在区间 内近似最优解；否则应缩短区间，按照 值保持两头大、中间小的原则构成新的三点，继续上述过程，直至不等式（4.11）成立为止 抛物线插值法抛物线插值法二、

33、抛物线插值法迭代步骤下面具体介绍缩短区间,构成新三点的方法 由式（4.10）得到的点,在区间 内既可能在点 的左侧(即 ),又可能在 的右侧(即 ).分别对应这两种情形比较 和 的大小，又有 等三种情形，故共有如下六种情况（如图所示）：抛物线插值法抛物线插值法 抛物线插值法抛物线插值法（1）对于图(a)的情况:因 ,所以相对 为说 是好点，故划掉区间 ,保留 为新区间，故置 保持不变；（2）对于图(b)的情况:因 ,所以相对 来说 是好点，故划掉 保留为 新区间，故置 与 保持不变；（3）对于图(c)的情况：因 所以相对 来说 是好点，故划掉 ,保留 为新区间，故置 保持不变；抛物线插值法抛物

34、线插值法（4）对于图(d)的情况:因 所以相对 来说 是好点，故划掉 保留 故置 ，与 保持不变（5）对于图(e)的情况：一般同时划掉 及 仅留中间的 ，故置（6）对于图(f)的情况：一般同时划掉 及 ，仅留中间的 ，故置 抛物线插值法抛物线插值法通过上述讨论,我们可直接给抛物线插值法的迭代流程图.三、抛物线插值法有关说明 抛物线插值法是多项式逼近法的一种所谓多项式逼近，是利用目标函数在若干点的函数值或导数值等信息，构成一个与目标函数相接近的低次插值多项式，用该多项式的最优解作为目标函数的近似最优解 抛物线插值法抛物线插值法 习题习题 1用加步探索法确定一维最优化问题 的搜索区间，要求选取 2

35、用对分法求解 已知初始单谷区间 ，按精度 计算3用Newton法求解 用第题求得的区间，按精度 计算用黄金分割法求解 已知初始单谷区间 ，按精度 计算用抛物线插值法求解 已知初始单谷区间 习题习题 三三 常用无约束最优化方法常用无约束最优化方法3.1 3.1 最速下降法最速下降法3.2 3.2 NewtonNewton法法3.3 3.3 修正修正NewtonNewton法法3.4 3.4 共轭方向法共轭方向法3.5 3.5 共轭梯度法共轭梯度法3.6 3.6 变尺度法变尺度法3.7 3.7 坐标轮换法坐标轮换法3.8 3.8 单纯形法单纯形法三三 常用无约束最优化方法常用无约束最优化方法本章开

36、始讨论多维无约束最优化问题其中 这个问题的求解是指在 中找一点 ，使得对于任意的 都有 成立，则点 就是问题（3.1）的全局最优点但是，大多数最优化方法只能求到局部最优点，即在 中找到一点 ，使得式（3.2）在 的某个领域中成立这个矛盾对于实际问题一般容易解决根据问题的实际意义多半可以判定用优化方法求出的局部最优解是否为全局最优解而在理论上这是个比较复杂的问题，本书不涉及无约束优化方法是优化技术中极为重要和基本的内容之一它不仅可以直接用来求解无约束优化问题，而且很多约束优化问题也常将其转化为无约束优化问题，然后用无约束优化方法来求解另外，有些无约束优化方法只需略加处理，即可用于求解约束优化问题

37、 三三 常用无约束最优化方法常用无约束最优化方法 无约束优化理论发展较早，比较成熟，方法也很多，新的方法还在陆续出现把这些方法归纳起来可以分成两大类：一类是仅用计算函数值所得到的信息来确定搜索方向，通常称它为直接搜索法，简称为直接法，另一类需要计算函数的一阶或二阶导数值所得到的信息来确定搜索方向，这一类方法称为间接法（解析法）直接法不涉及导数、Hesse矩阵，适应性强，但收敛速度较慢；间接法收敛速度快，但需计算梯度，甚至需要计算Hesse矩阵 一般的经验是,在可能求得目标函数导数的情况下还是尽可能使用间接方法；相反,在不可能求得目标函数的导数或根本不存在导数的情况下,当然就应该使用直接法 三三

38、 常用无约束最优化方法常用无约束最优化方法 对于问题（3.1）为了求其最优解，按最优化算法的基本思想是从一个给定的初始点 出发，通过基本迭代格式 ，按照特定的算法 产生一串点列 ，如果点列收敛，则该点列的极限点为问题（3.1）的最优解 3.1 3.1 最速下降法最速下降法一、最速下降法基本原理 在基本迭代格式 中，每次迭代搜索方向 取为目标函数 的负梯度方向，即 ，而每次迭代的步长 取为最优步长，由此所确定的算法 称为最速下降法最速下降法 3.1 3.1 最速下降法最速下降法为了求解问题（3.1），如图所示，假定我们 已经迭代了 次 获得了第 个迭代点 现在从 出发，可选择的下降方向很多，一个

39、非常自然的想法是沿最速下降方向（即负梯度方向）进行搜索应该是有利的，至少在 邻近的范围内是这样。因此，取搜索方向为 .3.1 3.1 最速下降法最速下降法为了使目标函数在搜索方向上获得最多的下降，沿 进行一维搜索，由此得到第 个迭代点 ，即 ，其中步长因子 按下式确定 也可记为显然,令 就可以得到一个点列 ，其中 是初始点,由计算者任意选定.当 满足一定的条件时,由式(5.3)所产生的点列 必收敛于的极小点以后为书写方便,记 .因此在不发生混淆时，再记 3.1 3.1 最速下降法最速下降法二、最速下降法迭代步骤 已知目标函数 及其梯度 ，终止 （1）选定初始点 ,计算 置 （2）作直线搜索：；

40、计算 （3）用终止准则检测是否满足：若满足，则打印最优 解 停机；否则，置 转(2)3.1 3.1 最速下降法最速下降法最速下降法算法流程如图所示开始结束选定X0YX，fH准则满足N 将最速下降法应用于正定二次函数 可以推出显式迭代公式.设第 次迭代点为 我们来求 的表达式 对式（5.4）关于 求梯度，有 因此，现在从 出发沿 作直线搜索以确定 ，于是，其中 是最优步长因子 3.1 3.1 最速下降法最速下降法 又因式(4.2),有 再利用(5.5),(5.6),(5.7)可得：或 由此解出：代入（5.7）中得到 这就是最速下降法用于二次函数的显式迭代公式3.1 3.1 最速下降法最速下降法3

41、.1 3.1 最速下降法最速下降法例例例例5.1 5.1 5.1 5.1 试用最速下降法求函数 的极小点.迭代两次，计算各迭代点的函数值，梯度及其模，并验证相邻两个搜索方向是正交的设初始点为 解解解解:与（5.4）比较，得 梯度表达式是 由 ，计算因为目标函数是二次的，可以使用式(5.8),所以有3.1 3.1 最速下降法最速下降法 因为 由此说明相邻两个搜索方向 是正交的 计算3.1 3.1 最速下降法最速下降法 三、最速下降法有关说明 最速下降法的优点是算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点.但它有一个严重缺点就是收敛速度 沿负梯度方

42、向函数值下降很快的廉洁，容易使人们产生一种错觉，认为这一定是最理想的搜索方向，沿该方向搜索时收敛速度应该很快，然而事实证明，梯度法的收敛速度并不快3.1 3.1 最速下降法最速下降法 特别是对于等值线（面）具有狭长深谷形状的函数，收敛速度更慢其原因是由于每次迭代后下一次搜索方向总是与前一次搜索方向相互垂直，如此继续下去就产生所谓的锯齿现象即从直观上看，在远离极小点的地方每次迭代可能使目标函数有较大的下降，但是在接近极小点的地方，由于锯齿现象，从而导致每次迭代行进距离缩短，因而收敛速度不快.3.1 3.1 最速下降法最速下降法3.2 Newton3.2 Newton法法 如果目标函数 在 上具有

43、连续的二阶偏导数，其Hesse矩阵 正定并且可以表达成为显式（今后为了简便起见，记 ，那么可以使用下述的Newton法这种方法一旦好用，收敛速度是很快的它是一维搜索Newton切线法的推广一、Newton法基本原理为寻求收敛速度快的算法，我们考虑在应用基本迭代公 式 中，每轮迭代在迭代的起始点 处用 一个适当的二次函数来近似该点处的目标函数，由此 用点 指向近似二次函数极小点的方向来构造搜索方向 (如图所示)3.2 Newton3.2 Newton法法下面具体讨论下面具体讨论Newton法法 设最优化问题为 ，其中 二阶可导，Hesse矩阵 正定不妨设经过 次迭代已获点 ，现将 在 处展开成二

44、阶泰勒公式，于是有显然 是二次函数，特别由题设知 还是正定二次函数，所以 是凸函数且存在唯一全局极小点3.2 Newton3.2 Newton法法为求此极小点，令即可解得亦即对照基本迭代格式易知，式（5.9）中的搜索方向 步长因子 3.2 Newton3.2 Newton法法换句话说从点 出发沿搜索方向 并取步长 即可得 的极小点 .因此 是直指点 处近似二次函数 的极小点的方向此时称 为从点 出发的Newton方向从初始点开始，每一轮从当前迭代点出发，沿Newton方向并取步长 的算法称为Newton法3.2 Newton3.2 Newton法法二、Newton法迭代步骤已知目标函数 及其梯

45、度 Hesse矩阵 ,终止限 (1)选定初始点 计算 置 (2)计算 (3)由方程 解出 (4)计算(5)判别终止准则是否满足：若满足，则打印最优解 停机；否则置 转(2).3.2 Newton3.2 Newton法法开始结束选定X0N求解方程H准则满足X,fNewton法的流程如图所示Y例例例例5.2 5.2 5.2 5.2 试用Newton法求 的极小点,初始点取为 解解解解:梯度为 Hesse矩阵为 其逆矩阵为 由迭代公式（5.13）得第1 迭代点为由于此时 ，停止迭代得因此，它就是极小点 3.2 Newton3.2 Newton法法 从上述例5.2我们看到，用Newton法求解，只经一

46、轮迭代就得到最优解这一结果并不是偶然的，因为从Newton方向的构造我们知道，对于正定二次函数，Newon方向就是指向其极小点的方向因此，用Newton法解目标函数为正定二次函数的无约束最优化问题，只需一次迭代就可得最优解3.2 Newton3.2 Newton法法对于目标函数是非二次函数的非约束最优化问题，一般地说，用Newton法通过有限轮迭代并不能保证可求得最优解但由于目标函数在最优解附近能近似于二次函数，因此当先取接近于最优解的初始点使用Newton法求解时，其收敛速度一般是快的事实上，可以证明在初始点离最优解不远的条件下，Newton法是二次收敛的但是当初始点选得离最优解太远时，Ne

47、wton法并不一定是收敛的方法，甚至连其下降性也很难保证3.2 Newton3.2 Newton法法 三、Newton法有关说明 Newton法收敛速度非常快具有二次收敛的优点，但它存在下面四个严重的缺点：（1）尽管每次迭代不会使目标函数 上升，但仍不能保证 下降当Hesse矩阵非正定时，Newton法的搜索将会失败（2）对初始点要求严格一般要求比较接近或有利于接近极值点，而这在实际计算中是比较难办的3.2 Newton3.2 Newton法法（3）在进行某次迭代时可能求不出搜索方向由于搜索方向为若目标函数在 点Hesse矩阵为奇异，则求不出 ，因而不有构成牛顿方向，从而使迭代无法进行（4）牛

48、顿方向构造困难，计算相当复杂，除了求梯度以外还需计算Hesse矩阵及其逆矩阵，占用机器内存相当大3.2 Newton3.2 Newton法法3.3 3.3 修正修正NewtonNewton法法 一、修正Newton法基本原理 为了克服Newton法的缺点，人们保留选Newton方向作为搜索方向，摒弃其步长恒取1，而用一维搜索确定最优步长，由此产生的算法称为修正Newton法（或阻力Newton法）3.3 3.3 修正修正NewtonNewton法法 二、修正Newton法迭代步骤已知目标函数 及其梯度 Hesse矩阵 终止限（1）选取初始点 令（2）求梯度向量计算 ，若 ，停 止迭代输出 否则

49、，转（3）（3）构造Newton方向计算 ，取（4）进行一维搜索求 ，使得 令 ，转（2）修正Newton法的流程如图所示k=0计算 求 使 计算开始结束选定YN三、修正Newton法有关说明 修正Newton法克服了Newton法的缺点特别是，当 迭代点接近于最优解时，此法具有收敛速度快的优点，对初始点的选择要求不严 但是，修正Newton法仍需要计算目标函数的Hesse矩 阵和逆矩阵，所以求解的计算量和存贮量均很大.另外，当目标函数的Hesse矩阵在某点处出现奇异时，迭代将 无法进行，因此修正Newton法仍有相当的局限性3.3 3.3 修正修正NewtonNewton法法3.4 3.4

50、共轭方向法共轭方向法构成各种不同最优化方法，往往取决于如何从基本迭代公式 中确定搜索方向在最速下降法中，由于取 从而导致搜索路线出现锯齿状，收敛速度降低；而在Newton法中，由于选取 收敛速度虽很快，但计算量很大，特别是还要求Hesse矩阵正定，从而导致该算法对初始点选择要求过严下面我们将给大家介绍一种新的最优化方法，它的计算量小，收敛速度没有Newton法快，但比最速下降法快得多的新算法，称为共轭方向法共轭方向法 一、共轭方向法基本原理 首先介绍共轭方向概念及其些性质 定义定义5.1 设 是对称矩阵,对于非零向量 若有 则称 与 相互 共轭或 正交的 对于非零向量组 若有 则称 是 共轭方