变尺度法及鲍威尔法

鲍威尔法为啥这么难？！！！！12:36:342020/1/1922.修正鲍威尔法改进的鲍威尔法放弃了原算法中不加分析地用新形成的方向替换上一轮搜索方向组中的第一个方向的作法。)(kS)(kS该算法规定：在每一轮迭代完成产生共轭方向后，在组成新的方向组时不一律舍去上一轮的第一个方向，而是先对共轭方向的好坏进行判别，检验它是否与其他方向线性相关或接近线性相关。)(1kS若共轭方向不好，则不用它作为下一轮的迭代方向，而仍采用原来的一组迭代方向；若共轭方向好，则可用它替换前轮迭代中使目标函数值下降最多的一个方向，而不一定是替换第一个迭代方向。这样得到的方向组，其收敛性更好。212:36:342020/1/193修正鲍威尔法对于是否用新的方向来替换原方向组的某一方向的判别条件为：在第k轮搜索中，根据下述条件式是否满足分两种情况来处理：221nn0/fffkkkkkXff00为第k环的起始点函数值；kkXffnn为第k环的沿基本方向组依次搜索后的终点函数值；knkXff11n为对映射点函数值，kX0knXkkkXXX0n1n2kkkkkkXfXfXfXfffi1im1-mm1-mmax1≤i≤n，为第环方向组中沿各方向一维搜索所得的函数值下降最大者。(4-43)312:36:342020/1/194两种情况：412:36:342020/1/196修正的鲍威尔法的迭代计算步骤如下：(1)给定初始点X(o)和收敛精度ε0；(2)取n个坐标轴的单位向量ei(i=1,2,…,n)为初始搜索方向Si(k)=ei，置k=1(k为迭代轮数)；(3)从出发，依次沿进行n次一维搜索，得到n个一维极小点)(0kX()(1,2,,)kiSin()()()()1(1,2,,)kkkkiiiiXXSin(4)连接、，构成新的共轭方向，即()()()0kkknSXX)(0kX)(knX)(kS(5)沿方向一维搜索求得步长,得)(kSkkkkkSXXn(6)检验精度，若，则结束迭代，得；否则继续进行下一步。612:36:342020/1/197()()()11mn()()()1={()()}(1,2,,)maxkkkmiikkkmmmfXfXinSXX(8)计算第k轮中各相邻极小点目标函数的差值，并找出其中的最大差值及其相应的方向:(9)计算第k轮初始点、终点和映射点的函数值(10)检验鲍威尔条件，原方向组是否需要替换：(7)沿共轭方向计算的映射点()()()102kkknnXXX)(kS)(0kX)()()()(1)(1)()()(0)(0knknknknkkXffXffXff712:36:342020/1/198由出发沿方向进行一维搜索，求出该方向的极小点，并以作为k+1轮迭代的初始点，即令；然后去掉方向，而将方向作为k+1轮迭代的最末一个方向，即第k+1轮的搜索方向为：)(knX)(kS)(kX(1)()0kkXX)(kX)(kmS)(kS()(1)11()(1)22()1()1()(1)()kkkkkmkmknkknSSSSSSSSS若上述判别条件满足，则进人第k+1轮迭代时，仍采用第k轮迭代的方向，初始点取(1)()11(1)()22(1)()kkkkkknnSSSSSS若不满足判别条件:时当时当kkkkkkkffXffXX1nn1n1nnn10812:36:342020/1/199(1)()00(1)()001(1)0()()()kkkkkXXfXfXfX***()XffX(8)进行收敛判断：若满足或否则，置，转入下一轮继续进行循环迭代。1kk修正鲍威尔法的计算框图如图4-c所示。可结束迭代计算，输出最优解：91、试用修正鲍威尔算法从开始求目标函数(0)[2,2]TX221212()2fXxxxx的最优解，并用表格列出各次的搜索方向。解：第一次迭代1）初始点为(1)(0)020.00012XX，2）取搜索方向为2个坐标轴的向量(1)(1)112210,01SeSe2.4.4鲍威尔法解：第一次迭代3）从出发，先从方向进行一维最优搜索(1)0X(1)1S(1)(1)(1)(1)(1)(1)110111212++=202XXS2.4.4鲍威尔法(1)11222121221(1)(1)1112+,2()2g()22+422+,xxfXxxxx即，代入函数，得解：第一次迭代从出发，沿方向进行一维最优搜索(1)1X(1)2S(1)(1)(1)(1)(1)21222(1)20.50.50+=212+XXS同理，得最优步长为(1)2-1.75(1)20.50.25X则2.4.4鲍威尔法11(1)1110=-1.5dgd求导即为，令得最优步长(1)10.5=2X则(1)(1)02,XX4）连接构成共轭方向(1)(1)(1)2020.51.520.251.75SXX解：第一次迭代沿着计算的映射点(1)0X(1)S(1)(1)(1)320121.5XXX5）计算本轮相邻二点函数值的下降量，并求其最大差值及其相应的方向1(1)(1)012()8,()3.5,()0.5625fXfXfX(1)(1)(1)101(1)(1)(1)212()()4.5,()()2.9375fXfXfXfX(1)(1)m1(1)(1)114.510mSSe所以2.4.4鲍威尔法1(1)(1)012()8,()3.5,()0.5625fXfXfX6）计算110(1)22(1)33()8,()0.5605,()=2.75FfXFfXFfX7）进行条件判断，条件成立，则需要按照原方向进行搜索，由于，F2F3，故第二轮迭代的初始点为(2)(1)02XX2.4.4鲍威尔法(2)(2)112210,01SeSe221nn0/fffkkk12:36:342020/1/1916两种情况：168）进行终止迭代判定(2)(1)000.521.5=0.00010.2521.75XX故需要进行下一次迭代2.4.4鲍威尔法