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

1、坐标轮换法的基本思想坐标轮换法的基本思想它是无约束多维函数的优化方法中最简单的一种，它将一个无约束n 维优化问题转化为依次沿着相应的n个坐标轴方向的一维优化问题来求解。2.3、坐标轮换法1.基本思想(原理)：二维迭代过程：推广到n维迭代过程 ) 1( n个变量固定不动只变化第一个变量 着第一个变量 即由初始点沿1xTe0, 0, 11进行一维 搜索，得到好点 (1)1x(2)保持除 外的) 1( n个变量不变，沿第二变量 2x进行一维搜索。得到好点Te0, 1, 02(1)先将 1x的方向 2x12( )x此时的搜索方向为 2x（3）如此沿 21neee方向(即坐标方向),且将前一次一维搜索的

2、极小点作为本次一维搜索的起始点，依次进行一维搜索后，完成一轮迭代。()knx为起始 （4）若未收敛则以前一次的末点 点，进行下一轮的循环，如此一轮一轮迭代下去，直到满足收敛准则，逼近最优点为止。2.迭代计算步骤1)取初始点 )0(x作为第一轮的起点 )1(x)1()0( xx 精度 迭代终止置 n个坐标轴方向矢量为单位坐标矢量 )0()0(2)0(1)0(nxxxxTnTTeee100010000121沿第 i个坐标方向，用一维搜索方法求最优迭代步长和各分量 Tknkkknkikikikixxxxniexx)()(2)(1)()()()(1)(), 2, 1(式中 )(kie为第 k轮迭代中沿

3、第 i坐标方向)k(i为第 k轮迭代中沿第 坐标方向的最)(kie优步长（通过一维优化求出最优解）2)按照上式公式进行迭代计算，式中k为迭代轮数的序号，取k1，2，为该轮中一维搜索的序号，依次取i1，2，n。步长 通过一维优化方法求得。)k(i 3)按点距准则判断是否收敛)(0)(kknxx（采用迭代准则是一轮迭代的始点与终点之间的点距，而不能按某搜索方向的前后迭代点）都满足迭代终止 并输出最优解 )(*)(*xffxxkn否则令 1 kk返回步骤(2) 坐标轮换法的流程图：入口 给定 )0(x1k 1i )0()k(1ixx沿 方向一维搜索求 ie)k(ii)k(i)k(1 - i)k(ie

4、xx1iini 1kk)k(0)k(nxx)k(n)0(xx是 否 是 否 )x(ffxx*出口 特点： 简单易行，但由于它只能轮流沿几个坐标方向前进，因而效率低下，特别是维数较高n10或目标函数性质不好的情况下收敛速度慢。本方法的收敛效率在很大程度上取决于目标函数等值线的形状。当椭圆簇的长短轴与坐标轴斜交，迭代次数将大大增加，收敛速度很缓慢。目标函数 等值线为椭圆簇其长短轴与坐标轴平行或同圆簇等值线收敛效率高速度快，若目标函数等值线出现脊线时沿着坐标轴方向搜索均不能使函数值有所下降，算法中将失效，这类函数对坐标轮换法来说是病态函数。搜索过程的几种储况a)搜索有效 b) 搜索低效 c) 搜索无

