机械优化设计第四节无约束--坐标轮换法3-5.ppt

坐标轮换法的基本思想它是无约束多维函数的优化方法中最简单的一种，它将一个无约束n维优化问题转化为依次沿着相应的n个坐标轴方向的一维优化问题来求解。,2.3、坐标轮换法,1.基本思想(原理)：,二维迭代过程：,推广到n维迭代过程,个变量固定不动只变化第一个变量,着第一个变量,即由初始点沿,进行一维,搜索，得到好点,(2)保持除外的,个变量不变，,沿第二变量,进行一维搜索。得到好点,(1)先将,的方向,此时的搜索方向为,（3）如此沿,方向(即坐标方向),且将前一次一维搜索的极小点作为本次一维搜索的起始点，依次进行一维搜索后，完成一轮迭代。,为起始,（4）若未收敛则以前一次的末点点，进行下一轮的循环，如此一轮一轮迭代下去，直到满足收敛准则，逼近最优点为止。,2.迭代计算步骤,1)取初始点,作为第一轮的起点,精度,迭代终止,置,个坐标轴方向矢量为单位坐标矢量,沿第,个坐标方向，用一维搜索方法求最优迭代,步长和各分量,式中,为第,轮迭代中沿第,坐标方向,为第,轮迭代中沿第,坐标方向的最,优步长（通过一维优化求出最优解）,2)按照上式公式进行迭代计算，式中k为迭代轮数的序号，取k1，2，为该轮中一维搜索的序号，依次取i1，2，n。步长通过一维优化方法求得。,3)按点距准则判断是否收敛,（采用迭代准则是一轮迭代的始点与终点之间的点距，而不能按某搜索方向的前后迭代点）都满足迭代终止并输出最优解,否则令,返回步骤(2),坐标轮换法的流程图：,是,否,是,否,特点：简单易行，但由于它只能轮流沿几个坐标方向前进，因而效率低下，特别是维数较高n10或目标函数性质不好的情况下收敛速度慢。本方法的收敛效率在很大程度上取决于目标函数等值线的形状。当椭圆簇的长短轴与坐标轴斜交，迭代次数将大大增加，收敛速度很缓慢。目标函数,等值线为椭圆簇其长短轴与坐标轴平行或同圆簇等值线收敛效率高速度快，若目标函数等值线出现脊线时沿着坐标轴方向搜索均不能使函数值有所下降，算法中将失效，这类函数对坐标轮换法来说是病态函数。,搜索过程的几种储况a)搜索有效b)搜索低效c)搜索无效,例：用坐标轮换法求目标函数,给定初始点,精度要求,解：作第一轮迭代计算沿方向,进行一维搜索,的无约束最优解：,求最步长,即极小化,此问题可用某种一维优化方法求出,在这里用,微分学(解析法)求导解出:令一阶导数为零可得,以,为起点沿,方向一维搜索,求最步长：,得,对于第一轮终止条件检验,继续进行第二轮迭代计算以下各轮列于下表,迭代轮数k,1,5,4.5,6.73,2,2.25,1.125,2.516,迭代轮数k,3,0.563,0.282,0.623,4,0.141,0.071,0.158,5,0.035,0.018,0.04,计算第五轮的有,近似优化解为：,2.4、共轭方向法,1、共轭方向坐标轮换法的收敛速度很慢，原因在于其搜索方向总是平行于坐标轴，不适应函数变化情况如图所示若把一轮的起点,与末点,连起来形成,一个新的搜索方向,与,有何关系。,如图所示，设给定两个平行方向,从两个任意初始点分别,，显然分别是两条平行线与函数等值线的相切点.,沿这两个平行方向进行一维搜索求得极小点,二维函数的共轭方向与,连结二切点构成向量。,即,则可以证明若函数,矩阵为正定矩阵则方向,的海色,与,满足下式,具有这样性质的方向，即是共轭方向,如图所示，同心椭圆簇具有这样一个特点，就是二条任意平行线的切点的连线必通过椭圆族的中心。,共轭方向的定义：,设A为,阶实对称正定矩阵,而,为,维空间,中的两个非零向量，如果满足,则称向量,关于对称正定矩阵A是共轭的或,关于A共轭,共轭方向的性质,1)设A为,阶实对称正定矩阵,为对A共轭的n个非零向量，则这n个向量是线形无关的,2)在n维空间中互相共轭的非零向量的个数不超过n。即:共轭向量的个数最多等于n(单位坐标向量系是一组线性无关的共轭向量的最简单例子，且它们也是正交向量系)。,3)设A为,阶实对称正定矩阵，,是关于A的,个互相共轭的非零向量。对于正定,二次函数,的极小化寻优问题，从任何初始点,出发依次沿,方向经,次一维搜索即可收敛到极,小点,这种性质表明这种迭代方法具有二次,收敛性。,对于二元二次正定函数,为共轭方向，若,为起始点,分别沿方向作（经过,两个共轭,方向的一维搜索得到极小点）一维搜索,即可到达二元二次正定函数的极小点。,明确了共轭方向的概念，再来证明,设二元函数在极值点,附近的二次泰勒近似展开,式为,由此可求得函数的一阶导数,故有,由于两平行方向,为等值线的切线,其切点分别为,故方向,应垂直于,处的梯度方向.,为目标函数,在,方向的极小点,两点目标函数的梯度,都与,矢量,正交即有,即有,所以在,两式相减的,而,故由上式可得,推演到n维函数即在n维空间中可以同时构成n个关于H的共轭方向,对于对称正定二次n,维函数从任意初始点,出发顺序沿着这个线性无,关的方向进行一维搜索就得到目标函数的极小点,(可以证明)。因而说共轭方向法具有有限步收敛的特性通常称具有这种性质的方法为二次收敛法.但对于非二次n维目标函数经过有限步共轭方向一维搜索，不一定就能达到极小点。,在这种情况下，可取其二次泰勒近似式加以讨论。当进行一轮次迭代还未取得极小点时可作为新的初始点再进行第二轮迭代。,共轭方向的基本原理,首先采用坐标轮换法进行第一轮迭代，然后以第一轮迭代的最末一个极小点和初始点相连构成一个新方向，并以此新方向为最末一个方向而去掉第一个方向得到第二轮迭代的方向.如此进行下去。直到求得问题的最小点。现以二维问题来说明,算法步骤,令循环次数,取初始点,初始搜索方向为,坐标方向,从,出发依次沿,和,进行一维搜索得到第一次,循环的极小点,构造新方向,沿,进行一维方向搜索得到,第k次循环的极小点,取下次循环的初始点,去掉原来的第一方向,构造新的搜索方向,令,转(2),继续迭代直到满足收敛条件，迭代计算结束,即某轮中初始点与末端点之间的距离达到,预期的精度要求。,同理,对于n维二次目标函数共轭方向的构成和迭代过程与上述2维二次目标函数共轭方向相类似。,对于正定二次n维函数，从任意的初始点出发，沿着这n个共轭方向进行一维搜索，就可以得到目标函数的极小点。因此，对于二次函数来说，经过n步搜索就可以达到函数的极小点。对于非二次n维函数，可以用二阶泰勒级数将函数在极小点附近展开，省略去高于二次的项后可以得到函数的二次近似，同样按照二次函数构成共轭方向。,共轭方向法具有二次收敛性,n维二次函数原始共轭方向的构成步骤第1环搜索,依次沿一组线性无关的初始基本方向组（坐标轴方向）进行一维优化搜索，以初始点和终点的连线作为第1环的新生方向，再沿方向搜索得到第1环的极小点。,第环搜索,以第环的极小点作为初始点，以第环的新生方向取代第1个方向，即，构成第环搜索基本方向组,进行一维最优化搜索。以初始点和终点的连线作为第环的新生方向，再沿方向搜索得到第环的极小点。,第n环搜索,当搜索环数时，完成一轮迭代。在一轮迭代过程中的新生方向构成了个共轭方向。对于正定二次函数，经过一轮迭代的极小点就是函数的极小点。而对于n维非二次函数来说，一般要经过若干轮迭代才能达到极小点。,2.5、鲍威尔法-powell共轭方向法,共轭方向法的基本要求是，各方向组的向量,应该是线性无关的.然而很不理想的是,上述方法高次迭代时所产生的新方向可能出现线性相关，从而导致计算不能收敛到真正的极小点而失败。为此1964年鲍威尔提出了对共轭方向法的改进方法。例如在进行某轮搜索时，由于在第一个分量这个特定的方向搜索没有进展而迭代点的收敛基本为零，则可能形成两个搜索方向基本上成为共线。以后的各次搜索在维数下降了的空间进行，真正的极小点可能被漏掉，这种现象称为“退化”新的一轮搜索中，迭代方向组成为线性相关，从而导致计算不能收敛到真正的极小点而失败。,以避免新产生的方向组中的各方向出现线性相关的情形，保证新方向组比前一方向组具有更好的共轭性质。为此powell提出了是否用,方向来组成新的搜索方向组的判别条件,powell提出了在每轮获得新方向,之后在组成新,的方向组时不一屡去掉前一轮的第一个方向,而去有选择,地去掉其中某一个方向,在powell法中判断是否用新的方向替换原方向组中某一方向的判别准则按下式是否同时满足来进行处理,判别条件：,式中,k轮中起始点,的函数值,k轮方向组一维搜索终点,的函数值,为,对,的映射点函数值,k轮函数函数值下降最大值,其对应的方向为,若同时满足判别准则（powell判别条件）则在,轮循环中选用新方向,将,补入,轮循,环的基本方向组的最后并去掉方向,即以,构成第,轮循环的基本方向组,并取第,轮循环的初始点为,(,为第,轮循,环中沿新方向,一维搜索求得的极小点);,轮循环仍用原来的n个搜索方向,此时初始点,则应选取,值较小者即当,两点中函数,时取,时取,若不满足判别准则（Powell判别条件）则在,powell法解决了两个关键问题在每一轮迭代完成并产生共轭方向后，先对共轭方向的好坏进行判别，检验它是否与其它方向线性相关。若共轭方向不好则不用它作为下轮的迭代方向，而后采用原来的一组迭代方向。若共轭方向好，则可用它替换前一轮迭代中使函数值下降最快的一个方向，而不一定替换第一个迭代方向。,Powell法解决了两个关键问题,在第环搜索时，首先，对于已经获得的个共轭方向（包括新生方向）好坏进行判断，检验它是否与其他方向线性相关或接近线性相关。如果共轭方向不好(不满足Powell判别式），则不用它作为下一环搜索的基本方向组，仍然选用上一环搜索的基本方向组，以保证能够选取个线性无关方向。如果共轭方向好(满足Powell判别式），则用它替换上一环搜索的基本方向组中函数值下降最多的一个方向，不一定替换上一环搜索基本方向组的第1个方向，以加快搜索的收敛速度。,powell算法的迭代步骤,给定初始点,和允许误差,或,取n个坐标轴的单位向量,为搜索方,向,置k=1(k为迭代轮组),从,出发,分别沿,作为一轮n次一维,搜索,依次得n个极小点,得到,计算各相邻极小点目标函数值的差值，并找出其中的最大值及其相应的方向,计算映射点,计算结果,判断是否满足powell条件