直接方法_147201111

第11章无约束最优化的直接方法坐标轮换法(CyclicCoordinateMethod)TnTTneeenR)1,,0,0(,,)0,,1,0(,)0,,0,1(21个基，分别为中有设在基本思想：12(1)111213111neeennxxxxxx1211212223221neeennnxxxxxx1221313233eenxxxx步骤：.1,),()(min0,.110)0()1(10)0(1)0(1)0(kexxexfexfeRxn置令进行一维搜索：，沿任取.13,1,),()(min.21)()1(1)(1)(1否则，返回；则进入，若置令进行一维搜索：沿nkkkexxexfexfekkkkkkkkkk。，返回否则，令；则停止计算，得点若1*,.3)()0()()0()(nnnxxxxxx这种方法简单、直观，但对于山脊形函数或自变量间有大的交互作用不适用。最优点终点x2x1x(1)x(0)x(2)模式搜索法（步长加速法）模式移动探测移动两种类型的移动探测移动：依次沿n个坐标轴进行，用于确定新的基点和有利于函数值下降的方向。模式移动：沿相邻两个基点连线方向进行，试图使函数值更快减少。12(1)()(1,0,,0),(0,1,,0),,(0,0,,1)0,1(0,1)0nTTTnnfxxReeexR设目标函数，，坐标轴方向分别为，给定初始点，各坐标方向的初始步长加速因子，缩短因子及精度要求。(1)(1)(1)..iiyyx把沿第个坐标方向搜索得到的点记为初始点探测性搜索：1(1)(1)1(2)(1)1(1)(1)111(1)(1)1(2)(1)1(1)(1)1(2)(1)(1)()().()()()().()()efyfyeyyefyfyeeefyfyeyyefyfyeyy沿方向进行探测性搜索若，则称探测成功，令若，则称探测失败，这时再沿的反方向进行探测性搜索：若，则称反方向探测成功，令若，则称探测失败，令。.,,)3()1(nyn最后得到个坐标方向都探测完毕直到沿重复上述步骤。得进行类似的探测搜索，出发，沿从)3(2)2()2(yey探测性搜索。开始进行，再从否则，要将步长缩短为模式搜索。，进行下一步探索为新的基点，记，以则称完成了探测性搜索若满意：检验总的探测效果是否)1()1()2()1()1()1(),()()4(xyxyxfyfnnn模式搜索。作模式移动，令出发，沿方向从)()1()2()2()1()1()2()2(xxxyxxx。得到的点仍记为毕进行探测搜索，探测完为起点，沿坐标轴方向以)1()1(nyy进行模式移动。，再沿得新的基点成功，，则表明此次模式移动若)2()3()1()3()2()1()()(xxyxxfyfnn为此。去，直到进行探测移动，如此下出发，沿坐标轴方向，再从，减少步长退回失败，，则表明此次模式移动若)2()2()2()1()()(xxxfyfn步骤：。，，置差，允许误，缩减率，加速因子步长，初始个坐标方向，给定初始点1,10)1,0(1,,,.1)1()1(21)1(jkxyeeenxn。；否则转转，，则令如果34)()(.2)()1()()(jjjjjjeyyyfeyf。转；否则令转，，则令如果4,4)()(.3)()1()()1()()(jjjjjjjjyyeyyyfeyf。；否则，转，转，则置如果521.4jjnj。；否则，转，则转若76)()(.5)()1(knxfyf。，转，置，，令置211)(.6)()1()1()1()1()1(jkkxxxyyxkkknk()(1)()7.1,12kkxyxkkj如果，则停止迭代，得点；否则，置，，置，转。22122151)(minxxxxf.1,21,)1,0(,)0,1(,)0,2(21)1(TTTeex1695121,233)(1695121,23169250,232)(169250,23)(1691970,2581)0,2(1)()()()()()()()()(TTTTTTiiiiiiiiiieyfeyeyfeyyfyi成功成功失败。点第一轮探测结束，得基Tyxyfxfyf21,23),()()()3()2()1()1()3(.)1,1()1()2()2()1()1()2(Txxxyxx方向进行模式移动，令沿TTTTTTTiiiiiiiiiieyfeyeyfeyyfyi1,13)(41121,1)(41123,101,12)(10130,21)(16181,230)1,1(1)()()()()()()()()(失败失败失败失败。模式移动成功，得基点Tyxxfyf1,1),(0)()3()3()2()3(.2321)2()3()3()1()2()3()3(Txxxyxxx，方向进行模式移动，令出发，沿从()()()()()()()()()1331,8.061,1.25()222321,1.251,25()1,10()231,10iiiiiiiiiiTTTTTTiyfyyefyeyefye成功失败成功(3)(3)(3)()0(),14fyfxx模式移动失败，退回基点，减少步长。，从新探测。，令Txy11)3()1(01,13)(31.043,1)(31.045,101,12)(02.11,43)(38.01,4501,11)()()()()()()()()(TTTTTTTiiiiiiiiiieyfeyeyfeyyfyi失败失败失败失败(3)(3)(3)(1)(3)()0(),1,8(1,1)Tfyfxxyx探测移动失败，退回基点，减少步长再从开始，探测仍然失败，且，所以为原问题的最优解。(1)(1)(2,0)xy(2)3,02y(3)(2)31,22yx(1)(2)(3)(3)1,1yyyx(1)13,22y(2)31,2y•特点：收敛速度比较慢，但编制程序比较简单，对变量不多的问题可以使用，而且确实是一种可靠的方法，另外，此法可用于求解非线性目标规划问题。Rosenbrock算法包括探测阶段和构造搜索方向两部分。探测阶段：从一点出发，依次沿n个单位正交方向进行探测移动，一轮探测之后，再从第一个方向开始继续探测，经过若干轮探测移动，完成一个探测阶段。转轴：构造一组新的单位正交方向。1．探测阶段.,,,,,,,,:)1()1(21)()2()1()(nnnkyydddnxk，终点为探测的起点为每轮沿各方向的步长为：个单位正交搜索方向为，次迭代的初始点为设第。依次探测，直到得到点，做探测移动，得点出发，沿再从，则探测失败，令如果，则探测成功，令如果探测。出发，沿从令第一轮探测移动：)1()3()2()2(11)1()2()1()1(1)1(11)1(1)1()2()1()1(1)1()1()1()()1());0,1((,)()();1(,)()(,nkyydyyyyfdyfdyyyfdyfdyxy.)1()1()1()1(nknyxyy令均失败为此。一轮沿各个方向的探测直至某，开始下一轮的探测，令2．构造新的搜索方向)()2(2)1(1)()1()()2(2)1(1)()1(nnkknnkkdddxxdddxx，有根据上一阶段探测结果njdddpjnnjjjjj,,100)()()()(令()()()()1()()()()1()()()12jjiTjjjiiTiijjjpjqqppqjqqqdq令单位化：.0,,,,,,)()()()2()1()()2()1(jjjnndddddddd时，有，且当也线性无关，互相正交所以线性无关且互相正交，因为步骤:.1,1,,2,1,0)0,1(1,,,,,,,,.1)0()1()1()0()0()0()()2()1()1(21jknixydddxiinn。置和允许误差，缩减因子，放大因子步长单位正交方向给定初始点；，则令如果；，则令如果jjjjjjjjjjjjjjjjjjyyyfdyfdyyyfdyf:,)()(:,)()(.2)()1()()()()()()1()()()(。；否则，转，转，则置如果421:.3jjnj(1)(1)(1)(1)(1)(1)4.()()12()()5nnnfyfyyyjfyfy如果，则令，置，转；如果，则转。(1)()()(1)(1)5.()()6,,12nkkjnfyfxjxyyj如果，则转；否则，如果对每个则停止计算，作为最优解的估价；如果不满足终止准则，则令，置，转。。返回置，置算；否则，计算极小点的估计，停止计为，则取。如果令2,1,1:,.,,2,1,,,2,1,2100,,,,.6)1(1)0()()()()()(11)()()()()()()()()()()(21)1()()1()1()1(jkkxynjnjddqqdjqqqpqpjpqddpxxxyxkjjjjjjjjiiiTijTijjjinjiiiijjnkkknk例：用Rosenbrock方法求解2212min()4(5)(6)fxxx(1)(1)(0)(0)12(1)(2)(8,9),()45,0.1(1,0),(0,1),3,0.5,TTTxfxdd解：取初始点第一次迭代(1)(1)(0)(1)(1)(1)1(2)(1)11(2)(2)(2)2(3)(1)22(3)(1)(1),1,1,,1,2()(8.1,9)47.44()0.05;()(8,9.1)45.61()0.05;()(),jjyxkjjfydffyyyfydffyyyfyfxy探测失败，令，：探测失败，令，：即两次均失败，令(3)(1)1yxj=，再从开始。(1)(1)(1)1(2)(1)(1)1111(2)(2)(2)2(3)(2)(2)2222(3)(1)()(7.95,9)43.81()0.15,0.05;()(7.95,8.95)43.125()0.15,0.05;()(),fydffyyydfydffyyydfyfy探测成功，令，：探测成功，令，：即沿两个坐标的探测至少有一次成功。12()10.157.808.9540.060.220.157.808.8039.200.210.457.358.8029.930.6520.457.358.3527.610.6511.356.008.359.522221.356.007.005.00214.051.957.0