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

1、参考文献:Matlab7.2优化设计实例指导教程褚洪生、杜增吉、阎金华 等编著机械工业出版社，2007本本 讲讲 内内 容容l多目标规划问题l最大最小化问题l半无限问题l整数规划问题l大规模最优化问题一、最优化理论概述一、最优化理论概述二、二、Matlab优化工具箱简介优化工具箱简介三、无约束优化问题三、无约束优化问题四、约束优化问题四、约束优化问题五、方程求解五、方程求解一、最优化理论概述一、最优化理论概述 最优化是一门研究如何科学、合理、迅速地确定可行方案并找到其中最优方案的学科。 最优化方法就是专门研究如何从多个方案中科学合理地提出最佳方案的科学。（一）最优化问题基本模型（一）最优化问题

2、基本模型最优化问题的一般形式：min( ),nf xxXR:nfXRR称为目标函数，X称为问题的可行域。min( ),.nf xxR无约束问题一般形式：约束问题一般形式：约束函数m in( )fx.( )0,1,( )0,1, .ieiest c xiEmc xiImm 等式约束条件不等式约束条件可行域X为： ( )0,; ( )0, .iiXc xiE c xiI线性规划二次规划凸规划此外还分成：整数规划、动态规划、网络规划、非光滑规划、随机规划、几何规划、多目标规划等。例例 数据拟合问题或无约束问题51( , )|()|iiif a byaxb2min( , ),( , ).Tf a ba

