第四章常用的无约束优化方法

机械优化设计1第四章常用的无约束优化方法§4-1坐标轮换法§4-2鲍威尔方法§4-3最速下降法（梯度法）§4-5共轭梯度法§4-5牛顿类方法§4-6无约束优化方法的评价准则机械优化设计2教学目的、要求1．掌握常用无约束优化方法的基本思想、方法构成、迭代步骤、终止准则。教学重点1．鲍威尔法2．梯度法3．牛顿法机械优化设计3*12min()(),:()01,2,,()01,2,,nnjkFXFxxxXRgXjmhXkl，，，D有约束优化问题模型一、无约束优化方法的数学模型无约束优化问题模型*12min()(),nnFXFxxxXR，，，概述机械优化设计4二、研究无约束优化方法的意义（1）有些实际问题，其数学模型本身就是一个无约束优化问题。（2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。（3）约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。机械优化设计5三、解法分类1）直接法其搜索方向直接取定或由计算目标函数值所得的信息来确定；2）间接法（解析法）确定搜索方向时用到一阶或（和）二阶导数的方法。机械优化设计6机械优化设计7一.搜索方向依次沿个n个正交坐标轴的方向搜索：二.迭代过程（以2维问题为例）2x1x00X1X20XX1X20XX1210121202...XXeXXeXXTnTTeee]1...00[...]0...10[]0...01[21§4-1坐标轮换法机械优化设计8机械优化设计9从出发沿方向进行一维搜索得：1iXieiiiiieXX1)(iXFF1ini给定,,0nX0XXn1iiFFXXn结束10kkXXn1k是否否是坐标轮换法流程图机械优化设计10三.算法特点如:(1)等值线为椭圆,且长短轴分别平行于坐标轴时--高效1x2xo(2)等值线为如图脊线时--无效1x2xo(3)一般情况--低效1）编程简单，容易掌握；2）收敛速度通常较低（其有效性取决于目标函数的性态），仅适于低维的情况。机械优化设计11四.算例用坐标轮换法求函数22121()23810fXxxx的极小点，已知(0)[1,2],0.001TXK120X1X2X20XX101102XX22(1)128(1)10f4(1)801dfd122X*20X2f1,2T2,2T2,0T2.2362,0T2,0T2,0T0机械优化设计12§4-2鲍威尔方法鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。1964年，鲍维尔提出这种算法，其基本思想是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后的实践中进行了改进。机械优化设计132x3x1xo0X1e2e3e3）若目标函数为正定二次函数，n轮结束后即可到达最优点。2）每轮迭代产生一个新方向取代原来的第一方向，n轮迭代后可产生n个彼此共轭的方向；nX1）开始采用坐标轴方向；一、Powell基本算法机械优化设计14二、Powell法（Powell修正算法）2x3x1xo0X2e3e1X应用Powell基本算法时，若有一次搜索的最优步长为0，且该方向被换掉，则该算法失效。1）问题的提出和重合0X1X以后的搜索均在ox2x3平面内进行退化机械优化设计152)Powell对基本算法的改进在获得新方向构成新方向组时,不是轮换地去掉原来的方向,而是经判别后,在n+1个方向中留下最接近共轭的n个方向.*①根据Powell条件判定是否需换方向；②如需换向，则换掉函数值下降量最大的方向.机械优化设计161.基本算法•二维情况描述鲍威尔的基本算法:1）任选一初始点x0(1)，选坐标轴单位向量e1=[1,0]T和e2=[0,1]T作为初始搜索方向。2）从X0(1)出发，顺次沿e1、e1作一维搜索，得点，两点连线得一新方向s1()()12,XX111(1)(1)20sXXx1x2o12X*1e(1)2X1se(1)1X(1)0X机械优化设计17(2)(2)220sXX沿s2作一维搜索得点X0(3)。即是二维问题的极小点X*。方法的基本迭代格式包括共轭方向产生和方向替换两主要步骤。用s1代替e1形成两个线性无关向量s1,e2，作为下一轮迭代的搜索方向。再从出发，沿S1作一维搜索得点，作为下一轮迭代的初始点。(1)2X(2)0X3）从，顺次沿e2,s1作一维搜索，得到点，两点连线得一新方向:(2)(2)12,XX(2)0X2so1(2)2X(2)0Xx1x2o12X*(2)1X1e(1)2X1se(1)1X(1)0X机械优化设计18•把二维情况的基本算法扩展到n维，则鲍威尔基本算法的要点是：•在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和n个线性独立的搜索方向。从始点出发顺次沿n个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。•用这个方向替换原来n个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。上述基本算法仅具有理论意义。机械优化设计192e2x3x1xo0X3e1X应用共轭方向法时，若有一次搜索的最优步长为0，且该方向被换掉，则共轭方向法失效。变成二维问题和重合0X1X2e以后的搜索均在ox2x3平面内进行退化机械优化设计202.修正算法在获得新方向构成新方向组时,不是轮换地去掉原来的方向,而是经判别后,在n+1个方向中留下最接近共轭的n个方向.*①根据Powell条件判定是否需换方向；②如需换向，则换掉函数值下降量最大的方向.机械优化设计21)(0kX()knX1）Powell条件),()(01kXFF)(0)()(12kknknXXX),()(2knXFF)()(13knXFF}),()(max{,...,...2,1)()(1nmikikiXFXF)()()()(1kmkmXFXF23122132113)(21))(2(FFFFFFFFF如下述两不等式同时成立则需换向，否则仍取原方向组。计算:（映射计算）)(1knX)(1kXPQ()kmmS为目标函数值下降量最大的方向的标号()2kX()1kS()2kS()knS机械优化设计222）更换方向的步骤()()()10kkknnSXX3）更换方向：2）构造新方向：1）找出该轮迭代中目标函数值下降量最大的方向（假定其标号为m）；(k)(k)mn1SS淘汰函数值下降量最大的方向，将Sn+1(k)补在最后第k+1环的方向组为：(k)(k)(k)(k)(k)(k)12m-1m+1nn+1S,S,...,S,S,...,S,S,机械优化设计23Powell修正算法F3F1QPSi=Si+1i=m,m+1,…nin输出X*=XnF*=F（X*）结束给定X0,Si=eii=1,2,…n,εK=0i=1自Xi-1始，沿Si方向搜索得一维最优点Xii=i+1Xn+1=2Xn-X0Sn+1=Xn-X0自Xn始，沿Sn+1方向搜索得一维最优点X*K=K+1F1=F(X0),F2=F(Xn),F3=F(Xn+1)求Δ及方向标号mYYYYNNNX0=X*NXn-X0≤ε若powell法中不需要换向，则是否仍为共轭方向法？检查两次前后sn+1是否对函数的海塞矩阵共轭即可。机械优化设计24•例用鲍威尔修正算法求目标函数2212112()242xxxxxFx解：（1）第1轮迭代计算(1)01X1(1)10F(X)3F沿e1方向进行一维搜索()201min()431FXe12得(1)(1)1011113XX2101e(1)1F(X)70.001。的最优解。已知初始点[1,1]T，迭代精度机械优化设计25以为起点，沿第二坐标轴方向e2进行一维搜索()11X(1)212minF(X)227e20.5得(1)(1)2122303XX0.5111.5e(1)22F=F(X)7.5机械优化设计26构成新的方向(1)(1)1203121.510.5SXX沿方向一维搜索得极小点和极小值S1(1)3.81.7X(1)()7.9FX，检查迭代终止条件(1)(1)220(3.81)(1.71)2.886XX需进行第二轮迭代计算。机械优化设计27确定第一轮中的最大下降量及其相应方向(1)(1)101F(X)F(X)4(1)(1)212F(X)F(X)0.512max[,]4m反射点及其函数值(1)(1)(1)320315X2XX21.512(1)33F(X)7F检验Powell条件2232(2)()1.25mFFFFF112130.5()32mFF373FF1(1)10F=F(X)3(1)22F=F(X)7.51e可能淘汰哪个方向？机械优化设计28由于满足Powell条件，则淘汰函数值下降量最大的方向e1，下一轮的基本方向组为e2，。1s第二轮迭代的起始点为()(1)3.81.7XX20(2)10F=F(X)7.9•（2）第2轮迭代计算沿e2方向进行一维搜索得(2)13.81.9X(2)1()7.98FX机械优化设计29以为起点沿方向一维搜索得(2)1X1s(2)23.961.9X(2)2()7.996FX构成新的方向(2)(2)2303.963.80.161.941.70.24sXX机械优化设计30确定第二轮中函数值最大下降量及其相应方向10.0820.01612max[,]0.08m沿方向进行一维搜索得2s(2)42X(2)()8FX•检验终止条件(2)(2)220(43.8)(21.7)0.36XX需进行第三轮迭代计算。机械优化设计31•反射点及其函数值(2)(2)(2)3203.963.84.12221.941.72.18XXX(2)3()7.964FX检验Powell条件，淘汰函数值下降量最大的方向e2，下一轮的基本方向组应为，。1s2s机械优化设计32（3）第3轮迭代计算此轮基本方向组为，，起始点为＝，先后沿，方向，进行一维搜索，得1s2s(3)0X(2)X1s2s(3)242X，(3)(3)200XX*42X*()8FX故最优解检验终止条件最优搜索步长为0机械优化设计33搜索方向s取该点的负梯度方向。§4-3梯度法1.梯度方向1()(0,1,2,)kkkkXXaFXk梯度方向是目标函数上升最快的方向，负梯度方向则是最速下降方向；2.基本思想)()()()(kkkgXFS迭代公式*可取最优步长或下降步长kg3.终止判别条件机械优化设计344.迭代过程（1）任选初始点，选定收敛精度；(0)X（2）求处的梯度,并计算梯度的模；()kX（3）判断是否满足迭代终止条件，若满足则输出最优解，否则到下一步；gk()()()()min()()kkkkFXgFXg（4）从出发，沿