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

坐标轮换法的基本思想它是无约束多维函数的优化方法中最简单的一种，它将一个无约束n维优化问题转化为依次沿着相应的n个坐标轴方向的一维优化问题来求解。2.3、坐标轮换法1.基本思想(原理)：二维迭代过程：推广到n维迭代过程)1(n个变量固定不动只变化第一个变量着第一个变量即由初始点沿1xTe0,0,1'1进行一维搜索，得到好点(1)1x(2)保持除外的)1(n个变量不变，沿第二变量2x进行一维搜索。得到好点Te0,1,0'2(1)先将1x的方向2x12()x此时的搜索方向为2x（3）如此沿''2'1neee方向(即坐标方向),且将前一次一维搜索的极小点作为本次一维搜索的起始点，依次进行一维搜索后，完成一轮迭代。()knx为起始（4）若未收敛则以前一次的末点点，进行下一轮的循环，如此一轮一轮迭代下去，直到满足收敛准则，逼近最优点为止。2.迭代计算步骤1)取初始点)0(x作为第一轮的起点)1(x)1()0(xx精度迭代终止置n个坐标轴方向矢量为单位坐标矢量)0()0(2)0(1)0(nxxxxTnTTeee100010000121沿第i个坐标方向，用一维搜索方法求最优迭代步长和各分量Tknkkknkikikikixxxxniexx)()(2)(1)()()()(1)(),2,1(式中)(kie为第k轮迭代中沿第i坐标方向)k(i为第k轮迭代中沿第坐标方向的最)(kie优步长（通过一维优化求出最优解）2)按照上式公式进行迭代计算，式中k为迭代轮数的序号，取k＝1，2，…，为该轮中一维搜索的序号，依次取i＝1，2，…，n。步长通过一维优化方法求得。)k(i3)按点距准则判断是否收敛)(0)(kknxx（采用迭代准则是一轮迭代的始点与终点之间的点距，而不能按某搜索方向的前后迭代点）都满足迭代终止并输出最优解)(**)(*xffxxkn否则令1kk返回步骤(2)坐标轮换法的流程图：入口给定)0(x1k1i)0()k(1ixx沿方向一维搜索求ie)k(ii)k(i)k(1-i)k(iexx1iini1kk)k(0)k(nxx)k(n)0(xx是否是否)x(ffxx**出口特点：简单易行，但由于它只能轮流沿几个坐标方向前进，因而效率低下，特别是维数较高n10或目标函数性质不好的情况下收敛速度慢。本方法的收敛效率在很大程度上取决于目标函数等值线的形状。当椭圆簇的长短轴与坐标轴斜交，迭代次数将大大增加，收敛速度很缓慢。目标函数等值线为椭圆簇其长短轴与坐标轴平行或同圆簇等值线收敛效率高速度快，若目标函数等值线出现脊线时沿着坐标轴方向搜索均不能使函数值有所下降，算法中将失效，这类函数对坐标轮换法来说是病态函数。搜索过程的几种储况a)搜索有效b)搜索低效c)搜索无效例：用坐标轮换法求目标函数60410)(21212221xxxxxxxf给定初始点Tx00)0(精度要求1.0解：作第一轮迭代计算沿方向1e进行一维搜索的无约束最优解：001000011)1(1)0(1)1(011)1(0)1(1xxxexxT求最步长1即极小化6010)(min121)1(1xf此问题可用某种一维优化方法求出1在这里用微分学(解析法)求导解出:令一阶导数为零可得5105)1(1x以)1(1x为起点沿2e方向一维搜索2222)1(1)1(251005exx求最步长：359)(min222)1(2xf得5.455.4)1(22x对于第一轮终止条件检验7.65.4522)1(0)1(2xx继续进行第二轮迭代计算以下各轮列于下表迭代轮数k)(0kx1)(1kx2)(2kx)(1)(2kkxx1T0,05T0,54.5T5.4,56.732T5.4,52.25T5.4,25.71.125T025.5,25.72.516迭代轮数k)(0kx1)(1kx2)(2kx)(1)(2kkxx3T025.5,25.70.563T625.5,813.70.282T907.5,813.70.6234T907.5,813.70.141T917.5,954.70.071T978.5,954.70.1585T978.5,954.70.035T978.5,989.70.018T996.5,989.70.04计算第五轮的有0394.0)978.5996.5()954.7989.7(22)5(0)5(2xx近似优化解为：000093.8)(996.5989.7**)5(2*xffxx2.4、共轭方向法1、共轭方向坐标轮换法的收敛速度很慢，原因在于其搜索方向总是平行于坐标轴，不适应函数变化情况如图所示若把一轮的起点11()x与末点)1(2x连起来形成一个新的搜索方向,2S与1S有何关系。如图所示，设给定两个平行方向1S,从两个任意初始点分别21xx，显然分别是两条平行线与函数等值线的相切点.2S沿这两个平行方向进行一维搜索求得极小点二维函数的共轭方向与1S2S连结二切点构成向量。2S即122xxS则可以证明若函数),(21xxf矩阵为正定矩阵则方向的海色1S与2S满足下式021HSST具有这样性质的方向，即是共轭方向1x2x*x1S1S2S如图所示，同心椭圆簇具有这样一个特点，就是二条任意平行线的切点的连线必通过椭圆族的中心。共轭方向的定义：设A为nn阶实对称正定矩阵,而1S2S为n维空间nR中的两个非零向量，如果满足0221ASST则称向量1S2S关于对称正定矩阵A是共轭的或1S2,S关于A共轭共轭方向的性质1)设A为nn阶实对称正定矩阵,nSSS21为对A共轭的n个非零向量，则这n个向量是线形无关的2)在n维空间中互相共轭的非零向量的个数不超过n。即:共轭向量的个数最多等于n(单位坐标向量系是一组线性无关的共轭向量的最简单例子，且它们也是正交向量系)。3)设A为nn阶实对称正定矩阵，)21(niSi是关于A的n个互相共轭的非零向量。对于正定二次函数)(xf的极小化寻优问题，从任何初始点出发依次沿iS方向经n次一维搜索即可收敛到极小点*x这种性质表明这种迭代方法具有二次收敛性。对于二元二次正定函数1S2S为共轭方向，若)1(x为起始点,分别沿方向作（经过1S2S两个共轭方向的一维搜索得到极小点）一维搜索即可到达二元二次正定函数的极小点。明确了共轭方向的概念，再来证明021HSST设二元函数在极值点*x附近的二次泰勒近似展开式为**2****)(21)()()(xxxfxxxxxfxfxfTT1S2,S由此可求得函数的一阶导数**2*)()()(xxxfxfxf***112()()()fxfxfxxx***222()()()fxfxfxxx故有**2****)(21)()()(xxxfxxxxxfxfxfTT由于两平行方向1S为等值线的切线,其切点分别为12,xx故方向1S应垂直于处的梯度方向.为目标函数)(xf在1S方向的极小点两点目标函数的梯度)(1xf都与)(2xf矢量1S正交即有0)()()(0)()()(*2*2*121*1*2*111xxxfxfSxfSxxxfxfSxfSTTTT即有所以在12,xx12,xx两式相减的0)()()(12*21121xxxfSxfxfSTT而122xxS故由上式可得0)(][)(][2*2112*21SxfSxxxfSTT推演到n维函数即在n维空间中可以同时构成n个关于H的共轭方向nSSS21对于对称正定二次n维函数从任意初始点0x出发顺序沿着这个线性无关的方向进行一维搜索就得到目标函数的极小点*x(可以证明)。因而说共轭方向法具有有限步收敛的特性通常称具有这种性质的方法为二次收敛法.但对于非二次n维目标函数经过有限步共轭方向一维搜索，不一定就能达到极小点。在这种情况下，可取其二次泰勒近似式加以讨论。当进行一轮次迭代还未取得极小点时可作为新的初始点再进行第二轮迭代。共轭方向的基本原理首先采用坐标轮换法进行第一轮迭代，然后以第一轮迭代的最末一个极小点和初始点相连构成一个新方向，并以此新方向为最末一个方向而去掉第一个方向得到第二轮迭代的方向.如此进行下去。直到求得问题的最小点。现以二维问题来说明算法步骤⑴令循环次数1k取初始点kx0初始搜索方向为坐标方向TkTkSS100121⑵从kx0出发依次沿kS1和kS2进行一维搜索得到第一次循环的极小点kkxx21⑶构造新方向kkkxxS023沿kS3进行一维方向搜索得到第k次循环的极小点kx3⑷取下次循环的初始点kkxx310去掉原来的第一方向kS1构造新的搜索方向kKkKSSSS312211令1kk转(2)继续迭代直到满足收敛条件，迭代计算结束kkxx02即某轮中初始点与末端点之间的距离达到预期的精度要求。同理,对于n维二次目标函数共轭方向的构成和迭代过程与上述2维二次目标函数共轭方向相类似。x1x3x2e1e2e3X0(1)S1e2e3S1X1(1)X2(1)X3(1)X0(2)X1(2)X2(2)X3(2)X0(3)S2e3S1S2S3X1(3)X2(3)X3(3)X0(4)第1轮第2轮第3轮•对于正定二次n维函数，从任意的初始点出发，沿着这n个共轭方向进行一维搜索，就可以得到目标函数的极小点。因此，对于二次函数来说，经过n步搜索就可以达到函数的极小点。•对于非二次n维函数，可以用二阶泰勒级数将函数在极小点附近展开，省略去高于二次的项后可以得到函数的二次近似，同样按照二次函数构成共轭方向。共轭方向法具有二次收敛性2.5、鲍威尔法------powell共轭方向法共轭方向法的基本要求是，各方向组的向量niSki2,1应该是线性无关的.然而很不理想的是上述方法高次迭代时所产生的新方向可能出现线性相关，从而导致计算不能收敛到真正的极小点而失败。为此1964年鲍威尔提出了对共轭方向法的改进方法。例如在进行某轮搜索时，由于在第一个分量这个特定的方向搜索没有进展而迭代点的收敛基本为零，则可能形成两个搜索方向基本上成为共线。以后的各次搜索在维数下降了的空间进行，真正的极小点可能被漏掉，这种现象称为“退化”新的一轮搜索中，迭代方向组成为线性相关，从而导致计算不能收敛到真正的极小点而失败。)(1knS以避免新产生的方向组中的各方向出现线性相关的情形，保证新方向组比前一方向组具有更好的共轭性质。为此powell提出了是否用方向来组成新的搜索方向组的判别条件powell提出了在每轮获得新方向)(1knS之后在组成新的方向组时不一屡去掉前一轮的第一个方向)(1kS而去有选择地去掉其中某一个方向nmSkm1)(•在powell法中判断是否用新的方向替换原方向组中