第四章 常用无约束最优化方法ppt课件.ppt
Company Logo,4.7,4.6,4.5,4.4,4.3,修正Newton法,共轭方向法,共轭梯度法,变尺度法,坐标轮换法,第四章 常用无约束最优化方法,4.2,4.1,4.8,最速下降法,Newton 法,单纯形法,Company Logo,成立点 就是问题（4.1）的全局最优点但是，大多数最优化方法只能求到局部最优点，即在 中找到一点 ，使得式（4.2)在 的某个领域中成立,第四章 常用无约束最优化法,本章开始讨论多维无约束最优化问题 （4.1）其中 这个问题的求解是指，在 中找一点 ，使得对于任意的 都有 （4.2）,Company Logo,这个矛盾对于实际问题来讲一般容易解决，因为根据问题的实际意义多半可以直接判定用优化方法求出的局部最优解是否为全局最优解但在理论上这是个比较复杂的问题，本书不涉及 无约束优化方法是优化技术中极为重要和基本的内容之一它不仅可以直接用来求解无约束优化问题，而且很多约束优化问题也常将其转化为无约束优化问题，然后用无约束优化方法来求解另外，有些无约束优化方法只需略加处理，即可用于求解约束优化问题,Company Logo,无约束优化理论发展较早，比较成熟，方法也很多，新的方法还在陆续出现把这些方法归纳起来可以分成两大类：一类是仅用计算函数值所得到的信息来确定搜索方向，通常称它为直接搜索法，简称为直接法，另一类需要计算函数的一阶或二阶导数值所得到的信息来确定搜索方向，这一类方法称为间接法（或解析法）直接法不涉及导数和Hesse矩阵，适应性强，但收敛速度一般较慢；间接法收敛速度一般较快，但需计算梯度，甚至需要计算Hesse矩阵一般的经验是，在可能求得目标函数导数的情况下还是尽可能使用间接方法；相反，在不可能求得目标函数的导数或根本不存在导数的情况下，当然就应该使用直接法,Company Logo,一、最速下降法基本原理 在基本迭代公式 中，每次迭代搜索 方向取为目标函数 的负梯度方向，即 ，而每次迭代的步长 取为最优步长，由此所确定的算法称为最速下降法,对于问题（4.1）为了求其最优解，按最优化算法的基本思想是从一个给定的初始点 出发，通过基本迭代公式 ，按照特定的算法产生一串点列 ，如果点列收敛，则该点列的极限点为问题（4.1）的最优解,4.1 最速下降法,Company Logo,为了求解问题（4.1），如图4.1所示，假定我们已经迭代了 次，获得了第 个迭代点 现在从 出发，可选择的下降方向很多，一个非常自然的想法是沿最速下降方向（即负梯度方向）进行搜索应该是有利的，至少在 邻近的范围内是这样因此，取搜索方向为 ,图4.1,Company Logo,为了使目标函数在搜索方向上获得最多的下降，沿 进行一维搜索，由此得到第 个迭代点 ，即 ， 其中步长因子 按下式确定 ，也可记为 （4.3） 显然，令 就可以得到一个点列 ，其中 是初始点，由计算者任意选定当 满足一定的条件时，由式（4.3）所产生的点列 必收敛于 的极小点 ,Company Logo,以后为书写方便，记 因此， 在不发生混淆时，再记 ,Company Logo,已知目标函数 及其梯度 ，终止限 、 和 （1）选定初始点 ，计算 ， ； 置 （2）作直线搜索： ；计算 ， （3）用终止准则检测是否满足：若满足，则打印最优解 ， ，结束；否则，置 ，转（2）最速下降法算法流程如图4.2所示,二、最速下降法迭代步骤,，,Company Logo,最速下降法算法流程如图所示,图4.2,Company Logo,设第 次迭代点为 ，我们来求 的表达式对式(4.4)关于求 梯度，有 ，(4.5)因此， (4.6)现在从 出发沿 作直线搜索以确定 ，于是 ， (4.7)其中 是最优步长因子,将最速下降法应用于正定二次函数 （4.4）可以推出显式迭代公式,Company Logo,又因式（4.2），有 ，再利用式（4.5），式（4.6）和式（4.7）可得或 由此解出 ，代入式（4.7）中得到 .（4.8）这就是最速下降法用于二次函数的显式迭代公式,Company Logo,例4.1 试用最速下降法求函数 的极小点迭代两次，计算各迭代点的函数值，梯度及其模，并验证相邻两个搜索方向是正交的设初始点为 ,Company Logo,解 与式（4.4）比较，得 ，梯度表达式是 ，由 ，计算出 ， ， 因为目标函数是二次的，可以使用式（4.8），所以有 ，,Company Logo,计算 因为 由此说明相邻两个搜索方向 与、 , 与 是正交的,Company Logo,三、最速下降法有关说明,最速下降法的优点是算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点，但它有一个严重缺点就是收敛速度慢 图4.3沿负梯度方向函数值下降很快的说法，容易使人们产生一种错觉，认为这一定是最理想的搜索方向，沿该方向搜索时收敛速度应该很快，然而事实证明，梯度法的收敛速度并不快特别是对于等值线（面）具有狭长深谷形状的函数，收敛速度更慢,Company Logo,其原因是由于每次迭代后下一次搜索方向总是与前一次搜索方向相互垂直，如此继续下去就产生所谓的锯齿现象（如图4.3所示）即从直观上看，在远离极小点的地方每次迭代可能使目标函数有较大的下降，但是在接近极小点的地方，由于锯齿现象，从而导致每次迭代行进距离缩短，因而收敛速度不快,图4.3,Company Logo,4.2 Newton法,如果目标函数 在 上具有连续的二阶偏导数，其Hesse矩阵 正定并且可以表达成为显式（今后为了简便起见，记 ，那么可以使用下述的Newton法这种方法一旦好用，收敛速度是很快的它是一维搜索Newton切线法的推广,图4.4,Company Logo,下面具体讨论Newton法 设最优化问题为 ，其中 二阶可导，Hesse矩阵 正定不妨设经过 次迭代已获点 ，现将 在 处展成二阶泰勒公式，于是有,一、Newton法基本原理 为寻求收敛速度快的算法，我们考虑在应用基本迭代公式 中，每轮迭代在迭代的起始点 处用一个适当的二次函数来近似该点处的目标函数，由此用点 指向近似二次函数极小点的方向来构造搜索方向 （如图4.4所示）,Company Logo,显然 是二次函数，特别由假设知 还是正定二次函数，所以 是凸函数且存在唯一全局极小点为求此极小点，令即可解得 ，亦即 .,，,(4.9),Company Logo,对照基本迭代公式易知，式（4.9）中的搜索方向 ，步长因子 换句话说从点 出发沿搜索方向并取步长 即可得 的极小点 因此，是直指点 处近似二次函数 的极小点的方向,Company Logo,此时称为从点 出发的Newton方向从初始点开始，每一轮从当前迭代点出发，沿Newton方向并取步长 的算法称为Newton法,Company Logo,二、Newton法迭代步骤,已知目标函数 及其梯度 ，Hesse矩阵 ，终止限 （1）选定初始点 ；计算 ；置 （2）计算 （3）由方程 解出 （4）计算 （5）判别终止准则是否满足：若满足，则打印最优解 ， 结束；否则，置 ，转（2） Newton法的流程如图4.5所示,Company Logo,Newton法的流程如图所示,图4.5,Company Logo,解 梯度为 ，Hesse矩阵为 ，其逆矩阵为 由迭代公式（4.13）得第1 迭代点为由于此时 ，停止迭代得 ，因此，它就是极小点,例4.2 试用Newton法求 的极小点，初始点取为 ,Company Logo,从上述例4.2我们看到，用Newton法求解，只经一轮迭代就得到最优解这一结果并不是偶然的，因为从Newton方向的构造我们知道，对于正定二次函数，Newon方向就是指向其极小点的方向因此，用Newton法解目标函数为正定二次函数的无约束最优化问题，只需一次迭代就可得最优解,Company Logo,对于目标函数是非二次函数的非约束最优化问题，一般地说，用Newton法通过有限轮迭代并不能保证可求得最优解但由于目标函数在最优解附近能近似于二次函数，因此当先取接近于最优解的初始点使用Newton法求解时，其收敛速度一般是快的 事实上，可以证明在初始点离最优解不远的条件下，Newton法是二次收敛的但是当初始点选得离最优解太远时，Newton法并不一定是收敛的方法，甚至连其下降性也很难保证,Company Logo,三、Newton法有关说明 Newton法收敛速度非常快具有二次收敛的优点，但它存在下面四个严重的缺点：（1）尽管每次迭代不会使目标函数 上升，但仍不能保证 下降当Hesse矩阵非正定时，Newton法的搜索将会失败（2）对初始点要求严格一般要求比较接近或有利于接近极值点，而这在实际计算中是比较难办的,Company Logo,（3）在进行某次迭代时可能求不出搜索方向由于搜索方向为若目标函数在 点Hesse矩阵为奇异，则求不出 ，因而不有构成牛顿方向，从而使迭代无法进行（4）牛顿方向构造困难，计算相当复杂，除了求梯度以外还需计算Hesse矩阵及其逆矩阵，占用机器内存相当大,Company Logo,4.3 修正Newton法,一、修正Newton法基本原理 为了克服Newton法的缺点，人们保留选Newton方向作为搜索方向，摒弃其步长恒取1，而用一维搜索确定最优步长，由此产生的算法称为修正Newton法（或阻力Newton法）,Company Logo,二、修正Newton法迭代步骤已知目标函数 及其梯度 Hesse矩阵 终止限 （1）选取初始点 令（2）求梯度向量计算 ，若 ，停止迭代输出 否则，转（3）（3）构造Newton方向计算 ， 取（4）进行一维搜索求 ，使得 令 ，转（2） 修正Newton法的流程如图4.6所示,令,，转（2）修正Newton法的流程如图5.6所示,Company Logo,修正Newton法的流程如图所示,图4.6,Company Logo,三、修正Newton法有关说明 修正Newton法克服了Newton法的缺点特别是，当 迭代点接近于最优解时，此法具有收敛速度快的优点， 对初始点的选择要求不严 但是，修正Newton法仍需要计算目标函数的Hesse矩 阵和逆矩阵，所以求解的计算量和存贮量均很大.另外， 当目标函数的Hesse矩阵在某点处出现奇异时，迭代将 无法进行，因此修正Newton法仍有相当的局限性,Company Logo,3.4 共轭方向法,构成各种不同最优化方法，往往取决于如何从基本迭代公式 中 确定搜索方向在最速下降法中，由于取 从而导致搜索路线出现锯齿状，收敛速度降低；而在Newton法中，由于选取 收敛速度虽很快，但计算量很大，特别是还要求Hesse矩阵正定，从而导致该算法对初始点选择要求过严下面我们将给大家介绍一种新的最优化方法，它的计算量小，收敛速度没有Newton法快，但比最速下降法快得多的新算法，称为共轭方向法,Company Logo,一、共轭方向法基本原理 首先介绍共轭方向概念及其些性质 定义4.1 设 是对称矩阵,对于非零向量若有 (4.10),则称 与 相互 共轭或 正交的 对于非零向量组 ,若有 (4.11)则称 是 共轭方向组或 正交方向组，也称 它们是一组 的共轭方向,Company Logo,在上述定义中若 ( 阶单位矩阵)，则式（4.10）和式（4.11）成为 和 由此可知，共轭概念是正交概念的推广，共轭方向是正交方向的推广定理4.1 设 是正定矩阵， 是非零向量若 是 一组 共轭方向，则它们是线性无关的,Company Logo,证明 设有一组实数 ,使得 .依次以 左乘上式得到 ,(4.12)因为 是一组 的共轭方向，故有 又由于A是正定矩阵，所以对于 有 把以上两式用于式（4.12），便可推知由此证明 是线性无关,Company Logo,考虑以二次函数为目标函数的无约束极小化问题 ,(4.13)其中 是对称正定矩阵 有如下定理： 定理4.2 设 是对称正定矩阵， 是一组 的共轭方向.对于问题（4.13）,若从任意点 出发依次沿 进行一维搜索，则至多经过 轮迭代，可得问题（4.13）的最优解,Company Logo,证明 设从点 出发依次按方向 进行一维搜索产生的迭代点是 , 其中最优步长 是通过下式来确定又由 和式（4.14）可推知即利用式（4.16）有,(4.14),(4.15),(4.16),Company Logo,对上式右乘 可得因为 是 共轭方向，故得 或 .另外，由式（4.15）可知,(4.17),(4.18),Company Logo,因为所以由式（4.18）有由式（4.17）和上式，对于 我们得到特别地，当 时有 .由于 是一组 的共轭方向,由定理4.1知它们是线性无关的,因而向量 可表示为这些向量的线性组合 ,其中 是实数 .,(4.19),Company Logo,所以由式（4.19）有 ,即有 于是得 ,即 是 的驻点又因为 是对称正定，故 是凸函数，因而 是问题（4.13）的最优解这说明，至多经过 次迭代必可求得 (4.13)的最优解.,Company Logo,通常，我们把从任意点 出发,依次沿某组共轭方向进行一维搜索的求解最优化问题的方法,叫做共轭方向法 为了直观起见,首先考虑二维情况现在我们把下降法用于形式为(4.13)的二元二次函数 任选初始点 从 出发沿某个下降方向 作一维搜索得到 (如图所示),Company Logo,由式（4.2）知 而且向量 所在的直线必与某条等值线（椭圆）相切于 点下一次迭代，如果按最速下降法选择负梯度方向为搜索方向，那末将要发生锯齿现象. 为了克服这种现象，我们设想，下一次迭代的搜索方向将直指极小点 如果能够选定这样的搜索方向，那么对于二元二次函数只须顺次进行两次直线搜索就可以求到极小点了 下面来讨论这样的方向 应该满足什么条件，怎样确定,(4.20),Company Logo,因为 直接指极小点 ,所以可写成 其中 是最优步长因子，显然，当 时， . 对（4.13）求导数，有 因为 是极小点，所以有 .将式（4.21）代入此式中，由（4.22）可得 .等式两边同时左乘 并注意到式(4.20)和 ,于是有, (4.21), (4.22),. (4.23),Company Logo,这就是为使 直指极小点所必须满足的条件显然（4.23）中 和 是 的共轭向量由式（4.20），不难给出 的表达式设 两边同时左乘 ，有 .由此解出 , 代回到式 （4.24），得 .,，(4.24),Company Logo,一般地，在 维空间中可以找出 个互相共轭的方向，对于 元正定二次函数，从任意初始点出发，顺次沿这 个共轭方向最多作 次直线搜索就可以求得目标函数的极小点这就是共轭方向法的算法形成的基本思想,Company Logo,对于 元正定二次目标函数，从任意初始点出发，如果经过有限次迭代就能够求得极小点，那么这种算法称为具有二次终止性 例如Newton法对于二次函数只须经过一次迭代就可以求得极小点，因此是二次终止的；而最速下降法不具有二次终止性；共轭方向法（包括共轭梯度法，变尺度法等）是二次终止的 一般来说，具有二次终止性的算法，在用于一般函数时，收敛速度较快,Company Logo,二、共轭方向法迭代步骤 已知具有正定矩阵 的二次目标函数 和终止限 （1）选定初始点 和具有下降的方向 ,置 （2）作直线搜索 .（3）判别 是否满足：若满足，则打印 , 结束；否则转（4）（4）提供共轭方向 使得 .（5） ，转（2）. 共轭方向法的流程如图4.7所示,Company Logo,共轭方向法的流程如图所示,图4.7,Company Logo,三、共轭方向法有关说明 上述算法针对二次目标函数，但也可用于一般的非二次函数在求优过程中 因舍入误差不能满足 时，可取 为新的初始点，再重复前面的过程,Company Logo,5.5 共轭梯度法,如果在共轭方向法中初始的共轭向量 恰好取为初始点 处的负梯度 ，而以下各共轭方向 由第 迭代点 处的负梯度 与已经得到的共轭向量 的线性组合来确定，那么就构成了一种具体的共轭方向法. 因为一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称为共轭梯度法,Company Logo,一、共轭梯度法基本原理设从任意点 出发，第一个搜索方向取为 处的负梯度方向 .当搜索得到点 后，设以下按 来产生搜索方向为了使选择 使所产生的 和 是 的共轭，以 右乘上式的两边，于是有 .,Company Logo,因为要使 和 是 的共轭, 应有 故由上式得 综上所述，我们可以生成 个方向,(4.25),Company Logo,式（4.25）中含有问题（4.13）的目标函数系数阵，这对于目标函数是非二次函数的问题是不方便的通过简化，一般地我们可以利用目标函数的梯度信息，来产生 个共轭方向由此得共轭梯度法算法,Company Logo,二、共轭梯度法迭代步骤已知目标函数 ，终止限 （1）选取初始点 ，给定终止限 （2）求初始梯度计算 ，若 ，停止迭代输出 ， 否则转（3）（3）构造初始搜索方向.取 ,令 ,转（4）（4）进行一维搜索求 使得 , 令 ，转（5）,Company Logo,（5）求梯度向量计算 ，若 ，停止迭代输出 否则转（6）.（6）检验迭代次数若 ，令 ，转（3）， 否则，转（7）（7）构造共轭方向取 , 令 ，转（4）.共轭梯度法的流程如图4.8所示,Company Logo,共轭梯度法的流程如图所示,图4.8,Company Logo,例4.3 用共轭梯度法求 ， 其中 ，选初始点 . 解: 显然,Company Logo,所以新的搜索方向由此，有 ,并且可推知 , .因而得下一迭代点由于 停止迭代输出所求得 .,Company Logo,例4.3的迭代的路径如图所示,Company Logo,三、共轭梯度法有关说明 实际上,可以把共轭梯度法看作是最速下降法的一种改进.当令 时,就变为最速下降法. 共轭梯度法由于不涉及矩阵,仅仅存储向量,因而存储量小,适合于维数较高的优化问题 另外,共轭梯度法不要求精确的直线搜索.但是,不精确的直线搜索可能导致迭代出来的向量不再共轭,从而降低方法的效能.克服的办法是:重设初始点,即把经过 次迭代得到的 作为初始点重新迭代,Company Logo,3.6 变尺度法,我们知道Newton法最突出的优点是收敛速度快,在这一点上其它算法无法比拟的.因此,建议凡是Hesse矩阵比较容易求出的问题尽可能使用Newton法求解. 然而Newton法还有一个严重缺陷,就是每次迭代都要计算目标函数的Hesse矩阵和它的逆矩阵,当问题的维数n较大时,计算量迅速增加,从而就抵消了Newton法的优点,Company Logo,为此，人们开始寻找一种算法既可以保持Newton法收敛速度快的优点，又可以摆脱关于Hesse矩阵的计算，这就是本节要给大家介绍的变尺度算法 变尺度法是一种非常好的方法其中DFP算法和BFGS算法，可以说直到目前为止在不用Hesse矩阵的方法中是最好的算法,Company Logo,一、变尺度法基本原理 在Newton法中，由基本迭代格式 , 其中 , . 令 , 于是有 其中 是初始点， 和 分别是目标函数 在 点 的梯度和Hesse矩阵,(4.26),Company Logo,为了消除这个迭代公式中的Hesse逆矩阵 可用某种近似矩阵 来替换它，即构造一个矩阵序列 去逼近Hesse逆矩阵序列 此时式（4.26）变为 . 事实上,式中 无非是确定了第 次迭代的搜索方向.为了取得更大的灵活性,我们考虑更一般的迭代公式 其中步长因子 通过从 出发沿 作直线搜索来确定.,(4.27),Company Logo,式（4 .27）是代表很广的一类迭代公式. 例如,当 （单位矩阵）时，它变为最速下降法的迭代 公式为使 确实与 近似并且有容易计算的特点， 必须对 附加某些条件：第一，为保证迭代公式具有下降性质，要求 中的每 一个矩阵都是对称正定的理由是，为使搜索方向 是下降方向，只要 成立即可，即 成立当 对称正定时,此式必然成立,从而保证式（4.27)具有下降性质,Company Logo,第二，要求 之间的迭代具有简单形式显然，是最简单的形式了其中 称为校正矩阵，式（4.28）称为校正公式第三， 必须满足拟Newton条件,(4.28),Company Logo,所谓拟Newton 条件由下面的推导给出 设迭代过程已进行到 步， 和 均已求出，现在推导 所必须满足的条件 设目标函数 具有连续的二阶偏导数现在将 在 处展成二阶泰勒公式: .令 ，于是有即 .,Company Logo,当 正定时， .当用 近似 时，由此看出 也必须满足 换句话说，式（4.29）就是称为 近似Newton 条 件为了今后书写方便，记于是拟Newton条件可写为,，,. (4.29),.,(4.30),Company Logo,二、变尺度法迭代步骤（拟Newton法）已知目标函数 及其梯度 ,终止限 .（1）选定初始点 ；计算 ；选定初始矩阵 ,要求 对称正定（例如 ）;置 （2）计算搜索方向 （3）作直线搜索 ，计算,Company Logo,（4）判别终止准则是否满足：若满足，则 就是所求的极小点，打印，结束；否则转（5）（5）计算 （6） , 转（2） 其中校正矩阵 可由确定的公式来计算不同的公式对应不同的拟Newton算法 拟Newton算法的流程如图4.9所示,Company Logo,拟Newton算法的流程如图所示,图4.9,Company Logo,以下几段将要讨论各种公式的构成以及相应算法 但是不论哪个公式都必须满足拟Newton条件，由式（4.30）和式（4.28）知， 必须满足 或 由此可见， 与 ， 和 有关 满足式（4.31）的 有无穷多个，因此上述拟Newton算法构成一族算法下面分别介绍两个常用的公式,选定,(4.31),Company Logo,（一）DFP算法 DFP算法首先是由Davidon（1959年）提出来的，后来，Fletcher和Powell（1963年）对Davidon的方法作了改进，最后才形成DFP算法 D，F，P是这三位学者名字的字头这种算法是无约束最优化方法最有效的方法之一,Company Logo,1DFP算法基本原理 考虑如下形式的校正公式 其中 ， 是待定 维向量， ， 是待定常数 这时,校正矩阵是 现在来确定 . 根据拟Newton条件， 必须满足（4.31），于是有 或 ,.(4.32),.,.,Company Logo,满足以上方程的待定向量 和 有无穷多种取法，下面是其中的一种： 注意到 和 都是数量，不妨取同时定出 将这两式代回（4.32）得 这就是DFP校正公式,.(4.33),Company Logo,2DFP算法迭代步骤 在拟Newton算法中,只要把第（5）步改为计算式（4.33） 而其它不变，该算法就为DFP算法了 但是由于计算中舍去误差的影响，特别是直线搜索不精确的影响，可能要破坏迭代矩阵 的正定性，从而导致算法失效为保证 的正定性，采取以下重置措施： 迭代 次后，重置初始点和迭代矩阵，即 以后重新迭代,Company Logo,已知目标函数 及其梯度 ,问题的维数 ,终止限 (1)选定初始点计算(2)置 (3)作直线搜索 计算(4)判别终止准则是否满足:若满足,则打印 结束；否则转(5)(5)若 ，则置 ， 转(2);否则,转(6).(6)计算 置 ，转(3).,，,，,，,，,.,Company Logo,例4.4 用DFP算法求 ,取 .解: 当我们取 时，DFP法与最速下降法具有相同的第1迭代点，在4.1中已作了计算,Company Logo,以下用DFP法作第二次迭代按DFP算法中的第（6）步计算因为所以,.,Company Logo,搜索方向为从 出发沿 进行直线搜索，即由 知 ，所以 ，由于 ,所以 是极小点,Company Logo,（二）BFGS算法 我们再介绍另一个有效和著名的变尺度算法由于它是Broyden， Fletcher（1970年），Goldfarb（1969年）和Shanno（1970年）共同研究的结果，因而叫做BFGS算法,Company Logo,1BFGS算法基本原理考虑如下形式的校正公式 式中,这时校正矩阵为,(4.34),Company Logo,式（4.34）中有一个参数 ，它可以取任何实数，每取一个实数就对应一种拟Newton算法容易验证，当取 时就是DFP校正公式令就转变为著名的DFGS校正公式 .,Company Logo,2DFGS算法迭代步骤已知目标函数 及其梯度 ,问题的维数 ,终止限 （1）选取初始点 ,初始矩阵 ,给定终止限 （2）求初始梯度向量，计算 ,若 ，停止迭代输出 ，否则，转（3）（3）构造初始BFGS方向，取 令 , 转（4）（4）进行一维搜索，求 ，使得 ， 令 ，转（5）,Company Logo,（5）求梯度向量，计算 ，若 ，停止迭代输出 ；否则，转（6）（6）检验迭代次数，若 ,令 转（3）；否 则，转（7）（7）构造BFGS方向，用BFGS公式计算 ，取 ，令 ，转（4） BFGS算法的流程如图4.10所示,Company Logo,DFGS算法的流程如图所示,图4.10,Company Logo,三、变尺度法有关说明 变尺度法中的二个重要算法DFP算法和BFGS算法，它们的迭代过程相同，区别仅在于校正矩阵 选取不同. 对于DFP法，由于一维搜索的不精确和计算误差的积累可能导致某一轮的 奇异，而BFGS法对一维搜索的精度要求不高.并且由它产生的 不易变为奇异矩阵. FGS法比DFP法更具有好的数值稳定性，它比DFP法更具有实用性,Company Logo,3.7 坐标轮换法,坐标轮换法属于直接法它既可用于无约束最优化问题的求解，又可经过适当的处理用于约束最优化问题的求解一、坐标轮换法基本原理 坐标轮换法的基本思想是把含有n 个变量的优化问题轮换地转化为单变量（其它变量视为常量）的优化问题 所谓单变量优化问题就是沿某个坐标轴方向进行一维搜索的问题,Company Logo,坐标轮换法的寻优思路是：先选定一个初始点 作为第一轮搜索的始点 ，依次沿 个坐标轴方向进行一维搜索，每次只在一个坐标轴方向上改变相应变量的值，其它 个变量均保持不变 在沿第一个坐标轴方向进行一维搜索得到目标函数值的最小点（或近似最小点） 后，再以此点作为始点转到沿第二个坐标轴方向进行一维搜索得到 ,直到沿第 个坐标轴方向搜索结束得到 为一个循环如果 不满足收敛准则,则以 作为初始点转入下一轮循环,直到经过 次循环,获得满足收敛准则的点 ,即作为最优点 .,Company Logo,对于二维最优化问题，其搜索过程如图所示,Company Logo,在坐标轮换法中，沿各个坐标轴方向进行一维搜索时，常选用最优步长因子或加速步长法加速步长法则是从初始点出发，沿搜索（坐标轴）方向先取一个较小的步长 ，作前进（或后退）试探如试探成功（目标函数值有所减小），则按步长序列 加大步长（注意每次加大步长都是由初始点算起），直至试探失败（目标函数值比前一次的有所增加）时，则取其前一次的步长作为沿这个坐标轴方向搜索的最优步长，并计算出该方向上的终止点，而后以这个终止点为始点再进行下一坐标轴方向的搜索，并重复上述步骤如此迭代下去，直到找到最优点 本节只用一维搜索法来确定最优步长,Company Logo,二、坐标轮换法迭代步骤 取初始点 置坐标轴搜索方向：首先沿 方向进行一维搜索，求出该方向上目标函数的极值点 ；再以 为初始点沿 方向进行一维搜索，得到极值点 仿此依次沿 进行一维搜索，最终得到极值点 这就完成了第一轮循环的搜索,，,，,Company Logo,如果 能够满足收敛准则，即可停止搜索，以 作为 输出否则，继续以 为初始点，进行第二轮循环，依次沿 进行一维搜索，得到第二循环的极值点如此进行下去，直至最终找到满足收敛准则（终止准则）的点 ，即求得了最优解 ，再求出目标函数值 .具体迭代过程如下：,Company Logo,已知目标函数 , 终止限 . （1）任选取始点 , 作为第一轮循环的初始点, . （2）置搜索方向依次为 , （3）按下式求最优步长并进行迭代计算 , ,，,，,Company Logo,上式中， 为循环次数， ; 为该循环中 一维搜索的序号， ; 为利用一维搜索求出的最优步长 （4）如果 ，即转（5）;如果 ，则转（3）. （5）收敛性准则 ： ，若满足判别式,即停止迭代，输出最优解 及 若不满足，则令 转（3）,Company Logo,坐标轮换法的计算流程如图所示,图4.11,Company Logo,例4.5 用坐标轮换法求 ， 初始点 . 解: 从初始点出发，依次沿方向 搜索，以第一步为例，从 出发，沿 方向搜索，求得 点,Company Logo,得 ，即 ，于是得 再从 出发，沿 方向搜索，求得 点 求 可得 ，即取 ，于是有 .,Company Logo,终止判别 ,因终止条件不满足,需继续迭代,取 ,进行第二轮循环迭代,各轮迭代计算数据见下表,最优解为 .,Company Logo,三、坐标轮换法有关说明 坐标轮换法的优点是算法简单，计算量小，其缺点是计算效率低，对高维问题尤为突出因此，坐标轮换法通常用于维数较低的优化问题（一般 ）,Company Logo,4.8 单纯形法,单纯形法是利用对简单几何图形各顶点的目标函数值作相互比较，在连续改变几何图形的过程中，逐步以目标函数值较小的顶点取代目标函数值最大的顶点，从而进行求优的一种方法,属于直接法之一,Company Logo,一、单纯形法基本原理 现以求二元函数的极小点为例,说明单纯形法形成原理. 设二元函数 在 平面上取不在同一条 直线上的三个点 , ,和 ，并以它们为顶点构成一单纯 形三角形算出各顶点的函数值 ， ， ，比较其大小，现假定比较后有 这说明点 最差，点 最好，点 次差为了寻找极小点，一般来说应向最差点的反对称方向进行搜索,这说明,Company Logo,以 记为 的中点（如图所示），在 的延长线上取点 ，使 . 称为 关于 的反射点算出 的函数值 ，可能出现以下几种情形：,Company Logo,(1) 这说明搜索方向正确，可进一步扩大效果，继续沿 向前搜索，也就是向前扩张这时取 , 其中 为扩张因子，一般取 如果 ，说明扩张有利，就可以 点 代替 点构成新的单纯形 如果 ，说明扩张不利，舍去点 ，仍以点 代替 构成新的单纯形 .,Company Logo,(2) 这说明搜索方向正确，但无须扩张，以 代替 构成新的单纯形 .(3) 这表示 点走得太远，应缩回一些若以 表示压缩因子，则有 常取为0.5.以 代替 构成新的单纯形,(4.35),Company Logo,(4) 这时应压缩更多一些，将新点压缩至 至 之间，令 注意，将式（4.35）中的 代之以 ,即可得式(4.36)如果 ，则以 代替 构成新的单纯形 ,否则认为 方向上所有点的函数值 都大于 ，不能沿此方向搜索 这时，可以以 为中心进行缩边 若使顶点 和 向 移近一半距离, 得新单纯形 . 以此单纯形 为基础再进行寻优,(4.36),Company Logo,以上说明，不管哪种情况，我们都可以得到一个新的单纯形，其中至少有一顶点的函数值比原单纯形为小如此继续，直至满足收敛终止准则 在 维情况下，一个单纯形含有 个顶点，计算工作量较大，但原理和上述二维情况相同,Company Logo,二、单纯形法迭代步骤已知设 为 维变量,目标函数为 ,终止限为 (1)构成初始单纯形 在 维空间中选初始点 （离最优点越近越好）,从 出发，沿各坐标方向以步长 得 个顶点 , 这样选择顶点可保证向量组 线性无关否则，就会使搜索范围局限在较低维的空间内，有可能找不到极小点当然，在各坐标方向可以走不同的距离 步长 的范围可取0.515.0，开始时常取 ，接近最优点时要减小，例如取0.51.0,Company Logo,(2) 计算各顶点的函数值 比较各函数值的大小，确定最好点 、最差点 和次 差点 ，即,Company Logo,(3) 计算 之外各点的“重心” ， 求出反射点(4) 当 时，需要扩张，令 如果 ，则以 代替 形成一新单纯 形；否则，以代 替 构成新单纯形然后转（8）.,Company Logo,(5)当 时，以 代替 构成新单纯形，然后转(8) (6)当 时，则需要收缩即令 以 代替 得新单纯形，并转(8),(4.37),Company Logo,(7) 当 时，令 如果 , 则将单纯形缩边，可将向量 的长度缩小一半，即 这样可得一新单纯形否则就以 代替 得新单纯 形然后转(8).,Company Logo,(8) 收敛性检验 每次迭代得到新单纯形后，即应进 行收敛性检验，如满足收敛指标，则迭代停止， 即 为所求的近似解否则，继续进行迭代计算 通常 所用的收敛准则是 或 式中 和 为预先给定的允许误差,Company Logo,例4.6 试用单纯形法求 的极小值 . 解: 选 ,并取 和 这三点不在一条直线上，用它们作为初始单纯形的顶点 （如图所示）,Company Logo,然后计算各顶点的函数值： 可知 为最差点， 为最好点以 表示 和 的重心，则反射点,Company Logo,由于 ，故需扩张取 ，则因为 ，故以 代替 ,由 ， 和 构成新单纯形，然后进行下一个循环该问题的最优解为 , 经32次循环，可把目标函数减小到 .,Company Logo,三、单纯形法有关说明 本算法上机占用内存很少，对变量不多且精度要求不高的问题此法很方便，但当变量个数多于10以上，此法就显得不十分有效,
