最优化方法及其应用课件

《最优化方法及其应用课件》由会员分享，可在线阅读，更多相关《最优化方法及其应用课件（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次迭代计算的步长因子次迭代计算的步长因子 一一 最优化问题总论最优化问题

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

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

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

17、度, ,或算法或算法A A叫做是叫做是 阶收敛的，特别地阶收敛的，特别地 : :一一 最优化问题总论最优化问题总论 当当 ，迭代点列，迭代点列 称为具有线性收敛称为具有线性收敛速度或算法速度或算法A A称为线性收敛的称为线性收敛的 当当 ，或，或 时，迭代点列时，迭代点列 叫做具有超线性收敛速度或称算法叫做具有超线性收敛速度或称算法A A是超线性是超线性收敛收敛 当当 时，迭代点列时，迭代点列 叫做具有二阶收敛速叫做具有二阶收敛速度或算法度或算法A A是二阶收敛的是二阶收敛的 一般认为，具有超线性收敛或二阶收敛的算法一般认为，具有超线性收敛或二阶收敛的算法是较快速的算法是较快速的算法 一一 最

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

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

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

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

24、搜索区间及其确定方法单谷区间和单谷函数有如下有用的性质：定理4.1 设 是的单谷区间，任取 并且 （1）若有 ，则 是 的单谷区间（2）若有 ，则 是 的单谷区间定理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对分法的计算流程如图所示三、对分法有

26、关说明 对分法每次迭代都取区间的中点 a.若这点的导数值小于零，说明的根位于右半区间中，因此去掉左半区间；b.若中点导数值大于零，则去掉右半区间；c.若中点导数值正好等于零，则该点就是极小点 因为每次迭代都使原区间缩短一半，所以称为对分法或二分法对分法对分法NewtonNewton切线法切线法一、Newton切线法基本原理 设 在已获得的搜索区间 内具有连续二阶导数，求 因为 在 上可微，故 在 上有最小值，令 下面不妨设在区间 中经过 次迭代已求得方程 的一个近似根 过 作曲线 的切线 ,其方程是然后用这条切线与横轴交点的横坐标 作为根的新的近似（如图）它可由方程（4.4）在令 的解出来，即

27、 这就是Newton切线法迭代公式 NewtonNewton切线法切线法二、二、NewtonNewton切线法迭代步骤切线法迭代步骤已知 ， 表达式，终止限 (1)确定初始搜索区间 ，要求(2) 选定 (3)计算 (4)若 ，则 ，转（3）；否则转（5）(5)打印 ，停机NewtonNewton切线法切线法Newton切线法的计算流程如图所示 三、Newton切线法有关说明这种方法一旦用好，收敛速度是很高的如果初始点选得适当，通常经过几次迭代就可以得到满足一般精度要求的结果.但是它也有缺点：第一，需要求二阶导数如果在多维最优化问题的一维搜索中使用这种方法，就要涉及Hesse矩阵，一般是难于求出

28、的NewtonNewton切线法切线法第二，当曲线 在 上有较复杂的弯曲时，这种方法也往往失效如图(a)所示的迭代： 结果 跳出 .迭代或者发散，或者找到的根并不是我们想要的结果第三，即使曲线比较正常，在 中或者上凹或者下凹，初始点的选取也必须适当在图（b）的情况下，曲线上凹，应选点b作为初始点；而在图（c）的情况下，曲线下凹，应选点a为初始点否则都可能失败NewtonNewton切线法切线法黄金分割法黄金分割法一、黄金分割法基本原理 要介绍黄金分割法有必要回顾一下古老的黄金分割问题所谓黄金分割就是将一线段分为二段的方法这样分后，要求整段长L与较长段x的比值正好等于较长段x与较短段 的比值(如

29、图)于是则解得由此可见长段的长度应为全长的0.618倍，而短段的长度应为全长的0.382倍因为古代的人们认为按0.618的比率来分割线段是最协调，胜似黄金，故称之为黄金分割黄金分割法黄金分割法 用黄金分割法进行一维搜索，其基本思想是在单谷区间内适当插入两点，由此把区间分为三段，然后再通过比较这两点函数值大小，就可以确定是删去最左段还是最右段，或者同时删去左右两段保留中间段如此继续下去可将单谷区间无限缩小黄金分割法黄金分割法二、黄金分割法迭代步骤二、黄金分割法迭代步骤 现在提出一个问题，就在 上如何选取二点使得迭代次数最小而区间缩短最快？要解决这个问题，人们想到对区间 选二点 等价于将区间长度

30、进行黄金分割，也就是将第一个搜索点 取在 的0.618处，第二个搜索点 取成 的对称点即 的0.382处（如图所示） 黄金分割法黄金分割法即要求接着计算 与 的值，并根据 与 的值的大小关系分情况讨论：（1） 若 ,说明 是好点，于是把区间 划掉，保留 ，则 内有一保留点 ，置新的区间 ；（2）若 ，说明 是好点，于是应将 划掉，保留 ,则 内有保留点 ,置新的区间 .黄金分割法黄金分割法(3)若 则应具体分析,看极小点可能在哪一边再决定取舍，在一般情况下，可同时划掉 和 仅保留中间的 重置新的区间 接下来是在留下的区间 内找好点重复上面的步骤，直到搜索区间 小于给定的允许误差 为止。这样就得

31、到黄金分割法迭代算法：黄金分割法黄金分割法已知 ，常数 0.382，终止限 (1)确定 的初始搜索区间 (2)计算 (3)计算 (4) 若 ,则打印 ，停机；否则，转(5)(5) 判别是否满足 ：若满足，则置 ， 然后转(3)；否则，置 ， 然后转(4) 黄金分割法黄金分割法黄金分割法算法流程如图所示 三、黄金分割法有关说明 黄金分割法是通过所选试点的函数值而逐步缩短单谷区间来搜索最优点该方法适用于单谷区间上的任何函数，甚至可以是不连续函数，因此这种算法属于直接法，适用相当广泛 黄金分割法黄金分割法 抛物线插值法抛物线插值法一、抛物线插值法基本原理 考虑一维搜索问题 假设其中 是定义在区间 上

32、的单峰函数首先用试探法在 上找一点 ，使之满足 通过目标函数曲线上的三个点 作它的二次拟合曲线（如图所示） 图4.14 抛物线插值法抛物线插值法 由于上述三个点既是目标函数曲线 上的点，又是二次拟合曲线 上的点，故有方程组 将方程组（4.5）中的 消去，得 抛物线插值法抛物线插值法 从方程组（4.6）可解出待定系数 对于二次拟合函数 ，我们很容易求得它的极小值点令 即 ，从中解出 即为二次拟合函数 的极小值点 抛物线插值法抛物线插值法将式（4.7）与式（4.8）代入式（4.9）得用区间 上二次拟合函数 的这个极小值点 作为目标函数 在该区间极小值点的一个估计值若 和 已充分接近，即对给定的允许

33、误差 使 成立时， 就可被看作是 在区间 内近似最优解；否则应缩短区间，按照 值保持两头大、中间小的原则构成新的三点，继续上述过程，直至不等式（4.11）成立为止 抛物线插值法抛物线插值法二、抛物线插值法迭代步骤下面具体介绍缩短区间,构成新三点的方法 由式（4.10）得到的点 ,在区间 内既可能在点 的左侧(即 ),又可能在 的右侧(即 ). 分别对应这两种情形比较 和 的大小，又有 等三种情形，故共有如下六种情况（如图所示）： 抛物线插值法抛物线插值法 抛物线插值法抛物线插值法（1）对于图(a)的情况:因 ,所以相对 为说 是好点，故划掉区间 ,保留 为新区间，故置 保持不变；（2）对于图(

34、b)的情况:因 ,所以相对 来说 是好点，故划掉 保留为 新区间，故置 与 保持不变；（3）对于图(c)的情况：因 所以相对 来说 是好点，故划掉 ,保留 为新区间 ，故置 保持不变； 抛物线插值法抛物线插值法（4）对于图(d)的情况:因 所以相对 来说 是好点，故划掉 保留 故置 ， 与 保持不变（5）对于图(e)的情况：一般同时划掉 及 仅留中间的 ，故置 （6）对于图(f)的情况：一般同时划掉 及 ，仅留中间的 ，故置 抛物线插值法抛物线插值法通过上述讨论,我们可直接给抛物线插值法的迭代流程图. 三、抛物线插值法有关说明 抛物线插值法是多项式逼近法的一种所谓多项式逼近，是利用目标函数在若

