第5讲无约束优化

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,无约束最优化,数学建模与数学实验,1,实验目的,实验内容,2、掌握用数学软件包求解无约束最优化问题。,1、了解无约束最优化基本算法。,1、无约束优化基本思想及基本算法,。,4,、实验作业。,3,、用MATLAB求解无约束优化问题。,2、MATLAB优化工具箱简介,2,无约束最优化问题,求解无约束最优化问题的的基本思想,*,无约束最优化问题的基本算法,返回,3,标准形式：,求解无约束最优化问题的基本思想,求解的基本思想,( 以二元函数为例 ),5,3,1,连续可微,4,5,多局部极小,唯一极小,(全局极小),6,搜索过程,最优点 (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,返回,7,无约束优化问题的基本算法,最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法.,1最速下降法（共轭梯度法）算法步骤：,8,2牛顿法算法步骤：,如果f是对称正定矩阵A的二次函数，则用牛顿法经过,一次迭代,就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点，,但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收,敛速度还是很快的.,牛顿法的收敛速度虽然较快，但要求Hessian矩阵要可逆,，,要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量.,9,3拟牛顿法,10,11,返回,12,Matlab优化工具箱简介,1.MATLAB求解优化问题的主要函数,13,2. 优化函数的输入变量,使用优化函数或优化工具箱中其它优化函数时, 输入变量见下表:,14,3. 优化函数的输出变量下表:,15,4控制参数options的设置,(3),MaxIter,: 允许进行迭代的最大次数,取值为正整数.,Options中常用的几个参数的名称、含义、取值如下:,(1),Display,: 显示水平.取值为off时,不显示输出; 取值为iter时,显示每次迭代的信息;取值为final时,显示最终结果.默认值为final.,(2),MaxFunEvals,: 允许进行函数评价的最大次数,取值为正整数.,16,例：opts=optimset(Display,iter,TolFun,1e-8),该语句创建一个称为opts的优化选项结构,其中显示参数设为iter, TolFun参数设为1e-8.,控制参数options可以通过函数optimset创建或修改。命令的格式如下：,(1),options=optimset(optimfun),创建一个含有所有参数名,并与优化函数optimfun相关的默认值的选项结构options.,（2）,options=optimset(param1,value1,param2,value2,.),创建一个名称为options的优化选项参数,其中指定的参数具有指定值,所有未指定的参数取默认值.,(3),options=optimset(oldops,param1,value1,param2,value2,.),创建名称为oldops的参数的拷贝,用指定的参数值修改oldops中相应的参数.,返回,17,用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（.）,18,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),19,例2,对边长为3米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？,解,先编写M文件fun0.m如下:,function f=fun0(x),f=-(3-2*x).2*x;,主程序为wliti2.m:,x,fval=fminbnd(fun0,0,1.5);,xmax=x,fmax=-fval,运算结果为:,xmax = 0.5000,fmax =2.0000.即剪掉的正方形的边长为0.5米时水槽的容积最大,最大容积为2立方米.,To Matlab(wliti2),20,命令格式为:,（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),21,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，最速下降法,22,例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,23,To Matlab (wliti31),To Matlab (wliti32),24,3.用fminsearch函数求解,To Matlab(wliti41),输入命令:,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,25,4.,用fminunc 函数,To Matlab(wliti44),(1)建立M-文件fun2.m,function,f=fun2(x),f=100*(x(2)-x(1)2)2+(1-x(1)2,(2)主程序wliti44.m,26,Rosenbrock函数不同算法的计算结果,可以看出，最速下降法的结果最差.因为最速下降法特别不适合于从一狭长通道到达最优解的情况.,27,例5,产销量的最佳安排,某厂生产一种产品有甲、乙两个牌号，讨论在产销平衡的情况下如何确定各自的产量，使总利润最大. 所谓产销平衡指工厂的产量等于市场上的销量.,28,基本假设,1价格与销量成线性关系,2成本与产量成负指数关系,29,模型建立,若根据大量的统计数据,求出系数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,) x,1,+ ( b,2,- a,22,x,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,30,模型求解,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.,To Matlab(wliti5),返回,31,实验作业,32,33,34,35,36,