3、 bR521( , )()iiif a byaxb例例 食谱问题线性规划问题1minnjjjc x1. .,1,0,1, .nijjijjs ta xbimxjn1m inniiic x nixbxaxaxabxaxaxabxaxaxatsimnmnmmnnnn,2,1,0.22112222212111212111线性规划问题的标准型：minTc x 0.xbAxts记记为为。则则线线性性规规划划标标准准型型可可记记nmijTnTmTnaAxxxxbbbbcccc )(,),(,),(,),(212121目目标标函函数数：)1(: maxTc x原 问 题 目 标 函 数minTc x约约束束

4、条条件件：)2(1 122( )iiinniia xa xa xb原问题条件： 02211iniinniniixbxxaxaxan ix称为松弛变量1 122( )iiinniiia xa xa xb原问题条件： 02211iniinniniixbxxaxaxan ix称为剩余变量()iiiix原问题：无非负约束，则令非标准型线性规划问题过渡到标准型线性规划问题的处理方法：iiiiix = u - vu ,v0例例 二次规划问题1min2TTx Hxgx11. .,1,1,.nijjiejnijjiejs taxbimaxbimm 通过逐步二次规划能使一般的非线性规划问题的求解过程得到简化，因

5、此，二次规划迭代法也是目前求解最优化问题时常用的方法。 由于二次规划问题本身也是一大类实际应用中经常碰到的问题，所以，二次规划问题在最优化理论和应用各方面都占有非常重要的地位。例例 最小二乘问题1( )( )( )2minnTxRfxr xr x( )0,1,irxim 如果r(x)是x的非线性函数，则问题称为非线性最小二乘问题；如果r(x)是x的线性函数，则问题称为线性最小二乘问题。 非线性最小二乘问题在数据拟合、参数估计和函数逼近等方面有广泛应用。 非线性最小二乘问题既可以看作为无约束极小化的特殊情形，又可以看作为解如下方程组：被称为残量函数（二）最优化问题的实现（二）最优化问题的实现 用

6、最优化方法解决最优化问题的技术称为最优化技术，它包含两个方面的内容： 建立数学模型。建立数学模型。即用数学语言来描述最优化问题。模型中的数学关系式反映了最优化问题所要达到的目标和各种约束条件。 数学求解。数学求解。数学模型建好以后，选择合理的最优化方法进行求解。 Matlab实现 由于最优化问题在近些年来得到了广泛的应用， Matlab工具箱函数也同时有了飞速的发展。利用Matlab的优化工具箱可以求解如下问题：线性、非线性最小化最大最小化二次规划半无限问题线性、非线性方程（组）的求解线性、非线性的最小二乘问题 此外，该工具箱还提供了线性、非线性最小化，方程求解，曲线拟合，二次规划等问题中大型

7、课题的求解方法，为优化方法在工程中的实际应用提供了更方便快捷的途径。(1)目标函数最小化(2)约束非正(3)避免使用全局变量 使用Matlab的优化工具箱时，由于优化函数要求目标函数和约束条件满足一定的格式，所以需要用户在进行模型输入时注意以下几个问题： 优化函数fminbnd、fminsearch、fminunc、fminicon、fgoalattain、fminmax和lsqnonlin都要求目标函数最小化，如果优化问题要求目标函数最大化，可以通过使该目标函数的负值最小化即 -f (x) 最小化来实现。近似地，对于quadprog 函数提供 -H 和 -f，对于linprog函数提供 -f

8、。 优化工具箱要求非线性不等式约束的形式为Ci(x) 0,通过对不等式取负可以达到使大于零的约束形式变为小于零的不等式约束形式的目的，如 Ci(x) 0形式的约束等价于-Ci(x) 0 ；Ci(x) b形式的约束等价于-Ci(x) +b0。二、二、Matlab优化工具箱简介优化工具箱简介（一）优化工具箱中的函数（一）优化工具箱中的函数优化工具箱中的函数包括下面几类： 函数函数 描述描述fminsearch, fminunc无约束非线性最小化fminbnd有边界的标量非线性最小化fmincon有约束的非线性最小化linprog线性规划quadprog二次规划fgoalattain多目标规划fmi

9、nimax最大最小化fseminf半无限问题1. 最小化函数最小化函数2. 最小二乘问题最小二乘问题 函数函数 描述描述 线性最小二乘lsqnonlin非线性最小二乘lsqnonneg非负线性最小二乘lsqlin有约束线性最小二乘lsqcurvefit非线性曲线拟合3. 方程求解函数方程求解函数 函数函数 描述描述 线性方程求解fzero标量非线性方程求解fsolve非线性方程求解u 中型问题方法演示函数中型问题方法演示函数4. 演示函数演示函数 函数函数 描述描述tutdemo教程演示optdemo演示过程菜单officeassign求解整数规划goaldemo目标达到举例dfildemo过

10、滤器设计的有限精度u 大型问题方法演示函数大型问题方法演示函数 函数函数 描述描述molecule用无约束非线性最小化进行分子组成求解circustent马戏团帐篷问题二次规划问题optdeblur用有边界线性最小二乘法进行图形处理（二）优化函数的变量（二）优化函数的变量 在Matlab的优化工具箱中，定义了一系列的标准变量，通过使用这些标准变量，用户可以使用Matlab来求解在工作中碰到的问题。主要有如下三类：1. 输入变量输入变量 调用 Matlab 优化工具箱，需要首先给出一些输入变量，优化工具箱函数通过对这些输入变量的处理得到用户需要的结果。输入变量大体上分成输入系数和输入参数两类：变

11、量名变量名 作用和含义作用和含义 主要的调用函数主要的调用函数A, bA矩阵和b向量分别为线性不等式约束的系数矩阵和右端项fgoalattain, fmincon, fminimax, fseminf, linprog, lsqlin, quadprogAeq, beqAeq矩阵和beq向量分别为线性方程约束的系数矩阵和右端项fgoalattain, fmincon, fminimax, fseminf, linprog, lsqlin, quadprogC, d矩阵C和向量d分别为超定或不定线性系统方程组的系数矩阵和进行求解的右端项lsqlin, lsqnonnegf线性方程或二次方程中线性

12、项的系数向量linprog, quadprogH二次方程中二次项的系数quadprogub, lb变量的上下界fgoalattain, fmincon, fminimax, fseminf, linprog, lsqlin, quadprog,lsqcurvefit, lsqnonlinfun待优化的函数fgoalattain, fminbnd, fmincon, fminimax, fminsearch, fminunc, fseminf, fzero, fsolve, lsqcurvefit, lsqnonlinnonlcon计算非线性不等式和等式fgoalattain, fmincon,

13、 fminimaxseminfcon计算非线性不等式约束、 等式约束和半无限约束的函数fseminf输入系数表输入系数表变量名变量名 作用和含义作用和含义 主要的调用函数主要的调用函数goal目标试图达到的值fgoalattainntheta半无限约束的个数fseminfoptions优化选项参数结构所有P1,P2,传给函数fun,变量nonlcon,变量seminfcon的其它变量fgoalattain, fminbnd, fmincon, fminimax, fsearch, fminunc, fseminf, fzero, fsolve, lsqcurvefit, lsqnonlinwe

14、ight控制对象未达到或超过的加权向量fgoalattainxdata,ydata拟合方程的输入数据和测量数据lsqcurvefitx0初始点除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处函数的最大值att

15、ainfactor解x处的达到因子residual解x处的残差值resnorm解x处残差的平方范数 调用 Matlab 优化工具箱函数后，给出一系列输出变量，提供给用户相应的输出信息。3. 优化参数优化参数参数名参数名 含义含义Derivativecheck对自定义的解析导数与有限差分导数进行比较Diagnostics打印进行最小化或求解的诊断信息DiffMaxChange有限差分求导的变量最大变化DiffMinChange有限差分求导的变量最小变化Display值为off时,不显示输出;为iter时,显示迭代信息;为final时,只显示结果在新版本中,notify,当函数不收敛时输出Goal

16、sExactAchieve精确达到的目标个数GradConstr用户定义的非线性约束的梯度GradObj用户定义的目标函数的梯度Hessian用户定义的目标函数的Hessian矩阵HessPattern有限差分的Hessian矩阵的稀疏模式HessUpdateHessian矩阵修正结构参数名参数名 含义含义Jacobian用户定义的目标函数的Jacobian矩阵JacobPattern有限差分的Jacobian矩阵的稀疏模式LargeScale使用大型算法(如果可能的话)Levenberg-Marquardt用Levenberg-Marquardt方法代替Gauss-Newton方法LineS

17、earchType一维搜索算法的选择MaxFunEvals允许进行函数评价的最大次数MaxIter允许进行迭代的最大次数MaxPCGIter允许进行PCG迭代的最大次数MeritFunction使用多目标函数MinAbsMax最小化最坏个案例绝对值的f(x)的个数PrecondBandWidthPCG前提的上带宽TolCon违背约束的终止容限TolFun函数值的终止容限TolPCGPCG迭代的终止容限TolXX处的终止容限TypicalX典型x值（三）参数设置（三）参数设置 对于优化控制，Matlab 提供了18个参数。利用optimset 函数，可以创建和编辑参数结构；利用optimget

18、函数，可以获得 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)opt

