搜索
第八章无约束最优化的直接法本章主要内容：坐标轮换法及其收敛性模式搜索法及其收敛性旋转方向法、Powell法。教学目的及要求：掌握坐标轮换法并理解其收敛性，掌握模式搜索法并理解其收敛性；了解旋转方向法、Powell法。教学重点：Powell法．教学难点：Powell法．教学方法：启发式．教学手段：多媒体演示、演讲与板书相结合．教学时间：6学时．教学内容：§8.1坐标轮换法考虑无约束最优化问题min()fx，（8.1.1）其中,:nnxRfRR．算法8-1（坐标轮换法）Step1选取初始数据．选取初始点0x，给定允许误差0，令1k．Step2进行一维搜索．从1kx出发，沿坐标轴方向010ke进行一维搜索，求1k和kx，使得111()min()kkkkkfxefxe，11kkkkxxe．Step3检查迭代次数．若kn，转Step4；否则，令:1kk，返回Step2．Step4检查是否满足终止准则．若0nxx，迭代终止，得nx为问题（8.1.1）的近似最优解；否则，令0:,:1nxxk，返回Step2．定理8.1.2设:nfRR具有一阶连续偏导数，0nxR，记0()fx，且水平集(,)Sf有界．若kx是用坐标轮换法求解问题（8.1.1）产生的点列，且在每次一维搜索中所得到的最优解都是唯一的，则（1）当kx为有穷点列时，其最后一个点是f的平稳点；（2）当kx为无穷点列时，它必有极限点，并且其任一极限点都是f的平稳点．例1用坐标轮换法求解问题2212112min()3fxxxxxx，（8.1.3）其中12(,)Txxx．取初始点(0)(0,0)Tx，允许误差0.1．解从点(0)x出发沿1e进行一维搜索：(0)101000xe，将12,0xx代入2212112()3fxxxxxx中，易得(1)(0)00133,(,0)22Txxe；从点(1)x出发沿2e进行一维搜索，得(2)(1)112333,(,)424Txxe；(2)(0)xx．再从点(2)x出发沿1e进行一维搜索，得(3)(2)2213153,(,)884Txxe；从点(3)x出发沿2e进行一维搜索，得(4)(3)33231515,(,)4816Txxe；(4)(2)xx．再从点(4)x出发沿1e进行一维搜索，得(5)(4)44136315,(,)323216Txxe；从点(5)x出发沿2e进行一维搜索，得(6)(5)55236363,(,)643264Txxe；(6)(4)xx．再从点(6)x出发沿1e进行一维搜索，得(7)(6)661325563,(,)12812864Txxe；从点(7)x出发沿2e进行一维搜索，得(8)(7)7723255255,(,)256128256Txxe；(8)(6)xx．迭代终止，得问题（8.1.3）的近似最优解为(8)255255(,)128256Tx．其实问题（8.1.3）的最优解为(2,1)T．§8.2模式搜索法算法8-2（模式搜索法）Step1选取初始数据．选取初始点0x，初始步长00，给定收缩因子(0,1)，给定允许误差0，令0k．Step2确定参考点．令,1kyxj．Step3进行正轴向探测．从点y出发，沿je作正轴向探测：若()()kjfyefy，令:kjyye，转Step5；否则，转Step4．Step4进行负轴向探测．从点y出发，沿je作负轴向探测：若()()kjfyefy，令:kjyye，转Step5；否则，转Step5．Step5检验探测次数．若jn，令:1jj，返回Step3；否则，令1kxy，转Step6．Step6进行模式移动．若1()()kkfxfx，从点1kx出发沿加速方向1kkxx作模式移动，令112,,:1,1kkkkyxxkkj，返回Step3；否则，转Step7．Step7检查是否满足终止准则．若k，迭代终止，得问题（8.1.1）的近似最优解为kx；否则，转Step8．Step8缩短步长．若1kkxx，令1,:1kkkk，返回Step2；否则，令11,,:1kkkkxxkk，返回Step2．定理8.2.1设:nfRR是具有一阶连续偏导数的凸函数，0nxR，记0()fx，并且水平集(,)Sf有界．若kx为由模式搜索法求解问题（8.1.1）产生的点列，则kx必存在极限，且其任一极限点都是问题（8.1.1）的最优解．§8.3旋转方向法算法8-3（旋转方向法）Step1选取初始数据．选取初始点0x，初始单位正交方向组12,,,nddd（可取12,,,nddd为坐标轴方向12,,,neee）．给定初始步长(0)(0)(0)(0)12(,,,)Tn，收缩因子(0,1)，放大因子1，允许误差0，令0k．Step2确定参考点．取参考点kyx，并令,1kzxj．Step3进行轴向探测．若()()()kjjfydfy，令()()():,:kkkjjjjyyd，转Step4；否则，令()():kkjj，转Step4．Step4检验探测次数．若jn，令:1jj，返回Step3；否则，转Step5．Step5判断探测是否结束．若()()fyfz，令,1zyj，返回Step3；若()(),()()kfyfzfyfx，令1kxy，转Step6；若()()()kfyfzfx，转Step7．Step6检查是否满足终止准则．若1kkxx，迭代终止，1kx为问题（8.1.1）的近似最优解；否则，转Step8．Step7检验步长大小．若对一切()1,2,,,kjjn，迭代终止，kx为问题（8.1.1）的近似最优解；否则，令,1zyj，返回Step3．Step8进行轴向旋转．计算各轴向移动的步长的代数和：12,,,n，利用,0,,0.jjnjiijijdpd（8.3.1）11,1,,2.jTjjijjjjTiiipjqqppdjqp（8.3.2）,1,2,,jjjqdjnq．（8.3.1）构造新的单位正交方向12,,,nddd，并令(1)(),,1,2,,,:1kkjjjjddjnkk，返回Step2．§8.4Powell法算法8-4（Powell法）Step1选取初始数据．选取初始点0x，n个线性无关的初始搜索方向011,,,nddd，给定允许误差0，令0k．Step2进行基本搜索．令0kyx，依次沿011,,,nddd进行一维搜索．对一切1,2,,jn，记11111()min()jjjjjfydfyd，111jjjjyyd．Step3检查是否满足终止准则．取加速方向0nndyy，若nd，迭代终止，得ny为问题的近似最优解；否则，转Step4．Step4确定搜索方向．按1101()()max{()()}mmjjjnfyfyfyfy（8.4.17）确定m，若001()2()(2)2[()()]nnmmfyfyfyyfyfy（8.4.18）成立，转Step5；否则，转Step6．Step5调整搜索方向．从点ny出发沿方向nd作一维搜索．求出n，使得()min()nnnnnfydfyd．令1knnnxyd，再令1:,,1,,1jjddjmmn，:1kk，返回Step2．Step6不调整搜索方向．令1knxy，:1kk，返回Step2．例2用Powell法求解问题（8.1.3）：2212112min()3fxxxxxx，仍取初始点(0)(0,0)Tx，初始搜索方向组01(0,1),(1,0)TTdd，给定允许误差0.1．解第一次迭代：令(0)(0)(0,0)Tyx，从点(0)y出发沿0d进行一维搜索，易得(1)(0)0000,(0,0)Tyyd；接着从点(1)y出发沿1d进行一维搜索，得(2)(1)11133,(,0)22Tyyd由此有加速方向(2)(0)23(,0)2Tdyy．因为23/2d，所以要确定调整方向．由于(0)(1)(2)9()0,()0,()4fyfyfy，按（8.4.17）式有(1)(2)()(1)()()max{()()|0,1}jjfyfyfyfyj，因此1m，并且()(1)(1)(2)9()()()()4mmfyfyfyfy．又因(2)(0)(2)0fyy，故（8.4.18）式不成立．于是，不调整搜索方向组，并令(1)(2)3(,0)2Txy．第二次迭代：取(0)(1)3(,0)2Tyx，从点(0)y出发沿0d作一维搜索，得(1)(0)000333,(,)424Tyyd．接着从点(1)y出发沿方向1d作一维搜索，得(2)(1)1113153,(,)884Tyyd．由此有加速方向(2)(0)233(,)84Tdyy．因为235/8d，所以要确定调整方向．因(0)(1)(2)945189(),(),()41664fyfyfy，故按（8.4.17）式易知0m，并且()(1)(0)(1)9()()()()16mmfyfyfyfy．由于(2)(0)45(2)16fyy，因此（8.4.18）式成立。于是，从点(2)y出发沿2d作一维搜索，得(2)(2)2221,(2,1)3Txyd。同时，以2d替换0d，即下一次迭代的搜索方向组取为0133(1,0),(,)84TTdd．第三次迭代：取(0)(2)(2,1)Tyx，类似地可求得(1)(2)(2,1),(2,1)TTyy，(2)(0)2(0,0)Tdyy．因为20d，所以迭代终止，得问题（8.1.3）的最优解为(3)(2)(2,1)Txy．