4无约束优化方法.ppt

1、6.4 无约束优化方法,最速下降法（梯度法） 牛顿型方法 共轭方向法 鲍威尔方法 单纯形法,目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。,（1）间接法要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。 （2）直接法不使用导数信息，如坐标轮换法、鲍威尔法、单纯形法等。,一、最速下降法（梯度法）,基本思想：函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题。利用负梯度作为搜索方向，故称最速下降法或梯度法。,搜索方向d 取该点的负梯度方向 (最速下降方向) ，使函数值在该点附近的范围内下降最快 。,为了

2、使目标函数值沿搜索方向 能够获得最大的下降值，其步长因子 应取一维搜索的最佳步长。即有,根据一元函数极值的必要条件和多元复合函数求导公式，得,在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。,图4-2 最速下降法的搜索路径,sk,图4-3最速下降法的程序框图,沿负梯度方向进行一维搜索，有,为一维搜索最佳步长，应满足极值必要条件,例1 求目标函数 的极小点。 解 取初始点 则初始点处函数值及梯度分别为,算出一维搜索最佳步长,第一

3、次迭代设计点位置和函数值,继续作下去，经10次迭代后，得到最优解,这个问题的目标函数的等值线为一簇椭圆,迭代点从 走的是一段锯齿形路线，见图4-4。,图4-4 等值线为椭圆的迭代过程,二、牛顿型法,设 为 的极小点,这就是多元函数求极值的牛顿法迭代公式。,对于二次函数 ，海赛矩阵H是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。,例2 求目标函数 的极小点。 解 取初始点,从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升 。,阻尼牛顿法,阻尼因

4、子 ，沿牛顿方向进行一维搜索的最佳步长，由下式求得：,图4-6 阻尼牛顿法程序框图,一般迭代式：,梯度法：,牛顿法：,梯度法与牛顿法比较：,阻尼牛顿法：,三、 共轭方向法,1.共轭方向： 设G为nn阶实对称正定矩阵，如果有两个n维向量d0和d1满足 ，则称向量d0与d1 关于矩阵G共轭。,当G为单位矩阵时，,假设目标函数f(x) 在极值点附近的二次近似函数为,任选取初始点x0沿某个下降方向d 0作一维搜索，得x1,因为 是沿d0方向搜索的最佳步长，即在点x1处函数f（x）沿方向d0的方向导数为零。考虑到点x1处方向导数与梯度之间的关系，故有,如果按最速下降法，选择负梯度方向 为搜索方向，则将发

5、生锯齿现象 。,取下一次的迭代搜索方向d1直指极小点x*。,如果能够选定这样的搜索方向，那么对于二元二次函数只需顺次进行d0、d1两次直线搜索就可以求到极小点x* ，即有,那么这样的d1方向应该满足什么条件呢 ?,对于前述的二次函数:,当 时，,x*是f(x)极小点，应满足极值必要条件，故有,将等式两边同时左乘 得：,有,就是使d1直指极小点x* ， d1所必须满足的条件 。,两个向量d0和d1称为G的共轭向量，或称d0和d1对G是共轭方向。,2.共轭方向的性质,性质1 若非零向量系d0,d1,d2,dm-1是对G共轭，则这m个向量是线性无关的。,性质2 在n维空间中互相共轭的非零向量的个数不

6、超过n。,性质3 从任意初始点出发，顺次沿n个G的共轭方向d0,d1, d2,dm-1进行一维搜索，最多经过n次迭代就可以找到的二次函数f(x)极小点。,在无约束方法中许多算法都是以共轭方向作为搜索方向，它们具有许多特点。根据构造共轭方向的原理不同，可以形成不同的共轭方向法。,3.共轭梯度法,共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。 考虑二次函数,从xk点出发，沿某一共轭方向dk作一维搜索，到达点xk+1 ，即,或,而在xk、xk+1点处的梯度gk、gk+1分别为,所以有,（414）,若dj和dk对G是共轭的，则有,利用（414）对两端前乘(

7、dj)T，即得,共轭梯度的几何说明,共轭梯度法计算过程,从xk出发，沿负梯度方向作一维搜索:,设与dk共轭的下一个方向dk+1由dk和点xk+1的负梯度的线形组合构成，即：,根据共轭条件：,则：,解得：,令,为函数的泰勒二次展开式,则,上两式相减，并代入,将式,与式,两边相乘，并应用共轭条件,得：,因此,利用梯度法的特点知：,例题 3 求下列问题的极值,解： 1）第一次沿负梯度方向搜寻 计算初始点处的梯度,为一维搜索最佳步长，应满足,得:,2）第二次迭代：,代入目标函数,得,因,收敛。,由,从而有：,四、 鲍威尔方法,鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。 1

