Matlab求解线性和非线性,凸函数(精品)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,线性规划,第,8,章 最优化方法,无约束规划,非线性规划,实验目的,实验内容,2,、掌握用数学软件包求解线性规划问题。,1,、了解线性规划的基本内容。,3,、,实验作业。,2,、用数学软件包求解线性规划问题。,1,、两个引例。,问题一 ：,任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为,800,和,900,，三种工件的数量分别为,400,、,600,和,500,，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,两个引例,解,设在甲车床上加工工件,1,、,2,、,3,的数量分别为,x,1,、,x,2,、,x,3,，在乙车床上加工工件,1,、,2,、,3,的数量分别为,x,4,、,x,5,、,x,6,。可建立以下线性规划模型：,解答,问题二：,某厂生产甲、乙两种产品，已知制成一吨产品甲需用资源,A 3,吨资源,B 4m,3,；制成一吨产品乙需用资源,A 2,吨，资源,B 6m,3,，资源,C 7,个单位。若一吨产品甲和乙的经济价值分别为,7,万元和,5,万元，三种资源的限制量分别为,90,吨、,200m,3,和,210,个单位。试应生产这两种产品各多少吨才能使创造的总经济价值最高？（,p153,，例,8-2,）,解：,这是个最优化问题，其,目标,为经济价值最高，,约束条件,为三种资源的数量有限，,决策,为生产甲、乙产品的数量。令生产产品甲的数量为,x,1,，生产产品乙的数量为,x,2,。由题意可以建立如下的线性规划模型。,故目标函数为：,约束条件为：,问题,2,线性规划模型：,解答,返 回,1.,线性规划的标准形式：,用单纯法求解时，常将标准形式化为：,2.,线性规划的基本算法,单纯形法,线性规划的基本算法,单纯形法,引入松弛变量,x,3, x,4, x,5,将不等式化为等式, 即单纯形标准形:,用,MATLAB,优化工具箱解线性规划,min,z=cX,1,、模型：,命令：,x=linprog,（,c,，,A,，,b,）,2,、模型,：,min,z=cX,命令：,x=linprog,（,c,，,A,，,b,，,Aeq,beq,）,注意：若没有不等式： 存在，则令,A= ,，,b= .,3,、模型,：,min,z=cX,VLBXVUB,命令：,1,x=linprog,（,c,，,A,，,b,，,Aeq,beq, VLB,，,VUB,）,2,x=linprog,（,c,，,A,，,b,，,Aeq,beq, VLB,，,VUB, X,0,）,注意：,1,若没有等式约束,: ,则令,Aeq= , beq= .,2,其中,X,0,表示初始点,4,、命令：,x,fval=linprog(),返回最优解及处的目标函数值,fval.,解 编写,M,文件如下：,c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6;,A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08;,b=850;700;100;900;,Aeq=; beq=;,vlb=0;0;0;0;0;0; vub=;,x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),解,:,编写,M,文件如下：,c=-7 -5;,A=3 2; 4 6; 0 7;,b=90;200;210;,Aeq=;,beq=;,vlb=0,0;,vub=inf,inf;,x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),问题,2,解答,S.t.,改写为：,例,3,问题一的解答,问题,编写,M,文件如下,:,f = 13 9 10 11 12 8;,A = 0.4 1.1 1 0 0 0,0 0 0 0.5 1.2 1.3;,b = 800; 900;,Aeq=1 0 0 1 0 0,0 1 0 0 1 0,0 0 1 0 0 1;,beq=400 600 500;,vlb = zeros(6,1);,vub=;,x,fval = linprog(f,A,b,Aeq,beq,vlb,vub),结果,:,x =,0.0000,600.0000,0.0000,400.0000,0.0000,500.0000,fval =1.3800e+004,即在甲机床上加工,600,个工件,2,在乙机床上加工,400,个工件,1,、,500,个工件,3,，可在满足条件的情况下使总加工费最小为,13800,。,结果为：,x =,14.0000,24.0000,fval =,-218.0000,注：,有些实际问题可能会有一个,约束条件,：决策变量只能取整数，如,x,1,、,x,2,取整数。这类问题实际上是,整数线性规划,问题。如果把它当成一个线性规划来解，求得其最优解刚好是整数时，故它就是该整数规划的最优解。若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解（如割平面法、分支定界法）。,实验作业,某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料,6,千克,工人,10,名,可获利,10,万元,;,每百箱乙饮料需用原料,5,千克,工人,20,名,可获利,9,万元,.,今工厂共有原料,60,千克,工人,150,名,又由于其他条件所限甲饮料产量不超过,8,百箱,.,问如何安排生产计划,即两种饮料各生产多少使获利最大,.,进一步讨论,:,1),若投资,0.8,万元可增加原料,1,千克,问应否作这项投资,.,2),若每百箱甲饮料获利可增加,1,万元,问应否改变生产计划,.,返 回,无约束最优化,数学实验,电子科技大学应用数学学院,实验目的,实验内容,2,、掌握用数学软件包求解无约束最优化问题。,1,、了解无约束最优化基本算法。,1,、无约束优化基本思想及基本算法,。,4,、实验作业。,3,、用,MATLAB,求解无约束优化问题。,2,、,MATLAB,优化工具箱简介,无约束最优化问题,求解无约束最优化问题的的基本思想,*,无约束最优化问题的基本算法,返回,标准形式：,求解无约束最优化问题的基本思想,求解的基本思想,(,以二元函数为例,),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,最速下降法（共轭梯度法）算法步骤：,2,牛顿法算法步骤：,如果,f,是对称正定矩阵,A,的二次函数，则用牛顿法经过,一次迭代,就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点，,但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收,敛速度还是很快的,.,牛顿法的收敛速度虽然较快，但要求,Hessian,矩阵要可逆,，,要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量,.,3,拟牛顿法,返回,Matlab,优化工具箱简介,1.MATLAB,求解优化问题的主要函数,2.,优化函数的输入变量,使用优化函数或优化工具箱中其它优化函数时,输入变量见下表,:,3.,优化函数的输出变量下表,:,4,控制参数,options,的设置,(3),MaxIter,:,允许进行迭代的最大次数,取值为正整数,.,Options,中常用的几个参数的名称、含义、取值如下,:,(1),Display,:,显示水平,.,取值为,off,时,不显示输出,;,取值为,iter,时,显示每次迭代的信息,;,取值为,final,时,显示最终结果,.,默认值为,final,.,(2),MaxFunEvals,:,允许进行函数评价的最大次数,取值为正整数,.,例：,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,中相应的参数,.,返回,用,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,（,.,）,主程序为,:,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),例,2,对边长为,3,米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？,p156,，例,8-1,解,先编写,M,文件,fminbndtest.m,如下,:,function f=myfun(x),f=,-,(3-2*x).2*x;,主程序调用,fminbnd:,x,fval=fminbnd(,fminbndtest,0,1.5);,xmax=x,fmax=-fval,运算结果为,:,xmax = 0.5000,fmax =2.0000.,即剪掉的正方形的边长为,0.5,米时水槽的容积最大,最大容积为,2,立方米,.,命令格式为,:,（,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,),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,文件,myprg3.m,如下,:,x,0,= -1, 1;,x=fminunc(,fun1,x,0,);,y=fun1(x),3,、运行结果,:,x= 0.5000 -1.0000,y = 1.3029e-10,2.,画出,Rosenbrock,函数的等高线图,输入命令：,contour(x,y,z,20),hold on,plot(-1.2,2, o );,text(-1.2,2,start point),plot(1,1,o),text(1,1,solution),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,4.,用,fminunc,函数,(1),建立,M-,文件,fun1.m,function,f=fun1(x),f=100*(x(2)-x(1)2)2+(1-x(1)2,(2),求解主程序,oldoptions=optimset(fminunc),options=optimset(oldoptions,LargeScale,off),options11=optimset(options,HessUpdate,dfp),x11,fval11,exitflag11,output11=fminunc(,fun1, -1.2 2,options11),Rosenbrock,函数不同算法的计算结果,可以看出，最速下降法的结果最差,.,因为最速下降法特别不适合于从一狭长通道到达最优解的情况,.,实验作业,数学实验,非线性规划,电子科技大学应用数学学院,实验目的,实验内容,2,、掌握用数学软件求解优化问题。,1,、直观了解非线性规划的基本内容。,1,、非线性规划的基本理论。,3,、实验作业。,2,、用数学软件求解非线性规划。,非线性规划的基本概念,非线性规划,定义,如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做,非线性规划问题,非现性规划的基本概念,一般形式,:,（,1,）,其中 ， 是定义在,E,n,上的实值函数，简记,:,其它情况,:,求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式,定义,1,把满足问题（,1,）中条件的解 称为,可行解,（或可行,点,），,所有可行点的集合称为,可行集,（或,可行域,）,记为,D,即,问题,(1),可简记为 ,定义,2,对于问题,(1),，设 ，若存在,使得对一切,，且 ，都有 ，则称,X,*,是,f(X),在,D,上的,局部极小值点,（,局部最优解,）,特别地当 时，若 ，则称,X,*,是,f(X),在,D,上的,严格局部极小值点,（,严格局部最优解,）,定义,3,对于问题,(1),设,对任意的,都有 则称,X,*,是,f(X),在,D,上的,全局极小值点,（,全局最优解,）,特别地当,时，若 ，则称,X,*,是,f(X),在,D,上的,严格全局极小值点,（,严格全局最优解,）,罚函数法,罚函数法,基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解这类方法称为,序列无约束最小化方法,简称为,SUMT,法,其一为,SUMT,外点法,，其二为,SUMT,内点法,其中,T(X,M),称为,罚函数,，,M,称为,罚因子,，,带,M,的项称为,罚项,，,这里的罚函数只对不满足约束条件的点实行惩罚,:,当 时，满足各 ，故罚项,=0,，不受惩罚当 时，必有 的约束条件，故罚项,0,，要受惩罚,SUTM,外点法,罚函数法的,缺点,是：每个近似最优解,X,k,往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着,M,k,的增大，可能导致错误,1,、,任意给定初始点,X,0,，取,M,1,1,，给定允许误差 ，令,k=1,；,2,、,求无约束极值问题 的最优解，设为,X,k,=X(M,k,),，即,；,3,、,若存在 ，使 ，则取,M,k,M( ),令,k=k+1,返回（,2,），否则，停止迭代得最优解,.,计算时也可将收敛性判别准则 改为,.,SUTM,外点法,(,罚函数法,),的,迭代步骤,SUTM,内点法（,障碍函数法,）,内点法的迭代步骤,用,MATLAB,软件求解,其,输入格式,如下,:,1.x=quadprog(H,C,A,b);,2.x=quadprog(H,C,A,b,Aeq,beq);,3.x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB);,4.x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X,0,);,5.x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X,0,options);,6.x,fval=quaprog(.);,7.x,fval,exitflag=quaprog(.);,8.x,fval,exitflag,output=quaprog(.);,1,、二次规划,例,1,min f(x,1,x,2,)=-2x,1,-6x,2,+x,1,2,-2x,1,x,2,+2x,2,2,s.t. x,1,+x,2,2,-x,1,+2x,2,2,x,1,0, x,2,0,1,、,写成标准形式,：,2,、,输入命令,：,H=1 -1; -1 2;,c=-2 ;-6;A=1 1; -1 2;b=2;2;,Aeq=;beq=; VLB=0;0;VUB=;,x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB),3,、,运算结果,为：,x =0.6667 1.3333 z = -8.2222,s.t.,1.,首先建立,M,文件,fun.m,定义目标函数,F,（,X,）,:,function f=fun(X);,f=F(X);,2,、一般非线性规划,其中,X,为,n,维变元向量，,G(X),与,Ceq(X),均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同,.,用,Matlab,求解上述问题，基本步骤分三步：,3.,建立主程序,.,非线性规划求解的函数是,fmincon,命令的基本格式如下：,(1),x=,fmincon,(fun,X,0,A,b),(2),x=,fmincon,(fun,X,0,A,b,Aeq,beq),(3),x=,fmincon,(fun,X,0,A,b, Aeq,beq,VLB,VUB),(4),x=,fmincon,(fun,X,0,A,b,Aeq,beq,VLB,VUB,nonlcon),(5),x=,fmincon,(fun,X,0,A,b,Aeq,beq,VLB,VUB,nonlcon,options),(6),x,fval=,fmincon(.),(7),x,fval,exitflag=,fmincon(.),(8)x,fval,exitflag,output=,fmincon(.),输出极值点,M,文件,迭代的初值,参数说明,变量上下限,注意：,1 fmincon,函数提供了大型优化算法和中型优化算法。默认时，若在,fun,函数中提供了梯度（,options,参数的,GradObj,设置为,on,），并且只有上下界存在或只有等式约束，,fmincon,函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。,2 fmincon,函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用,BFGS,法更新拉格朗日,Hessian,矩阵。,3 fmincon,函数可能会给出局部最优解，这与初值,X,0,的选取有关。,1,、,写成标准形式,：,s.t.,2x,1,+3x,2,6,s.t x,1,+4x,2,5,x,1,x,2,0,例,2,2,、,先建立,M-,文件,fun3.m:,function f=fun3(x);,f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)2,3,、再建立主程序,youh2.m,：,x0=1;1;,A=2 3 ;1 4; b=6;5;,Aeq=;beq=;,VLB=0;0; VUB=;,x,fval=fmincon(fun3,x0,A,b,Aeq,beq,VLB,VUB),4,、,运算结果为：,x = 0.7647 1.0588,fval = -2.0294,1,先建立,M,文件,fun4.m,定义目标函数,:,function f=fun4(x);,f=exp(x(1),*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);,x,1,+x,2,=0,s.t. 1.5+x,1,x,2,- x,1,- x,2,0,-x,1,x,2,10,0,例,3,2,再建立,M,文件,mycon.m,定义非线性约束：,function g,ceq=mycon(x),g=x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;,3,主程序为,:,x0=-1;1;,A=;b=;,Aeq=1 1;beq=0;,vlb=;vub=;,x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb,vub,mycon),3.,运算结果为,：,x = -1.2250 1.2250,fval = 1.8951,例,4,1,先建立,M-,文件,fun.m,定义目标函数,:,function f=fun(x);,f=-2*x(1)-x(2);,2,再建立,M,文件,mycon2.m,定义非线性约束：,function g,ceq=mycon2(x),g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;,3.,主程序,fxx.m,为,:,x0=3;2.5;,VLB=0 0;VUB=5 10;,x,fval,exitflag,output,=fmincon(fun,x0,VLB,VUB,mycon2),4.,运算结果为,:,x =,4.0000,3.0000,fval =-11.0000,exitflag = 1,output =,iterations: 4,funcCount: 17,stepsize: 1,algorithm: 1x44 char,firstorderopt: ,cgiterations: ,