MATLAB 第五节(优化工具箱).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五节 优化工具箱,郑州大学材料物理教育部重点实验室,授课教师,:,左秀荣,最优化方法，顾名思义，就是从所有可能方案中选择最合理的一种以达到最优目标的方法。最优化理论和方法是近几十年来随着电子计算机的普遍应用而发展起来的。由于其宗旨是追求最优目标，因此它具有广泛的应用性。目前，最优化在物质调运，自动控制，机械设计，采矿冶金，经济管理和系统工程等方面都已得到卓有成效的应用。,最优化的定义,所谓的最优化，就是求最小值的问题。作为最优化问题，至少要有两个要素：第一个就是可能的方案；第二个是追所求的最优目标。后者是前者的,函数,。如果第一个要素与时间无关的话，那么称为静态最优化问题；否则称为动态最优化问题。,最优化问题的一般形式,最优化问题的一般形式是：,min,f(x,),其中,x=x,1,，,x,2,，,，,x,n,T,s.t,.s(x)0,h(x,)=0,其中,s(x,)=s,1,，,s,2,，,，,s,n,(x)T,h(x,)=h,1,，,h,2,，,，,h,l,(x)T,这就是最优化问题的一般形式。,f(x,),称为目标函数，,s(x)0,称为不等式约束，,h(x,)=0,称为等式约束，,x,称为集约束，,满足所有约束的向量称为容许解或容许点，容许点的 集合称为容许集。,问题的求解是指在容许集中找一点,x*,，使得目标函数在该点取极小值，这样的点称为问题的最优点，也称为最小点，而相应的目标函数值,f(x,*),称为最优值，,(x*,f(x,*),称为最优解，习惯上,x*,称为最优解。,最优化问题常用的概念,根据有无约束条件，问题首先可以分为两大类：,如果对变量无任何约束条件，即研究,则称为无约束规划问题；,如果对变量,x,有一定的约束要求，即研究形如上式的问题，则称为有约束规划问题。,最优化问题分类,最优化就是在一切可能的方案中寻求最优的方案,最优化技术广泛应用于科学技术的各个领域以及科学管理与决策,.,尤其是在研究对象的复杂度与精确度越来越高的今天,最优化技术更是必不可少。,最基础的，在生产上经常会遇到不同尺寸的产品所用原料不同，带来的经济效益不同，那么就产生了一个如何安排下料方案，从而使原料的利用率最大，而且带的经济效益最大，这就需要最优化的设计。,最优化技术的发展能给企业带来的巨大的经济效益，在工业过程中的作用也越来越大，越来越明显，因此最优化技术又被称为“不用投资技术的改造”。,最优化算法的作用及意义,最优化工具箱介绍,MATLAB,工具箱可以解决许多优化问题。,无约束非线性最小化,Unconstrained nonlinear minimization,；,有约束非线性最小化（,including goal attainment problems,minimax,problems,and semi-infinite minimization problems,）,二次和线性规划（,Quadratic and linear programming,）,非线性最小二乘和曲线拟合（,Nonlinear least squares and curve-fitting,）,方程解的非线性系统（,Nonlinear system of equation solving,）,有约束的线性最小二乘（,Constrained linear least squares,）,稀疏和结构大规模问题,（,Sparse and structured large-scale problem,）,所用函数,x,向量；,f(x,),返回值为标量的函数；,fminunc,寻找无约束多变量函数,f(x,),最小值,.,无约束最小化的示例,x=fminunc(fun,x0),初始点为,x0,，寻找,fun,所定义的函数的局部最小。,x=fminunc(fun,x0,options),初始点为,x0,，寻找,fun,所定义的函数的局部最小，优化选项包含在结构,options,中。,x,fval=fminunc(.),x,为最小点，,fval,为最优值。,x,fval,exitflag=fminunc(.),exitflag,标识算法终止的原因。,x,fval,exitflag,output=fminunc(.),结构,output,中包含优化信息。,x,fval,exitflag,output,grad=fminunc(.),在,grad,中包含函数,fun,在,x,处的梯度值。,x,fval,exitflag,output,grad,hessian,=,fminunc,(.),hessian,中返回函数,fun,在,x,处的,Hessian,矩阵值。,exitflag,算法终止原因,1,梯度小于指定值,2,x,的变化,小于指定值,3,目标函数的变化,小于指定值,0,迭代数超过,options.MaxIter,或函数的计算数超过,options.FunEvals,-1,算法被输出函数终止,-2,直线搜索沿着目前的搜索方向不能找到可以接受的点,output,包含优化信息的结构,iterations,迭代数,funcCount,函数计算数,lgorithm,使用的算法,cgiterations,PCG,迭代数,(large-scale algorithm only),stepsize,最终步长,(medium-scale algorithm only),问题,Matlab,工具箱求解过程,步骤,1:,写一个目标函数的,M,文件,objfun.m,function f=,objfun(x,),f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);,步骤,2:,调用一个无约束优化程序,x0=-1,1;,%,起始点,options=,optimset(LargeScale,off,);,x,fval,exitflag,output,=fminunc(objfun,x0,options),注：可把步骤二的内容建立一个,M,文件,Unconstr.m,，在命令行运行,Unconstr,即得到以下运行结果。,运行结果,Matlab,命令窗口显示如下运行结果。,Optimization terminated:relative infinity-norm of gradient less than,options.TolFun,.,x=,0.5000 -1.0000,fval=,1.0983e-015,exitflag=,1,output=,iterations:8,funcCount,:66,stepsize,:1,firstorderopt,:7.3704e-008,algorithm:medium-scale:Quasi-Newton line search,message:1x85 char,结果分析,66,次函数计算后，找到最终答案。,x=,0.5000 -1.0000,在终点,x,处函数值为,fval,：,fval,=,1.0983e-015,exitflag,是算法是否收敛的标识,.,exitflag,0,意味着找到局部极小。,exitflag,=,1,输出结构给出更多关于优化的信息。对于,fminunc,，包括,iterations,中的迭代数，,funcCount,中的函数计算次数，,stepsize,中的最终步长，,firstorderopt,中的一阶最优性的测量。,Algorithm,中的算法的类型。,当多于一种局部最小存在，初始点,x1,，,x2,的设置影响函 数评价的次数和最终点的值。在前面的例子中，,x0,被初始化为,-1,，,1,。,变量,options,可被传递到,fminunc,改变优化算法的特性，,x=fminunc(objfun,x0,options),；,option,是一种包含终止误差和算法选择的结构。,Options,可以使用,optimset,函数创建。,options=,optimset(LargeScale,off,),；,这个例子中，已关闭了,large-scale,算法缺省选项，而使用,medium-scale,算法。其他选项包括控制优化迭代过程命令行显示的数量，终止准则的公差，使用使用者提供的梯度还是雅可比矩阵，迭代或函数计算的最大数。,非线性不等式约束,所用函数：,式中：,x,，,b,，,beq,，,lb,，,ub,向量；,A,，,Aeq,矩阵；,c(x,),，,ceq(x,),返回向量的函数；,f(x,),返回标量的函数；,f(x,),，,c(x,),，,ceq(x,),可以是非线性函数。,x=fmincon(fun,x0,A,b),x0,为起始点,，,寻找函数,fun,的最小值，约束条件为线性不等式约束,A*xb,。,x0,可以是标量、向量或矩阵。,x=fmincon(fun,x0,A,b,Aeq,beq),寻找函数,fun,的最小值，约束条件为线性等式约束,Aeq*x=beq,以及线性不等式约束,A*x b,。如果无线性不等式约束设置,A=,、,b=,。,x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub),定义了变量,x,的上下界,，,使最优解,x,为,lb x ub,。如果等式约束不存在，设置,Aeq,=,、,beq,=,如果,x(i,),无下界，设置,lb(i,)=-,Inf,；如果,x(i,),无上界，设置,ub(i,)=,Inf,。,x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon),nonlcon,中定义了,非线性不等式,c(x),或等式,ceq(x),约束。优化结果使,c(x,)0,、,ceq(x,)=0,。如果变量,x,无上下界，设置,lb=,、,ub=,。,x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options),优化选项在结构,options,中定义。使用,optimset,函数定义,options.,如果没有非线性不等式和等式约束，设置,nonlcon,=,。,x,fval,=,fmincon,(.),返回最优解（,x,，,fval,）。,x,fval,exitflag,=,fmincon,(.),返回描述,fmincon,结束的原因的标识符,exitflag,。,x,fval,exitflag,output,=,fmincon,(.),结构,output,中包含优化信息。,x,fval,exitflag,output,lambda=fmincon(.),返回最优解,x,的拉格朗日乘子,，,存储在结构,lambda,中。,x,fval,exitflag,output,lambda,grad=fmincon(.),在,grad,中包含函数,fun,在,x,处的梯度值。,x,fval,exitflag,output,lambda,grad,hessian,=,fmincon,(.),在,hessian,中包含函数,fun,在,x,处的,Hessian,矩阵值。,exitflag,算法终止原因,1,First order optimality conditions were satisfied to the specified tolerance,2,x,的变化,小于指定值,3,目标函数的变化,小于指定值,4,搜索方向的绝对值小于特定的容许值,并且约束偏差小于,options.TolCon,5,方向导数的绝对值小于特定的容许值,并且约束偏差小于,options.TolCon,0,迭代数超过,options.MaxIter,或函数的计算数超过,options.FunEvals,-1,算法被输出函数终止,-2,找不到可行点,lambda,在最优点,x,处的拉格朗日乘子,lower,下界,lb,upper,上界,ub,ineqlin,线性不等式,eqlin,线性等式,ineqnonlin,非线性不等式,Nonlinear equalities,非线性等式,output,包含优化信息的结构,iterations,迭代数,funcCount,函数计算数,lgorithm,使用的算法,cgiterations,PCG,迭代数,(large-scale algorithm only),stepsize,最终步长,(medium-scale algorithm only),firstorderopt,一阶最优性的测量,问题,约束条件：,Matlab,工具箱求解过程,不能在命令行把非线性的约束传给,fmincon,。但可创建一个,M-file,，,confun.m,，这个文件返回当前,x,的两个约束条件的变量,c,。接着调用带约束的优化函数,fmincon,。由于,fmincon,要求约束条件被写成,的形式，因此必须重写以下形式的约束。,步骤,1,：写一个约束条件的,confun.m,文件。,function c,ceq,=,confun(x,),c=1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;,%,非线性不等式约束,ceq,=;,%,非线性等式约束,步骤,2,：写一个目标函数的,M,文件,objfun.m,function f=,objfun(x,),f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);,步骤,3,：调用带约束的优化程序。,x0=-1,1;,%,起始点,options=,optimset(LargeScale,off,),；,x,fval,exitflag,output,=fmincon(objfun,x0,confun,options),运行结果,x=,-9.5474 1.0474,fval,=,0.0236,exitflag,=,1,output=,iterations:8,funcCount,:36,stepsize,:1,algorithm:medium-scale:SQP,Quasi-Newton,line-search,firstorderopt,:8.5125e-007,cgiterations,:,message:1x144 char,运行结果分析,36,次函数调用后，最优解为,x=,-9.5474 1.0474,fval,=,0.0236,也可计算最优解处的约束。,c,ceq,=,confun(x,),返回,c=,1.0e-14*,0.1110,-0.1776,ceq,=,可注意到约束值小于等于,0,，即,x,满足。,最优化函数,fminbnd,fminsearch,fminunc,fmincon,fgoalattain,fminimax,lsqcurvefit,和,lsqnonlin,都执行目标函数,f(x,),的,最小化,。,最大化,通过执行目标函数,f(x,),获得。,最优化工具箱均假设非线性不等式约束具有,的形式。,相等于约束,。,相等于约束,。,带边界的约束,问题,约束条件：,Matlab,工具箱求解过程,通过对约束优化函数定义简单的边界约束，变量,x,可以被限制在某一范围。对于函数,fmincon,，命令,x=fmincon(objfun,x0,lb,ub,confun,options);,限制,x,为,lb x,ub,。,步骤,1,：写一个约束条件的,confun.m,文件。,function c,ceq=confun(x),c=1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;,%,非线性不等式约束,ceq,=;,%,非线性等式约束,步骤,2,：写一个目标函数的,M,文件,objfun.m,function f=,objfun(x,),f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);,步骤,3,：调用带约束的优化程序,为使方程中,x,大于,0,，使用如下命令。,x0=-1,1;,%,估计问题的起始点,lb=0,0;,%,设置下界,ub,=;,%,无上界,options=,optimset(LargeScale,off,Display,iter,);,x,fval,exitflag,output,=fmincon(objfun,x0,lb,ub,confun,options),c,ceq,=,confun(x,),注意：为了向,fmincon,传递下界作为第七个变量，必须定义第三个到第六个变量的值。本例中因为没有线性不等式或线性等式约束，定义这些变量为空。,运行结果,x=,0 1.5000,fval,=,8.5000,exitflag,=,1,output=,iterations:3,funcCount,:15,stepsize,:1,algorithm:medium-scale:SQP,Quasi-Newton,line-search,firstorderopt,:1.6307e-012,cgiterations,:,message:1x144 char,c=,0,-10,ceq,=,运行结果分析,当,lb,或,ub,比,x,包含的元素少，仅仅,x,中对应的元素被约束。如果仅仅变量的一部分被约束，在,lb,中使用,-,inf,作为无约束的下边界向量，在,ub,中使用,inf,作为无约束的上变量。例如：,lb=-,inf,0,；,ub,=10,inf,；,边界,x110,、,x20,，,x1,没有下界和,x2,没有上界。使用,inf,和,-,inf,比使用很大的正数或很大的负数作为缺少的边界，得到更好的数值结果。,注意,:,进一步限制了搜索空间后，寻找最终解的函数计算次数减少,(663615),。当问题有较多的约束和边界限制时，通常有较少的函数计算。因为最优化关于步长和可行性区域，约束问题比无约束问题有更好的判断。因此，尽可能约束和限制问题较好，这可促进快速收敛。,为了显示每次迭代的输出，键入,options=,optimset(Display,iter,);,此命令设置,Display option,的值为,iter,。,这个命令的设置使工具箱每次迭代都显示结果。也可以关闭任何输出结果,(display,设为,off),仅仅在最后显示输出结果,(display,设为,final),，或在问题不收敛时显示,(display,设为,notify),。,当选项,Display,设为,iter,，运行结果呈以下形式。,max Directional First-order,Iter,F-count,f(x,)constraint Step-size derivative optimality Procedure,带梯度的约束,问题,约束条件：,Matlab,工具箱求解过程,步骤,1,：写一个目标函数和其梯度的,M,文件,objfungrad.m,文件。,function,f,G,=,objfungrad(x,),f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);,t=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);,%,目标函数的梯度,G=t+exp(x(1)*(8*x(1)+4*x(2),exp(x(1)*(4*x(1)+4*x(2)+2);,步骤,2,：写一个非线性约束和非线性约束梯度的,M,文件。,function c,ceq,DC,DCeq=confungrad(x),c(1)=1.5+x(1)*x(2)-x(1)-x(2);,%,不等式约束,c(2)=-x(1)*x(2)-10;,DC=x(2)-1,-x(2);x(1)-1,-x(1);,%,约束的梯度,ceq,=;,%,非线性等式约束,DCeq,=;,步骤,3,：调用带约束的优化程序。,x0=-1,1;%,初始点估计值,options=,optimset(LargeScale,off,);,options=,optimset(options,DerivativeCheck,on,);,options=,optimset(options,GradObj,on,GradConstr,on,Display,iter,);,lb=;,ub,=;%x,没有上下界,x,fval,=fmincon(objfungrad,x0,lb,ub,confungrad,options,),c,ceq,=,confungrad(x,)%,检查,x,点的约束值,运行结果,x=,-9.5474 1.0474,fval=,0.0236,c=,1.0e-007*,-0.9032,0.9032,ceq=,运行结果分析,G,包含目标函数,f,的偏导数，由函数,objfungrad(x,),返回。,DC,的包含每一个约束的偏导数。,DC,为：,M,文件,objfungrad.m,包含目标函数的梯度,，,confungrad.m,包含约束的梯度，应把这些信息传递给函数,fmincon,。,使用,optimset,把选项,GradObj,和,GradConstr,设为,on,，,否则,fmincon,不使用这些解析梯度。,options=,optimset(options,GradObj,on,GradConstr,on,);,可比较解析梯度和有限差分计算的梯度。这对检查目标函数或梯度函数公式的错误特别有用。采用下述命令设置,DerivativeCheck,选项为,on,：,options=,optimset(options,DerivativeCheck,on,);,首先检查目标函数和非线性约束的梯度。如在给定的允许范围之内，不能与有限差分梯度相比。给出警告信息显示差值并给出停止或继续优化的选项。,非线性等式约束必须与非线性不等式约束同时在,M,文件中计算。,问题,约束条件：,等 式 约 束,Matlab,工具箱求解过程,约束条件改写为：,约束条件,：,步骤,1,：写,M,文件,objfun.m,function f=,objfun(x,),f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);,步骤,2,：写非线性约束的,M,文件,constraints,function c,ceq,=,confuneq(x,),c=-x(1)*x(2)-10;,%,非线性不等式约束,ceq,=x(1)2+x(2)-1;,%,非线性等式约束,步骤,3,：调用约束优化程序,x0=-1,1;,%,估计初始点,options=,optimset(LargeScale,off,Display,iter,);,x,fval,=fmincon(objfun,x0,confuneq,options,),c,ceq,=,confuneq(x,),%,检查,x,点的约束值,x=,-0.7529 0.4332,fval,=,1.5093,c=,-9.6739,ceq,=,6.3038e-009,运行结果分析,在约束的缺省误差,1.0e-006,范围内为,0,，,c,小于等于,0,。,以嵌套函数和匿名函数的形式给函数传递参数,问题,求,x,3,+,bx,+c,函数的零点。,采用嵌套函数的形式调用优化函数,function y=,findzero(b,c,x0),options=,optimset(Display,off);,%,关闭,Display,y=fsolve(poly,x0,options);,function y=,poly(x,),%,计算多项式,y=x3+b*x+c;,end,end,对于任意系数,b,和,c,，均可调用函数,findzero,。上述多项式,b=2,、,c=3.5,、,x0=0,，求多项式的零点。调用函数,x=findzero(2,3.5,0),运行结果为：,x=,-1.0945,