35、干点的函数值或导数值等信息，构成一个与目标函数相接近的低次插值多项式，用该多项式的最优解作为目标函数的近似最优解 抛物线插值法抛物线插值法 习题习题 1用加步探索法确定一维最优化问题 的搜索区间，要求选取 2用对分法求解 已知初始单谷区间 ，按精度 计算3用Newton法求解 用第题求得的区间，按精度 计算用黄金分割法求解 已知初始单谷区间 ，按精度 计算用抛物线插值法求解 已知初始单谷区间 习题习题 三三 常用无约束最优化方法常用无约束最优化方法3.1 3.1 最速下降法最速下降法3.2 3.2 NewtonNewton法法3.3 3.3 修正修正NewtonNewton法法3.4 3.4

36、共轭方向法共轭方向法3.5 3.5 共轭梯度法共轭梯度法3.6 3.6 变尺度法变尺度法3.7 3.7 坐标轮换法坐标轮换法3.8 3.8 单纯形法单纯形法三三 常用无约束最优化方法常用无约束最优化方法本章开始讨论多维无约束最优化问题其中 这个问题的求解是指在 中找一点 ，使得对于任意的 都有 成立，则点 就是问题（3.1）的全局最优点但是，大多数最优化方法只能求到局部最优点，即在 中找到一点 ，使得式（3.2）在 的某个领域中成立这个矛盾对于实际问题一般容易解决根据问题的实际意义多半可以判定用优化方法求出的局部最优解是否为全局最优解而在理论上这是个比较复杂的问题，本书不涉及无约束优化方法是优

37、化技术中极为重要和基本的内容之一它不仅可以直接用来求解无约束优化问题，而且很多约束优化问题也常将其转化为无约束优化问题，然后用无约束优化方法来求解另外，有些无约束优化方法只需略加处理，即可用于求解约束优化问题 三三 常用无约束最优化方法常用无约束最优化方法 无约束优化理论发展较早，比较成熟，方法也很多，新的方法还在陆续出现把这些方法归纳起来可以分成两大类：一类是仅用计算函数值所得到的信息来确定搜索方向，通常称它为直接搜索法，简称为直接法，另一类需要计算函数的一阶或二阶导数值所得到的信息来确定搜索方向，这一类方法称为间接法（解析法） 直接法不涉及导数、Hesse矩阵，适应性强，但收敛速度较慢；间

38、接法收敛速度快，但需计算梯度，甚至需要计算Hesse矩阵 一般的经验是,在可能求得目标函数导数的情况下还是尽可能使用间接方法；相反,在不可能求得目标函数的导数或根本不存在导数的情况下,当然就应该使用直接法 三三 常用无约束最优化方法常用无约束最优化方法 对于问题（3.1）为了求其最优解，按最优化算法的基本思想是从一个给定的初始点 出发，通过基本迭代格式 ，按照特定的算法 产生一串点列 ，如果点列收敛，则该点列的极限点为问题（3.1）的最优解 3.1 3.1 最速下降法最速下降法一、最速下降法基本原理 在基本迭代格式 中，每次迭代搜索方向 取为目标函数 的负梯度方向，即 ，而每次迭代的步长 取为

39、最优步长，由此所确定的算法 称为最速下降法最速下降法 3.1 3.1 最速下降法最速下降法为了求解问题（3.1），如图所示，假定我们 已经迭代了 次 获得了第 个迭代点 现在从 出发，可选择的下降方向很多，一个非常自然的想法是沿最速下降方向（即负梯度方向）进行搜索应该是有利的，至少在 邻近的范围内是这样。因此，取搜索方向为 . 3.1 3.1 最速下降法最速下降法为了使目标函数在搜索方向上获得最多的下降，沿 进行一维搜索，由此得到第 个迭代点 ，即 ，其中步长因子 按下式确定 也可记为显然,令 就可以得到一个点列 ，其中 是初始点,由计算者任意选定.当 满足一定的条件时,由式(5.3)所产生的

40、点列 必收敛于的极小点以后为书写方便,记 . 因此在不发生混淆时，再记 3.1 3.1 最速下降法最速下降法二、最速下降法迭代步骤 已知目标函数 及其梯度 ，终止 （1）选定初始点 ,计算 置 （2）作直线搜索： ；计算 （3）用终止准则检测是否满足：若满足，则打印最优 解 停机；否则，置 转(2) 3.1 3.1 最速下降法最速下降法最速下降法算法流程如图所示开始结束选定X0YX ， fH准则满足N 将最速下降法应用于正定二次函数 可以推出显式迭代公式. 设第 次迭代点为 我们来求 的表达式 对式（5.4）关于 求梯度，有 因此， 现在从 出发沿 作直线搜索以确定 ，于是， 其中 是最优步长

41、因子 3.1 3.1 最速下降法最速下降法 又因式(4.2),有 再利用(5.5),(5.6),(5.7)可得： 或 由此解出： 代入（5.7）中得到 这就是最速下降法用于二次函数的显式迭代公式3.1 3.1 最速下降法最速下降法3.1 3.1 最速下降法最速下降法例例例例5.1 5.1 5.1 5.1 试用最速下降法求函数 的极小点.迭代两次，计算各迭代点的函数值，梯度及其模，并验证相邻两个搜索方向是正交的设初始点为 解解解解: : : : 与（5.4）比较，得 梯度表达式是 由 ，计算因为目标函数是二次的，可以使用式(5.8),所以有3.1 3.1 最速下降法最速下降法 因为 由此说明相邻

42、两个搜索方向 是正交的 计算3.1 3.1 最速下降法最速下降法 三、最速下降法有关说明 最速下降法的优点是算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点.但它有一个严重缺点就是收敛速度 沿负梯度方向函数值下降很快的廉洁，容易使人们产生一种错觉，认为这一定是最理想的搜索方向，沿该方向搜索时收敛速度应该很快，然而事实证明，梯度法的收敛速度并不快3.1 3.1 最速下降法最速下降法 特别是对于等值线（面）具有狭长深谷形状的函数，收敛速度更慢其原因是由于每次迭代后下一次搜索方向总是与前一次搜索方向相互垂直，如此继续下去就产生所谓的锯齿现象即从直观上看，

43、在远离极小点的地方每次迭代可能使目标函数有较大的下降，但是在接近极小点的地方，由于锯齿现象，从而导致每次迭代行进距离缩短，因而收敛速度不快.3.1 3.1 最速下降法最速下降法3.2 Newton3.2 Newton法法 如果目标函数 在 上具有连续的二阶偏导数，其Hesse矩阵 正定并且可以表达成为显式（今后为了简便起见，记 ，那么可以使用下述的Newton法这种方法一旦好用，收敛速度是很快的它是一维搜索Newton切线法的推广一、Newton法基本原理为寻求收敛速度快的算法，我们考虑在应用基本迭代公 式 中，每轮迭代在迭代的起始点 处用 一个适当的二次函数来近似该点处的目标函数，由此 用点

44、 指向近似二次函数极小点的方向来构造搜索方向 (如图所示)3.2 Newton3.2 Newton法法下面具体讨论下面具体讨论Newton法法 设最优化问题为 ，其中 二阶可导，Hesse矩阵 正定不妨设经过 次迭代已获点 ，现将 在 处展开成二阶泰勒公式，于是有显然 是二次函数，特别由题设知 还是正定二次函数，所以 是凸函数且存在唯一全局极小点3.2 Newton3.2 Newton法法为求此极小点，令即可解得亦即对照基本迭代格式易知，式（5.9）中的搜索方向 步长因子 3.2 Newton3.2 Newton法法换句话说从点 出发沿搜索方向 并取步长 即可得 的极小点 .因此 是直指点 处

45、近似二次函数 的极小点的方向此时称 为从点 出发的Newton方向从初始点开始，每一轮从当前迭代点出发，沿Newton方向并取步长 的算法称为Newton法3.2 Newton3.2 Newton法法二、Newton法迭代步骤已知目标函数 及其梯度 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法求