5、效例：用坐标轮换法求目标函数 60410)(21212221xxxxxxxf给定初始点 Tx00)0(精度要求 1 . 0解：作第一轮迭代计算沿方向 1e进行一维搜索 的无约束最优解：001000011) 1 (1)0(1) 1 (011) 1 (0) 1 (1xxxexxT求最步长 1即极小化 6010)(min121) 1 (1xf此问题可用某种一维优化方法求出 1在这里用微分学(解析法)求导解出:令一阶导数为零可得 5105)1(1x以 )1(1x为起点沿 2e方向一维搜索 2222) 1 (1) 1 (251005exx求最步长： 359)(min222) 1 (2xf得 5 . 45

6、5 . 4) 1 (22x对于第一轮终止条件检验 7 . 65 . 4522)1(0)1(2xx继续进行第二轮迭代计算以下各轮列于下表 迭代轮数k )(0kx1)(1kx2)(2kx)(1)(2kkxx1 T0,05 T0,54.5 T5 . 4,56.73 2 T5 . 4,52.25 T5 . 4,25. 71.125 T025. 5,25. 72.516 迭代轮数k )(0kx1)(1kx2)(2kx)(1)(2kkxx3 T025. 5,25. 70.563 T625. 5,813. 70.282 T907. 5,813. 70.623 4 T907. 5,813. 70.141 T9

7、17. 5,954. 70.071 T978. 5,954. 70.158 5 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(2x连起来形成 一个新的搜索方向 , 2S与

8、 1S有何关系。如图所示，设给定两个平行方向 1S,从两个任意初始点分别21xx，显然分别是两条平行线与函数等值线的相切点. 2S沿这两个平行方向进行一维搜索求得极小点 二维函数的共轭方向 与1S2S连结二切点构成向量 。 2S即 122xxS则可以证明若函数 ),(21xxf矩阵为正定矩阵则方向 的海色1S与 2S满足下式 021HSST具有这样性质的方向，即是共轭方向1x2x*x1S1S2S如图所示，同心椭圆簇具有这样一个特点，就是二条任意平行线的切点的连线必通过椭圆族的中心。共轭方向的定义： 设A 为 nn阶实对称正定矩阵,而 1S2S为 n维空间 nR中的两个非零向量，如果满足 022

9、1ASST则称向量 1S2S关于对称正定矩阵A 是共轭的或1S2,S关于A 共轭共轭方向的性质1)设 A为 nn阶实对称正定矩阵, nSSS21为对A共轭的n个非零向量，则这n个向量是线形无关的2)在n维空间中互相共轭的非零向量的个数不超过n。即:共轭向量的个数最多等于n (单位坐标向量系是一组线性无关的共轭向量的最简单例子，且它们也是正交向量系)。3)设A为 nn阶实对称正定矩阵， )21(niSi是关于A的 n个互相共轭的非零向量。对于正定二次函数 )(xf的极小化寻优问题，从任何初始点出发依次沿 iS方向经 n次一维搜索即可收敛到极 小点 *x这种性质表明这种迭代方法具有二次收敛性。对于

10、二元二次正定函数 1S2S为共轭方向，若 )1(x为起始点,分别沿 方向作（经过 1S2S两个共轭方向 的一维搜索得到极小点）一维搜索即可到达二元二次正定函数的极小点。明确了共轭方向的概念，再来证明 021HSST设二元函数在极值点 *x附近的二次泰勒近似展开 式为 *2*)(21)()()(xxxfxxxxxfxfxfTT1S2,S由此可求得函数的一阶导数 *2*)()()(xxxfxfxf*112()()()f xf xf xxx*222()()()f xf xf xxx故有 *2*)(21)()()(xxxfxxxxxfxfxfTT由于两平行方向 1S为等值线的切线,其切点分别为 12,

11、xx故方向 1S应垂直于 处的梯度方向.为目标函数 )(xf在 1S方向的极小点两点目标函数的梯度 )(1xf都与 )(2xf矢量 1S正交即有 0)()()(0)()()(*2*2*121*1*2*111xxxfxfSxfSxxxfxfSxfSTTTT即有所以在12,xx12,xx两式相减的 0)()()(12*21121xxxfSxfxfSTT而 122xxS故由上式可得 0)()(2*2112*21SxfSxxxfSTT推演到n维函数即在n维空间中可以同时构成n个关于H的共轭方向 nSSS21对于对称正定二次n维函数从任意初始点 0 x出发顺序沿着这个线性无关的方向进行一维搜索就得到目标

12、函数的极小点 *x (可以证明)。因而说共轭方向法具有有限步收敛的特性通常称具有这种性质的方法为二次收敛法.但对于非二次n维目标函数经过有限步共轭方向一维搜索，不一定就能达到极小点。 在这种情况下，可取其二次泰勒近似式加以讨论。当进行一轮次迭代还未取得极小点时可作为新的初始点再进行第二轮迭代。共轭方向的基本原理 首先采用坐标轮换法进行第一轮迭代，然后以第一轮迭代的最末一个极小点和初始点相连构成一个新方向，并以此新方向为最末一个方向而去掉第一个方向得到第二轮迭代的方向.如此进行下去。直到求得问题的最小点。现以二维问题来说明 算法步骤令循环次数 1k取初始点 kx0初始搜索方向为坐标方向 TkTk

13、SS100121从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)

14、X2(2)X3(2)X0(3)S2e3S1S2S3X1(3)X2(3)X3(3)X0(4)第第1轮轮第第2轮轮第第3轮轮 对于正定二次n维函数，从任意的初始点出发，沿着这n个共轭方向进行一维搜索，就可以得到目标函数的极小点。因此，对于二次函数来说，经过n步搜索就可以达到函数的极小点。 对于非二次n维函数，可以用二阶泰勒级数将函数在极小点附近展开，省略去高于二次的项后可以得到函数的二次近似，同样按照二次函数构成共轭方向。 共轭方向法具有二次收敛性 n维二次函数原始共轭方向的构成步骤第1环搜索 依次沿一组线性无关的初始基本方向组 （坐标轴方向 ）进行一维优化搜索，以初始点 和终点 的连线作为第1环