8、964年，鲍维尔提出这种算法，其基本思想是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后的实践中进行了改进。,对函数：,基本思想：在不用导数的前提下，在迭代中逐次构造G的共轭方向。,1.共轭方向的生成,设xk, xk+1为从不同点出发，沿同一方向dj进行一维搜索而到的两个极小点xk、xk+1。,梯度和等值面相垂直的性质, dj和 xk, xk+1两点处的梯度gk,gk+1之间存在关系:,另一方面，对于上述二次函数，其xk, xk+1两点处的梯度可表示为:,因而有,取,这说明只要沿dj方向分别对函作两次一维搜索，得到两个极小点xk和xk

9、+1 ，那么这两点的连线所给出的方向dk就是与dj一起对G共轭的方向。,2.基本算法,二维情况描述鲍威尔的基本算法:,1）任选一初始点x0，再选两个线性无关的向量，如坐标轴单位向量e1=1,0T和e2 =0,1T作为初始搜索方向。,2）从x0出发，顺次沿e1， e2作一维搜索，得 点，将x0和x02两点连线得一新方向d1,沿d2作一维搜索得点x2 。,即是二维问题的极小点x* 。,方法的基本迭代格式包括共轭方向产生和方向替换两主要步骤。,用 d1代替e1形成两个线性无关向量d1 ,e2 ，作为下一轮迭代的搜索方向。再 从出发，沿d1作一维搜索得点 ，作为下一轮迭代的初始点。,3）从出发 ，顺次

10、沿e2,d1 作一维搜索，得到点 ，两点连线得一新方向:,把二维情况的基本算法扩展到n维，则鲍威尔基本算法的要点是： 在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和n个线性独立的搜索方向。从始点出发顺次沿n个方向作一维搜索得一终点，由始点和终点决定了一个 新的搜索方向。,用这个方向替换原来n个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。,上述基本算法仅具有理论意义 。,因为在迭代中的n个搜索方向有时会变成线性相

11、关而不能形成共轭方向。这时组不成n维空间，可能求不到极小点，所以上述基本算法有待改进。,3.改进的算法,在鲍威尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原向量组中的第一个向量，而不管它的“好坏”，这是产生向量组线性相关的原因所在。,在改进的算法中首先判断原向量组是否需要替换。如果需要替换，还要进一步判断原向量组中哪个向量最坏，然后再用新产生的向量替换这个最坏的向量，以保证逐次生成共轭方向。,为此，要解决两个关键问题： （1）dk1是否较好？是否应该进入新的方向组？即方向组是否进行更新？,（2）如果应该更新方向组， dk1不一定替换方向 ，而是有选择地替换某一方向 。,令

12、在k次循环中,（,）,分别称为一轮迭代的始点、终点和反射点 。,则在循环中函数下降最多的第m次迭代是,相应的方向为 。,为了构成共轭性好的方向组，须遵循下列准则：,在k次循环中，若满足条件：,和,则选用新方向d k，并在第k+1迭代中用d k替换对应于 的方向 。否则，仍然用原方向组进行第k+1迭代。,因此,记：,这样重复迭代的结果，后面加进去的向量都彼此对G共轭，经n轮迭代即可得到一个由n个共轭方向所组成的方向组。对于二次函数，最多n次就可找到极小点，而对一般函数，往往要超过n次才能找到极小点（这里“n”表示设计空间的维数）。,例4 用改进的鲍威尔法求目标函数,解：（1）第1轮迭代计算,沿e

13、1方向进行一维搜索,得,以 为起点，沿第二坐标轴方向 e2 进行一维搜索,得,确定此轮中的最大下降量及其相应方向,反射点及其函数值,，,检验Powell条件,由于满足Powell条件，则淘汰函数值下降量最大的方向e1，下一轮的基本方向组为e2， 。,构成新的方向,此点为下轮迭代初始点。,按点距准则检验终止条件,需进行第二轮迭代计算。,（2）第2轮迭代计算,此轮基本方向组为e2， 起始点为 。,沿e2方向进行一维搜索得,以 为起点沿 方向一维搜索得,确定此轮中函数值最大下降量及其相应方向,反射点及其函数值,检验Powell条件，淘汰函数值下降量最大的方向e2，下一轮的基本方向组应为 ， 。,构成

