最优化方法及控制应用2

单击此处编辑母版标题样式,单击此处编辑母版文本样式,*,常用无约束最优化方法,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,），如图所示，假定我们 已经迭代了 次 获得了第 个迭代点 现在从 出发，可选择的下降方向很多，一个非常自然的想法是沿最速下降方向（即负梯度方向）进行搜索应该是有利的，至少在 邻近的范围内是这样。因此，取搜索方向为,.,最速下降法,为了使目标函数在搜索方向上获得最多的下降，沿 进行一维搜索，由此得到第 个迭代点 ，即 ，其中步长因子 按下式确定,也可记为,显然,令 就可以得到一个点列 ，,其中 是初始点,由计算者任意选定,.,当 满足一定的条件时,由式,(5.3),所产生的点列 必收敛于的极小点,以后为书写方便,记,.,因此,在不发生混淆时，再记 ,最速下降法,二、最速下降法迭代步骤,已知目标函数 及其梯度 ，终止,（,1,）选定初始点,计算 置 ,（,2,）作直线搜索： ；计算,（,3,）用终止准则检测是否满足：若满足，则打印最优,解 停机；否则，置 转,(2),最速下降法,最速下降法算法流程如图所示,开始,结束,选定,X,0,Y,X,，,f,H,准则满足,N,将最速下降法应用于正定二次函数,可以推出显式迭代公式,.,设第 次迭代点为 我们来求 的表达式 对式（,5.4,）关于 求梯度，有,因此，,现在从 出发沿 作直线搜索以确定 ，于是，,其中 是最优步长因子,最速下降法,又因式,(4.2),有,再利用,(5.5),(5.6),(5.7),可得：,或,由此解出：,代入（,5.7,）中得到,这就是最速下降法用于二次函数的显式迭代公式,最速下降法,最速下降法,例,5.1,试用最速下降法求函数 的极小点,.,迭代两次，计算各迭代点的函数值，梯度及其模，并验证相邻两个搜索方向是正交的设初始点为 ,解,:,与（,5.4,）比较，得,梯度表达式是,由 ，计算,因为目标函数是二次的，可以使用式,(5.8),所以有,最速下降法,因为,由此说明相邻两个搜索方向,是正交的,计算,最速下降法,三、最速下降法有关说明,最速下降法的优点是算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点,.,但它有一个严重缺点就是收敛速度,沿负梯度方向函数值下降很快的廉洁，容易使人们产生一种错觉，认为这一定是最理想的搜索方向，沿该方向搜索时收敛速度应该很快，然而事实证明，梯度法的收敛速度并不快,最速下降法,特别是对于等值线（面）具有狭长深谷形状的函数，收敛速度更慢其原因是由于每次迭代后下一次搜索方向总是与前一次搜索方向相互垂直，如此继续下去就产生所谓的锯齿现象,即从直观上看，在远离极小点的地方每次迭代可能使目标函数有较大的下降，但是在接近极小点的地方，由于锯齿现象，从而导致每次迭代行进距离缩短，因而收敛速度不快,.,最速下降法,Newton,法,如果目标函数 在 上具有连续的二阶偏导数，其,Hesse,矩阵 正定并且可以表达成为显式（今后为了简便起见，记 ，那么可以使用下述的,Newton,法这种方法一旦好用，收敛速度是很快的它是一维搜索,Newton,切线法的推广,一、,Newton,法基本原理,为寻求收敛速度快的算法，我们考虑在应用基本迭代公,式 中，每轮迭代在迭代的起始点 处用,一个适当的二次函数来近似该点处的目标函数，由此,用点 指向近似二次函数极小点的方向来构造搜索方向,(,如图所示,),Newton,法,下面具体讨论,Newton,法,设最优化问题为 ，其中 二阶可导，,Hesse,矩阵 正定不妨设经过 次迭代已获点 ，现将 在 处展开成二阶泰勒公式，于是有,显然 是二次函数，特别由题设知 还是正定二次函数，所以 是凸函数且存在唯一全局极小点,Newton,法,为求此极小点，令,即可解得,亦即,对照基本迭代格式,易知，式（,5.9,）中的搜索方向,步长因子 ,Newton,法,换句话说从点 出发沿搜索方向,并取步长 即可得 的极小点,.,因此 是直指点 处近似二次函数 的极小点的方向此时称 为从点 出发的,Newton,方向,从初始点开始，每一轮从当前迭代点出发，沿,Newton,方向并取步长 的算法称为,Newton,法,Newton,法,二、,Newton,法迭代步骤,已知目标函数 及其梯度,Hesse,矩阵,终止限,(1),选定初始点 计算 置 ,(2),计算,(3),由方程 解出 ,(4),计算,(5),判别终止准则是否满足：若满足，则打印最优解,停机；否则置 转,(2).,Newton,法,开始,结束,选定,X,0,N,求解方程,H,准则满足,X , f,Newton,法的流程如图所示,Y,例,5.2,试用,Newton,法求 的极小点,初始点取为 ,解,:,梯度为,Hesse,矩阵为 其逆矩阵为,由迭代公式（,5.13,）得第,1,迭代点为,由于此时 ，停止迭代得,因此，它就是极小点,Newton,法,从上述例,5.2,我们看到，用,Newton,法求解，只经一轮迭代就得到最优解,这一结果并不是偶然的，因为从,Newton,方向的构造我们知道，对于正定二次函数，,Newon,方向就是指向其极小点的方向,因此，用,Newton,法解目标函数为正定二次函数的无约束最优化问题，只需一次迭代就可得最优解,Newton,法,对于目标函数是非二次函数的非约束最优化问题，一般地说，用,Newton,法通过有限轮迭代并不能保证可求得最优解但由于目标函数在最优解附近能近似于二次函数，因此当先取接近于最优解的初始点使用,Newton,法求解时，其收敛速度一般是快的,事实上，可以证明在初始点离最优解不远的条件下，,Newton,法是二次收敛的但是当初始点选得离最优解太远时，,Newton,法并不一定是收敛的方法，甚至连其下降性也很难保证,Newton,法,三、,Newton,法有关说明,Newton,法收敛速度非常快具有二次收敛的优点，但它存在下面四个严重的缺点：,（,1,）尽管每次迭代不会使目标函数 上升，但仍不能保证 下降当,Hesse,矩阵非正定时，,Newton,法的搜索将会失败,（,2,）对初始点要求严格一般要求比较接近或有利于接近极值点，而这在实际计算中是比较难办的,Newton,法,（,3,）在进行某次迭代时可能求不出搜索方向由于搜索方向为,若目标函数在 点,Hesse,矩阵为奇异，则求不出 ，因而不有构成牛顿方向，从而使迭代无法进行,（,4,）牛顿方向构造困难，计算相当复杂，除了求梯度以外还需计算,Hesse,矩阵及其逆矩阵，占用机器内存相当大,Newton,法,修正,Newton,法,一、修正,Newton,法基本原理,为了克服,Newton,法的缺点，人们保留选,Newton,方向作为搜索方向，摒弃其步长恒取,1,，而用一维搜索确定最优步长，由此产生的算法称为修正,Newton,法（或阻力,Newton,法）,修正,Newton,法,二、修正,Newton,法迭代步骤,已知目标函数 及其梯度,Hesse,矩阵 终止限,（,1,）选取初始点 令,（,2,）求梯度向量计算 ，若 ，停,止迭代输出 否则，转（,3,）,（,3,）构造,Newton,方向计算 ，,取,（,4,）进行一维搜索求 ，使得,令 ，转（,2,）,修正,Newton,法的流程如图所示,k=0,计算,求 使,计算,开始,结束,选定,Y,N,三、修正,Newton,法有关说明,修正,Newton,法克服了,Newton,法的缺点特别是，当,迭代点接近于最优解时，此法具有收敛速度快的优点，,对初始点的选择要求不严,但是，修正,Newton,法仍需要计算目标函数的,Hesse,矩,阵和逆矩阵，所以求解的计算量和存贮量均很大,.,另外，,当目标函数的,Hesse,矩阵在某点处出现奇异时，迭代将,无法进行，因此修正,Newton,法仍有相当的局限性,修正,Newton,法,共轭方向法,构成各种不同最优化方法，往往取决于如何从基本迭代公式 中确定搜索方向,在最速下降法中，由于取 从而导致搜索路线出现锯齿状，收敛速度降低；,而在,Newton,法中，由于选取 收敛速度虽很快，但计算量很大，特别是还要求,Hesse,矩阵正定，从而导致该算法对初始点选择要求过严,下面我们将给大家介绍一种新的最优化方法，它的计算量小，收敛速度没有,Newton,法快，但比最速下降法快得多的新算法，称为共轭方向法,一、共轭方向法基本原理,首先介绍共轭方向概念及其些性质,定义,5.1,设 是对称矩阵,对于非零向量,若有,则称 与 相互 共轭或 正交的,对于非零向量组 若有,则称 是 共轭方向组或 正交方向组，也称,它们是一组 的共轭方向,共轭方向法,在上述定义中若,(,阶单位矩阵,),，则式（,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,共轭方向法,证明 设从点,X,0,出发依次按方向 进行一维搜索产生的迭代点是,其中最优步长 是通过下式来确定,又由 和式（,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),的最优解,.,3.4,共轭方向法,通常，我们把从任意点 出发,依次沿某组共轭方向进行一维搜索的求解最优化问题的方法,叫做,共轭方向法,为了直观起见,首先考虑二维情况现在我们把下降法用于形式为,(5.13),的二元二次函数,任选初始点 从 出发沿某个下降方向 作一维搜索得到,(,如图所示,),3.4,共轭方向法,由式（,4.2,）知,而且向量 所在的直线必与某条等值线（椭圆）相切于 点下一次迭代，如果按最速下降法选择负梯度方向为搜索方向，那末将要发生锯齿现象,.,为了克服这种现象，我们设想，下一次迭代的搜索方向将直指极小点 如果能够选定这样的搜索方向，那么对于二元二次函数只须顺次进行两次直线搜索就可以求到极小点了,下面来讨论这样的方向 应该满足什么条件，怎样确定,3.4,共轭方向法,因为 直接指极小点 所以可写成,其中 是最优步长因子，,显然，当 时，,对（,5.13,）求导数，有,因为 是极小点，所以有,将式（,5.21,）代入此式中，由（,5.22,）可得,等式两边同时左乘 并注意到式,(5.20),和 于是,3.4,共轭方向法,这就是为使 直指极小点所必须满足的条件显然（,5.23,）中 和 是,A,的共轭向量由式（,5.20,），不难给出 的表达式,两边同时左乘 ，有,由此解出,代回到式 （,5.24,），得,3.4,共轭方向法,一般地，在 维空间中可以找出 个互相共轭的方向，对于 元正定二次函数，从任意初始点出发，顺次沿这 个共轭方向最多作 次直线搜索就可以求得目标函数的极小点这就是共轭方向法的算法形成的基本思想,3.4,共轭方向法,对于 元正定二次目标函数，从任意初始点出发，如果经过有限次迭代就能够求得极小点，那么这种算法称为具有二次终止性,例如,Newton,法对于二次函数只须经过一次迭代就可以求得极小点，因此是二次终止的；而最速下降法不具有二次终止性；共轭方向法（包括共轭梯度法，变尺度法等）是二次终止的,一般来说，具有二次终止性的算法，在用于一般函数时，收敛速度较快,3.4,共轭方向法,二、共轭方向法迭代步骤,已知具有正定矩阵,A,的二次目标函数,和终止限 ,（,1,）选定初始点,X,0,和具有下降的方向,P,0,置,k,=0,（,2,）作直线搜索,（,3,）判别 是否满足：若满足，则打印,停机；否则转（,4,）,（,4,）提供共轭方向 使得,（,5,） ，转（,2,）,.,3.4,共轭方向法,共轭方向法的流程如图所示,e,+,),(,1,k,X,f,k=0,提供共轭方向,1,+,k,P,使得,k,j,QP,P,k,j,1,0,0,1,L,=,=,+,T,),(,1,k,k,s,k,P,X,l,X,=,+,开始,停,1,+,k,X,Y,N,k=k+1,选定,e,0,0,P,X,三、共轭方向法有关说明,上述算法针对二次目标函数，但也可用于一般的非二次函数在求优过程中 因舍入误差不能满足,时，可取 为新的初始点，再重复前面的过程,3.4,共轭方向法,3.5,共轭梯度法,如果在共轭方向法中初始的共轭向量 恰好取为初始点,处的负梯度 ，而以下各共轭方向 由第 迭代点 处的负梯度 与已经得到的共轭向量 的线性组合来确定，那么就构成了一种具体的共轭方向法,.,因为每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称为共轭梯度法,一、共轭梯度法基本原理,设从任意点 出发，第一个搜索方向取为 处的负梯度方向,当搜索得到点 后，设以下按,来产生搜索方向,为了使选择 使所产生的 和,是,A,的共轭，以 右乘上式的两边，于是有,3.5,共轭梯度法,因为要使 和 是,A,的共轭,应有,故由上式得,综上所述，我们可以生成,n,个,方向,3.5,共轭梯度法,式（,5.25,）中含有问题（,5.13,）的目标函数系数阵，这对于目标函数是非二次函数的问题是不方便的通过简化，一般地我们可以利用目标函数的梯度信息，来产生,n,个共轭方向,由此得共轭梯度法算法,3.5,共轭梯度法,二、共轭梯度法迭代步骤,已知目标函数 ，终止限 ,（,1,）选取初始点 ，给定终止限 ,（,2,）求初始梯度计算 ，若 ，停止迭,代输出 ， 否则转（,3,）,（,3,）构造初始搜索方向,.,取,令,转（,4,）,（,4,）进行一维搜索求 使得,令 ，转（,5,）,3.5,共轭梯度法,（,5,）求梯度向量计算 ，若 ，停止,迭代输出 否则转（,6,）,.,（,6,）检验迭代次数若 ，令 ，转（,3,），,否则，转（,7,）,（,7,）构造共轭方向取,转（,4,）,3.5,共轭梯度法,共轭梯度法的流程如图所示,结束,求,t,k,使,计算,开始,X,0,选定,Y,N,构造初始搜索方向取,计算,X,k+1,Y,N,Y,N,例,5.3,用共轭梯度法求,其中 选初始点,解:,显然,3.5,共轭梯度法,所以新的搜索方向,由此，有,并且可推知,因而得下一迭代点,由于 停止迭代输出所求得,3.5,共轭梯度法,例,5.3,的迭代的路径如图所示,3.5,共轭梯度法,三、共轭梯度法有关说明,实际上,可以把共轭梯度法看作是最速下降法的一种改进,.,当令 时,就变为最速下降法,.,共轭梯度法由于不涉及矩阵,仅仅存储向量,因而存储量小,适合于维数较高的优化问题,另外,共轭梯度法不要求精确的直线搜索,.,但是,不精确的直线搜索可能导致迭代出来的向量不再共轭,从而降低方法的效能,.,克服的办法是,:,重设初始点,即把经过 次迭代得到的 作为初始点重新迭代,3.5,共轭梯度法,我们知道,Newton,法最突出的优点是收敛速度快,在这一点上其它算法无法比拟的,.,因此,建议凡是,Hesse,矩阵比较容易求出的问题尽可能使用,Newton,法求解,.,然而,Newton,法还有一个严重缺陷,就是每次迭代都要计算目标函数的,Hesse,矩阵和它的逆矩阵,当问题的维数,n,较大时,计算量迅速增加,从而就抵消了,Newton,法的优点,3.6,变尺度法,3.6,变尺度法,为此，人们开始寻找一种算法既可以保持,Newton,法收敛速度快的优点，又可以摆脱关于,Hesse,矩阵的计算，这就是本节要给大家介绍的变尺度算法,变尺度法是一种非常好的方法其中,DFP,算法和,BFGS,算法，可以说直到目前为止在不用,Hesse,矩阵的方法中是最好的算法,一、变尺度法基本原理,在,Newton,法中，由基本迭代格式,其中 令,于是有,其中 是初始点， 和 分别是目标函数 在,点 的梯度和,Hesse,矩阵,3.6,变尺度法,为了消除这个迭代公式中的,Hesse,逆矩阵 可用某种近似矩阵 来替换它，即构造一个矩阵序列 去逼近,Hesse,逆矩阵序列 此时式（,5.26,）变为,事实上,式中 无非是确定了第 次迭代的搜索方向,.,为了取得更大的灵活性,我们考虑更一般的迭代公式,其中步长因子 通过从 出发沿 作直线搜,索来确定,3.6,变尺度法,式（,5.27,）是代表很广的一类迭代公式,.,例如,当 （单位矩阵）时，它变为最速下降法的迭代,公式为使 确实与 近似并且有容易计算的特点，,必须对,附加某些条件：,第一，为保证迭代公式具有下降性质，要求 中的每,一个矩阵都是对称正定的理由是，为使搜索方向,是下降方向，只要,成立即可，即,成立,当 对称正定时,此式必然成立,从而保证式（,5.27,）,具有下降性质,3.6,变尺度法,第二，要求 之间的迭代具有简单形式显然，,是最简单的形式了其中 称为校正矩阵，式（,5.28,）称为校正公式,第三， 必须满足拟,Newton,条件,3.6,变尺度法,所谓拟,Newton,条件由下面的推导给出,设迭代过程已进行到 步， 和 均已求出，现在推导 所必须满足的条件,设目标函数 具有连续的二阶偏导数现在将 在 处展成二阶泰勒公式,:,令 ，于是有,即,3.6,变尺度法,当 正定时，,当用 近似 时，由此看出 也必须满足,换句话说，式（,5.29,）就是称为 近似,Newton,条 件为了今后书写方便，记,于是拟,Newton,条件可写为,3.6,变尺度法,二、变尺度法迭代步骤（拟,Newton,法）,已知目标函数 及其梯度 终止限,（,1,）选定初始点 ；计算 ；选定初 始矩阵,要求 对称正定（例如 ）,;,置 ,（,2,）计算搜索方向,（,3,）作直线搜索 ，计算,3.6,变尺度法,（,4,）判别终止准则是否满足：若满足，则 就是,所求的极小点，打印，停机；否则转（,5,）,（,5,）计算,（,6,）,转（,2,）,其中校正矩阵 可由确定的公式来计算不同,的公式对应不同的拟,Newton,算法,3.6,变尺度法,拟,Newton,算法的流程如图所示,k=k+1,H,准则满足,X,k+,1,开始,结束,选定,X,0,， 对称,正定阵,H,0,，置,k=0,Y,N,以下几段将要讨论各种公式的构成以及相应算法但是不论哪个公式都必须满足拟,Newton,条件,.,由式（,5.30,）和式（,5.28,）知， 必须满足,或,由此可见， 与 ， 和 有关,满足式（,5.31,）的 有无穷多个，因此上述拟,Newton,算法构成一族算法下面分别介绍两个常用的公式,3.6,变尺度法,（一）,DFP,算法,DFP,算法首先是由,Davidon,（,1959,年）提出来的，后来，,Fletcher,和,Powell,（,1963,年）对,Davidon,的方法作了改进，最后才形成,DFP,算法,D,，,F,，,P,是这三位学者名字的字头这种算法是无约束最优化方法最有效的方法之一,3.6,变尺度法,1,DFP,算法基本原理,考虑如下形式的校正公式,其中 ， 是待定 维向量， ， 是待定常数,这时校正矩阵是,现在来确定,:,根据拟,Newton,条件， 必须满足（,5.31,），于是有,或,3.6,变尺度法,满足以上方程的待定向量 和 有无穷多种取法，下面是其中的一种：,注意到 和 都是数量，不妨取,同时定出,将这两式代回（,5.32,）得,这就是,DFP,校正公式,3.6,变尺度法,2,DFP,算法迭代步骤,在拟,Newton,算法中,只要把第（,5,）步改为计算式（,5.33,）,而其它不变，该算法就为,DFP,算法了,但是由于计算中舍去误差的影响，特别是直线搜索不精确的影响，可能要破坏迭代矩阵 的正定性，从而导致算法失效为保证 的正定性，采取以下重置措施：,迭代 次后，重置初始点和迭代矩阵，即,以后重新迭代,3.6,变尺度法,已知目标函数 及其梯度 ,问题的维数,终止限,(1),选定初始点计算,(2),置,(3),作直线搜索,计算,(4),判别终止准则是否满足,:,若满足,则打印,停机；否则转,(5),(5),若 则置 转,(2);,否则,转,(6).,(6),计算,置 转,(3).,3.6,变尺度法,例,5.4,用,DFP,算法求 取,解,:,当我们取 时，,DFP,法与最速下降法具有相同的第,1,迭代点，在,5.1,中已作了计算,3.6,变尺度法,以下用,DFP,法作第二次迭代,按,DFP,算法中的第（,6,）步计算,因为,所以,3.6,变尺度法,搜索方向为,从,X,1,出发沿,P,1,进行直线搜索，即,由 知 ，,所以 ，,由于 所以 是极小点,3.6,变尺度法,（二）,BFGS,算法,我们再介绍另一个有效和著名的变尺度算法由于它是,Broyden,，,Fletcher,（,1970,年），,Goldfarb,（,1969,年）和,Shanno,（,1970,年）共同研究的结果，因而叫做,BFGS,算法,3.6,变尺度法,1,BFGS,算法基本原理,考虑如下形式的校正公式,式中,这时校正矩阵为,3.6,变尺度法,式（,5.34,）中有一个参数 ，它可以取任何实数，每取一个实数就对应一种拟,Newton,算法,容易验证，当取 时就是,DFP,校正公式,令,就转变为著名的,DFGS,校正公式,3.6,变尺度法,2,DFGS,算法迭代步骤,已知目标函数 及其梯度,问题的维数,终止限,（,1,）选取初始点,初始矩阵,给定终止限,（,2,）求初始梯度向量，计算,若 ，停,止迭代输出 ，否则，转（,3,）,（,3,）构造初始,BFGS,方向，取,令 转（,4,）,（,4,）进行一维搜索，求 ，使得 ，,令 ，转（,5,）,3.6,变尺度法,（,5,）求梯度向量，计算 ，若 ，停,止迭代输出 ；否则，转（,6,）,（,6,）检验迭代次数，若,令 转（,3,）；否,则，转（,7,）,（,7,）构造,BFGS,方向，用,BFGS,公式,计算 ，取 ，令 ，转（,4,）,3.6,变尺度法,DFGS,算法的流程如图所示,结束,求,t,k,使,X,0,开始,计算,给定,Y,N,构造初始,BFGS,方向,取,计算,Xk+1,用,BFGS,公式计算,H,k+1,，,取,令,Y,N,Y,N,三、变尺度法有关说明,变尺度法中的二个重要算法,DFP,算法和,BFGS,算法，它们的迭代过程相同，区别仅在于校正矩阵选取不同,.,对于,DFP,法，由于一维搜索的不精确和计算误差的积累可能导致某一轮的奇异，而,BFGS,法对一维搜索的精度要求不高,.,并且由它产生的不易变为奇异矩阵,.,FGS,法比,DFP,法更具有好的数值稳定性，它比,DFP,法更具有实用性,3.6,变尺度法,3.7,坐标轮换法,坐标轮换法属于直接法它既可用于无约束最优化问题的求解，又可经过适当的处理用于约束最优化问题的求解,一、坐标轮换法基本原理,坐标轮换法的基本思想是把含有,n,个变量的优化问题轮换地转化为单变量（其它变量视为常量）的优化问题,所谓单变量优化问题就是沿某个坐标轴方向进行一维搜索的问题,坐标轮换法的寻优思路是：先选定一个初始点,X,0,作为第一轮搜索的始点 ，依次沿,n,个坐标轴方向进行一维搜索，每次只在一个坐标轴方向上改变相应变量的值，其它,(n-1),个变量均保持不变,在沿第一个坐标轴方向进行一维搜索得到目标函数值的最小点（或近似最小点） 后，再以此点作为始点转到沿第二个坐标轴方向进行一维搜索得到,直到沿第,n,个坐标轴方向搜索结束得到 为一个循环如果 不满足收敛准则,则以 作为初始点转入下一轮循环,直到经过 次循环,获得满足收敛准则的点,即作为最优点,3.7,坐标轮换法,对于二维最优化问题，其搜索过程如图所示,3.7,坐标轮换法,在坐标轮换法中，沿各个坐标轴方向进行一维搜索时，常选用最优步长因子或加速步长法加速步长法则是从初始点出发，沿搜索（坐标轴）方向先取一个较小的步长 ，作前进（或后退）试探如试探成功（目标函数值有所减小），则按步长序列 加大步长（注意每次加大步长都是由初始点算起），直至试探失败（目标函数值比前一次的有所增加）时，则取其前一次的步长作为沿这个坐标轴方向搜索的最优步长，并计算出该方向上的终止点，而后以这个终止点为始点再进行下一坐标轴方向的搜索，并重复上述步骤如此迭代下去，直到找到最优点 ,本节只用一维搜索法来确定最优步长,3.7,坐标轮换法,二、坐标轮换法迭代步骤,取初始点 置坐标轴搜索方向：,首先沿 方向进行一维搜索，求出该方向上目标函数的极值点 ；再以 为初始点沿 方向进行一维搜索，得到极值点 仿此依次沿 进行一维搜索，最终得到极值点 这就完成了第一轮循环的搜索,3.7,坐标轮换法,如果 能够满足收敛准则，即可停止搜索，以 作为 输出,否则，继续以 为初始点，进行第二轮循环，依次沿,进行一维搜索，得到第二循环的极值点,如此进行下去，直至最终找到满足收敛准则（终止准则）的点 ，即求得了最优解 再求出目标函数值,具体迭代过程如下：,3.7,坐标轮换法,已知目标函数 终止限,（,1,）任选取始点 作为第一轮循环的初始点,（,2,）置搜索方向依次为,（,3,）按下式求最优步长并进行迭代计算,3.7,坐标轮换法,上,式中， 为循环次数， 为该循环中,一维搜索的序号， 为利用一维搜索,求出的最优步长,（,4,）如果 ，即转（,5,）,;,如果 ，则转（,3,）,.,（,5,）收敛性准则 ： ，若满足判别式，,即停止迭代，输出最优解 及,若不满足，则令 转（,3,）,3.7,坐标轮换法,坐标轮换法的计算流程如图所示,k,=,k,+1,k=1,X=X,0,i=n?,开始,给定,Y,N,沿 求 使,i=1,i=i+1,N,结束,Y,X,*,例,5.5,用坐标轮换法求,初始点,解,:,从初始点出发，依次沿方向 搜索，以第一步为例,从,X,0,出发,沿,e,1,方向搜索,求得 点,3.7,坐标轮换法,得 即 于是得,再从 出发，沿 方向搜索，求得 点,求,可得 ，即取 于是有,3.7,坐标轮换法,终止判别,因终止条件不满足,需继续迭代,取 进行第二轮循环迭代,各轮迭代计算数据见下表,最优解为,3.7,坐标轮换法,循环,迭代,序号,是否满足收敛准则,1,0.00,，,3.00,3.13,3.13,，,1.56,1.44,3.13,，,1.56,1.63,3.45,否,2,3.13,，,1.56,0.50,2.63,，,1.56,0.25,2.63,，,1.31,0.16,0.56,否,3,2.63,，,1.31,0.19,2.44,，,1.31,0.09,2.44,，,1.22,0.04,0.21,否,4,2.44,，,1.22,0.09,2.35,，,1.22,0.05,2.35,，,1.17,0.015,0.10,否,5,2.35,，,1.17,0.06,2.29,，,1.17,0.03,2.29,，,1.14,0.007,0.06,否,6,2.29,，,1.14,0.04,2.25,，,1.14,0.02,2.25,，,1.12,0.004,0.045,否,7,2.25,，,1.12,0.03,2.22,，,1.12,0.01,2.22,，,1.11,0.002,0.03,是,3.7,坐标轮换法,三、坐标轮换法有关说明,坐标轮换法的优点是算法简单，计算量小，其缺点是计算效率低，对高维问题尤为突出因此，坐标轮换法通常用于维数较低的优化问题（一般 ）,3.8,单纯形法,单纯形法是利用对简单几何图形各顶点的目标函数值作相互比较，在连续改变几何图形的过程中，逐步以目标函数值较小的顶点取代目标函数值最大的顶点，从而进行求优的一种方法,属于直接法之一,一、单纯形法基本原理,现以求二元函数的极小点为例,说明单纯形法形成原理,.,设二元函数 在 平面上取不在同一条,直线上的三个点 并以它们为顶点构成一单纯,形,三角形算出各顶点的函数值,比较其大小，现假定比较后有,这说明点 最差，点 最好，点 次差,为了寻找极小点，一般来说应向最差点的反对称方向进行搜索,3.8,单纯形法,以 记为 的中点（如图所示），在 的延长线上取点 ，使,称为 关于 的反射点,算出 的函数值 ，可能出现以下几种情形：,3.8,单纯形法,(1),这说明搜索方向正确，可进一步扩大效果，继续沿,向前搜索，也就是向前扩张这时取,其中 为扩张因子，一般取 ,如果 ，说明扩张有利，就可以点 代替,点 构成新的单纯形 ,如果 ，说明扩张不利，舍去点 ，仍以点,代替 构成新的单纯形,3.8,单纯形法,(2),这说明搜索方向正确，但无须扩张，以,代替,构成新的单纯形,(3),这表示,点走得太远，应缩回一些若以,表示压缩因子，则有,常取为,0.5.,以,代替,构成新的单纯形,3.8,单纯形法,(4),这时应压缩更多一些，将新点压缩至,至,之间，令,注意，将式（,5.35,）中的,代之以,，即可得式（,5.36,）如果,，则以,代替,构成新的单,纯形,否则认为,方向上所有点的函数值,都大于,，不能沿此方向搜索,这时，可以以,为中心进行缩边,若使顶点,和,向,移近一半距离,得新单纯形,以此单纯形,为基础再进行寻优,3.8,单纯形法,以上说明，不管哪种情况，我们都可以得到一个新的单纯形，其中至少有一顶点的函数值比原单纯形为小如此继续，直至满足收敛终止准则,在,n,维情况下，一个单纯形含有 个顶点，计算工作量较大，但原理和上述二维情况相同,3.8,单纯形法,3.8,单纯形法,二、单纯形法迭代步骤,已知设 为 维变量,目标函数为,终止限为,(1),构成初始单纯形,在 维空间中选初始点 （离最优点越近越好）,从 出发，沿各坐标方向以步长 得 个顶点,这样选择顶点可保证向量组 线性无关否则，就会使搜索范围局限在较低维的空间内，有可能找不到极小点当然，在各坐标方向可以走不同的距离,步长 的范围可取,0.515.0,，开始时常取 ，接近最优点时要减小，例如取,0.51.0,(2),计算各顶点的函数值,比较各函数值的大小，确定最好点 、最差点 和次,差点 ，即,3.8,单纯形法,(3),计算 之外各点的“重点” ，,求出反射点,(4),当 时，需要扩张，令,如果，则以 代替 形成一新单纯,形；否则，以代 替 构成新单纯形然后转（,8,）,.,3.8,单纯形法,(5),当,时，以,代替,构成新单,纯形，然后转,(8),(6),当,时，则需要收缩即令,以,代替,得新单纯形，并转,(8),(7),当,时，令,如果,则将单纯形缩边，可将向量,的长度缩小一半，即,这样可得一新单纯形否则就以,代替,得新单纯,形然后转,(8).,3.8,单纯形法,(8),收敛性检验，每次迭代得到新单纯形后，即应进,行收敛性检验，如满足收敛指标，则迭代停止， 即,为所求的近似解否则，继续进行迭代计算 通常,所用的收敛准则是,或,式中 和 为预先给定的允许误差,3.8,单纯形