收藏 分销(赏)

Matlab在求解优化问题中的应用.ppt

上传人:仙人****88 文档编号:14773024 上传时间:2026-11-19 格式:PPT 页数:109 大小:654KB 下载积分:10 金币
下载 相关
Matlab在求解优化问题中的应用.ppt_第1页
第1页 / 共109页
Matlab在求解优化问题中的应用.ppt_第2页
第2页 / 共109页


点击查看更多>>
资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,*,第七讲 Matlab,在求解优化问题中的应用,参考文献,:,Matlab,7.2,优化,设计实例指导教程,褚洪生、杜增吉、阎金华 等编著,机械工业出版社,,2007,本 讲 内 容,多目标规划问题,最大最小化问题,半无限问题,整数规划问题,大规模最优化问题,一、最优化理论概述,二、,Matlab,优化工具箱简介,三、无约束优化问题,四、约束优化问题,五、方程求解,一、最优化理论概述,最优化是一门研究如何科学、合理、迅速地确定可行方案并找到其中最优方案的学科。,最优化方法就是专门研究如何从多个方案中科学合理地提出最佳方案的科学。,(一)最优化问题基本模型,最优化问题的一般形式:,称为目标函数,,X,称为问题的可行域。,无约束问题一般形式:,约束问题一般形式:,约束函数,等式约束条件,不等式约束条件,可行域,X,为:,线性规划,二次规划,凸规划,此外还分成:整数规划、动态规划、网络规划、非光滑规划、随机规划、几何规划、多目标规划等。,例,数据拟合问题,或,无约束问题,例,食谱问题,线性规划,问题,线性规划问题的标准型:,非标准型线性规划问题过渡到标准型线性规划问题的处理方法:,例,二次规划问题,通过逐步二次规划能使一般的非线性规划问题的求解过程得到简化,因此,二次规划迭代法也是目前求解最优化问题时常用的方法。,由于二次规划问题本身也是一大类实际应用中经常碰到的问题,所以,二次规划问题在最优化理论和应用各方面都占有非常重要的地位。,例,最小二乘问题,如果,r(x,),是,x,的非线性函数,则问题称为非线性最小二乘问题;如果,r(x,),是,x,的线性函数,则问题称为线性最小二乘问题。,非线性最小二乘问题在数据拟合、参数估计和函数逼近等方面有广泛应用。,非线性最小二乘问题既可以看作为无约束极小化的特殊情形,又可以看作为解如下方程组:,(二)最优化问题的实现,用最优化方法解决最优化问题的技术称为最优化技术,它包含两个方面的内容:,建立数学模型。,即用数学语言来描述最优化问题。模型中的数学关系式反映了最优化问题所要达到的目标和各种约束条件。,数学求解。,数学模型建好以后,选择合理的最优化方法进行求解。,Matlab,实现,由于最优化问题在近些年来得到了广泛的应用,,Matlab,工具箱函数也同时有了飞速的发展。,利用,Matlab,的优化工具箱可以求解如下问题:,线性、非线性最小化,最大最小化,二次规划,半无限问题,线性、非线性方程(组)的求解,线性、非线性的最小二乘问题,此外,该工具箱还提供了线性、非线性最小化,方程求解,曲线拟合,二次规划等问题中大型课题的求解方法,为优化方法在工程中的实际应用提供了更方便快捷的途径。,使用,Matlab,的优化工具箱时,由于优化函数要求目标函数和约束条件满足一定的格式,所以需要用户在进行模型输入时注意以下几个问题:,优化函数,fminbnd,、,fminsearch,、,fminunc,、,fminicon,、,fgoalattain,、,fminmax,和,lsqnonlin,都要求目标函数最小化,如果优化问题要求目标函数最大化,可以通过使该目标函数的负值最小化即,-,f,(,x,),最小化来实现。近似地,对于,quadprog,函数提供,-,H,和,-,f,,对于,linprog,函数提供,-,f,。,优化工具箱要求非线性不等式约束的形式为,C,i,(,x,)0,通过对不等式取负可以达到使大于零的约束形式变为小于零的不等式约束形式的目的,如,C,i,(,x,),0,形式的约束等价于,-,C,i,(,x,)0,;,C,i,(,x,)b,形式的约束等价于,-,C,i,(,x,)+b0,。,二、,Matlab,优化工具箱简介,(一)优化工具箱中的函数,优化工具箱中的函数包括下面几类:,函数,描述,fminsearch,fminunc,无约束非线性最小化,fminbnd,有边界的标量非线性最小化,fmincon,有约束的非线性最小化,linprog,线性规划,quadprog,二次规划,fgoalattain,多目标规划,fminimax,最大最小化,fseminf,半无限问题,1.,最小化函数,2.,最小二乘问题,函数,描述,线性最小二乘,lsqnonlin,非线性最小二乘,lsqnonneg,非负线性最小二乘,lsqlin,有约束线性最小二乘,lsqcurvefit,非线性曲线拟合,3.,方程求解函数,函数,描述,线性方程求解,fzero,标量非线性方程求解,fsolve,非线性方程求解,中型问题方法演示函数,4.,演示函数,函数,描述,tutdemo,教程演示,optdemo,演示过程菜单,officeassign,求解整数规划,goaldemo,目标达到举例,dfildemo,过滤器设计的有限精度,大型问题方法演示函数,函数,描述,molecule,用无约束非线性最小化进行分子组成求解,circustent,马戏团帐篷问题,二次规划问题,optdeblur,用有边界线性最小二乘法进行图形处理,(二)优化函数的变量,在,Matlab,的优化工具箱中,定义了一系列的标准变量,通过使用这些标准变量,用户可以使用,Matlab,来求解在工作中碰到的问题。主要有如下三类:,1.,输入变量,调用,Matlab,优化工具箱,需要首先给出一些输入变量,优化工具箱函数通过对这些输入变量的处理得到用户需要的结果。输入变量大体上分成,输入系数,和,输入参数,两类:,变量名,作用和含义,主要的调用函数,A,b,A,矩阵和,b,向量分别为,线性不等式约束的系数,矩阵和右端项,fgoalattain,fmincon,fminimax,fseminf,linprog,lsqlin,quadprog,Aeq,beq,Aeq,矩阵和,beq,向量分别为线性方程约束的系数矩阵和右端项,fgoalattain,fmincon,fminimax,fseminf,linprog,lsqlin,quadprog,C,d,矩阵,C,和向量,d,分别为超定或不定线性系统方程组的系数矩阵和进行求解的右端项,lsqlin,lsqnonneg,f,线性方程或二次方程中线性项的系数向量,linprog,quadprog,H,二次方程中二次项的系数,quadprog,ub,lb,变量的上下界,fgoalattain,fmincon,fminimax,fseminf,linprog,lsqlin,quadprog,lsqcurvefit,lsqnonlin,fun,待优化的函数,fgoalattain,fminbnd,fmincon,fminimax,fminsearch,fminunc,fseminf,fzero,fsolve,lsqcurvefit,lsqnonlin,nonlcon,计算非线性不等式和等式,fgoalattain,fmincon,fminimax,seminfcon,计算非线性不等式约束、等式约束和半无限约束的函数,fseminf,输入系数表,变量名,作用和含义,主要的调用函数,goal,目标试图达到的值,fgoalattain,ntheta,半无限约束的个数,fseminf,options,优化选项参数结构,所有,P1,P2,传给函数,fun,变量,nonlcon,变量,seminfcon,的其它变量,fgoalattain,fminbnd,fmincon,fminimax,fsearch,fminunc,fseminf,fzero,fsolve,lsqcurvefit,lsqnonlin,weight,控制对象未达到或超过的加权向量,fgoalattain,xdata,ydata,拟合方程的输入数据和测量数据,lsqcurvefit,x0,初始点,除,fminbnd,所有,x1,x2,函数最小化的区间,fminbnd,输入参数表,2.,输出变量,变量名,作用和含义,x,由优化函数求得的解,fval,解,x,处的目标函数值,exitflag,退出条件,output,包含优化结果信息的输出结构,lambda,解,x,处的,Lagrange,乘子,grad,解,x,处函数,fun,的梯度值,hessian,解,x,处函数,fun,的,Hessian,矩阵,jacobian,解,x,处函数,fun,的,Jacobian,矩阵,maxfval,解,x,处函数的最大值,attainfactor,解,x,处的达到因子,residual,解,x,处的残差值,resnorm,解,x,处残差的平方范数,调用,Matlab,优化工具箱函数后,给出一系列输出变量,提供给用户相应的输出信息。,3.,优化参数,参数名,含义,Derivativecheck,对自定义的解析导数与有限差分导数进行比较,Diagnostics,打印进行最小化或求解的诊断信息,DiffMaxChange,有限差分求导的变量最大变化,DiffMinChange,有限差分求导的变量最小变化,Display,值为,off,时,不显示输出,;,为,iter,时,显示迭代信息,;,为,final,时,只显示结果,在新版本中,notify,当函数不收敛时输出,GoalsExactAchieve,精确达到的目标个数,GradConstr,用户定义的非线性约束的梯度,GradObj,用户定义的目标函数的梯度,Hessian,用户定义的目标函数的,Hessian,矩阵,HessPattern,有限差分的,Hessian,矩阵的稀疏模式,HessUpdate,Hessian,矩阵修正结构,参数名,含义,Jacobian,用户定义的目标函数的,Jacobian,矩阵,JacobPattern,有限差分的,Jacobian,矩阵的稀疏模式,LargeScale,使用大型算法,(,如果可能的话,),Levenberg,-Marquardt,用,Levenberg,-Marquardt,方法代替,Gauss-Newton,方法,LineSearchType,一维搜索算法的选择,MaxFunEvals,允许进行函数评价的最大次数,MaxIter,允许进行迭代的最大次数,MaxPCGIter,允许进行,PCG,迭代的最大次数,MeritFunction,使用多目标函数,MinAbsMax,最小化最坏个案例绝对值的,f(x,),的个数,PrecondBandWidth,PCG,前提的上带宽,TolCon,违背约束的终止容限,TolFun,函数值的终止容限,TolPCG,PCG,迭代的终止容限,TolX,X,处的终止容限,TypicalX,典型,x,值,(三)参数设置,对于优化控制,,Matlab,提供了,18,个参数。利用,optimset,函数,可以创建和编辑参数结构;利用,optimget,函数,可以获得,options,优化参数。这些参数的具体意义如下:,参数名,含义,options(1),参数显示控制,(,默认值为,0),等于,1,时显示一些结果,options(2),优化点,x,的精度控制,(,默认值为,1e-4),options(3),优化函数,F,的精度控制,(,默认值为,1e-4),options(4),违反约束的结束标准,(,默认值为,1e-6),options(5),算法选择,不常用,options(6),优化程序方法选择,为,0,则为,BFCG,算法,为,1,则采用,DFP,算法,options(7),线性插值算法选择,为,0,则为混合插值算法,为,1,则采用立方插值算法,options(8),函数值显示,(,多目标规划问题中的,Lambda),options(9),若需要检测用户提供的梯度,则设为,1,options(10),函数和约束估值的数目,options(11),函数梯度估值的个数,options(12),约束估值的数目,options(13),等式约束条件的个数,options(14),函数估值的最大次数,(,默认值为,100,变量个数,),options(15),用于多目标规划问题中的特殊目标,options(16),优化过程中变量的最小有限差分梯度值,options(17),优化过程中变量的最大有限差分梯度值,options(18),步长设置,(,默认为,1,或更小,),1.,参数值,2.,optimset,函数,optimset,函数的功能是创建或编辑优化选项参数结构。具体的调用格式为:,options=,optimset,(,param1,value1,param2,value2,),options=,optimset,(,oldopts,param1,value1,),功能:,创建一个称为,options,的优化选项参数,其中指定的参数具有指定值。所有未指定的参数都设置为空矩阵,(将参数设置为,表示当,options,传递给优化函数时给参数,赋默认值,)。赋值时只要输入参数前面的字母就行了。,功能:,创建一个,oldopts,的复制,用指定的数值修改参数。,options=,optimset,(,oldopts,newopts,),功能:,将已经存在的选项结构,oldopts,与新的选项结构,newopts,进行合并。,newopts,参数中的所有元素将覆盖,oldopts,参数中的所有对应元素。,optimset,功能:,没有任何输入输出参数,将显示一张完整的带有有效值的参数列表如左:,Display:off|on|,iter,|notify|final,MaxFunEvals,:positive scalar,MaxIter,:positive scalar,TolFun,:positive scalar,TolX,:positive scalar,FunValCheck,:off|on,OutputFcn,:function|,BranchStrategy,:,mininfeas,|,maxinfeas,DerivativeCheck,:on|off,Diagnostics:on|off,DiffMaxChange,:positive scalar|1e-1,DiffMinChange,:positive scalar|1e-8,GoalsExactAchieve,:positive scalar|0,options=,optimset,(,with no input arguments,),功能:,创建一个选项结构,options,,其中所有的元素被设置为,。,optimset,(,optimfunction,),功能:,创建一个含有所有参数名和与优化函数,optimfun,相关的默认值的选项结构,options,。,options=optimset(Display,iter,TolFun,1e-8),例,1,options=,Display:,iter,MaxFunEvals,:,MaxIter,:,TolFun,:1.0000e-008,TolX,:,FunValCheck,:,OutputFcn,:,ActiveConstrTol,:,BranchStrategy,:,DerivativeCheck,:,Diagnostics:,DiffMaxChange,:,DiffMinChange,:,GoalsExactAchieve,:,optnew,=optimset(options,Tol,X,1e-,4,),例,2,options=,Display:,iter,MaxFunEvals,:,MaxIter,:,TolFun,:1.0000e-008,TolX,:1.0000e-004,FunValCheck,:,OutputFcn,:,ActiveConstrTol,:,BranchStrategy,:,DerivativeCheck,:,Diagnostics:,DiffMaxChange,:,DiffMinChange,:,GoalsExactAchieve,:,options=,optimset,(,fminbnd,),例,3,options=,Display:notify,MaxFunEvals,:500,MaxIter,:500,TolFun,:,TolX,:1.0000e-004,FunValCheck,:off,OutputFcn,:,返回,options,优化结构,其中包含所有的参数名和与,fminbnd,函数相关的默认值,结果如左:,optimset,fminbnd,例,4,若只希望看到,fminbnd,函数的默认值,只需要简单地键入上面的语句之一就可以了。其输出结果同上例。,optimset,(,fminbnd,),或,3.,optimget,函数,optimget,函数的功能是获得,options,的优化参数。具体的调用格式为:,val,=,optimget,(,options,name,),val,=,optimget,(,options,name,default,),功能:,返回优化参数,options,中指定的参数的值。只需要用参数开头的字母来定义参数就行了。,功能:,若,options,结构参数中没有定义指定参数,则返回默认值。注意,这种形式的函数主要用于其它优化函数。,设置了参数,options,后就可以用上述调用形式完成指定任务了。,val,=,optim,g,et,(options,Display,),例,5,val,=,notify,optnew,=,optim,g,et,(options,Display,final,),例,6,optnew,=,notify,如果显示参数没有定义,则返回值,final,。,(四)模型输入时需要注意的问题,使用优化工具箱时,由于优化函数要求目标函数和约束条件满足一定的格式,所以需要用户在进行模型输入时注意以下几个问题:,优化函数,fminbnd,、,fminsearch,、,fminunc,、,fminicon,、,fgoalattain,、,fminmax,和,lsqnonlin,都要求目标函数最小化,如果优化问题要求目标函数最大化,可以通过使该目标函数的负值最小化即,-,f,(,x,),最小化来实现。近似地,对于,quadprog,函数提供,-,H,和,-,f,,对于,linprog,函数提供,-,f,。,优化工具箱要求非线性不等式约束的形式为,C,i,(,x,)0,通过对不等式取负可以达到使大于零的约束形式变为小于零的不等式约束形式的目的,如,C,i,(,x,)0,形式的约束等价于,-,C,i,(,x,)0,;,C,i,(,x,),b,形式的约束等价于,-,C,i,(,x,)+,b,0,。,在,Matlab,语言中,函数内部定义的变量除特殊声明外均为局部变量,即不加载到工作空间中。如果需要使用全局变量,则应当使用命令,global,定义,而且在任何时候使用该全局变量的函数中都应该加以定义。在命令窗口中也不例外。当程序比较大时,难免会在无意中修改全局变量的值,因而导致错误。更糟糕的是,这样的错误很难查找。因此,在编程时应该尽量避免使用全局变量。,(五)函数,Matlab6.0,以后的版本中可以,用,函数进行,函数调用,。,函数返回指定,Matlab,函数的句柄,其调用格式为:,handle=,function,利用函数进行函数调用的好处:,用句柄将一个函数传递给另一个函数;,减少定义函数的文件个数;,改进重复操作;,保证函数计算的可靠性。,fhandle,=humps;,例,7,x=,0.6370,x=fminbnd(,fhandle,0,1),为,humps,函数创建一个函数句柄,并将它指定为,fhandle,变量。,传递句柄给另一个函数,也将传递所有变量。,x=fminbnd(,humps,0,1),x=fminbnd,(,humps,0,1,),或,或,(六)优化算法介绍,参数优化就是求一组设计参数,x=,(,x,1,x,2,x,n,),,以满足在某种意义下最优。一个简单的情况就是对某依赖于,x,的问题求极大值或极小值。复杂一点的情况是欲进行优化的目标函数,f,(,x,),受到以下限定条件:,1.,参数优化问题,等式约束条件:,不等式约束条件:,参数有界约束:,这类问题的一般数学模型为:,要有效而且精确地解决这类问题,不仅依赖于问题的大小即约束条件和设计变量的数目,而且依赖目标函数和约束条件的性质。,线性规划,二次规划,非线性规划,能得到可靠的解,一般是通过求解线性规划、二次规划或无约束优化的子问题来解决。,2.,无约束优化问题,搜索法,是对非线性或不连续问题求解的合适方法,当欲优化的函数具有连续一阶导数时,,梯度法,(一个简单的方法是沿负梯度方向搜索)一般说来更为有效,,高阶法,(例如,Newton,法)仅实用于目标函数的二阶信息能计算出来的情况。,拟,Newton,法,在使用梯度信息的方法中,最为有效的方法是拟,Newton,方法。此方法的实质是建立每次迭代的曲率信息,以此来解决如下形式的二次模型问题:,其中,H,为目标函数的,Hessian,矩阵,,H,对称正定,,b,为常数向量,,c,为常数。最优解为:,多项式近似,对应于拟,Newton,法,,Newton,法,直接计算,H,,并使用线搜索策略沿下降方向经过一定次数的迭代后确定最小值,为了得到矩阵,H,需要经过大量的计算;,拟,Newton,法,则不同,它通过使用,f,(,x,),和它的梯度来修正,H,的近似值,常用的拟,Newton,法(,Hessian,矩阵修正方法),BFGS,方法,DFP,方法,该法用于目标函数比较复杂的情况。在这种情况下寻找一个与它近似的函数来代替目标函数,并用近似函数的极小点作为原函数极小点的近似。常用的近似函数为二次多项式和三次多项式。,二次内插的一般问题是,在定义域空间给定三个点,x,1,,,x,2,,,x,3,和它们所对应的函数值,f,(,x,1,),,,f,(,x,2,),,,f,(,x,3,),,,由二阶匹配得出最小值点如下:,二次内插,极值点:,二次函数:,此点可能是最小值或最大值点。当执行内插或,a,为正时是最小值。只要利用三个梯度或者函数方程组即可确定系数,a,和,b,,从而可确定,x,*,。得到该值以后,进行搜索区间的收缩。,其中,三次插值的基本思想和二次插值一致,它是,用,4,个已知点,构造一个三次多项式来逼近目标函数,同时以三次多项式的极小点作为目标函数极小点的近似。,三次插值,三次插值法需要计算目标函数的导数,优点是计算速度快。同类的方法还有,Newton,切线法、对分法、割线法等。优化工具箱中使用的比较多的是三次插值法。,二次插值法的计算速度比黄金分割搜索法快,但是对于一些强烈扭曲或者可能多峰的函数,这种方法的收敛速度变得很慢,甚至失败。,一般来讲,三次插值法比二次插值法的收敛速度快,但是每次迭代需要计算两个导数值。,如果导数容易求得,一般来说首先考虑使用三次插值法,因为它具有较高的效率,对于只需要计算函数值的方法中,二次插值是一个很好的方法,它的收敛速度较快,在极小点所在的区间较小时尤其如此。黄金分割法是一种十分稳定的方法,并且计算简单。由于上述原因,,Matlab,优化工具箱中较多地使用二次插值法、三次插值法以及二次三次混合插值法和黄金分割法,。,三次插值法的迭代公式为:,其中,3.,拟,Newton,法实现,在函数,fminunc,中使用拟,Newton,法,算法的实现过程包括两个阶段:,确定搜索方向,搜索方向的选择由选择,BFGS,方法还是选择,DFP,方法来决定,在优化工具箱中,,通过将,options,参数,HessUpdate,设置为,BFGS,或,DFP,来确定搜索方向,。,Hessian,矩阵,H,总是保持正定的,使得搜索方向总是保持为下降方向。这意味着,对于任意小的步长,在上述搜索方向上目标函数值总是减小的。只要,H,的初始值为正定并且计算出的,q,k,T,s,k,总是正的,则,H,的正定性得到保证。并且只要执行足够精度的线性搜索,,q,k,T,s,k,为正的条件总能得到满足。,要确定搜索方向首先必须完成,Hessian,矩阵的修正。,Newton,法由于需要多次计算,Hessian,矩阵,所以计算量很大。拟,Newton,法通过构建一个,Hessian,矩阵的近似矩阵来避开这个问题。,线性(一维)搜索过程,另外,在三次插值法中,每一个迭代周期都要进行梯度和函数的计算。,在优化工具箱中有两种线性搜索方法可以使用,这取决于梯度信息是否可以得到。当梯度值可以直接得到时,默认情况下使用三次多项式方法;当梯度值不能直接得到时,默认情况下,采用混合二次和三次插值法。,4.,最小二乘优化,前面介绍了函数,fminunc,中使用的是在拟,Newton,法中介绍的线性搜索法,在最小二乘优化程序,lsqnonlin,中也部分地使用这一方法。最小二乘问题的优化描述如下:,在实际应用中,特别是数据拟合时存在大量这种类型的问题,如非线性参数估计等。控制系统中也经常会遇到这类问题,如希望系统输出的,y,(,x,t,),跟踪某一个连续的期望轨迹,这个问题可以表示为:,将问题离散化得到:,最小二乘问题的梯度和,Hessian,矩阵具有特殊的结构,定义,r,(,x,),的,Jacobian,矩阵为,J,(,x,),,则,F,(,x,),的梯度和,F,(,x,),的,Hessian,矩阵定义为:,其中,GaussNewton,法,在,GaussNewton,法中,每个迭代周期均会得到搜索方向,d,。它是最小二乘问题的一个解。,GaussNewton,法用来求解如下问题:,当,Q,(,x,),很大时,,GaussNewton,法很难得到问题的解,在这种情况下,,LevenbergMarquadt,方法显得更有效。,Levenberg,Marquadt,法,Levenberg,Marquadt,法使用的搜索方向是一组线性等式的解:,5.,非线性最小二乘实现,GaussNewton,实现,GaussNewton,法是用前面求无约束问题中讨论过的多项式线性搜索策略来实现的。使用,Jacobian,矩阵的,QR,分解,可以避免在求解线性最小二乘问题中等式条件恶化的问题。,这种方法中包含一项鲁棒性检测技术,这种技术步长低于限定值或当,Jacobian,矩阵的条件数很小时,将改为使用,Levenberg,Marquadt,法。,这种实现方法在大量非线性问题中得到了成功的应用,并被证明比,GaussNewton,法具有更好的鲁棒性,比无约束条件方法具有更好的迭代效率。在使用,lsqnonlin,函数时,函数所使用的默认算法是,Levenberg,Marquadt,法。当,options(5)=1,时,使用,GaussNewton,法。,Levenberg,Marquadt,实现,实现,Levenberg,Marquadt,方法的主要困难是在每一次迭代中,如何控制,的大小的策略问题,,这种控制可以使它对于宽谱问题有效。这种实现的方法是使用线性预测平方总和和最小函数值的三次插值估计,来估计,目标函数的相对非线性,用这种方法,的大小在每一次迭代中都能确定。,6.,约束优化,在约束最优化问题中,一般方法是先将问题变换为较容易的子问题,然后再求解。前面所述方法的一个特点是可以用约束条件的罚函数将约束优化问题转化为基本的无约束优化问题,按照这种方法,条件极值问题可以通过参数化为无约束优化序列来求解。但这些方法效率不高,目前已经被通过,求解,KuhnTucker,方程,的方法所取代。,KuhnTucker,方程是条件极值问题的,必要条件,。如果欲解决的问题是所谓的凸规划问题,那么,KuhnTucker,方程有解是极值问题有全局解的充分必要条件。,求解,KuhnTucker,方程是很多非线性规划算法的基础,这些方法试图直接计算,Lagrange,乘子。因为在每一次迭代中都要求解一次,QP,子问题,这些方法一般又被称为,逐次(或序列)二次规划(,SQP,)方法,。,这个问题可以通过任何求解二次规划问题的算法求解。,使用序列二次规划方法,非线性约束条件的极值问题经常可以比无约束优化问题用更少的迭代得到解。造成这种现象的一个原因是:受到可行域的限制,这种方法更可能得到恰当的搜索方向和迭代步长。,给定一个约束最优化问题,求解的基本思想是基于,Lagrange,函数的二次近似求解二次规划子问题:,从而得到二次规划子问题:,7.SQP,实现,在每一次迭代中,均作,Lagrange,函数的,Hessian,矩阵的正定拟,Newton,近似,通过,BFGS,方法进行计算。,Matlab,工具箱的,SQP,实现由三个部分组成:,修正,Lagrange,函数的,Hessian,矩阵,二次规划问题求解,线性搜索,修正,Hessian,矩阵,用,BFGS,公式修正,Hessian,矩阵:(略),此算法要求有一个合适的初始值,如果由逐次二次规划方法得到的当前计算点是不合适的,则通过求解下述线性规划问题可以得到合适的计算点:,如果上述问题存在要求的点,就可以通过将,x,赋值为满足等式条件的值来得到。,求解二次规划问题,初始化,在逐次二次规划方法中,每一次迭代都要解一个二次规划问题:,三、无约束优化问题,(一)一维优化问题,1.,数学原理及模型,一般的优化问题,因受多种因素的影响与制约,目标函数一般都是多元函数,称为多维优化问题。求解多维优化问题,常常化为逐步的沿某一方向求单元函数的极值问题,也就是一维搜索问题,在这里称为一维优化问题。一维搜索方法的好坏直接影响到优化算法的求解速度。,一维搜索的直接目的是寻求单变量函数的极小点,在理论上,一维搜索主要是作为求多变量函数的极小点的手段而进行研究的。然而,在实际应用中,很多问题都需要直接使用一维搜索的方法,如工程中常见的参数反演问题。应该指出,所选用的一维搜索方法是否得当,常常对于整个计算的进程的影响极大。,数学模型,一维优化问题的数学模型为:,对于一维优化问题来说,由于问题本身比较简单,可选择的方法也比较多。比较经典的方法有:进退法、,Fibonacci,法(也叫分数法)、黄金分割法(也叫,0.618,法)、试位法以及各种插值法。一般来说,对于形态比较好、比较光滑的函数可以使用,插值法,,这样可以较快地逼近极小点;而对于形态比较差的函数,则可以使用,黄金分割法,。这也是,Matlab,优化工具箱中的库函数使用的两种方法。,算法介绍,2.,Matlab,工具箱中的基本函数,在,Matlab,中,一维优化问题,也就是,一维搜索问题的实现是由函数,fminbnd,来实现的,。,应当注意:该函数所求的目标函数必须是连续的,并且只用于实数变量。同时该函数只能给出目标函数的局部最优解。对于问题的解位于区间边界上的情况,此函数收敛速度非常慢。,具体的调用格式如下:,x=,fminbnd,(,fun,,,x1,,,x2,),功能:,返回在区间,(x1,,,x2),中标量函数,fun,的最小值点。,x=,fminbnd,(,fun,,,x1,,,x2,,,options,),功能:,用,options,参数指定的优化参数进行最小化,其中,,options,可取值为:,Display,,,TolX,,,MaxFunEval,,,MaxIter,,,FunValCheck,,和,OutputFcn,。,options,参数,含义,Display,显示的水平:为,off,时,不显示输出;为,iter,时,显示每一步迭代输出;为,final,时,显示最终结果。,TolX,在点,x,处的终止容限,MaxFunEval,函数评价的最大允许次数,MaxIter,最大允许迭代次数,FunValCheck,检查非法函数值,OutputFcn,可加载输出函数名,options,参数各个取值的含义如下表所示:,x,,,fval,=,fminbnd,(,),功能:,同时返回解,x,和在点,x,处的目标函数,值,。,exitflag,值,含义,1,函数收敛到目标函数最优解处,0,达到最大迭代次数或达到函数评价,-1,算法由输出函数终止,-2,下界大于上界,exitflag,值和相应的含义如下表所示:,x,,,fval,,,exitflag,=,fminbnd,(,),功能:,同时返回解,x,和在点,x,处的目标函数值。另外,返回,exitflag,值,描述极小化函数的退出条件。,output,结构值,含义,output,.iterations,迭代次数,output,.funcCount,函数评价次数,output,.algorithm,所用的算法,output,包含的内容和相应的含义如下表所示:,x,,,fval,,,exitflag,,,output=,fminbnd,(,),功能:,返回同上述格式的值。另外,返回包含,output,结构的输出。,例,8,fminbnd,演示。,x=fminbnd(,cos,3,4),x=,3.1416,x,fval,exitflag,=fminbnd(,cos,3,4,optimset(TolX,1e-12,Display,off,),),x=,3.1416,fval=-1,exitflag=1,例,9,求函数,f,(,x,),=,(,x-4,),2-5,在区间,(0,6),内的最小值。,function f=ex9(x),f=(,x-4,),2-5,2;,编辑目标函数的,M,文件,ex9.m,:,x,fval,=fminbnd(,ex9,0,6,),x=,4,fval=,-5,在命令窗口中输入:,例,10,带参数优化问题。,function f=ex10(x,a),%This function is to demonstrate minimize the objective,%given in the function which is parameterized by its second,%argument a,f=(x-a)2;,编辑如下,M,文件,ex10.m,:,a=1.5;%define parameter first,x=,fminbnd(,(x,)ex10(x,a),0,1,),x=,0.9999,在命令窗口中输入:,3.,应用实例分析,function f=ex11(x),%The purpose of this file is to give the objective function,%This is a function to calculate the volume,f=-(5-2*x).2*x;,编辑如下,M,文件,ex11.m,:,例,11,容积最大化问题。,对边长为,5m,的正方形钢板,在,4,个角处剪去相等的正方形以制成方形无盖的容器,问如何剪去使得容器的容积最大?,假设剪去的正方形的边长为,x,,则容器的容积计算公式为:,这里需要将最大化问题转化为最小化问题,目标函数为:,x,fval,exitflag,output,=,fminbnd(,ex11,0,1.5,),x=,0.8333,fval=-9.2593,exitflag=1,output=,iterations:8,funcCount:9,algorithm:golden section search,parabolic interpolation,message:1x112 char,在命令窗口中输入:,(二)无约束非线性规划问题,1.,数学原理及模型,无约束最优化是一个十分古老的课题,至少可以追溯到,Newton,发明微积分的时代。无约束最优化问题在实际应用中也非常常见,另外,许多约束优化问题也可以转化成无约束优化问题求解,所以,无约束优化问题还是十分重要的。,由于简单的无约束线性问题非常容易,这里提到的无约束最优化问题就是指无约束非线性规划问题。,数学模型,设,f,(,x,),是一个定义在,n,维欧式空间上的函数。把寻找,f,(,x,
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 包罗万象 > 大杂烩

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服