46、 的极小点,初始点取为 解解解解: : : : 梯度为 Hesse矩阵为 其逆矩阵为 由迭代公式（5.13）得第1 迭代点为由于此时 ，停止迭代得因此，它就是极小点 3.2 Newton3.2 Newton法法 从上述例5.2我们看到，用Newton法求解，只经一轮迭代就得到最优解这一结果并不是偶然的，因为从Newton方向的构造我们知道，对于正定二次函数，Newon方向就是指向其极小点的方向因此，用Newton法解目标函数为正定二次函数的无约束最优化问题，只需一次迭代就可得最优解3.2 Newton3.2 Newton法法对于目标函数是非二次函数的非约束最优化问题，一般地说，用Newton法

47、通过有限轮迭代并不能保证可求得最优解但由于目标函数在最优解附近能近似于二次函数，因此当先取接近于最优解的初始点使用Newton法求解时，其收敛速度一般是快的事实上，可以证明在初始点离最优解不远的条件下，Newton法是二次收敛的但是当初始点选得离最优解太远时，Newton法并不一定是收敛的方法，甚至连其下降性也很难保证3.2 Newton3.2 Newton法法 三、Newton法有关说明 Newton法收敛速度非常快具有二次收敛的优点，但它存在下面四个严重的缺点：（1）尽管每次迭代不会使目标函数 上升，但仍不能保证 下降当Hesse矩阵非正定时，Newton法的搜索将会失败（2）对初始点要求

48、严格一般要求比较接近或有利于接近极值点，而这在实际计算中是比较难办的3.2 Newton3.2 Newton法法（3）在进行某次迭代时可能求不出搜索方向由于搜索方向为若目标函数在 点Hesse矩阵为奇异，则求不出 ，因而不有构成牛顿方向，从而使迭代无法进行（4）牛顿方向构造困难，计算相当复杂，除了求梯度以外还需计算Hesse矩阵及其逆矩阵，占用机器内存相当大3.2 Newton3.2 Newton法法3.3 3.3 修正修正NewtonNewton法法 一、修正Newton法基本原理 为了克服Newton法的缺点，人们保留选Newton方向作为搜索方向，摒弃其步长恒取1，而用一维搜索确定最优步

49、长，由此产生的算法称为修正Newton法（或阻力Newton法）3.3 3.3 修正修正NewtonNewton法法 二、修正Newton法迭代步骤已知目标函数 及其梯度 Hesse矩阵 终止限 （1）选取初始点 令（2）求梯度向量计算 ，若 ，停 止迭代输出 否则，转（3）（3）构造Newton方向计算 ， 取（4）进行一维搜索求 ，使得 令 ，转（2） 修正Newton法的流程如图所示k=0计算 求 使 计算开始结束选定YN三、修正Newton法有关说明 修正Newton法克服了Newton法的缺点特别是，当 迭代点接近于最优解时，此法具有收敛速度快的优点， 对初始点的选择要求不严 但是，

50、修正Newton法仍需要计算目标函数的Hesse矩 阵和逆矩阵，所以求解的计算量和存贮量均很大.另外， 当目标函数的Hesse矩阵在某点处出现奇异时，迭代将 无法进行，因此修正Newton法仍有相当的局限性3.3 3.3 修正修正NewtonNewton法法3.4 3.4 共轭方向法共轭方向法构成各种不同最优化方法，往往取决于如何从基本迭代公式 中确定搜索方向在最速下降法中，由于取 从而导致搜索路线出现锯齿状，收敛速度降低；而在Newton法中，由于选取 收敛速度虽很快，但计算量很大，特别是还要求Hesse矩阵正定，从而导致该算法对初始点选择要求过严下面我们将给大家介绍一种新的最优化方法，它的

51、计算量小，收敛速度没有Newton法快，但比最速下降法快得多的新算法，称为共轭方向法共轭方向法 一、共轭方向法基本原理 首先介绍共轭方向概念及其些性质 定义定义5.1 设 是对称矩阵,对于非零向量 若有 则称 与 相互 共轭或 正交的 对于非零向量组 若有 则称 是 共轭方向组或 正交方向组，也称 它们是一组 的共轭方向3.4 3.4 共轭方向法共轭方向法 在上述定义中若 ( 阶单位矩阵)，则式（5.10）和式（5.11）成为 和 由此可知，共轭概念是正交概念的推广，共轭方向是正交方向的推广定理定理5.1 设 是正定矩阵， 是非零向量若 是 一组 共轭方向，则它们是线性无关的3.4 3.4 共

52、轭方向法共轭方向法3.4 3.4 共轭方向法共轭方向法证明 设有一组实数 使得 依次以 左乘上式得到 因为 是一组 的共轭方向，故有 又由于A是正定矩阵，所以对于 有 把以上两式用于式（5.12），便可推知 由此证明 是线性无关3.4 3.4 共轭方向法共轭方向法考虑以二次函数为目标函数的无约束极小化问题其中 是对称正定矩阵 有如下定理：定理定理5.2 设 是对称正定矩阵， 是一 组A 的共轭方向.对于问题（5.13）,若从任意点 出发依次沿 进行一维搜索，则至多经过n 轮迭代，可得问题（5.13）的最优解3.4 3.4 共轭方向法共轭方向法证明 设从点X0 出发依次按方向 进行一维搜索产生的

53、迭代点是其中最优步长 是通过下式来确定又由 和式（5.14）可推知即利用式（5.16）有 对上式右乘 可得因为 是 A共轭方向，故得 或另外，由式（5.15）可知 3.4 3.4 共轭方向法共轭方向法因为所以由式（5.18）有由式（5.17）和上式，对于 我们得到特别地，当 时有 由于 是一组A的共轭方向,由定理5.1知它们是线性无关的,因而向量 可表示为这些向量的线性组合 其中 是实数3.4 3.4 共轭方向法共轭方向法所以由式（5.19）有 即有 于是得即Xn是f(X) 的驻点又因为A是对称正定，故f(X)是凸函数，因而Xn是问题（5.13）的最优解这说明，至多经过n 次迭代必可求得 (5

54、.13)的最优解.3.4 3.4 共轭方向法共轭方向法 通常，我们把从任意点 出发,依次沿某组共轭方向进行一维搜索的求解最优化问题的方法,叫做共轭方向法共轭方向法为了直观起见,首先考虑二维情况现在我们把下降法用于形式为(5.13)的二元二次函数任选初始点 从 出发沿某个下降方向 作一维搜索得到 (如图所示)3.4 3.4 共轭方向法共轭方向法由式（4.2）知 而且向量 所在的直线必与某条等值线（椭圆）相切于 点下一次迭代，如果按最速下降法选择负梯度方向为搜索方向，那末将要发生锯齿现象.为了克服这种现象，我们设想，下一次迭代的搜索方向将直指极小点 如果能够选定这样的搜索方向，那么对于二元二次函数

55、只须顺次进行两次直线搜索就可以求到极小点了下面来讨论这样的方向 应该满足什么条件，怎样确定3.4 3.4 共轭方向法共轭方向法 因为 直接指极小点 所以可写成 其中 是最优步长因子， 显然，当 时， 对（5.13）求导数，有 因为 是极小点，所以有 将式（5.21）代入此式中，由（5.22）可得等式两边同时左乘 并注意到式(5.20)和 于是3.4 3.4 共轭方向法共轭方向法这就是为使 直指极小点所必须满足的条件显然（5.23）中 和 是A的共轭向量由式（5.20），不难给出 的表达式两边同时左乘 ，有由此解出代回到式 （5.24），得3.4 3.4 共轭方向法共轭方向法一般地，在 维空间中

56、可以找出 个互相共轭的方向，对于 元正定二次函数，从任意初始点出发，顺次沿这 个共轭方向最多作 次直线搜索就可以求得目标函数的极小点这就是共轭方向法的算法形成的基本思想3.4 3.4 共轭方向法共轭方向法对于 元正定二次目标函数，从任意初始点出发，如果经过有限次迭代就能够求得极小点，那么这种算法称为具有二次终止性具有二次终止性例如Newton法对于二次函数只须经过一次迭代就可以求得极小点，因此是二次终止的；而最速下降法不具有二次终止性；共轭方向法（包括共轭梯度法，变尺度法等）是二次终止的一般来说，具有二次终止性的算法，在用于一般函数时，收敛速度较快3.4 3.4 共轭方向法共轭方向法二、共轭方