19、ions(9)若需要检测用户提供的梯度,则设为1options(10)函数和约束估值的数目options(11)函数梯度估值的个数options(12)约束估值的数目options(13)等式约束条件的个数options(14)函数估值的最大次数(默认值为100变量个数)options(15)用于多目标规划问题中的特殊目标options(16)优化过程中变量的最小有限差分梯度值options(17)优化过程中变量的最大有限差分梯度值options(18)步长设置(默认为1或更小)1. 参数值参数值2. optimset 函数函数 optimset 函数的功能是创建或编辑优化选项参数结构。具体的

20、调用格式为： options=optimset( param1,value1, param2, value2, ) options=optimset( oldopts,param1, value1, ) 功能：功能：创建一个称为options 的优化选项参数，其中指定的参数具有指定值。所有未指定的参数都设置为空矩阵 （将参数设置为 表示当options传递给优化函数时给参数赋默认值赋默认值）。赋值时只要输入参数前面的字母就行了。 功能：功能：创建一个oldopts的复制，用指定的数值修改参数。 options=optimset ( oldopts,newopts ) 功能：功能：将已经存在的选

21、项结构 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: functi

22、on | 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( opt

23、imfunction ) 功能：功能：创建一个含有所有参数名和与优化函数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: G

24、oalsExactAchieve: optnew=optimset(options,TolX,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

25、)例例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的优化参数。具体的调

26、用格式为： val=optimget( options, name ) val=optimget ( options, name,default ) 功能：功能：返回优化参数options中指定的参数的值。只需要用参数开头的字母来定义参数就行了。 功能：功能：若options结构参数中没有定义指定参数，则返回默认值。注意，这种形式的函数主要用于其它优化函数。 设置了参数options后就可以用上述调用形式完成指定任务了。val=optimget(options,Display)例例5 val =notifyoptnew=optimget(options,Display,final)例例6 op

27、tnew =notify如果显示参数没有定义，则返回值final。（四）模型输入时需要注意的问题（四）模型输入时需要注意的问题 使用优化工具箱时，由于优化函数要求目标函数和约束条件满足一定的格式，所以需要用户在进行模型输入时注意以下几个问题：1. 目标函数最小化 优化函数fminbnd、fminsearch、fminunc、fminicon、fgoalattain、fminmax和lsqnonlin都要求目标函数最小化，如果优化问题要求目标函数最大化，可以通过使该目标函数的负值最小化即-f (x)最小化来实现。近似地，对于quadprog函数提供-H和-f，对于linprog函数提供-f。3.