15、的新生方向 ，再沿方向 搜索得到第1环的极小点 。 ), 2 , 1()1(niSi)1(0X)1(nX)1 (0)1 ()1 (XXSn)1(S)1(X), 2 , 1(niei第 环搜索 以第 环的极小点 作为初始点，以第 环的新生方向 取代第1个方向 ，即 ，构成第 环搜索基本方向组, 进行一维最优化搜索。以初始点 和终点 的连线作为第 环的新生方向 ，再沿方向 搜索得到第 环的极小点 。 K1K)1(KX)1(KS)1(1KS)1()(KKnSS), 2 , 1()(niSKi)(0KX)(KnX)(0)()(KKnKXXS)(KS)(KX1KKKK第n环搜索 当搜索环数 时，完成一轮

16、迭代。 在一轮迭代过程中的新生方向 构成了 个共轭方向。 对于正定二次函数 ，经过一轮迭代的极小点 就是函数的极小点 。而对于n维非二次函数来说，一般要经过若干轮迭代才能达到极小点。nK ), 2 , 1()(nKSKn)(Xf)(nX*X2.5、鲍威尔法-powell共轭方向法共轭方向法的基本要求是，各方向组的向量 niSki2, 1应该是线性无关的.然而很不理想的是 上述方法高次迭代时所产生的新方向可能出现线性相关，从而导致计算不能收敛到真正的极小点而失败。为此1964年鲍威尔提出了对共轭方向法的 改进方法。例如在进行某轮搜索时，由于在第一个分量这个特定的方向搜索没有进展而迭代点的收敛基本

17、为零，则可能形成两个搜索方向基本上成为共线。以后的各次搜索在维数下降了的空间进行，真正的极小点可能被漏掉，这种现象称为“退化”新的一轮搜索中，迭代方向组成为线性相关，从而导致计算不能收敛到真正的极小点而失败。)(1knS 以避免新产生的方向组中的各方向出现线性相关的情形，保证新方向组比前一方向组具有更好的共轭性质。为此powell提出了是否用方向来组成新的搜索方向组的判别条件powell提出了在每轮获得新方向 )(1knS之后在组成新 的方向组时不一屡去掉前一轮的第一个方向 )(1kS而去有选择 地去掉其中某一个方向 nmSkm1)(在powell法中判断是否用新的方向替换原方向组中某一方向的

18、判别准则按下式是否同时满足来进行处理判别条件： 231212)()(2123113FFFFFFFFFKMKM式中 )()(01kxfFk轮中起始点 kx0的函数值 )()(2knxfFk轮方向组一维搜索终点 knx的函数值 )2()()(0)()(13kknknxxfxfFknx1为 kx0对 )(knx的映射点函数值 )(0)()(12kknknxxx)()(max)()()()(1)()(1)(kikikmkmkmxfxfxfxfk轮函数函数值下降最大值 ni2, 1其对应的方向为 )( kmS若同时满足判别准则（powell判别条件）则在 1k轮循环中选用新方向 )(1knS将 )(1k

19、nS补入 1k轮循 环的基本方向组的最后并去掉方向 )(kmS即以 )(1)()(1)(1)(2)(1,knknkmkmkkSSSSSS)(1knS )(2kS)(kmS)(knS)(1kS)(0kx )(1kx )(2kx )(1kmx )(kmx )( knx )(1knx )(1knx ( )kx)()(2knxfF)2()()(0)()(13kknknxxfxfF1()0kFf x 构成第 1k轮循环的基本方向组 niSKi2, 11并取第 1k轮循环的初始点为 )()1(0kkxx( )(kx为第 k轮循 环中沿新方向 )(1knS一维搜索求得的极小点);1k轮循环仍用原来的n 个搜

20、索方向 knkkSSS21此时初始点 (1 )0kx则应选取 ( )( )1kknnxx值较小者即当 两点中函数23FF时取 (1)()0kknxx23FF时取 (1)( )01kknxx若不满足判别准则（Powell判别条件）则在 powell法解决了两个关键问题 在每一轮迭代完成并产生共轭方向后，先对共轭方向的好坏进行判别，检验它是否与其它方向线性相关。若共轭方向不好则不用它作为下轮的迭代方向，而后采用原来的一组迭代方向。 若共轭方向好，则可用它替换前一轮迭代中使函数值下降最快的一个方向，而不一定替换第一个迭代方向。Powell法解决了两个关键问题 在第 环搜索时，首先，对于已经获得的 个

21、共轭方向（包括新生方向） 好坏进行判断，检验它是否与其他方向线性相关或接近线性相关。 如果共轭方向不好(不满足Powell判别式），则不用它作为下一环搜索的基本方向组，仍然选用上一环搜索的基本方向组，以保证能够选取 个线性无关方向。 如果共轭方向好(满足Powell判别式），则用它替换上一环搜索的基本方向组中函数值下降最多的一个方向，不一定替换上一环搜索基本方向组的第1个方向，以加快搜索的收敛速度。K1nn()()()()121,KKKKnnSSSSpowell算法的迭代步骤 给定初始点 )0(x和允许误差 1或 2取 n个坐标轴的单位向量 niei2,1为搜索方 向 ikieS)(置k=1(k为迭代轮组)0()(0 xxk从 )(0kx出发,分别沿 niSki2, 1)(作为一轮n次一维搜索,依次得n个极小点 )(min)()()(1)()()(1kikkikikkiSxf