57、向法迭代步骤 已知具有正定矩阵A 的二次目标函数 和终止限 （1）选定初始点X0 和具有下降的方向P0,置 k=0（2）作直线搜索 （3）判别 是否满足：若满足，则打印 停机；否则转（4）（4）提供共轭方向 使得（5） ，转（2）.3.4 3.4 共轭方向法共轭方向法共轭方向法的流程如图所示 e+)(1kXf k=0 提供共轭方向1+kP使得 kjQPPkj, 1 ,0,01L=+T ),(1kkskPXlX=+ 开始 停 1+kX Y N k=k+1 选定e,00PX 三、共轭方向法有关说明 上述算法针对二次目标函数，但也可用于一般的非二次函数在求优过程中 因舍入误差不能满足 时，可取 为新

58、的初始点，再重复前面的过程3.4 3.4 共轭方向法共轭方向法3.5 3.5 共轭梯度法共轭梯度法如果在共轭方向法中初始的共轭向量 恰好取为初始点 处的负梯度 ，而以下各共轭方向 由第 迭代点 处的负梯度 与已经得到的共轭向量 的线性组合来确定，那么就构成了一种具体的共轭方向法.因为每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称为共轭梯度法共轭梯度法一、共轭梯度法基本原理设从任意点 出发，第一个搜索方向取为 处的负梯度方向 当搜索得到点 后，设以下按 来产生搜索方向为了使选择 使所产生的 和 是A的共轭，以 右乘上式的两边，于是有 3.5 3.5 共轭梯度法共轭梯度法因为要使 和

59、 是A 的共轭, 应有 故由上式得综上所述，我们可以生成n个方向3.5 3.5 共轭梯度法共轭梯度法式（5.25）中含有问题（5.13）的目标函数系数阵，这对于目标函数是非二次函数的问题是不方便的通过简化，一般地我们可以利用目标函数的梯度信息，来产生n 个共轭方向由此得共轭梯度法算法3.5 3.5 共轭梯度法共轭梯度法 二、共轭梯度法迭代步骤已知目标函数 ，终止限 （1）选取初始点 ，给定终止限 （2）求初始梯度计算 ，若 ，停止迭 代输出 ， 否则转（3）（3）构造初始搜索方向.取 ,令 ,转（4）（4）进行一维搜索求 使得 令 ，转（5） 3.5 3.5 共轭梯度法共轭梯度法（5）求梯度向

60、量计算 ，若 ，停止 迭代输出 否则转（6）.（6）检验迭代次数若 ，令 ，转（3）， 否则，转（7）（7）构造共轭方向取 转（4）3.5 3.5 共轭梯度法共轭梯度法共轭梯度法的流程如图所示结束求tk使计算开始X0选定YN构造初始搜索方向取计算Xk+1YNYN例例例例5.3 5.3 5.3 5.3 用共轭梯度法求 其中 选初始点 解解解解: : : : 显然3.5 3.5 共轭梯度法共轭梯度法所以新的搜索方向由此，有并且可推知因而得下一迭代点由于 停止迭代输出所求得 3.5 3.5 共轭梯度法共轭梯度法例5.3的迭代的路径如图所示3.5 3.5 共轭梯度法共轭梯度法三、共轭梯度法有关说明实际

61、上,可以把共轭梯度法看作是最速下降法的一种改进.当令 时,就变为最速下降法.共轭梯度法由于不涉及矩阵,仅仅存储向量,因而存储量小,适合于维数较高的优化问题另外,共轭梯度法不要求精确的直线搜索.但是,不精确的直线搜索可能导致迭代出来的向量不再共轭,从而降低方法的效能.克服的办法是:重设初始点,即把经过 次迭代得到的 作为初始点重新迭代3.5 3.5 共轭梯度法共轭梯度法 我们知道Newton法最突出的优点是收敛速度快,在这一点上其它算法无法比拟的.因此,建议凡是Hesse矩阵比较容易求出的问题尽可能使用Newton法求解.然而Newton法还有一个严重缺陷,就是每次迭代都要计算目标函数的Hess

62、e矩阵和它的逆矩阵,当问题的维数n较大时,计算量迅速增加,从而就抵消了Newton法的优点3.6 3.6 变尺度法变尺度法3.6 3.6 变尺度法变尺度法为此，人们开始寻找一种算法既可以保持Newton法收敛速度快的优点，又可以摆脱关于Hesse矩阵的计算，这就是本节要给大家介绍的变尺度算法变尺度算法 变尺度法是一种非常好的方法其中DFP算法算法和BFGS算法算法，可以说直到目前为止在不用Hesse矩阵的方法中是最好的算法一、变尺度法基本原理 在Newton法中，由基本迭代格式 其中 令 于是有 其中 是初始点， 和 分别是目标函数 在 点 的梯度和Hesse矩阵 3.6 3.6 变尺度法变尺

63、度法为了消除这个迭代公式中的Hesse逆矩阵 可用某种近似矩阵 来替换它，即构造一个矩阵序列 去逼近Hesse逆矩阵序列 此时式（5.26）变为事实上,式中 无非是确定了第 次迭代的搜索方向.为了取得更大的灵活性,我们考虑更一般的迭代公式 其中步长因子 通过从 出发沿 作直线搜 索来确定3.6 3.6 变尺度法变尺度法 式（5.27）是代表很广的一类迭代公式. 例如,当 （单位矩阵）时，它变为最速下降法的迭代 公式为使 确实与 近似并且有容易计算的特点， 必须对 附加某些条件： 第一，为保证迭代公式具有下降性质，要求 中的每 一个矩阵都是对称正定的理由是，为使搜索方向 是下降方向，只要 成立即

64、可，即 成立 当 对称正定时,此式必然成立,从而保证式（5.27） 具有下降性质3.6 3.6 变尺度法变尺度法第二，要求 之间的迭代具有简单形式显然，是最简单的形式了其中 称为校正矩阵，式（5.28）称为校正公式 第三， 必须满足拟Newton条件3.6 3.6 变尺度法变尺度法 所谓拟Newton 条件由下面的推导给出设迭代过程已进行到 步， 和 均已求出，现在推导 所必须满足的条件设目标函数 具有连续的二阶偏导数现在将 在 处展成二阶泰勒公式:令 ，于是有 即3.6 3.6 变尺度法变尺度法 当 正定时， 当用 近似 时，由此看出 也必须满足 换句话说，式（5.29）就是称为 近似New

65、ton 条 件为了今后书写方便，记于是拟Newton条件可写为3.6 3.6 变尺度法变尺度法二、变尺度法迭代步骤（拟Newton法）已知目标函数 及其梯度 终止限（1）选定初始点 ；计算 ；选定初 始矩阵 ,要求 对称正定（例如 ）;置 （2）计算搜索方向 （3）作直线搜索 ，计算 3.6 3.6 变尺度法变尺度法（4）判别终止准则是否满足：若满足，则 就是 所求的极小点，打印，停机；否则转（5）（5）计算 （6） , 转（2） 其中校正矩阵 可由确定的公式来计算不同 的公式对应不同的拟Newton算法 3.6 3.6 变尺度法变尺度法拟Newton算法的流程如图所示k=k+1H准则满足Xk

66、+1开始结束选定X0， 对称正定阵H0，置k=0YN以下几段将要讨论各种公式的构成以及相应算法但是不论哪个公式都必须满足拟Newton条件.由式（5.30）和式（5.28）知， 必须满足 或 由此可见， 与 ， 和 有关满足式（5.31）的 有无穷多个，因此上述拟Newton算法构成一族算法下面分别介绍两个常用的公式3.6 3.6 变尺度法变尺度法（一）（一）DFP算法算法DFP算法首先是由Davidon（1959年）提出来的，后来，Fletcher和Powell（1963年）对Davidon的方法作了改进，最后才形成DFP算法D，F，P是这三位学者名字的字头这种算法是无约束最优化方法最有效的

67、方法之一3.6 3.6 变尺度法变尺度法 1DFP算法基本原理算法基本原理 考虑如下形式的校正公式 其中 ， 是待定 维向量， ， 是待定常数 这时校正矩阵是 现在来确定 : 根据拟Newton条件， 必须满足（5.31），于是有 或 3.6 3.6 变尺度法变尺度法满足以上方程的待定向量 和 有无穷多种取法，下面是其中的一种：注意到 和 都是数量，不妨取同时定出将这两式代回（5.32）得 这就是DFP校正公式3.6 3.6 变尺度法变尺度法 2DFP算法迭代步骤 在拟Newton算法中,只要把第（5）步改为计算式（5.33） 而其它不变，该算法就为DFP算法了 但是由于计算中舍去误差的影响，

68、特别是直线搜索不精确的影响，可能要破坏迭代矩阵 的正定性，从而导致算法失效为保证 的正定性，采取以下重置措施： 迭代 次后，重置初始点和迭代矩阵，即 以后重新迭代 3.6 3.6 变尺度法变尺度法已知目标函数 及其梯度 ,问题的维数 ,终止限 (1)选定初始点计算(2)置 (3)作直线搜索 计算(4)判别终止准则是否满足:若满足,则打印 停机；否则转(5)(5)若 则置 转(2);否则,转(6).(6)计算 置 转(3). 3.6 3.6 变尺度法变尺度法例例例例5.4 5.4 5.4 5.4 用DFP算法求 取解解解解: : : : 当我们取 时，DFP法与最速下降法具有相同的第1迭代点，在

69、5.1中已作了计算3.6 3.6 变尺度法变尺度法以下用DFP法作第二次迭代按DFP算法中的第（6）步计算因为所以3.6 3.6 变尺度法变尺度法搜索方向为从 X1出发沿P1进行直线搜索，即由 知 ，所以 ，由于 所以 是极小点3.6 3.6 变尺度法变尺度法（二）（二）BFGS算法算法 我们再介绍另一个有效和著名的变尺度算法由于它是Broyden， Fletcher（1970年），Goldfarb（1969年）和Shanno（1970年）共同研究的结果，因而叫做BFGS算法3.6 3.6 变尺度法变尺度法1BFGS算法基本原理算法基本原理考虑如下形式的校正公式 式中 这时校正矩阵为 3.6

70、3.6 变尺度法变尺度法式（5.34）中有一个参数 ，它可以取任何实数，每取一个实数就对应一种拟Newton算法容易验证，当取 时就是DFP校正公式令就转变为著名的DFGS校正公式3.6 3.6 变尺度法变尺度法2DFGS算法迭代步骤算法迭代步骤已知目标函数 及其梯度 ,问题的维数 ,终止限 （1）选取初始点 ,初始矩阵 ,给定终止限 （2）求初始梯度向量，计算 ,若 ，停 止迭代输出 ，否则，转（3）（3）构造初始BFGS方向，取 令 转（4）（4）进行一维搜索，求 ，使得 ， 令 ，转（5）3.6 3.6 变尺度法变尺度法（5）求梯度向量，计算 ，若 ，停 止迭代输出 ；否则，转（6）（6

71、）检验迭代次数，若 ,令 转（3）；否 则，转（7）（7）构造BFGS方向，用BFGS公式 计算 ，取 ，令 ，转（4） 3.6 3.6 变尺度法变尺度法DFGS算法的流程如图所示结束求tk使X0开始计算给定YN构造初始BFGS方向,取计算Xk+1用BFGS公式计算Hk+1，取令YNYN三、变尺度法有关说明变尺度法中的二个重要算法DFP算法和BFGS算法，它们的迭代过程相同，区别仅在于校正矩阵选取不同.对于DFP法，由于一维搜索的不精确和计算误差的积累可能导致某一轮的奇异，而BFGS法对一维搜索的精度要求不高.并且由它产生的不易变为奇异矩阵.FGS法比DFP法更具有好的数值稳定性，它比DFP法

72、更具有实用性3.6 3.6 变尺度法变尺度法3.7 3.7 坐标轮换法坐标轮换法坐标轮换法属于直接法它既可用于无约束最优化问题的求解，又可经过适当的处理用于约束最优化问题的求解一、坐标轮换法基本原理坐标轮换法的基本思想是把含有n 个变量的优化问题轮换地转化为单变量（其它变量视为常量）的优化问题所谓单变量优化问题就是沿某个坐标轴方向进行一维搜索的问题坐标轮换法的寻优思路是：先选定一个初始点 X0 作为第一轮搜索的始点 ，依次沿n个坐标轴方向进行一维搜索，每次只在一个坐标轴方向上改变相应变量的值，其它(n-1) 个变量均保持不变在沿第一个坐标轴方向进行一维搜索得到目标函数值的最小点（或近似最小点）

73、 后，再以此点作为始点转到沿第二个坐标轴方向进行一维搜索得到 ,直到沿第 n个坐标轴方向搜索结束得到 为一个循环如果 不满足收敛准则,则以 作为初始点转入下一轮循环,直到经过 次循环,获得满足收敛准则的点 ,即作为最优点 3.7 3.7 坐标轮换法坐标轮换法对于二维最优化问题，其搜索过程如图所示3.7 3.7 坐标轮换法坐标轮换法 在坐标轮换法中，沿各个坐标轴方向进行一维搜索时，常选用最优步长因子或加速步长法加速步长法则是从初始点出发，沿搜索（坐标轴）方向先取一个较小的步长 ，作前进（或后退）试探如试探成功（目标函数值有所减小），则按步长序列 加大步长（注意每次加大步长都是由初始点算起），直至

74、试探失败（目标函数值比前一次的有所增加）时，则取其前一次的步长作为沿这个坐标轴方向搜索的最优步长，并计算出该方向上的终止点，而后以这个终止点为始点再进行下一坐标轴方向的搜索，并重复上述步骤如此迭代下去，直到找到最优点 本节只用一维搜索法来确定最优步长 3.7 3.7 坐标轮换法坐标轮换法二、坐标轮换法迭代步骤 取初始点 置坐标轴搜索方向：首先沿 方向进行一维搜索，求出该方向上目标函数的极值点 ；再以 为初始点沿 方向进行一维搜索，得到极值点 仿此依次沿 进行一维搜索，最终得到极值点 这就完成了第一轮循环的搜索 3.7 3.7 坐标轮换法坐标轮换法如果 能够满足收敛准则，即可停止搜索，以 作为

75、输出否则，继续以 为初始点，进行第二轮循环，依次沿 进行一维搜索，得到第二循环的极值点如此进行下去，直至最终找到满足收敛准则（终止准则）的点 ，即求得了最优解 再求出目标函数值具体迭代过程如下：3.7 3.7 坐标轮换法坐标轮换法 已知目标函数 终止限 （1）任选取始点 作为第一轮循环的初始点 （2）置搜索方向依次为 （3）按下式求最优步长并进行迭代计算 3.7 3.7 坐标轮换法坐标轮换法 上 式中， 为循环次数， 为该循环中 一维搜索的序号， 为利用一维搜索 求出的最优步长（4）如果 ，即转（5）;如果 ，则转（3）.（5）收敛性准则 ： ，若满足判别式， 即停止迭代，输出最优解 及 若不

76、满足，则令 转（3） 3.7 3.7 坐标轮换法坐标轮换法坐标轮换法的计算流程如图所示k=k+1k=1X=X0i=n?开始给定YN沿 求 使i=1i=i+1N结束YX* 例例例例5.5 5.5 5.5 5.5 用坐标轮换法求 初始点 解解解解: : : : 从初始点出发，依次沿方向 搜索，以第一步为例,从X0出发,沿e1方向搜索,求得 点 3.7 3.7 坐标轮换法坐标轮换法得 即 于是得 再从 出发，沿 方向搜索，求得 点 求 可得 ，即取 于是有 3.7 3.7 坐标轮换法坐标轮换法 终止判别 因终止条件不满足,需继续迭代,取 进行第二轮循环迭代,各轮迭代计算数据见下表,最优解为 3.7

77、3.7 坐标轮换法坐标轮换法循环迭代序号是否满足收敛准则10.00，3.003.133.13，1.561.443.13，1.561.633.45否23.13，1.560.502.63，1.560.252.63，1.310.160.56否32.63，1.310.192.44，1.310.092.44，1.220.040.21否42.44，1.220.092.35，1.220.052.35，1.170.0150.10否52.35，1.170.062.29，1.170.032.29，1.140.0070.06否62.29，1.140.042.25，1.140.022.25，1.120.0040.04

78、5否72.25，1.120.032.22，1.120.012.22，1.110.0020.03是3.7 3.7 坐标轮换法坐标轮换法三、坐标轮换法有关说明 坐标轮换法的优点是算法简单，计算量小，其缺点是计算效率低，对高维问题尤为突出因此，坐标轮换法通常用于维数较低的优化问题（一般 ） 3.8 3.8 单纯形法单纯形法 单纯形法是利用对简单几何图形各顶点的目标函数值作相互比较，在连续改变几何图形的过程中，逐步以目标函数值较小的顶点取代目标函数值最大的顶点，从而进行求优的一种方法,属于直接法之一 一、单纯形法基本原理 现以求二元函数的极小点为例,说明单纯形法形成原理. 设二元函数 在 平面上取不在

79、同一条 直线上的三个点 并以它们为顶点构成一单纯 形三角形算出各顶点的函数值 比较其大小，现假定比较后有 这说明点 最差，点 最好，点 次差 为了寻找极小点，一般来说应向最差点的反对称方向进行搜索 3.8 3.8 单纯形法单纯形法以 记为 的中点（如图所示），在 的延长线上取点 ，使 称为 关于 的反射点算出 的函数值 ，可能出现以下几种情形： 3.8 3.8 单纯形法单纯形法 (1) 这说明搜索方向正确，可进一步扩大效果，继续沿 向前搜索，也就是向前扩张这时取 其中 为扩张因子，一般取 如果 ，说明扩张有利，就可以点 代替 点 构成新的单纯形 如果 ，说明扩张不利，舍去点 ，仍以点 代替 构

80、成新的单纯形 3.8 3.8 单纯形法单纯形法(2) 这说明搜索方向正确，但无须扩张，以 代替 构成新的单纯形 (3) 这表示 点走得太远，应缩回一些若以 表示压缩因子，则有 常取为0.5.以 代替 构成新的单纯形3.8 3.8 单纯形法单纯形法 (4) 这时应压缩更多一些，将新点压缩至 至 之间，令 注意，将式（5.35）中的 代之以 ，即可得式（5.36）如果 ，则以 代替 构成新的单 纯形 否则认为 方向上所有点的函数值 都大于 ，不能沿此方向搜索 这时，可以以 为中心进行缩边 若使顶点 和 向 移近一半距离, 得新单纯形 以此单纯形 为基础再进行寻优3.8 3.8 单纯形法单纯形法 以

81、上说明，不管哪种情况，我们都可以得到一个新的单纯形，其中至少有一顶点的函数值比原单纯形为小如此继续，直至满足收敛终止准则 在n维情况下，一个单纯形含有 个顶点，计算工作量较大，但原理和上述二维情况相同3.8 3.8 单纯形法单纯形法3.8 3.8 单纯形法单纯形法 二、单纯形法迭代步骤已知设 为 维变量,目标函数为 ,终止限为 (1) 构成初始单纯形 在 维空间中选初始点 （离最优点越近越好）,从 出发，沿各坐标方向以步长 得 个顶点 这样选择顶点可保证向量组 线性无关否则，就会使搜索范围局限在较低维的空间内，有可能找不到极小点当然，在各坐标方向可以走不同的距离步长 的范围可取0.515.0，

82、开始时常取 ，接近最优点时要减小，例如取0.51.0 (2) 计算各顶点的函数值 比较各函数值的大小，确定最好点 、最差点 和次 差点 ，即 3.8 3.8 单纯形法单纯形法(3) 计算 之外各点的“重点” ， 求出反射点(4) 当 时，需要扩张，令 如果，则以 代替 形成一新单纯 形；否则，以代 替 构成新单纯形然后转（8）.3.8 3.8 单纯形法单纯形法(5)当 时，以 代替 构成新单 纯形，然后转(8) (6)当 时，则需要收缩即令 以 代替 得新单纯形，并转(8)(7) 当 时，令 如果 则将单纯形缩边，可将向量 的长度缩小一半，即 这样可得一新单纯形否则就以 代替 得新单纯 形然后

83、转(8).3.8 3.8 单纯形法单纯形法 (8) 收敛性检验，每次迭代得到新单纯形后，即应进 行收敛性检验，如满足收敛指标，则迭代停止， 即 为所求的近似解否则，继续进行迭代计算 通常 所用的收敛准则是 或 式中 和 为预先给定的允许误差3.8 3.8 单纯形法单纯形法 例例例例5.65.65.65.6试用单纯形法求 的极小值 . 解解解解: : : : 选 并取 和 这三点不在一条直线上，用它们作为初始单纯形的顶点 （如图所示）3.8 3.8 单纯形法单纯形法然后计算各顶点的函数值： 可知 为最差点， 为最好点以 表示 和 的重心，则反射点3.8 3.8 单纯形法单纯形法由于 ，故需扩张取

84、 ，则因为 ，故以 代替 ,由 ， 和 构成新单纯形，然后进行下一个循环该问题的最优解为 经32次循环，可把目标函数 减小到3.8 3.8 单纯形法单纯形法3.8 3.8 单纯形法单纯形法 三、单纯形法有关说明 本算法上机占用内存很少，对变量不多且精度要求不高的问题此法很方便，但当变量个数多于10以上，此法就显得不十分有效 习题习题1用最速下降法求解2用Newton法求解 初始点 3用修正Newton法求解 初始点 习题习题4用共轭梯度法求解 取初始点5用共轭梯度法求解 自定初始点 6用DFP法求解 初始点 习题习题7用坐标轮换法求解取初始点8用单纯形法求解 给定初始单纯形顶点为 四四 常用约

85、束最优化方法常用约束最优化方法4.1 4.1 外点罚函数法外点罚函数法4.2 4.2 内点罚函数法内点罚函数法4.3 4.3 混合罚函数法混合罚函数法4.4 4.4 约束坐标轮换法约束坐标轮换法4.5 4.5 复合形法复合形法四四 常用约束最优化方法常用约束最优化方法考虑一般的约束最优化问题，其数学模型为 求解约束优化问题，就是要在可行域 中，找一个可行点 使目标函数 取得最小值此时称 为问题（6.1）的最优解 由处理约束条件的办法不同，约束优化方法也可分为直接法和间接法两大类 间接法的基本思想是将约束优化问题首先转换为一系列的无约束优化问题，然后利用无约束优化方法来求解，逐渐逼近约束问题的最

86、优解这些算法一般比较复杂，但由于它们可以采用计算效率高、稳定性好的无约束优化方法，故可用于求解高维的优化问四四 常用约束最优化方法常用约束最优化方法 直接法的基本思想是构造一迭代过程，使每次迭代点都在可行域D中，且一步一步地降低目标函数值，直到求得最优解这类方法很多，如约束坐标轮换法，复合形法等这类方法一般是算法简单，对目标函数和约束函数无特殊要求；但计算量大，需用机时较多，不适用维数较高的问题，而且一般用于求解只含不等式约束的优化问题.四四 常用约束最优化方法常用约束最优化方法4.1 4.1 外点罚函数法外点罚函数法 对于问题（6.1），本节所述方法的基本策略是，根据约束特点（等式或不等式）

87、构造某种“罚函数”，然后把它加到目标函数中去，使得对约束最优化问题的求解转化为对一系列无约束问题极小点或者无限地向可行域靠近，或者一直保持在可行集内移动，直到收敛于原来约束最优化问题极小点4.1 4.1 外点罚函数法外点罚函数法一、外点罚函数法基本原理 对问题（6.1），构造一函数为 其中 在式（6.2）中， 又称为惩罚函数 是一个逐渐增大的参数， 称为惩罚 因子 又称为问题（6.1）的增广目标函数显然，增广目标函数 是定义在 上的一个无 约束函数由增广目标函数 的构造知：4.1 4.1 外点罚函数法外点罚函数法当 时， 此时 的最优解就是问题（6.1）的最优解；而当 时, 的最优解就不一定是

88、问题（6.1）的最优解.但是研究当 时, 的最优解我们是不感兴趣的,为此规定:当 时, 在X点处的函数值迅速变大,换句话说,可行域外的任一点X处的函数值 都相当大.此时要求 在 中的最优解，只能让点X回到D内才有可能求得 在 中的最优解,然而一旦当点X回到D内,即 ,此时 就与问题（6.1）就有相同的最优解 4.1 4.1 外点罚函数法外点罚函数法 当 时， 迅速变大是通过罚因子M来实现简言之，外点罚函数法的思想是：当点 时，设法加大不可行点处的函数值，使不可行点不能成为 在 中的最优解一般，在用外点罚函数法求解问题（6.1）时，我们首先构造增广目标函数 ，然后按照无约束优化方法求解如果求出

89、的最优解为 ，则判断 是否属 于D .如果 ,则 是问题（6.1）的最优解；如果 ，则不是问题（6.1）的最优解，此时说明原来的罚因子给小了，需加大罚因子，使得 ，然后再重新计算 的最优解4.1 4.1 外点罚函数法外点罚函数法二、外点罚函数法迭代步骤 已知问题（6.1），构造增广目标函数其中惩罚函数 按式(6.2)构造,给定终止限 (可取 ).（1）选定初始点 ，初始罚因子 可取 ） 罚因子放大系数 ，置 （2）假设已获迭代点 ，以 为初始点，求解无约束问题 设其极小点为 （3）若 ，则 就是所要求的最优解，打印 ，停机；否则，转（4）（4）置 ，转（2）.4.1 4.1 外点罚函数法外点罚

90、函数法外点罚函数法的流程如图所示YN开始选定计算求出最优解输出结束例例例例6.1 6.1 6.1 6.1 求解解解解解: : : : 可以看出，本题的约束最优解为 现用外点罚函数法解这个约束优化问题 构造增广目标函数 由此解 得 给定一个罚因子 ,即可求得极小点 ,可以看出 不是可行点，且有4.1 4.1 外点罚函数法外点罚函数法右图给出了不同 时 的的轨迹例6.1可以帮助读者进一步 理解用外点罚函数法求极小点序列 时怎样收敛于约束最优点 4.1 4.1 外点罚函数法外点罚函数法例例例例6.2 6.2 6.2 6.2 用外点罚函数法求解解解解: : : : 增广目标函数为 按阶跃函数的定义，4

91、.1 4.1 外点罚函数法外点罚函数法 对于 ，下图画出了 的图形由图可 以看出， 的极小点 全不属于可行域因此只须 考虑 的情况4.1 4.1 外点罚函数法外点罚函数法 实际上，对于固定的 ，令 由此解得 这就是对于固定的 ， 的极小点例如，当 时， ； 当 时， ； 当 时， 若令 时，则这里的 就是例6.2的极小点4.1 4.1 外点罚函数法外点罚函数法二、外点罚函数法有关说明 在外点罚函数中，是通过一系列惩罚因子 求 的极小点来逼近原约束问题的最优点这一系列的无约束极小点 将从约束可行域外部向约束边界运动，实际上，随着罚因子的增大，迫使惩罚项的值逐渐减小，从而使 的极小点 沿着某一运动

92、轨迹逐渐接近等式约束面与起作用的不等式约束面上的最优点 当 趋于无穷大时， 的极小点就是原问题的最优点 4.1 4.1 外点罚函数法外点罚函数法 容易提出这样的问题：既然越大越好，那么迭代一开始 就把 取得很大，似乎求解一次无约束问题就可以求 到约束问题的最优解，可以少解几次无约束问题但是 可以证明， 越大，增广目标函数 的Hesse矩 阵的条件数越坏，给无约束问题求解增加越来越大的困 难，甚至无法求解4.1 4.1 外点罚函数法外点罚函数法因此，在迭代开始时又不得不把 取得小一些无疑，这增加了计算量，这正是外点罚函数法的弱点此外，当 在 处无定义时， 的性质变得很复杂另一方面，由于外点罚函数

93、法是从 外迭代点逼近D内最优解，所以在寻优的过程中不能直接观察到D内点的变化情况，也无法求得近似最优解4.1 4.1 外点罚函数法外点罚函数法4.2 4.2 内点罚函数法内点罚函数法 内点罚函数法刚好克服了外点罚函数法的不足之处，内点罚函数法的迭代过程均在可行域D内进行，它是通过在D内寻找一串点列 来逼近最优解 一、内点罚函数法基本原理首先在D的边界设置一道障碍，当从可地域D中的某点 出发进行迭代时，每当迭代点靠近D的边界时，便被此边界上的障碍（形如绝壁）阻挡碰回，这种阻挡碰回实质上也是一种惩罚，换句话说，所谓阻挡碰回就是当迭代点靠近D的边界时，离边界越近函数值增加越大，特别当迭代点到达边界上

94、时，函数值变为无穷大由此可以想象不可能在靠近D的边界上取得最优解，只能在远离D的边界内找到最优解4.2 4.2 内点罚函数法内点罚函数法按照这种想法，对于构造如下增广目标函数其中， 称为障碍因子， 称为障碍函数4.2 4.2 内点罚函数法内点罚函数法下面我们来分析 是否符合内点罚函数法的构造设想显然 和 都定义在D内， 取值较小时，当迭代点远离边界， ，此时 的最优解可作为问题（6.3）的近似最优解；4.2 4.2 内点罚函数法内点罚函数法4.2 4.2 内点罚函数法内点罚函数法但当迭代点靠近D的边界时，由 的构造知，即使 取值很小，但 ，即 使得 的函数值变得很大，此时显然不可能在区域D的边

95、界附近求得 的最优解，于是迫使迭代点被阻挡碰回到远离区域D的边界去寻优.用式子表示即是当障碍因子 逐渐减小时，有 且 式（6.4）中 为 的极小点序列， 为问题（6.3）的最优解.4.2 4.2 内点罚函数法内点罚函数法二、内点罚函数法迭代步骤已知对问题（6.3），构造增广目标函数 给定终止限（1）选定初始点 初始障碍因子 障碍因子的缩小系数 （可取 ）,置（2）假设已获迭代点 以 为初始点，求解 设其最优解为4.2 4.2 内点罚函数法内点罚函数法 （3）若 ，则 是问题（6.3）的 最优解，打印 停机；否则，转（4） （4） ，转（2）4.2 4.2 内点罚函数法内点罚函数法内点罚函数法的

96、流程图如图所示YN开始选定计算求出最优解输出结束例例例例6.3 6.3 6.3 6.3 用内点罚函数法求解解解解: : : : 构造增广目标函数 由 解得4.2 4.2 内点罚函数法内点罚函数法 给定一个罚因子 ，即可求得一极小点 右图给出不同罚因子时 的轨迹.可看出 在可行域内,且随着 逐渐逼近于0， 逐渐逼近理论最优点 例6.3可帮助读者进一步理解用内点罚函数法求极小点序列 时是怎样收敛于约束 最优点 4.2 4.2 内点罚函数法内点罚函数法三、内点罚函数法有关说明内点罚函数法的优点在于每次迭代都是可行点，当迭代到一定次数时，尽管可能没有达到约束最优点，但可以被接受为一个较好的近似最优点在

97、实际应用中，按该点求得的解可能比初始解有很大的改进，因而被工程技术人员接受，作为一种最优设计方案4.2 4.2 内点罚函数法内点罚函数法然而，内点罚函数法要求初始点位于可行域内部，即所有的约束需按严格不等式满足这对于简单的优化问题是不难解决的，因为原设计方案可能是用常规设计方法求得的，虽然不是最优，但一般是可行的，因此就可将原方案作为初始点但对复杂的优化问题，由于变量和约束较多，要想得到一个可行的初始点，并不十分容易，这时就要采用求可行点的算法4.2 4.2 内点罚函数法内点罚函数法在内点罚函数法中，障碍函数的定义域是约束可行域因此，在求 的最优解时，并不是求它在整个 维欧氏空间 中的最优解，

98、而是求 在约束可行域 上的极小点这是因为障碍函数 在D 的边界上无定义，而在 D的外部某些项为负，并且可取绝对值任意大的负值，从而使 趋于 所以 在全空间 内的极小点是不存在的4.2 4.2 内点罚函数法内点罚函数法因此，在用无约束优化方法求 的最优解时，要防止越过约束边界而搜索到非可行域中去，这就要求在一维搜索时，要适当控制步长，保证搜索在可行域内进行4.2 4.2 内点罚函数法内点罚函数法4.3 4.3 混合罚函数法混合罚函数法 前面介绍了外点罚函数法和内点罚函数法外点罚函数法的初始点可以任选，适用于求解具有等式约束与不等式约束的优化问题；而内点罚函数法要求初始点在可行域内，适用于求解不等

99、式约束优化问题为了综合外点罚函数法与内点罚函数法的优点，常将两种算法结合起来使用，这样便形成了混合罚函数法 一、混合罚函数法基本原理 对于同时具有不等式约束和等式约束的优化问题， 混合罚函数法采用的罚函数形式又分为内点形式和外点形式两种下面只介绍内点形式的混合罚函数，即4.3 4.3 混合罚函数法混合罚函数法采用内点形式的混合罚函数时，混合初始点 应选为满足各个不等式约束条件的点，障碍因子 亦应按内点罚函数法取为递减序列，即在混合罚函数 中， 的作用是限制搜索跑出不等式约束确定的区域，相当于内点罚函数法。而 的作用是迫使搜索点向等式约束面靠近，相当于外点罚函数法4.3 4.3 混合罚函数法混合

100、罚函数法 二、混合罚函数法迭代步骤已知问题（6.1），构造增广目标函数 给定终止限（1）选定初始点 ，要求满足不等式约束，初始障碍因子 ，惩罚因子缩小系数 ，置（2）假设已获 迭代点，以 为初始点，求 设其最优解为 4.3 4.3 混合罚函数法混合罚函数法（3）若 则 是问题（6.1）的最优解，打印 ， 停机；否则转（4）（4） ，转（2）4.3 4.3 混合罚函数法混合罚函数法三、混合罚函数法有关说明为了加速罚函数法的收敛速度，可以采用外插技术外插技术我们知道，在罚函数法中，给定一个罚因子（可以是障碍因子，也可以是惩罚因子）就可以求 的一个极小点 ，因此 的极小点可以看作是 的函数，记为 4

101、.3 4.3 混合罚函数法混合罚函数法前面讲过，当 时， 趋于约束最优点 因此可以设想，只要能将 的函数表达式写出来，就可通过求极限的方法求得约束最优点 为求 的表达式，自然会想到利用前几点 通过曲线的拟合来近似地予以反映这就是外插技术基本思想4.3 4.3 混合罚函数法混合罚函数法假定对于罚因子 已求得 的极小点 则可用高次多项式来拟合极小点的轨迹曲线，即式中 为系数向量，其值可由 个线性方程组求得4.3 4.3 混合罚函数法混合罚函数法令 则得它是约束最优点的 一个更好的逼近，可将其作为 的极小点的初始点,这将有利于加速收敛在实际应用中，常采用两点外插法或三点外插法两点外插法就是利用前两次

102、求得的 的极小点 和 来外插求得4.3 4.3 混合罚函数法混合罚函数法通常采用的外插公式为 式中 均为 维向量用已知 和 两点，而且 ，代入上式可求得 在式(6.5)中令 ，立即可求得外插点 也就是 4.3 4.3 混合罚函数法混合罚函数法4.4 4.4 约束坐标轮换法约束坐标轮换法 约束坐标轮换法是在无约束坐标轮换法的基础上，加入由约束函数构成的可行性限制，使每次迭代都必须在可行域内进行它的基本思想是将一个维的约束优化问题转化为依次沿个坐标轴方向轮流进行迭代的一维搜索问题一、约束坐标轮换法基本原理对于 维约束优化问题,依次沿坐标向量 的方向进行搜索时，由于只能在可行域内进行搜索，故不宜采用

103、最优步长，以免越出可行域为此，通常利用加步搜索法来确定搜索步长，以求得一系列可行点，使目标函数值逐次下降，直至收敛到最优解 4.4 4.4 约束坐标轮换法约束坐标轮换法现以 下图所示的二维情况进行说明4.4 4.4 约束坐标轮换法约束坐标轮换法设已知初始点 且满足约束条件,用步长 沿坐标轴方向 的正向搜索到点 时；因目标函数 的值增大(这意味着试探失败),故改为自 点沿 的负方向搜索得点 该点在可行域内,且使目标函数值有所下降(这意味着试探成功),说明该点同时满足可行性与适用性两个条件,于是再由点 出发,按加速步长 搜索至点 此点仍在可行域内,且该点的目标函数值继续下降;于是再按加速步长 搜索

104、至点 但此点已越出了可行域,即不满足可行性条件,故舍弃点 退回到点 并记其为 4.4 4.4 约束坐标轮换法约束坐标轮换法再由该点出发，转为用步长 沿坐标轴方向 搜索，得点 ，该点在可行域内，且使目标函数值下降；当加速步长为 后，所得的点 虽在可行域内，但不能使目标函数值下降，故予舍弃，仍退回到点 ，并记其为 至此，第一轮搜索完毕如点 已能满足计算精度，则停止搜索；否则，视该点为初始点 ，转入第二轮搜索，如果所求的最终点与初始点相同，则将步长缩小，即取步长为 ，然后重新进行搜索，直至求得满足计算精度的最优点 4.4 4.4 约束坐标轮换法约束坐标轮换法二、约束坐标轮换法迭代步骤已知目标函数 ，

105、约束函数 终止限 步长缩放因子 (1)选取初始点 ，初始步长 ，置 (2)由 出发，按步长 ，沿坐标轴 的正方向进行搜索，取 4.4 4.4 约束坐标轮换法约束坐标轮换法如果 且 ，则取 ，即加速向前搜索，直到不满足可行性条件或适用性条件，然后退回前一搜索点，将其作为该方向的最终点 如果沿 的正方向搜索不到能同时满足可行性条件和适用性条件的点，则改为沿 的负方向搜索，即取搜索步长为 ，仿照沿正方向的搜索过程，求得该方向的最终点 如果沿 的正、负两方向搜索均失败，则将点 作为该方向的最终点 ，然后转向下一个坐标轴方向继续进行搜索4.4 4.4 约束坐标轮换法约束坐标轮换法 (3)由 出发，沿坐标

106、轴方向 进行搜索，按步骤 (2)的做法，求得该方向的最终点 以此类推，直到沿第n个坐标轴方向 进行一维搜 索完毕，得到设计点 至此，完成了第 k轮搜 索，记第 k轮搜索得到的最优点为 (4)若 转(5)；否则需要进行下一轮搜索， 即令 转(2) (5)进行步长判别，如果步长 已缩短到足够小时， 即满足 时，则 为最优点，输出 结束否则，收缩步长，即令 转(2)4.4 4.4 约束坐标轮换法约束坐标轮换法 约束坐标轮换法的流程如图所示NYN开始选定从Xk-1出发沿各坐标方向依次搜索得到Xkk=k+1结束Y三、约束坐标轮换法有关说明 约束坐标轮换法具有算法明了，迭代简单，便于使用者掌握运用等优点但

107、是，它的收敛速度较慢，对于维数较高的优化问题很费机时另外，这种方法在某些情况下还会出现“死点”的病态，导致输出伪最优点为了辨别输出最优点的真伪可用 条件来检验通常的做法是输入多个初始点，并给出各种不同的初始步长进行多次运算，再从众多的输出解中进行比较而排除伪最优点4.4 4.4 约束坐标轮换法约束坐标轮换法4.5 4.5 复合形法复合形法 复合形法是目前求约束优化问题的一种重要的直接法，它是无约束最优化问题中单纯形法的推广其基本思想是：在可行域内选取 个设计点作为初始复合形的顶点，为了克服单纯形法容易产生降维的缺点，复合形的顶点个数取为n+2k5的优化问题，一般应适当减少顶点数目，取 （取整）

108、当然，顶点的最少数目不得低于 4.5 4.5 复合形法复合形法 习题习题1用外点罚函数法求解 2用外点罚函数法求解 习题习题3用外点罚函数法编程计算 取终止限 4. 用内点罚函数法求解 习题习题5用内点罚函数法求解6用内点罚函数法编程计算取初始点 初始障碍因子 缩小系数取 终止限 习题习题7分别用内点罚函数法和混合罚函数法编程计算 取终止限 8用约束坐标轮换法编程计算 取终止限 习题习题9.用复合形法编程计算 取终止限五 程序设计及其他优化方法1Fminbnd：进行有约束的一元函数最小值求解2Fminsearch：进行多变量函数的无约束优化。3Fminunc：也是对多变量无约束函数优化4Fmincon：对有约束的多变量函数寻优。