28、避免使用全局变量2.约束非正 优化工具箱要求非线性不等式约束的形式为Ci(x) 0,通过对不等式取负可以达到使大于零的约束形式变为小于零的不等式约束形式的目的，如 Ci(x) 0形式的约束等价于-Ci(x) 0 ；Ci(x)b形式的约束等价于-Ci(x) +b0。 在Matlab语言中，函数内部定义的变量除特殊声明外均为局部变量，即不加载到工作空间中。如果需要使用全局变量，则应当使用命令global定义，而且在任何时候使用该全局变量的函数中都应该加以定义。在命令窗口中也不例外。当程序比较大时，难免会在无意中修改全局变量的值，因而导致错误。更糟糕的是，这样的错误很难查找。因此，在编程时应该尽量避

29、免使用全局变量。（五）函数（五）函数 Matlab6.0以后的版本中可以用函数进行函数调用函数调用。函数返回指定Matlab函数的句柄，其调用格式为： handle= function 利用函数进行函数调用的好处：u用句柄将一个函数传递给另一个函数；u减少定义函数的文件个数；u改进重复操作；u保证函数计算的可靠性。fhandle=humps;例例7 x = 0.6370 x=fminbnd(fhandle,0,1)为 humps 函数创建一个函数句柄，并将它指定为 fhandle 变量。传递句柄给另一个函数，也将传递所有变量。x=fminbnd(humps,0,1)x=fminbnd(hump

30、s,0,1)或或（六）优化算法介绍（六）优化算法介绍 参数优化就是求一组设计参数 x=(x1,x2,xn)，以满足在某种意义下最优。一个简单的情况就是对某依赖于 x 的问题求极大值或极小值。复杂一点的情况是欲进行优化的目标函数 f (x) 受到以下限定条件：1. 参数优化问题参数优化问题( )0,1,2,iec xim 等式约束条件：等式约束条件： 不等式约束条件：不等式约束条件：( )0,1,iec ximm 参数有界约束：参数有界约束：LbxUb. .( )0,1,2,( )0,1, ,.ieiestc ximc ximmLbxUb这类问题的一般数学模型为：min( )nx Rf x 要有

31、效而且精确地解决这类问题，不仅依赖于问题的大小即约束条件和设计变量的数目，而且依赖目标函数和约束条件的性质。线性规划二次规划非线性规划能得到可靠的解一般是通过求解线性规划、二次规划或无约束优化的子问题来解决。2. 无约束优化问题无约束优化问题 搜索法搜索法是对非线性或不连续问题求解的合适方法，当欲优化的函数具有连续一阶导数时，梯度法梯度法（一个简单的方法是沿负梯度方向搜索）一般说来更为有效，高阶法高阶法（例如Newton法）仅实用于目标函数的二阶信息能计算出来的情况。 拟Newton法 在使用梯度信息的方法中，最为有效的方法是拟Newton方法。此方法的实质是建立每次迭代的曲率信息，以此来解决

32、如下形式的二次模型问题：1min( )2nTTx Rf xx Hxb xc其中H为目标函数的Hessian矩阵，H对称正定，b为常数向量，c为常数。最优解为：*1.xH b 多项式近似 对应于拟Newton法， Newton法法直接计算H，并使用线搜索策略沿下降方向经过一定次数的迭代后确定最小值，为了得到矩阵 H 需要经过大量的计算；拟拟Newton法法则不同，它通过使用 f (x)和它的梯度来修正 H 的近似值常用的拟Newton法（ Hessian矩阵修正方法）BFGS方法DFP方法 该法用于目标函数比较复杂的情况。在这种情况下寻找一个与它近似的函数来代替目标函数，并用近似函数的极小点作为

33、原函数极小点的近似。常用的近似函数为二次多项式和三次多项式。 二次内插的一般问题是，在定义域空间给定三个点x1，x2，x3和它们所对应的函数值 f (x1)，f (x2)，f (x3)，由二阶匹配得出最小值点如下：u 二次内插2313121231231312123()()()12()()()kf xf xf xxf xf xf x极值点：二次函数：此点可能是最小值或最大值点。当执行内插或a为正时是最小值。只要利用三个梯度或者函数方程组即可确定系数a和b，从而可确定x*。得到该值以后，进行搜索区间的收缩。22, , 2,3,3,1,1,2ijijijijxxxxi j2( )f xaxbxc*2

