第四章 无约束优化方法

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第四章 无约束优化方法,4-1,概述,4-2,最速下降法（梯度法）,4-3,牛顿类方法,4-4,坐标轮换法,4-5,鲍威尔方法,4-6,共轭梯度法,4-1,概述,第一章所列举的机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于约束优化问题。工程问题大都如此。,为什么要研究无约束优化问题,?,（,1,）有些实际问题，其数学模型本身就是一个无约束优化问题。,（,2,）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。,（,3,）约束优化问题的求解可以通过一系列无约束优化 方法来达到。所以无约束优化问题的解法是优化设计,方法的基本组成部分，也是优化方法的基础。,（,4,）对于多维无约束问题来说，古典极值理论中令一阶导数为零，但要求二阶可微，且要判断海赛矩阵为正定才能求得极小点，这种方法有理论意义，但无实用价值。和一维问题一样，若多元函数,F(X),不可微，亦无法求解。,重点介绍求解无约束优化问题常用的数值解法。,目前已研究出很多种无约束优化方法，它们的主要,不同点在于,构造搜索方向,上,的差别。,无约束优化问题：,求,n,维设计变量,使目标函数,在本章中，我们将重点介绍求解无约束优化问题常用的,数值解法。,搜索类方法,的基本思想是从某一给定的初始点,x,0,开始，,沿给定的搜索方向,s,0,进行搜索，确定步长,a,0,使函数值沿,s,0,下,降最大（或达到给定的值）。此类方法的迭代格式如下：,可见，给定方向,s,k,后，多维无约束的优化设计问题，就变成 了一维优化设计问题，用前面所讲的一维优化设计方法进行步长寻优，可求出其最优点。,不同搜索类无约束优化方法的区别就是在于确定其搜索方向,s,k,的方法不同，,搜索方向的构成问题是该类无约束优化方法的关键。,( 1),间接法,要使用导数信息，如梯度法、牛顿类方法、共轭梯度法等。,间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其,Hessian,矩阵。,（,2,）直接法,不使用导数信息，如坐标轮换法、鲍威尔法等。,直接法寻找极小点，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的（,n 20,）问题，一般情况下比间接法效率低。,根据构成搜索方向使用信息性质不同，无约束优化,方法分两类：,4-2,最速下降法（梯度法）,基本思想：,目标函数,负梯度向量方向,代表最速下降方向，因此选择负梯度向量方向作为搜索方向，期望很快找到最优点。,利用负梯度作为搜索方向，故称,最速下降法或梯度法。,搜索方向,将,n,维问题转化为一系列沿负梯度方向用一维,搜索方法寻优的问题。,则,为了使目标函数值沿搜索方向 能够获得最大的下降值，其步长因子 应取一维搜索的最佳步长。即有,根据一元函数极值的必要条件和复合函数求导公式，得,在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成,“,之,”,字形的锯齿现象，而且越接近极小点锯齿越细。,从整体上看则走了许多弯路，因此函数的下降速度并不算快。,图,4-1,最速下降法的搜索路径,图,4-2,最速下降法的迭代过程,沿负梯度方向进行一维搜索，有,为一维搜索最佳步长，应满足极值必要条件,例,4-1,求目标函数 的极小点。,取初始点,解,:,初始点处函数值及梯度分别为,（最速下降法）,算出一维搜索最佳步长,第一次迭代设计点位置和函数值,继续作下去，经,10,次迭代后，得到最优解,这个问题的目标函数的等值线为一簇椭圆,迭代点从 走的是一段锯齿形路线，见图,4-3,。,1,1,图,4-3,等值线为一簇椭圆,将上例中目标函数 引入变换,其等值线由椭圆变成一簇同心圆。,变换,出发最速下降法寻优。此时：,沿负梯度方向进行一维搜索：,则函数 变为：,y,1,=,x,1,y,2,=5,x,2,为一维搜索最佳步长，可由极值条件算出,从而得出第一次搜索后设计点的位置及相应的目标函数值为：,可见经过坐标变换后，只需经过一次迭代，就可找到最优解,，,。,比较以上两种函数形式我们可以发现，,其等值线越接近于同心圆族，用梯度法收敛的速度也就越快,。如果其等值线不是圆族，则：,在远离极值点时，梯度法的收敛速度较快，在靠近极值点时，梯度法的收敛速度较慢。,图,4-3,最速下降法的程序框图,最速下降法的特点,:,1,迭代过程简单，对初始点的选择要求不高。,2,梯度方向目标函数值下降迅速只是个局部性质，从整体来看，不一定是收敛最快的方向。,3,以二维二次函数为例，相邻两次的搜索方向是正交的，所以搜索路径是曲折的锯齿形的；,4,对于高维的非线性函数，接近极值点处，容易陷入稳定的锯齿形搜索路径；,5,在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。,4,-3,牛顿类方法,基本思想：,最速下降法只使用了函数一阶导数的信息，在极,值点附近收敛较慢，如果利用二次导数的信息，在极值点附近,进行寻优，应该有更快的收敛速度。,一,.,牛顿法（二阶梯度法）：,将,f(x),在,x,(k),点作,Taylor,展开，取二次函数式,(x),作为近似,函数,以,(x),的极小值点作为,f(x),的近似极小值点。,说明：,这就是多元函数求极值的牛顿法迭代公式。,对于二次函数,，,海色矩阵,H,是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。,例,4-2,求目标函数 的极小点。,取初始点,解,:,（牛顿法）,经过一次迭代即求得极小点,函数极小值,从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升,。,对于二次函数，其泰勒展开式是精确的，海色矩阵是一个常矩阵，则无论从任何点出发，只需一步就可找到极小点。在数值计算中，如果某一迭代方法能使二次型函数在有限次迭代内达到极小点，称此迭代方法具有二次收敛性，可见，牛顿法是,二次收敛,的。,牛顿法特点,:,二、阻尼牛顿法,图,4-4,阻尼牛顿法程序框图,阻尼牛顿法方法特点,:,（,1,） 初始点应选在,x,*,附近，有一定难度；,（,2,）阻尼牛顿法每次迭代都在牛顿方向进行一维搜索，这就避免了迭代后函数值上升的现象，从而保证了牛顿法二次收敛的特性。,（,3,） 若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；,（,4,）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的,F,(,X,),也不适用。,虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和理论依据。,一般迭代式：,梯度法：,牛顿法：,阻尼牛顿法：,迭代式比较,(,一次迭代求,x,(1),),解,:,前面所讲的几种无约束的寻优方法，在产生寻优方向时，都用到函数的梯度或函数的海色矩阵，对于许多工程优化问题，其目标函数很难用解析方程表示出来，即使能用解析方式表示，其表达形式又非常复杂，再对这些函数进行求导甚至计算其海色矩阵，就更加困难。为此，在工程上建立了另外的一些方法，这些方法，不计算函数的梯度，通过函数值本身，即可求出寻优的方向，相对于用到函数梯度的寻优方法，这些方法叫做直接寻优方法。坐标轮换法、模式搜索法、,POWELL,法等都属于这类方法。前面介绍的用到函数梯度的寻优方法，称为间接方法。,4-4,坐标轮换法,一 基本思想：,是将一个,n,维优化问题转化为依次沿,n,个坐标方向反复进行一维搜索问题,。这种方法的实质是把,n,维问题的求优过程转化为对每个变量逐次进行一维求优的循环过程。每次一维搜索时，只允许,n,个变量的一次改动，其余,(n-1),个变量固定不变。故坐标轮换法也常称单变量法或变量交错法。,图,4-5,坐标轮换法,这种方法的收敛效果,受目标函数的性态影响很大。很大程度上取决于目标函数的性质。,如图,a),所示，二次就收敛到极值点；,如图,b),所示，多次迭代后逼近极值点；,如图,c),所示，目标函数等值线出现山脊（或称陡谷），若搜索到,A,点，再沿两个坐标轴，以,t,0,步长测试，目标函数值均上升，计算机判断,A,点为最优点。事实上发生错误。,图,4-6,坐标轮换法收敛速度,坐标轮换法,（,1,）计算简单，程序简单，不需要求函数导数的直接探索目标函数最优解的方法；但收敛慢，以振荡方式逼近最优点,。,（,2,）探索路线较长，问题的维数愈多求解的效率愈低。当维数,n,10,时,维数增加时,效率明显下降,则不应采用此法。仅适用于,n,较少（,n 10,）的目标函数求优。,（,3,）受目标函数的性态影响很大。改变初始点重新迭代，可避免出现病态。,从上述分析可以看出，采用坐标轮换法只能轮流沿着坐标方向搜索，尽管也能使函数值步步下降，但要经过多次曲折迂回的路径才能达到极值点；尤其在极值点附近步长很小，收敛很慢，所以坐标轮换法不是一种很好的搜索方法。但是，在坐标轮换法的基础上可以构造出更好的搜索策略，下面讨论的模式搜索法和鲍威尔（,Powell,）方法就属于这种情况。,坐标轮换法方法特点,二、模式搜索法,从上面我们可以看出，在沿着坐标进行了一轮搜索后，如果沿着,x,0,k,、,x,n,k,所定义的方向,S,k,= x,n,(k),- x,0,(k),进行一次寻优，将大大提高坐标轮换法寻优的速度，这种寻优方法的基本原理如图,4-7,所示。,图,4-7,模式搜索法,按照上述的寻优原理，模式搜索法的基本寻优步骤如下：,1),选定初始点,x,0,(1),，步长,h,，计算精度,和迭代轮数,k=1,；,2),从,x,0,(k),开始，进行坐标轮换搜索，求出,x,n,(k),；,3),判断 “是”则收敛，输出,x*=x,n,(k),。否则，计算方向 ，沿,s,k,方向进行一维寻优，得新的寻优起点 ，令,k=k+1,，转入步骤,2,。,从上面的分析可以看出，模式搜索法是对坐标轮换法的一种改进，它改变了完全沿着坐标方向寻优的模式，可以较好的提高计算速度，并利用已有的计算信息。, 4-5,鲍威尔方法,鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。,1964,年，鲍维尔提出这种算法，其,基本思想是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点,。,这种方法是在研究具有正定矩阵,H,的二次函数,坐标轮换法的收敛速度很慢，其原因在于搜索方向总是平行于坐标轴，不适应函数的变化情况。共轭方向是在坐标轮换法基础发展起来的一种方法，收敛速度较快。,极小化的基础上形成的。,一、共轭方向的生成,设,X,K,、,X,K+1,为从不同点出发，沿同一方向,S,j,进行一维搜索而得到的两个极小点，如图,4-8,所示。根据梯度与等值面相垂直的性质，,S,j,和,X,k,、,X,k+1,两点处的梯度,g,k,、,g,k+1,之间存在关系,、,、,图,4-8,两式相减，得,因而有,这说明只要沿,S,j,方向分别对函数作两次一维搜索，得到两个极小点,X,k,和,X,k+1,，那么这两点的连线所给出的方向,S,k,就是与,S,j,一起对,H,共轭的方向。,若取方向,另一方面，对于上述二次函数，其,X,k,X,k+1,两点处的梯度可表示为,:,图,4-9,二维情况下的共轭方向,二维情况下的共轭方向,对于二维问题，沿此共轭方向进行一维搜索就可以找到函数,的极小点。,二、基本算法,现针对二维的情况，描述鲍威尔的基本算法，如图,4-9,所示。,1),任选一初始点,X,0,，再选两个线性无关的向量，如坐标轴单位向量 和 作为初始搜索方向。,2),从,X,0,出发，顺次沿,e,1,、,e,2,作一维搜索得到点,X,1,(1),和,X,2,(1),，两点连线得新方向 ，并沿,S,1,进行一维寻优，得到下一轮的搜索起点,X,0,(2),。用,S,1,代替,e,1,形成两个线性无关向量,e,2,、,S,1,，作为下一轮迭代的搜索方向。,3),从,X,0,2,出发，顺次沿,e,2,、,S,1,作一维搜索，得到点,X,1,(2),、,X,2,(2),，两点连线得新方向 ，沿,S,2,进行一维寻优，对于二次函数，即可得到其最优解。,图,4-9,二维情况的鲍威尔算法,迭代步骤：,替换的原则是：,去掉原方向组的第一个方向而将新方向排在原方向的最后。此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。,因为这种方法在迭代中逐次生成共轭方向，而共轭方向是较好的搜索方向，,所以鲍威尔法又称作方向加速法。,基本算法的要点是：,在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和,n,个线性独立的搜索方向。从始点出发顺次沿坐标轴方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。用这个方向替换原来个方向中的一个，形成新的搜索方向组。,方法评价：,计算步骤复杂,;,是二次收敛方法，收敛快。对非正定函数，也很有效,;,是比较稳定的方法。,三,.,改进的算法,在鲍威尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原向量组中的第一个向量，而不管它的,“,好坏,”,，这是产生向量组线性相关的原因所在。,在改进的算法中首先判断原向量组是否需要替换。如果需要替换，还要进一步判断原向量组中哪个向量最坏，然后再用新产生的向量替换这个最坏的向量，以保证逐次生成共轭方向。,把二维情况的基本算法扩展到,n,维，因为在迭代中的,n,个搜索方向有时会变成线性相关而不能形成共轭方向。这时组不成,n,维空间，可能求不到极小点，所以上述基本算法有待改进。,改进算法的具体步骤如下：,1),任选初始点,X,0,（记,X,0,0,），选取初始方向组，它由,n,个线性无关的向量（如,n,个坐标轴单位向量,e,1,，,e,2,，,.e,n,，）组成，置,k=0,。,2),从,X,0,k,出发，顺次沿这,n,个线性无关的向量作一维搜索得到点,X,1,k,，,X,2,k,，,，,X,n,k,。接着以,X,n,k,为起点，沿方向 移动一个 的距离，得：,分别称为一轮迭代的,始点,、,终点,和,反射点,。,始点、终点和反射点所对应的函数值分别表示为：,同时，计算各中间点处的函数值，并记为,因此，有,计算各函数值之差 ， ，,， 。记作 其中最大值记作,3),根据是否满足判别条件,和,来确定是否要对原方向组进行替换。,这样重复迭代的结果，后面加进去的向量都彼此对,H,共轭，经,n,轮迭代即可得到一个由,n,个共轭方向所组成的方向组。对于二次函数，最多,n,次就可找到极小点，而对一般函数，往往要超过,n,次才能找到极小点（这里,“,n,”,表示设计空间的维数）。,4),判断是否满足收敛准则。继续进行下一轮迭代。,若,不满足判别条件,，则下轮迭代仍用原方向组，并以,X,n,k,、,X,n+1,K,中函数值小者作为下轮迭代的始点。,若,满足上述判别条件,，则下轮迭代应对原方向组进行替换，将,S,n+1,k,补充到原方向组的最后位置，而除掉,S,m,k,。即新方向组为,S,1,k,，,S,2,k,，,，,S,m-1,k,，,S,m+1,k,，,，,S,n,k,，,S,n+1,k,作为下轮迭代的搜索方向。,例,4-6,用鲍威尔法求函数,的极小值。,解 选初始点,，初始搜索方向,，,初始点处的函数值,。,，,。,1,）第一轮迭代：,沿,方向进行一维搜索，得,最佳步长,可通过,得,从而算出,点处的函数值及沿,走一步后函数值的增量,2),再沿,方向进行一维搜索，得,最佳步长,的计算可根据,得,从第一轮终点,处出发，沿,走一步后的函数值增量为：,沿,、,寻优后函数值增量中的最大者为：,终点,的反射点及其函数值为,3),为确定下一轮迭代的搜索方向和起始点，需检查判别条件,和,是否满足。,因为,，所以不满足判别条件，因而下轮迭代中应继续,使用原来的搜索方向,、,。,第二轮迭代：,(,省略）,4-6,共轭梯度法（旋转梯度法）,(,新增内容）,一,.,基本思想,：,二,.,共轭方向：,对梯度法作一个修正，将搜索方向由负梯度方向旋转一个角度，使相邻的两次搜索方向由正交变为共轭，成为二次收敛。,三,.,共轭系数：,(k),S,(k),图,4-11,共轭梯度法,(1),而在 、 点处的梯度为：,所以有（两式相减）,由迭代公式： （代入上式）,将得到：,将上式同乘 得：,关于 的确定（ 待定系数）,设函数为二次型：,得： （,2,）,将（,1,）式代入（,2,）式，并考虑 得：,范数：,从而得共轭方向的递推公式：,四,.,步,骤：,五,.,方法评,价：,迭代程序简单，容易实现，存储量较小。开始采用梯度方向，目标函数值下降快，后又为旋转梯度方向，具有二次收敛速度，,收敛快。,X,K,X,K+1,S,K,S,K+1,/,例,4-3,用共轭梯度法求二次函数,的极小点和极小值。,解：取初始点,1.,方向,则： 取：,2.,沿 方向进行一维搜索：,最佳步长,通过 求得：,则：,3.,建立 方向,从而求得第二个共轭方向：,4,、对 进行一维搜索,由 求得，得 ,1,则,5,、计算,得到满足极值的必要条件，再根据,X,2,点的海色矩阵,正定,X,2,：满足极值充分必要条件，故,X,2,为极小点，,即：,此时函数极小值,六、共轭梯度法的特点：,1,、第一个梯度方向取作负梯度方向，即最速下降法（收敛较快），然后各步的搜索方向是将负梯度偏转一个角度，即对负梯度进行修正。所以共轭梯度法实质上是对最速下降法的一种改进，故又称为旋转梯度法。,2,、程序简单，存储量少，收敛速度比最速下降法快（使用一阶导数）。,用牛顿法、,Poweel,法、共轭梯度法进行计算，并进行比较。,堂课练习,无约束优化设计方法小结,Poweel,法 共轭梯度法 牛顿法,迭代次数,搜索次数,搜索方向,收敛速度,存储量,适用维数,稳定性,2 2 1,6 2 1,共轭方向,零阶算法 一阶算法 二阶算法,较慢 二次收敛 收敛最快,小 中 最大,存储量随,n,2,n20 n200,300,好 中 差,用共轭梯度法求,(,堂课练习,),的极小点，取初始点为,X,0,=2,2,T,无约束优化方法,间接法总结,1,、梯度法,方向负梯度 用到一阶导数， 适合于精度不高或,用于复杂函数寻找一个好的初始点。,2,、牛顿法,用到一阶导数和海色矩阵，具有二次收敛性，,要求海色矩阵奇异，且维数不宜太高。,3,、共轭梯度法,用到一阶导数，具有二次收敛性。,1,、坐标轮换法,计算效率较低,适合维数较低,目标函数无导数或导数较难求得情况,3,、,Powell,法,具有二次收敛性，收敛速度较快，可靠性高，被认为是直接法中最有效的方法之一,无约束优化方法,直接法总结,常用无约束优化方法的特点及选用,一、无约束优化方法的选用原则,1,可靠性,满足合理的求解精度的条件下，在一定时间内，求解具体优化问题的成功率。,2,有效性,对于同一问题，在同样条件（初始点相同、精度相等）下，目标函数的求值、求导次数应当最少。,3,编程简单、占用存储单元量少。,基于上述,3,个方面，一般来说：,1,、对于低维优化问题（即小型优化问题），采用较简单的直接法为宜。,2,对于维数较高的优化问题，采用间接法（解析法）更为有利。,二、 常用无约束优化方法的比较,无约束优化方法,基本原理,特 点,应用场合,直接法,坐标轮换法,每次只变动,1,个变量，而其余,n-1,个变量保持不变,化多维问题为一系列一维问题。算法简单，易于掌握，但收敛速度较慢,维数,n 10,；目标函数不可导或不易求导。目标函数的等值线类似于椭圆（椭球体），且长短轴平行于坐标轴。,Powell,法,先用坐标轮换法迭代，以其最后的极小点与始点构成的方向作为最后一个新方向，并去掉第一个方向,共轭方向,d1,、,d2,满足：,d1,T,Ad2=0,，收敛速度比坐标轮换法快，可靠性较好,不需要求偏导数，目标函数比二次函数复杂。适用于小型或一些中型问题,间接法,梯度法,取负梯度方向为搜索方向,迭代过程简单，对初始点的要求不高。但收敛速度较慢,等值线接近于圆；精度要求不高，作为其他优化方法的初始方法,牛顿法,梯度法的发展。取目标函数,Taylor,展开式的前,3,项（二次函数）的极小点作为目标函数的近似极小点,收敛速度比梯度法快得多。但对于初始点的要求高，计算,Hessian,矩阵及其逆矩阵的工作量大,目标函数存在,2,阶导数，维数不太高。很少单独使用,1,梯度法、牛顿法、区别在于：怎样构造使目标函数值下降的搜索方向，其他则基本相同。,2,Powell,法、最可靠的无约束优化方法。,Powell,法的计算速度比慢些，,但,Powell,法不必计算目标函数的导数，这对于工程上许多优化问题很重要。,