最优化方法及其应用.ppt

最优化（一）,一 最优化问题总论二 一维搜索法三 常用无约束最优化方法四 常用约束最优化方法五 程序设计及其他优化方法,一 最优化问题总论,无论做任何一件事，人们总希望以最少的代价取得最大的效益，也就是力求最好，这就是优化问题最优化就是在一切可能的方案中选择一个最好的方案以达到最优目标的学科例如，从甲地到乙地有公路、水路、铁路、航空四种走法，如果我们追求的目标是省钱，那么只要比较一下这四种走法的票价，从中选择最便宜的那一种走法就达到目标这是最简单的最优化问题，实际优化问题一般都比较复杂,概括地说，凡是追求最优目标的数学问题都属于最优化问题作为最优化问题，一般要有三个要素：第一是目标；第二是方案；第三是限制条件而且目标应是方案的“函数”如果方案与时间无关，则该问题属于静态最优化问题；否则称为动态最优化问题本书只讨论静态最优化问题,一 最优化问题总论,最简单的最优化问题实际上在高等数学中已遇到，这就是所谓函数极值，我们习惯上又称之为经典极值问题例1.1 对边长为a的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？,一 最优化问题总论,解 设剪去的正方形边长为x，由题意易知，与此相应的水槽容积为 令 得两个驻点：,一 最优化问题总论,第一个驻点不合实际，这是因为剪去4个边 长为的正方形相当于将铁板全部剪去现在来判断第二个驻点是否为极大点 因为 所以 是极大点 结论是：每个角剪去边长为的正方形可使所制成的水槽容积最大,一 最优化问题总论,例1.2 求侧面积为常数体积最大的长方体体积解 设长方体的长、宽、高分别为，体积为，则依题意知体积为限制条件为 由拉格朗日乘数法，考虑函数,1.1 最优化问题数学模型,令 由题意可知 应是正数，由此，将上面三个等式分别乘以，并利用已知条件得到,1.1 最优化问题数学模型,比较以上三式可得,从而x=y=z=a，右侧面积固定的长方体的最大体积客观存在，因此侧面积固定的长方体中以正方体体积最大,一 最优化问题总论,例1.3 某单位拟建一排四间的停车房，平面位置如图1.1所示由于资金及材料的限制，围墙和隔墙的总长度不能超过40m，为使车房面积最大，应如何选择长、宽尺寸？,一 最优化问题总论,解 设四间车房长为，宽为由题意可 知面积为 且变量，应满足 即求，,一 最优化问题总论,最优化问题的数学模型包含有三个要求：即变量（又称设计变量）、目标函数、约束条件一、变量二、目标函数三、约束条件四、带约束条件的优化问题数学模型表示形式,一 最优化问题总论,综上所述，全书所要讨论的问题是如下的（静态）最优化问题，其表示形式有三种：第一种最优化问题表示形式为第二种最优化问题表示形式为,一 最优化问题总论,第三种最优化问题表示形式为（1.1）其中,一 最优化问题总论,上述三种表示形式中，称为集约束在所讨论的最优化问题中，集约束是无关紧要的这是因为一般，不然的话，通常也可用不等式约束表达出来因此今后一般不再考虑集约束 满足所有约束的点称为容许点或可行点容许点的集合称为容许集或可行域可用 表示,一 最优化问题总论,一般地，对于最优化问题（1.1）的求解，是指在可行域内找一点，使得目标函数在该点取得极小值，即 这样的称为问题（1.1）的最优点，也称极小点，而相应的目标函数值 称为最优值；合起来称为最优解，但习惯上把本身称为最优解最优点的各分量和最优值必须是有限数,一 最优化问题总论,一、二维最优化问题的图解法 讨论二维最优化问题为,一 最优化问题总论,（一）约束集合当约束函数为线性时，等式约束在坐标平面上为一条直线，不等式约束在坐标平面上为一半平面；当约束函数为非线性时，等式约束条件在坐标平面上为一条曲线（如图），不等式约束把坐标平面分成两部分当中的一部分（如图）,一 最优化问题总论,综上所述，当把约束条件中的每一个等式所确定的曲线，以及每一个不等式所确定的部分在坐标平面上画出之后，它们相交的公共部分即为约束集合D,一 最优化问题总论,例1.4 在坐标平面上画出约束集合解:满足的区域为以原点为圆心，半径为1的圆；满足的区域为第一象限的扇形（如图所示）,一 最优化问题总论,（二）等高线 我们知道 在三维空间中表示一张曲面 其中 为常数）在三维空间中表示平行于 平面的一个平面，这个平面上任何一点的高度都等于常数（如图）在三维空间中曲面 与平面 有一条交线 交线在平面上的投影曲线是，可见曲线上的点到平面 的高度都等于常数C，也即曲线上的的函数值都具有相同的值,一 最优化问题总论,当常数取不同的值时，重复上面的讨论，在平面上得到一族曲线等高线.等高线的形状完全由曲面的形状所决定；反之，由等高线的形状也可以推测出曲面的形状,一 最优化问题总论,例1.5 在坐标平面 上画出目标函数的等高线 解:因为当 取时，曲线表示是以原点为圆心，半径为的圆因此等高线是一族以原点为圆心的同心圆（如图所示）,一 最优化问题总论,例1.6 用图解法求解二维最优化问题解:如图，目标函数的等高线是以为圆心的同心圆，并且这族同心圆的外圈比内圈的目标函数值大因此，该问题为在约束集中找一点,使其落在半径最小的那个同心圆上。问题的最优解为：,一 最优化问题总论,二、最优化问题的迭代解法（一）迭代方法,在经典极值问题中，解析法虽然具有概念简明,计算精确等优点，但因只能适用于简单或特殊问题的寻优,对于复杂的工程实际问题通常无能为力，所以极少使用。最优化问题的迭代算法是指：从某一选定的初始点出发，根据目标函数、约束函数在该点的某些信息，确定本次迭代的一个搜索方向和适当的步长，从而到达一个新点，用式子表示即为,(1.2),一 最优化问题总论,式中,前一次已取得的迭代点，在 开始计算时为迭代初始点；新的迭代点；第k次迭代计算的搜索方向；第k次迭代计算的步长因子,一 最优化问题总论,按照式（1.2）进行一系列迭代计算所根据的思想是所谓的“爬山法”，就是将寻求函数极小点（无约束或约束极小点）的过程比喻为向“山”的顶峰攀登的过程，始终保持向“高”的方向前进，直至达到“山顶”当然“山顶”可以理解为目标函数的极大值，也可以理解为极小值，前者称为上升算法，后者称为下降算法这两种算法都有一个共同的特点，就是每前进一步都应该使目标函数有所改善，同时还要为下一步移动的搜索方向提供有用的信息如果是下降算法，则序列迭代点的目标函数值必须满足下列关系,一 最优化问题总论,如果是求一个约束的极小点，则每一次迭代的新点都应该在约束可行域内，即 下图为迭代过程,一 最优化问题总论,（二）收敛速度与计算终止准则（1）收敛速度作为一个算法A，能够收敛于问题的最优解当然是必要的，但光能收敛还不够，还必须能以较快的速度收敛，这才是好的算法定义1.1 设由算法A产生的迭代点列 在某种“|”的意义下收敛于点，即,若存在实数 及一个与迭代次数 无关的常数 使得 则算法A产生的迭代点列叫做具有 阶收敛速度,或算法A叫做是 阶收敛的，特别地:,一 最优化问题总论,当，迭代点列 称为具有线性收敛速度或算法A称为线性收敛的 当，或 时，迭代点列 叫做具有超线性收敛速度或称算法A是超线性收敛 当 时，迭代点列 叫做具有二阶收敛速度或算法A是二阶收敛的 一般认为，具有超线性收敛或二阶收敛的算法是较快速的算法,一 最优化问题总论,(2)计算终止准则 用迭代方法寻优时，其迭代过程总不能无限制地进行下去，那么什么时候截断这种迭代呢？这就是迭代什么时候终止的问题 从理论上说，当然希望最终迭代点到达理论极小点，或者使最终迭代点与理论极小点之间的距离足够小时才终止迭代但是这在实际上是办不到的因为对于一个待求的优化问题，其理论极小点在哪里并不知道所知道的只是通过迭代计算获得的迭代点列，因此只能从点列所提供的信息来判断是否应该终止迭代 对于无约束优化问题通常采用的迭代终止准则有以下几种：,一 最优化问题总论,点距准则相邻两迭代点之间的距离已达到充分小，即式中 是一个充分小正数，代表计算精度函数下降量准则相邻两迭代点的函数值下降量已达到充分小当 时，可用函数绝对下降量准则当 时，可用函数相对下降量准则梯度准则目标函数在迭代点的梯度已达到充分小，即这一准则对于定义域上的凸函数是完全正确的若是非凸函数，有可能导致误把驻点作为最优点。对于约束优化问题，不同的优化方法有各自的终止准则,一 最优化问题总论,综上所述，优化算法的基本迭代过程如下：选定初始点，置 按照某种规则确定搜索方向 按某种规则确定 使得 计算 判定 是否满足终止准则若满足，则打印 和,停机；否则置,转,一 最优化问题总论,上述算法框图如右图,一 最优化问题总论,就优化机制与行为而分，目前工程中常用的优化算法主要可分为：经典算法、构造型算法、改进型算法、基于系统动态演化的算法和混合型算法等（1）经典算法包括线性规划、动态规划、整数规划和分枝定界等运筹学中的传统算法，其算法计算复杂性一般很大，只适于求解小规模问题，在工程中往往不实用,一 最优化问题总论,（2）构造型算法用构造的方法快速建立问题的解，通常算法的优化质量差，难以满足工程需要譬如，调度问题中的典型构造型方法有：Johnson法、Palmer法、Gupta法、CDS法、Daunenbring的快速接近法、NEH法等（3）改进型算法，或称邻域搜索算法从任一解出发，对其邻域的不断搜索和当前解的替换来实现优化根据搜索行为，它又可分为局部搜索法和指导性搜索法,一 最优化问题总论,（4）基于系统动态演化的算法将优化过程转化为系统动态的演化过程，基于系统动态的演化来实现优化，如神经网络和混沌搜索等（5）混合型算法指上述各算法从结构或操作上相混合而产生的各类算法 优化算法当然还可以从别的角度进行分类，如确定性算法和不确定性算法，局部优化算法和全局优化算法等,一 最优化问题总论,一、组合优化问题建模 归纳而言，最优化问题可分为函数优化问题和组合优化问题两大类。上一节介绍的最优化数学模型属于函数优化问题，该函数优化的对象是一定区间内的连续变量。本节重点介绍组合优化问题，组合优化的对象是解空间中的离散状态,一 最优化问题总论,组合优化问题是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，所研究的问题涉及信息技术、经 济管理、工业工程、交通运输、通信网络 等诸多领域，该问题数学模式可表示为 其中，为目标函数，为约束函数，X为决策变量，表示有限个点组成的集合,一 最优化问题总论,例1.9 0-1背包问题（knapsack problem）,设有一个容积为 b的背包，n个体积分别为，价值分别为 的物品，如何以最大的价值装包?该问题称为0-1背包问题用数学模型表示为(1.3)其中目标(1.3)欲使包内所装物品的价值最大；(1.4)为包的能力限制；(1.5)表示xi为二进制变量，xi=1表示装第i个物品，xi=0表示不装,一 最优化问题总论,例1.10 旅行商问题(TSP，traveling salesman problem)一个商人欲到个城市推销商品，每两个城市i和j之间的距离为，如何选择一条道路使得商人每个城市走一遍后回到起点且所走路径最短 TSP还可以细分为对称和非对称距离两大类问题当对任意的I,j时都有,则称该TSP为对称距离TSP，否则称非对称距离TSP,一 最优化问题总论,对一般的TSP，它的一种数学模型描述,一 最优化问题总论,以上是基于图论的数学模型 式（1.10）中的决策变量 表示商人行走的路线包含从城市i到城市路径，表示商人没有选择走这条路 的约束可以减少变量的个数，使得共有 个决策变量;目标（1.6）要求距离之和最小;式（1.7）要求商人从城市出来一次;式（1.8）要求商人走入城市只有一次;式（1.7）和式（1.8）表示每个城市经过一次;仅有式（1.7）和式（1.8）的约束无法避免回路的产 生，一条回路是由 个城市和k条弧组成，式（1.9）约束旅行商在任何一个城市子集中不形 成回路，其中|S|表示集合S中元素个数,一 最优化问题总论,例1.11 聚类问题 m维空间上的n个模式 要求聚类成k类，使得各类本身内的点最相近，即 其中 为第p类的中心，为第p类中的点数,一 最优化问题总论,二 一维搜索法,搜索区间及其确定方法 对分法 Newton切线法 黄金分割法 抛物线插值法,由第一章关于求解最优化问题概述中我们知道，从已知迭代点 出发按照基本迭代格式 来求解最优化问题，其关键在于如何构造一个搜索方向 和确定一个步长 使下一迭代点 处的目标函数值下降，即 现在我们来讨论，当搜索方向 已经确定的情况下，如何来确定步长？步长因子的选取有多种方法，如取步长为常数，但这样选取的步长并不最好，如何选取最好步长呢？实际计算通常采用一维搜索来确定最优步长,二 一维搜索法,对无约束最优化问题当已知迭代点 和下降方向 时，要确定适当的步长 使 比 有所下降，即相当于对于参量 的函数 要在区间 上选取 使 即 由于这种从已知点 出发，沿某一下降的探索方向 来确定步长 的问题，实质上是单变量函数 关于变量 的一维搜索选取问题，故通常叫做一维搜索,二 一维搜索法,按这种方法确定的步长 又称为最优步长,这种方法的优点是:它使目标函数值在搜索方向上下降得最多 今后为了简便起见，我们用记号 表示从点 出发沿方向 对目标函数作直线搜索所得到的极小点是 其中l和s分别是Linear search(直线搜索)两词的词首,在目标函数 已确定的条件下(4.1)等价于如下两式：,二 一维搜索法,下面进一步解释迭代点 的空间位置容易证明，若从 出发，沿 方向进步一维搜索得极小点 则该点 处的梯度方向 与搜索方向 之间应满足事实上，设 对 求导有令 即 所以,二 一维搜索法,式（4.2）的几何意义是明显的:从某一点 出发沿方向 对目 标函数 作直线搜索,所得到 的极小点为 式（4.2）指出，梯度 必与搜索方向 正交.又因为 与目标函数过点 的等值面 正交，所以进一步看到，搜索方向 与这个等值面在点 处相切（如图所示）,二 一维搜索法,搜索区间及其确定方法,一、搜索区间 设一维最优化问题为 为了求解问题(4.3),我们引入如下的搜索区间概念 定义4.1 若存在闭区间 使 则称 是问题(4.3)的搜索区间 简言之，一个一维最优化问题的搜索区间，就是包含该问题最优解的一个闭区间通常，在进行一维搜索时，一般要先确定出问题的一个搜索区间，然后再此区间中进行搜索求解,二、加步探索法下面，介绍一个确定问题(4.3)的搜索区间的简单方法这个方法的思想是：先选定一个初始点 或 和初始步长 然后，沿着轴的正方向探索前进一个步长，得到新点 若目标函数在新点处的值是下降了,即 则下一步就从新点 出发加大步长，再向前探索.若目标函数在新点处的值上升,即 则下一步仍以 为出发点以原步长开始向 轴的负方向同样探索当达到目标函数上升的点时，就停止探索，这时便得到问题（4.3）的一个搜索区间这种以加大步长进行探索来寻找探索区间的方法叫加步探索法,搜索区间及其确定方法,加步探索法算法的计算步骤：(1)选取初始数据选取初始点 计算 给出初始步长 加步系数 令(2)比较目标函数值令 计算，若 转(3)否则转(4)(3)加大探索步长,令 同时令 转(2)(4)反向探索,若 转换探索方向,令 转(2);否则,停止迭代,令 输出,搜索区间及其确定方法,加步探索法算法的流程图如图所示,在加步探索法中，一般建议 若能估计问题（4.3）的最优解的大体位置的话，初始点要尽量取接近于问题（4.3）的最优解.在具体运用上述加步探索法时，有时还要考虑一些细节问题例如，当探索得到新点处的目标函数值和出发点处相同时，以及初始步长应如何选取等，都需作适当处理,搜索区间及其确定方法,三、单谷区间与单谷函数 由于以后要介绍的一些维搜索方法，主要适用于问题（4.3）在搜索区间中只有唯一的最优解的情况，为此，我们再给出下面单谷区间与单谷函数概念 定义4.2 设 闭区间 若存在点 使得 在 上严格递减，在 上严格递增，则称 是函数 的单谷区间，是 上单谷函数,搜索区间及其确定方法,由定义4.2易知，一个区间是某函数的单谷区间意味着，在该区间中函数只有一个“凹谷”（极小值）例如，左图中的 是 的单谷区间，也即 是 上的单谷函数右图中的 不是 的单谷区间，即 不是 上的单谷函数,搜索区间及其确定方法,另外，从定义4.2还可知，某区间上的单谷函数在该区间上不一定是连续函数，而凸函数在所给区间上必然是单谷函数（如左图所示）由定义4.1和定义4.2知，函数的单谷区间总是相应问题（4.3）的一个搜索区间（如左图所示），但反之不然（如右图所示）,搜索区间及其确定方法,单谷区间和单谷函数有如下有用的性质：定理4.1 设 是的单谷区间，任取 并且（1）若有，则 是 的单谷区间（2）若有，则 是 的单谷区间定理4.1说明，经过函数值的比较可以把单谷区间缩短为一个较小的单谷区间换句话说利用这个定理可以把搜索区间无限缩小，从而求到极小点.以下介绍的几种一维搜索方法都是利用这个定理通过不断地缩短搜索区间的长度，来求得一维最优化问题的近似最优解,搜索区间及其确定方法,一、对分法基本原理求解一维最优化问题 一般可先确定它的一个有限搜索区间，把问题化为求解问题，然后通过不断缩短区间的长度，最后求得最优解,对分法,设 在已获得的搜索区间 内具有连续的一阶导数因为 在 上可微，故 在 上连续，由此知 在 上有最小值令，总可求得极小点 不妨设 在 上是单减函数；在 上是单增函数所以 时，故；当 时，亦即 对分法的原理如图,对分法,二、对分法迭代步骤已知，表达式，终止限 确定初始搜索区间，要求(2)计算 的中点(3)若，则，转(4)；若，则，转(5)；若，则，转(4)(4)若，则，转(5)；否则转(2)(5)打印，停机,对分法,对分法的计算流程如图所示,三、对分法有关说明 对分法每次迭代都取区间的中点 a.若这点的导数值小于零，说明的根位于右半区间中，因此去掉左半区间；b.若中点导数值大于零，则去掉右半区间；c.若中点导数值正好等于零，则该点就是极小点 因为每次迭代都使原区间缩短一半，所以称为对分法或二分法,对分法,Newton切线法,一、Newton切线法基本原理 设 在已获得的搜索区间 内具有连续二阶导数，求 因为 在 上可微，故 在 上有最小值，令,下面不妨设在区间 中经过 次迭代已求得方程 的一个近似根 过 作曲线 的切线,其方程是然后用这条切线与横轴交点的横坐标 作为根的新的近似（如图）它可由方程（4.4）在令 的解出来，即 这就是Newton切线法迭代公式,Newton切线法,二、Newton切线法迭代步骤已知，表达式，终止限 确定初始搜索区间，要求 选定 计算 若，则，转（3）；否则转（5）打印，停机,Newton切线法,Newton切线法的计算流程如图所示,三、Newton切线法有关说明这种方法一旦用好，收敛速度是很高的如果初始点选得适当，通常经过几次迭代就可以得到满足一般精度要求的结果.但是它也有缺点：第一，需要求二阶导数如果在多维最优化问题的一维搜索中使用这种方法，就要涉及Hesse矩阵，一般是难于求出的,Newton切线法,第二，当曲线 在 上有较复杂的弯曲时，这种方法也往往失效如图(a)所示的迭代：结果 跳出.迭代或者发散，或者找到的根并不是我们想要的结果第三，即使曲线比较正常，在 中或者上凹或者下凹，初始点的选取也必须适当在图（b）的情况下，曲线上凹，应选点b作为初始点；而在图（c）的情况下，曲线下凹，应选点a为初始点否则都可能失败,Newton切线法,黄金分割法,一、黄金分割法基本原理 要介绍黄金分割法有必要回顾一下古老的黄金分割问题所谓黄金分割就是将一线段分为二段的方法这样分后，要求整段长L与较长段x的比值正好等于较长段x与较短段 的比值(如图),于是则解得由此可见长段的长度应为全长的0.618倍，而短段的长度应为全长的0.382倍因为古代的人们认为按0.618的比率来分割线段是最协调，胜似黄金，故称之为黄金分割,黄金分割法,用黄金分割法进行一维搜索，其基本思想是在单谷区间内适当插入两点，由此把区间分为三段，然后再通过比较这两点函数值大小，就可以确定是删去最左段还是最右段，或者同时删去左右两段保留中间段如此继续下去可将单谷区间无限缩小,黄金分割法,二、黄金分割法迭代步骤 现在提出一个问题，就在 上如何选取二点使得迭代次数最小而区间缩短最快？要解决这个问题，人们想到对区间 选二点 等价于将区间长度 进行黄金分割，也就是将第一个搜索点 取在 的0.618处，第二个搜索点 取成 的对称点即 的0.382处（如图所示）,黄金分割法,即要求接着计算 与 的值，并根据 与 的值的大小关系分情况讨论：（1）若,说明 是好点，于是把区间 划掉，保留，则 内有一保留点，置新的区间；（2）若，说明 是好点，于是应将 划掉，保留,则 内有保留点,置新的区间.,黄金分割法,(3)若 则应具体分析,看极小点可能在哪一边再决定取舍，在一般情况下，可同时划掉 和 仅保留中间的 重置新的区间 接下来是在留下的区间 内找好点重复上面的步骤，直到搜索区间 小于给定的允许误差 为止。这样就得到黄金分割法迭代算法：,黄金分割法,已知，常数 0.382，终止限(1)确定 的初始搜索区间(2)计算(3)计算(4)若,则打印，停机；否则，转(5)(5)判别是否满足：若满足，则置，然后转(3)；否则，置，然后转(4),黄金分割法,黄金分割法算法流程如图所示,三、黄金分割法有关说明 黄金分割法是通过所选试点的函数值而逐步缩短单谷区间来搜索最优点该方法适用于单谷区间上的任何函数，甚至可以是不连续函数，因此这种算法属于直接法，适用相当广泛,黄金分割法,抛物线插值法,一、抛物线插值法基本原理 考虑一维搜索问题 假设其中 是定义在区间 上的单峰函数首先用试探法在 上找一点，使之满足,通过目标函数曲线上的三个点 作它的二次拟合曲线（如图所示）,图4.14,抛物线插值法,由于上述三个点既是目标函数曲线 上的点，又是二次拟合曲线 上的点，故有方程组 将方程组（4.5）中的 消去，得,抛物线插值法,从方程组（4.6）可解出待定系数 对于二次拟合函数，我们很容易求得它的极小值点令 即，从中解出 即为二次拟合函数 的极小值点,抛物线插值法,将式（4.7）与式（4.8）代入式（4.9）得用区间 上二次拟合函数 的这个极小值点 作为目标函数 在该区间极小值点的一个估计值若 和 已充分接近，即对给定的允许误差 使 成立时，就可被看作是 在区间 内近似最优解；否则应缩短区间，按照 值保持两头大、中间小的原则构成新的三点，继续上述过程，直至不等式（4.11）成立为止,抛物线插值法,二、抛物线插值法迭代步骤下面具体介绍缩短区间,构成新三点的方法 由式（4.10）得到的点,在区间 内既可能在点 的左侧(即),又可能在 的右侧(即).分别对应这两种情形比较 和 的大小，又有 等三种情形，故共有如下六种情况（如图所示）：,抛物线插值法,抛物线插值法,（1）对于图(a)的情况:因,所以相对 为说 是好点，故划掉区间,保留 为新区间，故置 保持不变；（2）对于图(b)的情况:因,所以相对 来说 是好点，故划掉 保留为 新区间，故置 与 保持不变；（3）对于图(c)的情况：因 所以相对 来说 是好点，故划掉,保留 为新区间，故置 保持不变；,抛物线插值法,（4）对于图(d)的情况:因 所以相对 来说 是好点，故划掉 保留 故置，与 保持不变（5）对于图(e)的情况：一般同时划掉 及 仅留中间的，故置（6）对于图(f)的情况：一般同时划掉 及，仅留中间的，故置,抛物线插值法,通过上述讨论,我们可直接给抛物线插值法的迭代流程图.,三、抛物线插值法有关说明 抛物线插值法是多项式逼近法的一种所谓多项式逼近，是利用目标函数在若干点的函数值或导数值等信息，构成一个与目标函数相接近的低次插值多项式，用该多项式的最优解作为目标函数的近似最优解,抛物线插值法,习题,1用加步探索法确定一维最优化问题 的搜索区间，要求选取 2用对分法求解 已知初始单谷区间，按精度 计算3用Newton法求解 用第题求得的区间，按精度 计算,用黄金分割法求解 已知初始单谷区间，按精度 计算用抛物线插值法求解 已知初始单谷区间,习题,三 常用无约束最优化方法,3.1 最速下降法3.2 Newton法3.3 修正Newton法3.4 共轭方向法3.5 共轭梯度法3.6 变尺度法3.7 坐标轮换法3.8 单纯形法,三 常用无约束最优化方法,本章开始讨论多维无约束最优化问题其中 这个问题的求解是指在 中找一点，使得对于任意的 都有 成立，则点 就是问题（3.1）的全局最优点但是，大多数最优化方法只能求到局部最优点，即在 中找到一点，使得式（3.2）在 的某个领域中成立这个矛盾对于实际问题一般容易解决根据问题的实际意义多半可以判定用优化方法求出的局部最优解是否为全局最优解而在理论上这是个比较复杂的问题，本书不涉及,无约束优化方法是优化技术中极为重要和基本的内容之一它不仅可以直接用来求解无约束优化问题，而且很多约束优化问题也常将其转化为无约束优化问题，然后用无约束优化方法来求解另外，有些无约束优化方法只需略加处理，即可用于求解约束优化问题,三 常用无约束最优化方法,无约束优化理论发展较早，比较成熟，方法也很多，新的方法还在陆续出现把这些方法归纳起来可以分成两大类：一类是仅用计算函数值所得到的信息来确定搜索方向，通常称它为直接搜索法，简称为直接法，另一类需要计算函数的一阶或二阶导数值所得到的信息来确定搜索方向，这一类方法称为间接法（解析法）直接法不涉及导数、Hesse矩阵，适应性强，但收敛速度较慢；间接法收敛速度快，但需计算梯度，甚至需要计算Hesse矩阵 一般的经验是,在可能求得目标函数导数的情况下还是尽可能使用间接方法；相反,在不可能求得目标函数的导数或根本不存在导数的情况下,当然就应该使用直接法,三 常用无约束最优化方法,对于问题（3.1）为了求其最优解，按最优化算法的基本思想是从一个给定的初始点 出发，通过基本迭代格式，按照特定的算法 产生一串点列，如果点列收敛，则该点列的极限点为问题（3.1）的最优解,3.1 最速下降法,一、最速下降法基本原理 在基本迭代格式 中，每次迭代搜索方向 取为目标函数 的负梯度方向，即，而每次迭代的步长 取为最优步长，由此所确定的算法 称为最速下降法,3.1 最速下降法,为了求解问题（3.1），如图所示，假定我们 已经迭代了 次 获得了第 个迭代点 现在从 出发，可选择的下降方向很多，一个非常自然的想法是沿最速下降方向（即负梯度方向）进行搜索应该是有利的，至少在 邻近的范围内是这样。因此，取搜索方向为.,3.1 最速下降法,为了使目标函数在搜索方向上获得最多的下降，沿 进行一维搜索，由此得到第 个迭代点，即，其中步长因子 按下式确定 也可记为显然,令 就可以得到一个点列，其中 是初始点,由计算者任意选定.当 满足一定的条件时,由式(5.3)所产生的点列 必收敛于的极小点以后为书写方便,记.因此在不发生混淆时，再记,3.1 最速下降法,二、最速下降法迭代步骤 已知目标函数 及其梯度，终止（1）选定初始点,计算 置（2）作直线搜索：；计算（3）用终止准则检测是否满足：若满足，则打印最优 解 停机；否则，置 转(2),3.1 最速下降法,最速下降法算法流程如图所示,N,将最速下降法应用于正定二次函数 可以推出显式迭代公式.设第 次迭代点为 我们来求 的表达式 对式（5.4）关于 求梯度，有 因此，现在从 出发沿 作直线搜索以确定，于是，其中 是最优步长因子,3.1 最速下降法,又因式(4.2),有 再利用(5.5),(5.6),(5.7)可得：或 由此解出：代入（5.7）中得到 这就是最速下降法用于二次函数的显式迭代公式,3.1 最速下降法,3.1 最速下降法,例5.1 试用最速下降法求函数 的极小点.迭代两次，计算各迭代点的函数值，梯度及其模，并验证相邻两个搜索方向是正交的设初始点为 解:与（5.4）比较，得 梯度表达式是,由，计算因为目标函数是二次的，可以使用式(5.8),所以有,3.1 最速下降法,因为 由此说明相邻两个搜索方向 是正交的,计算,3.1 最速下降法,三、最速下降法有关说明 最速下降法的优点是算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点.但它有一个严重缺点就是收敛速度 沿负梯度方向函数值下降很快的廉洁，容易使人们产生一种错觉，认为这一定是最理想的搜索方向，沿该方向搜索时收敛速度应该很快，然而事实证明，梯度法的收敛速度并不快,3.1 最速下降法,特别是对于等值线（面）具有狭长深谷形状的函数，收敛速度更慢其原因是由于每次迭代后下一次搜索方向总是与前一次搜索方向相互垂直，如此继续下去就产生所谓的锯齿现象即从直观上看，在远离极小点的地方每次迭代可能使目标函数有较大的下降，但是在接近极小点的地方，由于锯齿现象，从而导致每次迭代行进距离缩短，因而收敛速度不快.,3.1 最速下降法,3.2 Newton法,如果目标函数 在 上具有连续的二阶偏导数，其Hesse矩阵 正定并且可以表达成为显式（今后为了简便起见，记，那么可以使用下述的Newton法这种方法一旦好用，收敛速度是很快的它是一维搜索Newton切线法的推广,一、Newton法基本原理为寻求收敛速度快的算法，我们考虑在应用基本迭代公 式 中，每轮迭代在迭代的起始点 处用 一个适当的二次函数来近似该点处的目标函数，由此 用点 指向近似二次函数极小点的方向来构造搜索方向(如图所示),3.2 Newton法,下面具体讨论Newton法 设最优化问题为，其中 二阶可导，Hesse矩阵 正定不妨设经过 次迭代已获点，现将 在 处展开成二阶泰勒公式，于是有显然 是二次函数，特别由题设知 还是正定二次函数，所以 是凸函数且存在唯一全局极小点,3.2 Newton法,为求此极小点，令即可解得亦即对照基本迭代格式易知，式（5.9）中的搜索方向 步长因子,3.2 Newton法,换句话说从点 出发沿搜索方向 并取步长 即可得 的极小点.因此 是直指点 处近似二次函数 的极小点的方向此时称 为从点 出发的Newton方向从初始点开始，每一轮从当前迭代点出发，沿Newton方向并取步长 的算法称为Newton法,3.2 Newton法,二、Newton法迭代步骤已知目标函数 及其梯度 Hesse矩阵,终止限(1)选定初始点 计算 置(2)计算(3)由方程 解出(4)计算(5)判别终止准则是否满足：若满足，则打印最优解 停机；否则置 转(2).,3.2 Newton法,Newton法的流程如图所示,Y,例5.2 试用Newton法求 的极小点,初始点取为 解:梯度为 Hesse矩阵为 其逆矩阵为 由迭代公式（5.13）得第1 迭代点为由于此时，停止迭代得因此，它就是极小点,3.2 Newton法,从上述例5.2我们看到，用Newton法求解，只经一轮迭代就得到最优解这一结果并不是偶然的，因为从Newton方向的构造我们知道，对于正定二次函数，Newon方向就是指向其极小点的方向因此，用Newton法解目标函数为正定二次函数的无约束最优化问题，只需一次迭代就可得最优解,3.2 Newton法,对于目标函数是非二次函数的非约束最优化问题，一般地说，用Newton法通过有限轮迭代并不能保证可求得最优解但由于目标函数在最优解附近能近似于二次函数，因此当先取接近于最优解的初始点使用Newton法求解时，其收敛速度一般是快的事实上，可以证明在初始点离最优解不远的条件下，Newton法是二次收敛的但是当初始点选得离最优解太远时，Newton法并不一定是收敛的方法，甚至连其下降性也很难保证,3.2 Newton法,三、Newton法有关说明 Newton法收敛速度非常快具有二次收敛的优点，但它存在下面四个严重的缺点：（1）尽管每次迭代不会使目标函数 上升，但仍不能保证 下降当Hesse矩阵非正定时，Newton法的搜索将会失败（2）对初始点要求严格一般要求比较接近或有利于接近极值点，而这在实际计算中是比较难办的,3.2 Newton法,（3）在进行某次迭代时可能求不出搜索方向由于搜索方向为若目标函数在 点Hesse矩阵为奇异，则求不出，因而不有构成牛顿方向，从而使迭代无法进行（4）牛顿方向构造困难，计算相当复杂，除了求梯度以外还需计算Hesse矩阵及其逆矩阵，占用机器内存相当大,3.2 Newton法,3.3 修正Newton法,一、修正Newton法基本原理 为了克服Newton法的缺点，人们保留选Newton方向作为搜索方向，摒弃其步长恒取1，而用一维搜索确定最优步长，由此产生的算法称为修正Newton法（或阻力Newton法）,3.3 修正Newton法,二、修正Newton法迭代步骤已知目标函数 及其梯度 Hesse矩阵 终止限（1）选取初始点 令（2）求梯度向量计算，若，停 止迭代输出 否则，转（3）（3）构造Newton方向计算，取（4）进行一维搜索求，使得 令，转（2）,修正Newton法的流程如图所示,三、修正Newton法有关说明 修正Newton法克服了Newton法的缺点特别是，当 迭代点接近于最优解时，此法具有收敛速度快的优点，对初始点的选择要求不严 但是，修正Newton法仍需要计算目标函数的Hesse矩 阵和逆矩阵，所以求解的计算量和存贮量均很大.另外，当目标函数的Hesse矩阵在某点处出现奇异时，迭代将 无法进行，因此修正Newton法仍有相当的局限性,3.3 修正Newton法,3.4 共轭方向法,构成各种不同最优化方法，往往取决于如何从基本迭代公式 中确定搜索方向在最速下降法中，由于取 从而导致搜索路线出现锯齿状，收敛速度降低；而在Newton法中，由于选取 收敛速度虽很快，但计算量很大，特别是还要求Hesse矩阵正定，从而导致该算法对初始点选择要求过严下面我们将给大家介绍一种新的最优化方法，它的计算量小，收敛速度没有Newton法快，但比最速下降法快得多的新算法，称为共轭方向法,一、共轭方向法基本原理 首先介绍共轭方向概念及其些性质 定义5.1 设 是对称矩阵,对于非零向量 若有 则称 与 相互 共轭或 正交的 对于非零向量组 若有 则称 是 共轭方向组或 正交方向组，也称 它们是一组 的共轭方向,3.4 共轭方向法,在上述定义中若(阶单位矩阵)，则式（5.10）和式（5.11）成为 和 由此可知，共轭概念是正交概念的推广，共轭方向是正交方向的推广定理5.1 设 是正定矩阵，是非零向量若 是 一组 共轭方向，则它们是线性无关的,3.4 共轭方向法,3.4 共轭方向法,证明 设有一组实数 使得 依次以 左乘上式得到 因为 是一组 的共轭方向，故有 又由于A是正定矩阵，所以对于 有 把以上两式用于式（5.12），便可推知 由此证明 是线性无关,3.4 共轭方向法,考虑以二次函数为目标函数的无约束极小化问题其中 是对称正定矩阵 有如下定理：定理5.2 设 是对称正定矩阵，是一 组A 的共轭方向.对于问题（5.13）,若从任意点 出发依次沿 进行一维搜索，则至多经过n 轮迭代，可得问题（5.13）的最优解,3.4 共轭方向法,证明 设从点X0 出发依次按方向 进行一维搜索产生的迭代点是其中最优步长 是通过下式来确定又由 和式（5.14）可推知即利用式（5.16）有,对上式右乘 可得因为 是 A共轭方向，故得 或另外，由式（5.15）可知,3.4 共轭方向法,因为所以由式（5.18）有由式（5.17）和上式，对于 我们得到特别地，当 时有 由于 是一组A的共轭方向,由定理5.1知它们是线性无关的,因而向量 可表示为这些向量的线性组合 其中 是实数,3.4 共轭方向法,所以由式（5.19）有 即有 于是得即Xn是f(X)的驻点又因为A是对称正定，故f(X)是凸函数，因而Xn是问题（5.13）的最优解这说明，至多经过n 次迭代必可求得(5.13