无约束优化.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,参考书目：,赵静 但琦 数学建模与数学实验，高等教育出版社，,2005,无约束优化,数学建模,西安电子科技大学数学与统计学院 李伟,引例,标准形式：,无约束优化标准形式,一些相关的概念,:,整体最优解,:,设,f(x),为目标函数,S,为可行域,x*S,若对任意,xS,成立,f(x*)f(x),则称,x*,为极小化问题的最优解,.,局部最优解,:,若存在,x*,的某邻域，使得对该邻域中的每个,x,成立,f(x*)f(x),，则称,x*,为极小化问题的局部最优解。,为,f(x),在点,x,处的,Hesse,矩阵（如果二阶偏导数存在）,梯度,:,称向量,为,f(x),（如果一阶偏导数存在）在点,x,处的梯度,局部极小点的充分条件：设函数,f(x),在点,x*,处二次可微，若梯度,f(x*)=0,，且,Hesse,矩阵正定，则,x*,是局部极小点。,无约束问题,的极值条件,:,一阶必要条件,:,设函数,f(x),在点,x*,处可微,若,x*,是局部极小点,则梯度,f(x*)=0.,二阶必要条件,:,设函数,f(x),在点,x*,处二次可微,若,x*,是局部极小点,则梯度,f(x*)=0,且,Hesse,矩阵半正定。,下降方向,:,设向量,d,是,x*,点的任一方向,若存在,0,对每个实数,(0,),都有,f(x*+,d)f(x*),则称,d,为函数,f(x),在,x*,处的下降方向。,如果,f(x),是可微函数,且,f(x*),T,d0,对每个实数,(0,),都有,x*+,d,S,则称,d,为,x*,点的一个可行方向。,求解无约束最优化问题的基本思想,5,3,1,搜索过程,最优点,(1 1),初始点,(-1 1),-1,1,4.00,-0.79,0.58,3.39,-0.53,0.23,2.60,-0.18,0.00,1.50,0.09,-0.03,0.98,0.37,0.11,0.47,0.59,0.33,0.20,0.80,0.63,0.05,0.95,0.90,0.003,0.99,0.99,1E-4,0.999,0.998,1E-5,0.9997,0.9998,1E-8,最速下降法是一种最基本的算法，它在最优化方法中占有重要地位,.,最速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法,.,1,最速下降法（共轭梯度法）算法步骤：,搜索算法最速下降法,-,-,为了由,x,k,产生,x,k+1,，用二次函数,Q,(,x,),近似,f,(,x,),两边对,x,求导，则,搜索算法牛顿法,Newton,法的基本思想是用一个二次函数去近似目标函数,牛顿法算法步骤：,如果,f,是对称正定矩阵,A,的二次函数，则用牛顿法经过,一次迭代,就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点，,但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收,敛速度还是很快的,.,牛顿法的收敛速度虽然较快，但要求,Hessian,矩阵要可逆,，,要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量,.,则极小点为,：,3,拟牛顿法,Matlab,优化工具箱简介,1.MATLAB,求解优化问题的主要函数,用,Matlab,解无约束优化问题,其中（,3,）、（,4,）、（,5,）的等式右边可选用（,1,）或（,2,）的等式右边。,函数,fminbnd,的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。,常用格式如下：,（,1,）,x=fminbnd(,fun,x,1,x,2,),（,2,）,x=fminbnd(,fun,x,1,x,2,，,options),（,3,）,x,，,fval=fminbnd,（,.,）,（,4,）,x,，,fval,，,exitflag=fminbnd,（,.,）,（,5,）,x,，,fval,，,exitflag,，,output=fminbnd,（,.,）,To Matlab(wliti1),主程序为,wliti1.m:,f=2*exp(-x).*sin(x);,fplot(f,0,8);%,作图语句,xmin,ymin=fminbnd(f,0,8),f1=-2*exp(-x).*sin(x);,xmax,ymax=fminbnd(f1,0,8),命令格式为,:,（,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,（,.,）,2,、多元函数无约束优化问题,标准型为,：,min F(X),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,，最速下降法,例,3,min f(x)=(4x,1,2,+2x,2,2,+4x,1,x,2,+2x,2,+1)*exp(x,1,),To Matlab(wliti3),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,某厂生产一种产品有甲、乙两个牌号，讨论在产销平衡的情况下如何确定各自的产量，使总利润最大,.,所谓产销平衡指工厂的产量等于市场上的销量,.,实例 产销量的最佳安排,基本假设,1,价格与销量成线性关系,基本假设,2,成本与产量成负指数关系,模型建立,若根据大量的统计数据,求出系数,b,1,=100,a,11,=1,a,12,=0.1,b,2,=280,a,21,=0.2,a,22,=2,r,1,=30,1,=0.015,c,1,=20,r,2,=100,2,=0.02,c,2,=30,则问题转化为无约束优化问题：求甲,乙两个牌号的产量,x,1,，,x,2,，使总利润,z,最大,.,为简化模型,先忽略成本,并令,a,12,=0,a,21,=0,问题转化为求,:,z,1,=(b,1,-a,11,x,1,-q,1,)x,1,+(b,2,-a,22,x,2,-q,2,)x,2,的极值,.,显然其解为,x,1,=b,1,/2a,11,=50,x,2,=b,2,/2a,22,=70,我们把它作为原问题的,初始值,.,总利润为：,z,(,x,1,x,2,)=(,p,1,-q,1,),x,1,+(,p,2,-q,2,),x,2,模型求解,1.,建立,M-,文件,fun.m:,function f=fun(x),y,1,=(100-x(1)-0.1*x(2)-(30*exp(-0.015*x(1)+20)*x(1);,y,2,=(280-0.2*x(1)-2*x(2)-(100*exp(-0.02*x(2)+30)*x(2);,f=-y,1,-y,2,;,2.,输入命令,:,x0=50,70;,x=fminunc(,fun,x0),z=fun(x),3.,计算结果,:,x=23.9025,62.4977,z=6.4135e+003,即甲的产量为,23.9025,乙的产量为,62.4977,最大利润为,6413.5.,