34、bxa 其中 三次插值的基本思想和二次插值一致，它是用用4个已知个已知点点构造一个三次多项式来逼近目标函数，同时以三次多项式的极小点作为目标函数极小点的近似。u 三次插值 三次插值法需要计算目标函数的导数，优点是计算速度快。同类的方法还有Newton切线法、对分法、割线法等。优化工具箱中使用的比较多的是三次插值法。 二次插值法的计算速度比黄金分割搜索法快，但是对于一些强烈扭曲或者可能多峰的函数，这种方法的收敛速度变得很慢，甚至失败。 一般来讲，三次插值法比二次插值法的收敛速度快，但是每次迭代需要计算两个导数值。 如果导数容易求得，一般来说首先考虑使用三次插值法，因为它具有较高的效率，对于只需要

35、计算函数值的方法中，二次插值是一个很好的方法，它的收敛速度较快，在极小点所在的区间较小时尤其如此。黄金分割法是一种十分稳定的方法，并且计算简单。由于上述原因， Matlab优化工具箱中较多地使用二次插值法、三次插值法以及二优化工具箱中较多地使用二次插值法、三次插值法以及二次三次混合插值法和黄金分割法次三次混合插值法和黄金分割法。三次插值法的迭代公式为：12112121222112()()()()3,()()f xf xf xf xxxf xf x 其中2211221212()()()()2kf xxxxxf xf x3. 拟拟Newton法实现法实现 在函数 fminunc 中使用拟 Newt

36、on 法，算法的实现过程包括两个阶段： 确定搜索方向 搜索方向的选择由选择 BFGS 方法还是选择 DFP 方法来决定，在优化工具箱中，通过将 options 参数 HessUpdate设置为 BFGS 或 DFP 来确定搜索方向。 Hessian 矩阵 H 总是保持正定的，使得搜索方向总是保持为下降方向。这意味着，对于任意小的步长，在上述搜索方向上目标函数值总是减小的。只要 H 的初始值为正定并且计算出的 qkTsk 总是正的，则 H 的正定性得到保证。并且只要执行足够精度的线性搜索， qkTsk 为正的条件总能得到满足。 要确定搜索方向首先必须完成 Hessian 矩阵的修正。Newton

37、 法由于需要多次计算 Hessian 矩阵，所以计算量很大。拟 Newton 法通过构建一个 Hessian 矩阵的近似矩阵来避开这个问题。 线性（一维）搜索过程 另外，在三次插值法中，每一个迭代周期都要进行梯度和函数的计算。 在优化工具箱中有两种线性搜索方法可以使用，这取决于梯度信息是否可以得到。当梯度值可以直接得到时，默认情况下使用三次多项式方法；当梯度值不能直接得到时，默认情况下，采用混合二次和三次插值法。4. 最小二乘优化最小二乘优化 前面介绍了函数 fminunc 中使用的是在拟 Newton 法中介绍的线性搜索法，在最小二乘优化程序 lsqnonlin 中也部分地使用这一方法。最小

