坐标轮换法汇总

1、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(k)为第I个设计变量的坐标轴方向；i第k轮第I次搜索的步长：a(k)S(k)；II第k轮第I次搜索的迭代公式：x(k)=x(k)+a.(k)S(k),I=1,2,.,n；I/-11I第k轮第I次搜索的收敛条件：ai(k)S(k)|

2、o3.方法评价：方法简单，容易实现。当维数增加时，效率明显下降。收敛慢，以振荡方式逼近最优点。受目标函数的性态影响很大。如图a)所示，二次就收敛到极值点；如图b)所示，多次迭代后逼近极值点；如图c)所示，目标函数等值线出现山脊(或称陡谷)，若搜索到A点，再沿两个坐标轴以土to步长测试，目标函数值均上升，计算机判断A点为最优点。事实上发生错误。4.8Poweel法1.基本思想：若沿连接相邻两轮搜索末端的向量S方向搜索，收敛速度加快。其中：S=x2（2）-x2（i）因为两条平行线S1,S2与同心椭圆族相切，两个切点的连线S直指中心。称S1,S2与S为共轭方向。目的：以共轭方向打破振荡，加速收敛。2

3、.共轭方向：设A为实对称正定矩阵，若有两个n维向量S和S，12满足StAS=0,则称向量S和S是关于矩阵共轭，1212S和S的方向是共轭方向。12若A为单位矩阵I，贝ySTIS=0时，即STS=0,1212则S和S正交。12设A为正定实对称矩阵，若有一组非零向量S,S，,S,12n能满足STAS=0（i丰j）,则称这组向量是关于矩阵A共轭。ij3.共轭方向的性质：这组关于A矩阵共轭的n个非零向量S,S，,S是线性无关的。12n若S(1),S,S是线性无关的向量组，则可以构造出n个向量TOC o 1-5 h z12nS,S,S，满足StAS(2)=0,(i丰j)。12nii设S,S,.,S是关于

4、A矩阵共轭的n个非零向量，对于函数f(x)12n分别从两个初始点x和x出发，沿S(i=1,2,.,n)方向进行一维00i搜索，分别得到最优点x和x，向量S=x-x，也是与向量组1221S(i=1,2,.,n)中每一个向量关于A矩阵共轭。i设S,S,.,S是关于A矩阵共轭的n个非零向量，则对于二次函数12nf(x)=C+BtX+丄XtAX，从任意初始点x(0)出发，依次沿2S(i=1,2,.,n)方向进行一维搜索，至多n步可收敛至极值点，称为i二次收敛性。4.步骤：第一轮迭代：选初始点x(0)，令xG=x(0)，依次沿0两个坐标轴方向S，G作两次一维搜索,分别求彳得(x的极值点xG,xG。12构

5、筑共轭方向：SG=G-xG,沿此方向作第三次搜索，求得f(x的极值点x3第二轮迭代：令xC)=x(1)，分别沿S?G,SG方向作两次一维搜索，分别求得/6的极值点xC),xC)。12构筑共轭方向：S()=x(2)-xC)，沿此方向作第三次搜索，求得f(x)的极值点xC)。lx(k+1)-x)卜,或f(k+1)f(k)00f(k+1)J08。23若满足，则x每轮迭代结束时，检验是否满足收敛条件：=x(k+1)。3若不满足，则作下一轮迭代。5.说明：若是正定二次函数，n轮迭代后收敛于最优点x*。若是非正定二次函数，则迭代次数增加。若是n维问题，步骤相同。搜索方向：第一轮迭代，沿初始方向组Si(l)

6、(i=l,2,.,n)的n个方向和共轭方向S(l),搜索n+1次得极值点xn+1(1)；第二轮迭代，沿方向组Si(i=1,2,.,n；iMm)的n-1个方向和共轭方向S(1)，构筑共轭方向S(2)搜索n+1次得极值点xn+1。其中，为保证搜索方向的线性无关，去除了Sm(2)方向。在第k轮迭代中，为避免产生线性相关或近似线性相关，需要去除前一轮中的某个方向Sm(k)。6.方法评价：计算步骤复杂;是二次收敛方法，收敛快。对非正定函数，也很有效;是比较稳定的方法。第六章约束优化方法第一节概述一.有约束问题解法分类：直接解法：随机方向搜索法、复合形法、可行方向法间接解法：内点惩罚函数法、外点惩罚函数法

