坐标轮换法汇总.docx
4.7坐标轮换法1 .基本思想：每次以一个变量坐标轴作为搜索方向，将n维的优化问题转化为一维搜索问题。例，第 k轮迭代的第i次搜索，是固定除xi外的n-1个变量，沿xi变量坐标轴作一维搜索，求得极值点xi（k）n次搜索后获得极值点序列x1（k）, x2（k）,，xn（k）,若未收敛，则开始第 k+1次迭代，直至收敛到最优点x* 。2 .搜索方向与步长:第k轮第i次搜索的方向：S的为第i个设计变量的坐标轴方 向；第k轮第i次搜索的步长：ai（k） Si（k）；第k轮第i次搜索的迭代公式：xi（k）=xik）+ai（k）Si（k）, i=1,2,n；第k轮第i次搜索的收敛条件：,产忖f=%3 .方法评价：方法简单，容易实现。当维数增加时，效率明显下降。收敛慢，以振荡方式逼近最优点。受目标函数的性态影响很大。如图a）所示，二次就收敛到极值点；如图b）所示，多次迭代后逼近极值点；如图c）所示，目标函数等值线出现山脊（或称陡谷） ，若搜索到 A点，再沿两个坐标轴, 以土 t0步长测试，目标函数值均上升，计算机判断A点为最优点。事实上发生错误。X/ 01 XE/U) &a )b )4.8 Poweel 法1 .基本思想：若沿连接相邻两轮搜索末端的向量S方向搜索，收敛速度加快。其中：S=X2-X2因为两条平行线 S1, S2与同心椭圆族相切，两个切点的连线S直指中心。称 S1, S2与S为共轲方向。目的：以共轲方向打破振荡，加速收敛。2 .共轲方向:设A为实对称正定矩阵，若有两个n维向量§和S2, 满足 S1TAs2=0,则称向量3和52是关于矩阵共轲， S,和S2的方向是共轲方向。若A为单位矩阵I,则 STIS2=。时，即S1T S2 = 0,则 6和52正交。设A为正定实对称矩阵，若有一组非零向量S1,S2,Sn,能满足 SiT ASj =0(i #j),则称这组向量是关于矩 阵A共轲。3 .共轲方向的性质: 这组关于A矩阵共腕的n个非零向量§,&,.,a是线性无关的。 若Si"),S2，,Sn是线性无关的向量组，则可以构造出n个向量Si ,S2 ,Sn：满足S(2)TAS=0, (i¥j)。 设S,S2,Sn是关于A矩阵共腕的n个非零向量，对于函数f(x)分别从两个初始点xo和xo出发，沿Si(i=1,2,n)方向进行一维 搜索，分别彳#到最优点xi和X2,向量S=x2-%也是与向量组 § (i =1,2,n)中每一个向量关于A矩阵共腕。 设5,$,&是关于A矩阵共腕的n个非零向量，则对于二 次函数 T 1f (x) =C+BTX十XTAX,从任意初始点x(0)出发，依次沿 Si(i=1,2,n)方向进行一维搜索，至 多n步可收敛至极值点，称 为 二次收敛性。4 .步骤：第一轮迭代：选初始点x(0),令xoC)=x(O),依次沿两个坐标轴方向S4)S2°祚两次一维搜索，分别求得f(x的极值点/)x2O构筑共轲方向：sQ= x8Lx/ )沿此方向作第三次搜索，求得f(x的极值点x3,)第二轮迭代: 令。=乂3(1),分别沿力向作两次 一维搜索，分别求得f(x的极值点为(2履2) 构筑共腕方向：S(2)= x2(2)- x0(2)沿此方向作第三次搜索，求得f (x的极值点&(2) 每轮迭代结束时，检验 是否满足收敛条件:fok1-2°若满足，贝 x* = x3(k+) o若不满足，则作下一轮 迭代。若是正定二次函数，n 轮迭代后收敛于最优点x* 。若是非正定二次函数，则迭代次数增加。若是 n 维问题，步骤相同。搜索方向：第一轮迭代，沿初始方向组Si(1) (i=1,2,n)的n个方向和共轲方向 S(1),搜索n+1次得极值点 xn+1(1);第二轮迭代，沿方向组Si(2) ( i=1,2,n; iwm )的n-1个方向和共轲方向S(1),构筑共轲方向S(2)搜索n+1次得极值点xn+1(2)。其中，为保证搜索方向的线性无关，去除了Sm(2) 方向 。在第 k 轮迭代中，为避免产生线性相关或近似线性相关，需要去除前一轮中的某个方向Sm(k)。6. 方法评价：计算步骤复杂;是二次收敛方法，收敛快。对非正定函数，也很有效是比较稳定的方法。第六章约束优化方法 第一节概述 一.有约束问题解法分类：直接解法：随机方向搜索法、复合形法、可行方向法间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数法二.直接解法的基本思想：合理选择初始点，确定搜索方向，以迭代公式x(k+1)= x(k)+ “(k)S(k)在可行域中寻优，经过若干次迭代，收敛至最优点。收敛条件：边界点的收敛条件应该符合K-T条件；内点的收敛条件为：xk1 -xk ；f(x,书 Lf(xnxp特点： 在可行域内进行； 若可行域是凸集，目标函数是定义在凸集上的凸函数，则收敛到全局最优点；否则,结果与初始点有关。有解的条件：f(x)和g(x)都连续可微； 存在一个有界的可行域；可行域为非空集； 迭代要有目标函数的下降性和设计变量的可行性。1 .基本思想：每次以一个变量坐标轴作为搜索方向，将n维的优化问题转化为一维搜索问题。例，第 k轮迭代的第i次搜索，是固定除xi外的n-1个变量，沿xi变量坐标轴作一维搜索，求得极值点xi（k）n次搜索后获得极值点序列x1（k）, x2（k）,，xn（k）,若未收敛，则开始第 k+1次迭代，直至收敛到最优点x* 。2 .搜索方向与步长:第k轮第i次搜索的方向：S的为第i个设计变量的坐标轴方向；第k轮第i次搜索的步长：5（k）Si（k）；第k轮第i次搜索的迭代公式：为二为二坨严飞严，i=1,2,n；第k轮第i次搜索的收敛条件：ai（k）Si（k）8o3 .方法评价：方法简单，容易实现。当维数增加时，效率明显下降。收敛慢，以振荡方式逼近最优点。受目标函数的性态影响很大。如图a）所示，二次就收敛到极值点；如图b）所示，多次迭代后逼近极值点；如图c）所示，目标函数等值线出现山脊（或称陡谷），若搜索到 A点，再沿两个坐标轴,以土 t0步长测试，目标函数值均上升，计算机判断A点为最优点。事实上发生错误。X/ 01 XE/U) &a )b )4.8 Poweel 法1 .基本思想：若沿连接相邻两轮搜索末端的向量S方向搜索，收敛速度加快。其中：S=X2-X2因为两条平行线 S1, S2与同心椭圆族相切，两个切点的连线S直指中心。称 S1, S2与S为共轲方向。目的：以共轲方向打破振荡，加速收敛。2 .共轲方向:设A为实对称正定矩阵，若有两个n维向量§和S2, 满足 S1TAs2=0,则称向量3和52是关于矩阵共轲， S,和S2的方向是共轲方向。3 .共轲方向的性质: 这组关于A矩阵共腕的n个非零向量§,&,.,a是线性无关的。 若Si"),S2，,Sn是线性无关的向量组，则可以构造出n个向量Si ,S2 ,Sn：满足S(2)TAS=0, (i¥j)。 设S,S2,Sn是关于A矩阵共腕的n个非零向量，对于函数f(x)分别从两个初始点xo和xo出发，沿Si(i=1,2,n)方向进行一维 搜索，分别彳#到最优点xi和X2,向量S=x2-%也是与向量组 § (i =1,2,n)中每一个向量关于A矩阵共腕。 设5,$,&是关于A矩阵共腕的n个非零向量，则对于二 次函数 T 1f (x) =C+BTX十XTAX,从任意初始点x(0)出发，依次沿 Si(i=1,2,n)方向进行一维搜索，至 多n步可收敛至极值点，称 为 二次收敛性。4 .步骤：第一轮迭代：选初始点x(0),令xoC)=x(O),依次沿两个坐标轴方向S4)S2°祚两次一维搜索，分别求得f(x的极值点/)x2O构筑共轲方向：sQ= x8Lx/ )沿此方向作第三次搜索，求得f(x的极值点x3,)第二轮迭代: 令。=乂3(1),分别沿力向作两次 一维搜索，分别求得f(x的极值点为(2履2) 构筑共腕方向：S(2)= x2(2)- x0(2)沿此方向作第三次搜索，求得f (x的极值点&(2) 每轮迭代结束时，检验 是否满足收敛条件:fok1-2°若满足，贝 x* = x3(k+) o若不满足，则作下一轮 迭代。5.说明:若是正定二次函数，n 轮迭代后收敛于最优点x* 。若是非正定二次函数，则迭代次数增加。若是 n 维问题，步骤相同。搜索方向：第一轮迭代，沿初始方向组Si(1) (i=1,2,n)的n个方向和共轲方向 S(1),搜索n+1次得极值点 xn+1(1);第二轮迭代，沿方向组Si(2) ( i=1,2,n; iwm )的n-1个方向和共轲方向S(1),构筑共轲方向S(2)搜索n+1次得极值点xn+1(2)。其中，为保证搜索方向的线性无关，去除了Sm(2) 方向 。在第 k 轮迭代中，为避免产生线性相关或近似线性相关，需要去除前一轮中的某个方向Sm(k)。6. 方法评价：计算步骤复杂;是二次收敛方法，收敛快。对非正定函数，也很有效是比较稳定的方法。