38、二乘问题的优化描述如下： 在实际应用中，特别是数据拟合时存在大量这种类型的问题，如非线性参数估计等。控制系统中也经常会遇到这类问题，如希望系统输出的 y (x,t) 跟踪某一个连续的期望轨迹，这个问题可以表示为：212min( ( , )( )tty x ttdt1( )( )( )2minnTx Rf xr xr x21min( )( ( , )( )( )( )mTiiiF xy x ttr xr x将问题离散化得到： 最小二乘问题的梯度和 Hessian 矩阵具有特殊的结构，定义 r (x)的 Jacobian 矩阵为J(x)，则 F (x)的梯度和F(x) 的Hessian 矩阵定义为

39、：其中1( )( )( )miiiQ xr x H x( )2 ( )( )( )2 ( )( )2 ( )TTF xJ xr xH xJ xJ xQ x22min()()kkkJ x dr x GaussNewton法 在GaussNewton法中，每个迭代周期均会得到搜索方向d。它是最小二乘问题的一个解。GaussNewton法用来求解如下问题： 当Q(x)很大时，GaussNewton法很难得到问题的解，在这种情况下，LevenbergMarquadt方法显得更有效。()()()()TTkkkkkkJ xJ xI dJ xr x LevenbergMarquadt法 LevenbergM

40、arquadt法使用的搜索方向是一组线性等式的解：5. 非线性最小二乘实现非线性最小二乘实现 GaussNewton实现 GaussNewton法是用前面求无约束问题中讨论过的多项式线性搜索策略来实现的。使用Jacobian矩阵的QR分解，可以避免在求解线性最小二乘问题中等式条件恶化的问题。 这种方法中包含一项鲁棒性检测技术，这种技术步长低于限定值或当Jacobian矩阵的条件数很小时，将改为使用LevenbergMarquadt法。 这种实现方法在大量非线性问题中得到了成功的应用，并被证明比GaussNewton法具有更好的鲁棒性，比无约束条件方法具有更好的迭代效率。在使用lsqnonlin

41、函数时，函数所使用的默认算法是LevenbergMarquadt法。当options(5)=1时，使用GaussNewton法。 LevenbergMarquadt实现 实现LevenbergMarquadt方法的主要困难是在每一次迭代中如何控制的大小的策略问题，这种控制可以使它对于宽谱问题有效。这种实现的方法是使用线性预测平方总和和最小函数值的三次插值估计，来估计目标函数的相对非线性，用这种方法的大小在每一次迭代中都能确定。6. 约束优化约束优化 在约束最优化问题中，一般方法是先将问题变换为较容易的子问题，然后再求解。前面所述方法的一个特点是可以用约束条件的罚函数将约束优化问题转化为基本的无

42、约束优化问题，按照这种方法，条件极值问题可以通过参数化为无约束优化序列来求解。但这些方法效率不高，目前已经被通过求解求解KuhnTucker方程方程的方法所取代。 KuhnTucker方程是条件极值问题的必要条件必要条件。如果欲解决的问题是所谓的凸规划问题，那么KuhnTucker方程有解是极值问题有全局解的充分必要条件。 求解KuhnTucker方程是很多非线性规划算法的基础，这些方法试图直接计算Lagrange乘子。因为在每一次迭代中都要求解一次QP子问题，这些方法一般又被称为逐次逐次（或序列）二次规划（或序列）二次规划（SQP）方法）方法。这个问题可以通过任何求解二次规划问题的算法求解。

43、 使用序列二次规划方法，非线性约束条件的极值问题经常可以比无约束优化问题用更少的迭代得到解。造成这种现象的一个原因是：受到可行域的限制，这种方法更可能得到恰当的搜索方向和迭代步长。1( , )( )( )miiiL xf xc x 给定一个约束最优化问题，求解的基本思想是基于Lagrange函数的二次近似求解二次规划子问题：1min()2TTkkd H df xd从而得到二次规划子问题：. .( )( )0,1,( )( )0,1, .TiieTiiestc xdc xiEmc xdc xiImm7. SQP实现实现 在每一次迭代中，均作Lagrange函数的Hessian矩阵的正定拟Newt

44、on 近似，通过BFGS方法进行计算。Matlab工具箱的SQP实现由三个部分组成：u修正Lagrange函数的Hessian矩阵u二次规划问题求解u线性搜索 修正Hessian矩阵用BFGS公式修正Hessian矩阵：（略） 此算法要求有一个合适的初始值，如果由逐次二次规划方法得到的当前计算点是不合适的，则通过求解下述线性规划问题可以得到合适的计算点：如果上述问题存在要求的点，就可以通过将 x 赋值为满足等式条件的值来得到。 求解二次规划问题 初始化 在逐次二次规划方法中，每一次迭代都要解一个二次规划问题：. .s tAxbAeq xbeq1min2TTxx H xfx. .s tAxbAe

45、q xbeq,minnR x R三、无约束优化问题三、无约束优化问题（一）一维优化问题（一）一维优化问题1. 数学原理及模型数学原理及模型 一般的优化问题，因受多种因素的影响与制约，目标函数一般都是多元函数，称为多维优化问题。求解多维优化问题，常常化为逐步的沿某一方向求单元函数的极值问题，也就是一维搜索问题，在这里称为一维优化问题。一维搜索方法的好坏直接影响到优化算法的求解速度。 一维搜索的直接目的是寻求单变量函数的极小点，在理论上，一维搜索主要是作为求多变量函数的极小点的手段而进行研究的。然而，在实际应用中，很多问题都需要直接使用一维搜索的方法，如工程中常见的参数反演问题。应该指出，所选用的

46、一维搜索方法是否得当，常常对于整个计算的进程的影响极大。 数学模型一维优化问题的数学模型为： 对于一维优化问题来说，由于问题本身比较简单，可选择的方法也比较多。比较经典的方法有：进退法、Fibonacci法（也叫分数法）、黄金分割法（也叫0.618法）、试位法以及各种插值法。一般来说，对于形态比较好、比较光滑的函数可以使用插值法插值法，这样可以较快地逼近极小点；而对于形态比较差的函数，则可以使用黄金分黄金分割法割法。这也是Matlab优化工具箱中的库函数使用的两种方法。 算法介绍12min( ),x Rf xxxx2. Matlab工具箱中的基本函数工具箱中的基本函数 在Matlab中，一维优

47、化问题，也就是一维搜索问题的一维搜索问题的实现是由函数实现是由函数fminbnd来实现的来实现的。 应当注意：该函数所求的目标函数必须是连续的，并且只用于实数变量。同时该函数只能给出目标函数的局部最优解。对于问题的解位于区间边界上的情况，此函数收敛速度非常慢。具体的调用格式如下： x=fminbnd( fun，x1，x2 ) 功能：功能：返回在区间(x1，x2)中标量函数fun的最小值点。 x=fminbnd( fun，x1，x2，options ) 功能：功能： 用options参数指定的优化参数进行最小化，其中， options可取值为： Display ，TolX，MaxFunEval，

48、MaxIter，FunValCheck，和OutputFcn。options参数参数 含义含义Display显示的水平：为off时，不显示输出；为iter时，显示每一步迭代输出；为final时，显示最终结果。TolX在点x处的终止容限MaxFunEval函数评价的最大允许次数MaxIter最大允许迭代次数FunValCheck检查非法函数值OutputFcn可加载输出函数名options 参数各个取值的含义如下表所示： x，fval =fminbnd( ) 功能：功能：同时返回解x和在点x处的目标函数值。exitflag值值 含义含义 1函数收敛到目标函数最优解处 0达到最大迭代次数或达到函数

49、评价 -1算法由输出函数终止 -2下界大于上界exitflag值和相应的含义如下表所示： x，fval，exitflag=fminbnd( ) 功能：功能：同时返回解 x 和在点 x 处的目标函数值。另外，返回 exitflag 值，描述极小化函数的退出条件。output结构值结构值含义含义output.iterations迭代次数output.funcCount函数评价次数output.algorithm所用的算法output包含的内容和相应的含义如下表所示： x，fval，exitflag，output=fminbnd( ) 功能：功能：返回同上述格式的值。另外，返回包含output结构的

50、输出。例例8 fminbnd 演示。x=fminbnd(cos,3,4)x = 3.1416x,fval,exitflag=fminbnd(cos,3,4,optimset(TolX,1e-12, Display,off)x = 3.1416fval = -1exitflag =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 = 4fval = -5在命令窗口中输入：例例10 带参数优化问题。function f=ex1

51、0(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 t

52、o give the objective function %This is a function to calculate the volumef=-(5-2*x).2*x;编辑如下 M 文件 ex11.m ：例例11 容积最大化问题。对边长为 5m 的正方形钢板，在 4 个角处剪去相等的正方形以制成方形无盖的容器，问如何剪去使得容器的容积最大？假设剪去的正方形的边长为 x，则容器的容积计算公式为：xxxg2)25()(xxxf2)25()(这里需要将最大化问题转化为最小化问题，目标函数为：x,fval,exitflag,output=fminbnd(ex11,0,1.5)x = 0.833

53、3fval = -9.2593exitflag = 1output = iterations: 8 funcCount: 9 algorithm: golden section search, parabolic interpolation message: 1x112 char在命令窗口中输入：（二）无约束非线性规划问题（二）无约束非线性规划问题1. 数学原理及模型数学原理及模型 无约束最优化是一个十分古老的课题，至少可以追溯到 Newton 发明微积分的时代。无约束最优化问题在实际应用中也非常常见，另外，许多约束优化问题也可以转化成无约束优化问题求解，所以，无约束优化问题还是十分重要的。

54、由于简单的无约束线性问题非常容易，这里提到的无约束最优化问题就是指无约束非线性规划问题。 数学模型 设 f (x)是一个定义在 n 维欧式空间上的函数。把寻找f (x)的极小点的问题称为一个无约束最优化问题，这个问题可以用下列形式表示：12min( ),( ,)Tnnf xxx xxR 算法介绍u最速下降法：适用于变量不多的问题；uNewton法u变尺度法(也称为拟Newton法)u信赖域方法uPowell直接方法u共轭梯度法 直接搜索法 直接搜索法适用于目标函数高度非线性，没有导数适用于目标函数高度非线性，没有导数或导数很难计算的情况或导数很难计算的情况，由于实际工程中很多问题都是非线性的，

55、直接搜索法不失为一种有效的解决办法。常用的直接搜索法为单纯形法，其缺点是收敛速度慢。 在函数的导数可求函数的导数可求的情况下，梯度法是一种更优的方法，该法利用函数的梯度（一阶导数）和Hessian矩阵（二阶导数）构造算法，可以获得更快的收敛速度。函数 f (x)的负梯度方向- f (x)即反映了函数的最大下降方向。当搜索方向取为负梯度方向时称为最速下降法。当需要最小化的函数有一狭长的谷形值域时，该法的效率很低。 常用的梯度法有最速下降法、Newton 法、Marquadt法、共轭梯度法和拟 Newton 法等。 梯度法a) Hessian矩阵的修正l 确定搜索方向l 一维搜索阶段 在所有这些方

56、法中，用得最多的是拟拟Newton法法。拟Newton法包括两个阶段，即 Newton法由于需要多次计算Hessian矩阵，计算量很大，而拟Newton法则通过构建一个Hessian矩阵的近似矩阵来避开这个问题。 在优化工具箱中，通过将options参数 HessUpdate设置为 BFGS或DFP来决定搜索方向。 当Hessian矩阵H始终保持正定的，搜索方向就总是保持为下降方向。 Hessian矩阵的修正方法很多，对于求解一般问题， BFGS法是最有效的。 另一个有名的方法是DFP法。作为初值， H0可以设为任意对称正定矩阵。b) 一维搜索 若用户在fun函数中提供梯度信息，则缺省时函数将

57、选择大型优化算法，该算法是基于内部映射Newton法的子空间置信域法。计算中的每一次迭代涉及到用PCG法求解大型线性系统得到的近似解。 工具箱中有两套方案进行一维搜索。当梯度值可以直接得到时，用三次插值的方法进行一维搜索，当梯度值不能直接得到时，采用二次、三次混合插值法。Matlab的库函数中使用的方法为变尺度法和信赖域方法。大型优化算法：大型优化算法： 缺省时的一维搜索算法，当options.LineSearchType 设置为quadcubic时，将采用二次和三次混合插值法。将options.LineSearchType 设置为cubicpoly时，将采用三次插值法。第二种方法需要的目标函

58、数计算次数更少，但梯度的计算次数更多。这样，如果提供了梯度信息，或者能较容易地算得，则三次插值法是更佳的选择。中型优化算法：中型优化算法： 此时fminunc函数的参数options.LargeScale设置为off。该算法采用的是基于二次和三次混合插值一维搜索法的BFGS拟Newton法。该法通过BFGS公式来修正Hessian矩阵。通过将HessUpdate参数设置为dfp，可以用DFP公式来求得Hessian矩阵逆的近似。通过将HessUpdate参数设置为steepdesc，可以用最速下降法来更新Hessian矩阵。但一般不建议使用最速下降法。2. Matlab工具箱中的基本函数工具箱

59、中的基本函数 在Matlab优化工具箱函数中，有以下两个函数用来求解上述问题。 fminunc、fminsearch具体的调用格式如下： x= fminunc( fun，x0 ) 功能：功能：给定起始点x0，求函数fun的局部极小点x。其中， x0 可以是一个标量、向量或者矩阵。 fminunc x= fminunc( fun，x0，options ) 功能：功能：用options参数指定的优化参数进行最小化，其中， options可取值为：Display，TolX，TolFun，Derivativecheck，Diagnostics，FunValCheck，GradObj，HessPatte

60、rn， Hessian，HessMult，HessUpdate，InitialHessType，InitialHessMatrix，MaxFunEvals， MaxIter， DiffMinChange和DiffMaxChange， TypicalX ， LargeScale，MaxPCGIter， PrecondBandWidth， TolPCG x，fval= fminunc( fun，x0， ) 功能：功能：同时返回解x和在点x处的目标函数值。 x，fval ，exitflag= fminunc( fun，x0， ) 功能：功能：同时返回解x和在点x处的目标函数值。另外，返回exitfl