0第07-1章无约束 (多维)最优化(精品)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第七章 无约束,(,多维,),最优化,梯度法（最速下降法）,牛顿法与拟牛顿法,变尺度法,(DFP,法,),共轭梯度法,模式搜索法,Powell,法,单纯形加速法,最小二乘法,1,序 无约束最优化问题,解析方法,：利用函数的解析性质,驻点，得到最优解。,数值方法,：利用函数的解析性质构造迭代公式使之收敛到最优解。,2,无约束问题的最优性条件,定理,1,定理,2,梯度为,0,的点称为函数的,驻点。,驻点可能是极小点，也可能是极大点，也可能即不是极大也不是极小，这时称为函数的,鞍点。,定理,2,说明：,UMP,问题的局部最优解必是目标函数的驻点。,注：,（一阶必要条件）,3,定理,3,定理,4,（二阶充分条件）,（若改成,Hesse,矩阵半正定，则成为二阶必要条件）,4,迭代公式：,如何选择下降最快的方向？,7.1,梯度法（最速下降法）,5,一、梯度法（最速下降法）：,二、梯度法算法步骤：,6,最速下降法框图,x,(1),0,k,=1,|,f,(,x,(,k,),),|,或,|,d,(,k,),|0,得,x,(k+1),=,x,(k),+,k,d,(k,),k=k,+1,7,解：,例,8,三、最速下降法的特点,1.,性质.,9,2.,最速下降法的锯齿现象,10,特点,：线性收敛，易产生扭摆现象而造成早停。,（当,x,(k),距最优点较远时，速度快，而接近最优点时，速度下降）,原因,：,f(x)=f(x,(k),)+,f(x,(k,),),T,(x-x,(k,),),+,o|(x-x,(k),)2,|,当,x,(k),接近,x*,，时,f(x,(k),),0，,于是高阶项,o|x-x,(k),|,的影响可能超过,f(x,(k,),),T,(x-x,(k,),),。,如果用,f(x,),的,Taylor,展开近似计算？,牛顿法,11,1.问题,7.2 Newton,法,如果用,f(x,),的,Taylor,展开近似计算？,12,2. 算法思想,13,14,3. 算法步骤,15,算法框图（一维）,给定初始点,x,0,和精度,是,是,停止，输出,x,0,是,否,停止，解题失败,否,停止，输出,x,1,否,16,例,1,：,解,：,取,x,0,=1,计算：,迭代过程如下表：,1.137,0.1163,0.1169,2,-0.001061,3,1.3258,-0.5178,-0.5708,1,0.5000,0.7854,1,0,17,（,ii,）,编写,M,文件,nwfun.m,如下：,function f,df,d2f=,nwfun(x,);,f=x(1)4+25*x(2)4+x(1)2*x(2)2;,df(1)=4*x(1)3+2*x(1)*x(2)2;,df(2)=100*x(2)3+2*x(1)2*x(2);,d2f(1,1)=12*x(1)2+2*x(2)2;,d2f(1,2)=4*x(1)*x(2);,d2f(2,1)=d2f(1,2);,d2f(2,2)=300*x(2)2+4*x(1)*x(2);,编写,M,文件,nwfun2.m,：,clc,x=2;2;,f0,g1,g2=,nwfun(x,),while,norm(g1)0.00001,i=1:3,p=-inv(g2)*g1,p=,p/norm(p,),t=1.0,f=,detaf(x+t,*p),while,ff0,t=t/2,f=,detaf(x+t,*p),%,步长减半,end,x=,x+t,*p,f0,g1,g2=,nwfun(x,),end,18,收敛速度快，为二阶收敛。,(2),初始点的选取困难，甚至无法实施。,4. 算法特点,存在缺点及修正,初始点要选在最优点附近。,19,阻尼,Newton,法,20,7.3,拟牛顿法,(,变尺度法,),一、拟牛顿法的思想,21,22,23,分析：,。,k,k,k,k,k,x,x,g,g,H,-,=,-,+,+,+,1,1,1,),(,24,Step,4.,判断 是否满足终止准则：,yes:,计算,stop,No :,转,step 5 。,;,),(,.,2,k,k,k,x,f,H,d,Step,-,=,计算搜索方向,拟,Newton,条件或拟,Newton,方程,:,25,Step,4.,判断 是否满足终止准则：,yes:,计算,stop,No :,转,step 5 。,26,7.4 DFP,算法,一、,DFP,法的提出,27,28,29,三、,DFP,算法的步骤,改为,:,30,四、变尺度法算法框图：,x,(1),H,(1),对称,0,k,=1,d,(k),=-H,(k), f(x,(k),),一维搜索得,k,x,(k+1),=x,(k),+ ,k,d,(k),|,x,(k+1),-x,(k),| ,?,修正,H,(k),产生,H,(k+,1),Stop.,x,(k+1),-,解,k=k,+1,y,N,31,例,解,32,33,4.6.3,34,35,六、变尺度法的主要特点,只需用到函数的一阶梯度；（,Newton,法用到二阶,Hesse,阵）,下降算法，故全局收敛；,不需求矩阵逆；（计算量小）,一般可达到超线性收敛；（速度快）,有二次终结性。,36,一、共轭方向和共轭方向法,共轭是正交的推广。,1,定义,7.5,共轭梯度法,37,2,共轭方向,设直线,AB,和,CD,过椭圆中心，且,CD,平行于椭圆在点,A,，,B,的切线，则称,AB,与,CD,为,共轭直径,，,与,的方向为,共轭方向,，（或,A,B,的切线方向与,称为,共轭方向）见图,1,。,-,AB,-,CD,-,AB,的方向,A,B,C,D,图,1,38,定理,1,39,3.,几何意义,40,41,42,4.,共轭方向法,43,5.,共轭梯度法,如何选取一组共轭方向？,以下分析算法的具体步骤：,基本思想,对于,44,45,46,47,48,49,FR,算法特点：,1、全局收敛（下降算法）；线性收敛；,2、每步迭代只需存储若干向量（适用于大规模问题）；,3、有二次终结性（对于正定二次函数，至多,n,次迭代可达,opt.）,50,例,解：,51,52,53,6.,用于一般函数的共轭梯度法,54,对不同的,i,公式，对于正定二次函数是相等的，对非正定二次函数，有不同的效果，经验上,PRP,效果较好。,55,2.,牛顿法,3.,拟牛顿法,(,变尺度法,),1,、梯度法（最速下降法）：,多变量无约束优化搜索方法,56,3.,拟牛顿法,(,变尺度法,),4.,特殊拟牛顿法,1DFP,算法：,5.,特殊拟牛顿法,2BFGS,算法：,多变量无约束优化搜索方法,;,),(,:,k,k,k,x,f,H,d,-,=,搜索方向,57,6.,共轭梯度法,1,7.,共轭梯度法,2,多变量无约束优化搜索方法,58,各种方法比较,59,bandem,%,香蕉最优化展示,expo-style banana optimization,60,命令格式为,:,（,1,）,x=,fminunc,（,fun,X,0,）；或,x=,fminsearch,（,fun,X,0,）,（,2,）,x=,fminunc,（,fun,X,0,，,options,）；,或,x=,fminsearch,（,fun,X,0,，,options,）,（,3,）,x,，,fval,=,fminunc,（,.,）；,或,x,，,fval,=,fminsearch,（,.,）,（,4,）,x,，,fval,，,exitflag,=,fminunc,（,.,）；,或,x,，,fval,，,exitflag,=,fminsearch,（,5,）,x,，,fval,，,exitflag,，,output=,fminunc,（,.,）；,或,x,，,fval,，,exitflag,，,output=,fminsearch,（,.,）,多元函数无约束优化问题,标准型为,：,min F(X),61,3,fminunc,为中型优化算法的步长一维搜索提供了两种算法，,由,options,中参数,LineSearchType,控制：,LineSearchType,=,quadcubic,(,缺省值,),，混合的二次和三,次多项式插值；,LineSearchType,=,cubicpoly,，,三次多项式插,使用,fminunc,和,fminsearch,可能会得到局部最优解,.,说明,:,fminsearch,是用单纯形法寻优,.,fminunc,的算法见以下几点说明：,1,fminunc,为无约束优化提供了大型优化和中型优化算法。由,options,中的参数,LargeScale,控制：,LargeScale,=on(,默认值,),使用大型算法,LargeScale,=off(,默认值,),使用中型算法,2,fminunc,为中型优化算法的搜索方向提供了,4,种算法，由,options,中的参数,HessUpdate,控制：,HessUpdate,=,bfgs,（,默认值），拟牛顿法的,BFGS,公式；,HessUpdate,=,dfp,，,拟牛顿法的,DFP,公式；,HessUpdate,=,steepdesc,，,最速下降法,62,例,1,min f(x)=(4x,1,2,+2x,2,2,+4x,1,x,2,+2x,2,+1)*exp(x,1,),1,、编写,M-,文件,fun1.m:,function f = fun1 (x),f = exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);,2,、,输入,M,文件,wliti3.m,如下,:,x,0,= -1, 1;,x=fminunc(fun1,x,0,);,y=fun1(x),3,、运行结果,:,x= 0.5000 -1.0000,y = 1.3029e-10,63,64,3.,用,fminsearch,函数求解,输入命令,:,f=100*(x(2)-x(1)2)2+(1-x(1)2;,x,fval,exitflag,output,=,fminsearch(f, -1.2 2),运行结果,:,x =1.0000 1.0000,fval,=1.9151e-010,exitflag,= 1,output =,iterations: 108,funcCount,: 202,algorithm: ,Nelder,-Mead simplex direct search,65,