7、、混合惩罚函数法二.直接解法的基本思想：合理选择初始点，确定搜索方向，以迭代公式x(k+l)=x(k)+a(k)S(k)在可行域中寻优，经过若干次迭代，收敛至最优点。收敛条件：边界点的收敛条件应该符合K-T条件；内点的收敛条件为：X(k+1)XG)卜2特点：在可行域内进行；若可行域是凸集，目标函数是定义在凸集上的凸函数，则收敛到全局最优点；否则结果与初始点有关。有解的条件：f(x)和g(x)都连续可微；存在一个有界的可行域；可行域为非空集；迭代要有目标函数的下降性和设计变量的可行性。1.基本思想：每次以一个变量坐标轴作为搜索方向，将n维的优化问题转化为一维搜索问题。例，第k轮迭代的第i次搜索，

8、是固定除xi外的n-1个变量，沿xi变量坐标轴作一维搜索，求得极值点xi(k)n次搜索后获得极值点序列x1(k),x2(k)，,xn(k)，若未收敛，则开始第k+1次迭代，直至收敛到最优点x*。搜索方向与步长：第k轮第i次搜索的方向：S(k)为第i个设计变量的坐标轴方向；i第k轮第i次搜索的步长：a(k)S(k)；ii第k轮第i次搜索的迭代公式：x(k)=x(k)+a.(k)S(k),i=1,2,.,n；ii-11i第k轮第i次搜索的收敛条件：ai(k)S(k)|8O3.方法评价：方法简单，容易实现。当维数增加时，效率明显下降。收敛慢，以振荡方式逼近最优点。受目标函数的性态影响很大。如图a)所

9、示，二次就收敛到极值点；如图b)所示，多次迭代后逼近极值点；如图c)所示，目标函数等值线出现山脊(或称陡谷)，若搜索到A点，再沿两个坐标轴以土tO步长测试，目标函数值均上升，计算机判断A点为最优点。事实上发生错误。4.8Poweel法1.基本思想：若沿连接相邻两轮搜索末端的向量S方向搜索，收敛速度加快。其中：S=x2（2）-x2（i）因为两条平行线S1,S2与同心椭圆族相切，两个切点的连线S直指中心。称S1,S2与S为共轭方向。目的：以共轭方向打破振荡，加速收敛。2.共轭方向：设A为实对称正定矩阵，若有两个n维向量S和S，12满足StAS=0,则称向量S和S是关于矩阵共轭，1212S和S的方向

10、是共轭方向。12若A为单位矩阵I，贝ySTIS=0时，即STS=0,1212则S和S正交。12设A为正定实对称矩阵，若有一组非零向量S,S，,S,12n能满足STAS=0（i丰j）,则称这组向量是关于矩阵A共轭。ij共轭方向的性质：这组关于A矩阵共轭的n个非零向量S,S，,S是线性无关的。12n若S(1),S,S是线性无关的向量组，则可以构造出n个向量TOC o 1-5 h z12nS,S,S，满足StAS(2)=0,(i丰j)。12nii设S,S,.,S是关于A矩阵共轭的n个非零向量，对于函数f(x)12n分别从两个初始点x和x出发，沿S(i=1,2,.,n)方向进行一维00i搜索，分别得到

11、最优点x和x，向量S=x-x，也是与向量组1221S(i=1,2,.,n)中每一个向量关于A矩阵共轭。i设S,S,.,S是关于A矩阵共轭的n个非零向量，则对于二次函数12nf(x)=C+BtX+丄XtAX，从任意初始点x(0)出发，依次沿2S(i=1,2,.,n)方向进行一维搜索，至多n步可收敛至极值点，称为i二次收敛性。4.步骤：第一轮迭代：选初始点x(0)，令xG=x(0)，依次沿0两个坐标轴方向S，G作两次一维搜索,分别求彳得(x的极值点xG,xG。12构筑共轭方向：SG=G-xG,沿此方向作第三次搜索，求得f(x的极值点x3第二轮迭代：令xC)=x(1)，分别沿S?G,SG方向作两次一维搜索，分别求得/6的极值点xC),xC)。12构筑共轭方向：S()=x(2)-xC)，沿此方向作第三次搜索，求得f(x)的极值点xC)。lx(k+1)-x)卜,或f(k+1)f(k)00f(k+1)J08。23若满足，则x每轮迭代结束时，检验是否满足收敛条件：=x(k+1)。3若不满足，则作下一轮迭代。5.说明：若是正定二次函数，n轮迭代后收敛于最优点x*。若是非正定二次函数，则迭代次数增加。若是n维问题，步骤相同。搜索方向：第一轮迭代，沿初始方向组Si(l)(i=l,2,.,n)的n个方向和共轭方向S(l),搜索n+1次得极值点xn+1(1)