14、新的方向,沿 方向进行一维搜索得,（3）第3轮迭代计算,故最优解,检验终止条件,此轮基本方向组为 ， ,起始点为 ，先后沿 ， 方向，进行一维搜索，得,实际上，前两轮迭代的 ， 为共轭方向，由于本例目标函数是二次函数，按共轭方向的二次收敛性，故前两轮的结果就是问题的最优解，但每一轮迭代都需要进行n+1次迭代。,前面介绍的许多优化方法，除鲍威尔（Powell）法外，都需要计算目标函数的导数，而在实际工程的最优化问题中，目标函数的导数往往很难求出或者根本无法求出。下面所介绍的方法只需要计算目标函数值，无需求其导数，因此计算比较简单，其几何概念也比较清晰，属于直接法的无约束最优化方法。这类方法适用于

15、不知道目标函数的数学表达式而仅知其具体算法的情况。这也是直接法的一个优点。,五、 单纯形法,（一）基本思想 单纯形替换法也是一种不使用导数的求解无约束极小化问题的直接搜索方法，与前面几种方法不同的是，单纯形替换法不是利用搜索方向从一个点迭代到另一个更优的点，而是从一个单纯形迭代到另一个更优的单纯形。,定义：单纯形 n维空间中的恰好有n+1个顶点（极点）的有界的凸多面体称之为一个单纯形。 根据定义，可知，一维空间中的单纯形是线段，二维空间中的单纯形是三角形，而三维空间中的单纯形则是四面体。 在单纯形替换算法中，从一个单纯形到另一个单纯形的迭代主要通过反射、扩张、收缩和缩边这4个操作来实现。下面以

16、二维问题为例来对4种操作进行说明（参见下图）。,（1）反射设除了最劣点X1以外的基余顶点的中心为X4，作X1关于点X4的对称点X5，称X5为X1的反射点。求反射点的过程称之为反射。,设当前的单纯形的顶点为X1，X2，X3，且有,（2）扩张在得到反射点X5之后，如果X5优于原单纯形的最劣点（即有 ），表明反射方向（X5X1）是有利方向，反射成功。若进一步有 ，可沿反射方向前进适当的距离到点X6。X6称之为扩张点，求扩张点的过程称之为扩张。扩张之后，若扩张点X6优于反射点X5，则扩张成功，以X6取代X1，得新单纯形X6,X2,X3；否则，扩张失败，舍弃扩张点，以反射X5点取代X1，得新单纯形X5,

17、X2,X3。,如果出现 。表示反射完全失败，应退回到介于X4与X1之间的某个点X0。,（3）收缩在得到反射点X5之后，如果有,表示反射部分成功，方向（X5X1）虽然是有利方向，但X5前进过远，应收缩到介于X4与X5之间的某个点X7。,上述两种从反射点向X1方向后退的过程都称之为收缩。如果收缩点优于原来的最劣点X1，称收缩成功，并以收缩点取代原最劣点，构成新单纯形X7,X2,X3或X0,X2,X3；否则，称之为收缩失败，舍弃收缩点。,（4）缩边若收缩失败，则应压缩当前单纯形的边长：令最优点X3不动，而其余顶点向X3方向压缩，使边长缩短（通常缩短一半），以产生新单纯形。如下图所示，点X1压缩到点X

18、9，点X2压缩到点X10，得新单纯形X9,X10,X3，这一过程称之为缩边。,（二）单纯形替换算法 设初始点为X0，初始边长h，ei为坐标轴方向的单位向量i=1,2,n，预定正数1,（2）比较各项点Xi的函数值，挑出其中的最优点，记为XL；最劣点，记XH；次差点，记为XG； （3）求反射中心,其中，a0，通常取a=1；,；,例5 试用单形替换法求 的极小 。,解 选x0=8 9T，x1=10 11T，x2=8 11T为顶点作初始单纯 形，如图所示。 计算各顶点函数值f0=f(x0)=45, f1=f(x1)=125, f2=f(x2)=61。 可见最好点xL=x0，最差点xH=x1，次差点xG=x2。 求x0、x2的重点x3 求反射点x4及其函数值f4,由于f4f0，故需扩张，取=2得扩张点x5,由于f5f4，故以x5代替x1，由x0 x2x5构成新单纯形，进行下一循环。经32次循环，可将目标函数值降到110-6，接近极小值f