第二章 优化问题与计算.doc

第二章 优化问题与计算 我们在Matlab6.5软件包中讨论问题。2.1 Matlab内部优化命令（1） fminbnd 此命令的功能是在一个指定的区间中求一元函数f(x)极小值。调用的格式如下：x = fminbnd( fun, a, b)x = fminbnd( fun, a, b, options )x = fminbnd( fun, a, b, options, P1, P2, . )或者 x, fval = fminbnd(.) x, fval, exitflag = fminbnd(.) x, fval, exitflag, output = fminbnd(.)解释（1.1） x = fminbnd( fun,a, b )为基本调用格式, 功能是在一个指定的区间中求一元函数f(x)极小值。 x = fminbnd( fun, a, b, options )表示添加选项options的调用格式，选项options的参数在函数optimiset中定义，例如，是输出每次迭代的细节（此时选择iter），还是仅仅输出最后的结果（此时选择final），另外，还可以选择最大的迭代次数等等；如果没有选项，则可以令options= 。 x = fminbnd( fun, a, b, options, P1, P2,.)中的P1, P2，是目标函数中的其它参变量。解释（1.2） x,fval = fminbnd(.) 表示显示计算结果中的解x和解x处的目标函数值fval。 x,fval,exitflag = fminbnd(.)表示显示计算结果中的解x和解x处的目标函数值fval，以及返回指标exitflag，表示目标函数收敛到解x；表示已经达到规定的最高迭代次数；表示目标函数不收敛。 x,fval,exitflag,output = fminbnd(.) 表示除了显示（2）中返回结果以外，还要返回“output”项目中的内容，包括被使用的算法、目标函数被计算的次数、迭代的次数等等。解释（1.3） x = fminbnd(myfun,x0)表示调用自定义函数myfun作为目标函数。 可以利用inline函数直接定义一元目标函数。例如，在区间中求目标函数的最小值。首先写一个名字为opt_fminbnd_1的M文件：f = inline(x.3-2*x-5);x,fval,exitflag,output = fminbnd(f, 0, 2)存盘后按F5键执行，得到结果：x = 0.8165fval = -6.0887exitflag = 1output = iterations: 9 funcCount: 11algorithm: golden section search, parabolic interpolation其中，“iterations: 9”表示共迭代9次，“funcCount: 11”表示目标函数被计算11次，“algorithm: golden section search, parabolic interpolation ”表示所使用的算法是黄金分割搜索与抛物内插值方法。（2）fminsearch 此命令的功能是求解多元函数的极小值，它使用的是参考文献2中介绍的单纯形方向搜索法（the simplex direct search method）。调用格式是：x = fminsearch(fun,x0)x = fminsearch(fun,x0,options)x = fminsearch(fun,x0,options,P1,P2,.)或者x,fval = fminsearch(.)x,fval,exitflag = fminsearch(.)x,fval,exitflag,output = fminsearch(.)解释（2.1） fminsearch 主要解决无约束、非线性的多元函数的极小优化问题。 x = fminsearch(fun,x0) 表示以x0为起点求解函数fun的局部极小值x，其中 x0 可以是数值、向量和矩阵。 x = fminsearch(fun,x0,options) 表示带有选项options的优化问题，目标函数是 fun，起点是x0，其中选项options 可以在函数optimiset中设定。 x = fminsearch(fun,x0,options,P1,P2,.) 中的P1, P2，是目标函数中的其它参变量。 返回形式有如下几种：x,fval = fminsearch(.) 、x,fval,exitflag = fminsearch(.) 、x,fval,exitflag,output = fminsearch(.)。 还可以调用M文件中的函数myfun，调用格式如下：x = fminsearch(myfun,x0,A,b)如果是一元目标函数，可以直接使用inline函数设定，格式如下：x = fminsearch(inline(sin(x*x),x0,A,b);Other arguments are described in the syntax descriptions above. 例2.1 多元优化问题有一个著名的Rosenbrock 香蕉函数：在范围内，f的图像如下：在范围内，f的图像如下：其最小值在（x，y）（1，1）处达到，最小值是0。通常的搜索起点是(-1.2,1)。以下在Matlab6.5中求解：第一步 写一个名字为 banana 的M文件：function f = banana(x)f = 100*(x(2)-x(1)2)2+(1-x(1)2;第二步 调用banana 函数求解：x,fval = fminsearch(banana,-1.2, 1)得到：x = 1.0000 1.0000fval = 8.1777e-010即，Matlab6.5求得的解为（x, y）=(1, 1), fval = 。例2.2 求下列函数的最小值。首先写一个名字为humps的M文件，在这个文件中定义一个名字为humps的函数：function y = humps(x)y = 1./(x-.3).2 + .01) + 1./(x-.9).2 + .04) - 6;存盘后，再写一个名称为opt_humps_1的M文件：x = 0:.002:1;y = humps(x);plot(x,y)其中“x = 0:.002:1;”表示x从0到1每隔0.001取一个值计算。存盘后按F5键执行，得到图像如下：我们发现在x=0.5的附近函数有极小值，于是，计算如下：p,fval,exitflag,output = fminsearch(humps,0.5)执行后得到结果为：x = 0.6370fval = 11.2528exitflag = 1output = iterations: 12 funcCount: 24 algorithm: Nelder-Mead simplex direct search这说明x = 0.6370是极小值点，函数在此点的极小值为fval =11.2528。其中“algorithm: Nelder-Mead simplex direct search”表示所使用的算法为Nelder-Mead单纯形方向搜索法。（3）fzero 此命令的功能是寻找一元函数的零点，搜索所依据的理论方法来自于参考文献3、4。命令的调用格式如下：x = fzero(fun,x0)x = fzero(fun,x0,options)x = fzero(fun,x0,options,P1,P2,.)x,fval = fzero(.)x,fval,exitflag = fzero(.)x,fval,exitflag,output = fzero(.)解释（3.1）x = fzero(fun,x0) 表示在x0附近搜索函数fun的零点。x = fzero(fun,x0,options) 表示带有选项options的格式，没有选项时，或者不写，或者写成options = 。x = fzero(fun,x0,options,P1,P2,.) 带有多个选项的格式。 x,fval = fzero(.) 表示同时返回搜索得到的解x和函数在x点的值。 x,fval,exitflag = fzero(.) 增加了返回提示exitflag：exitflag0，表示搜索得到零点x。exitflag0，0，0表示函数收敛到解x；Exitflag0表示算法在计算时超过了最大迭代上限；Exitflag0表示函数不收敛到解x 。参数Lambda 表示Lagrange 乘子所涉及到的结构。可能的解构有下列四种： Lower：表示具有下界lbUpper：表示具有上界ubIneqlin：表示具有线性不等式约束Eqlin：表示具有线性等式约束输出项Output 包含最优化过程的信息内容，有以下几个方面：Iterations： 迭代的次数Algorithm：所用的算法Cgiterations：当使用大尺度法时，PCG 的迭代次数Firstorderopt：当使用大尺度法时，首序最优性的度量（Measure of first-order optimality）。对于大尺度有界约束问题，首序最优性是v.*g的无穷平均，此处v被定义为盒子约束（where v is defined as in Box Constraints），g是梯度。 对于带有线性等式约束的大尺度问题，首序最优性是导出前提共轭梯度的标量剩余z = Mr的2-平均（参考前提共轭梯度算法或线性约束问题算法）。Medium-Scale and Large-Scale Algorithms：表示在计算中允许同时使用中尺度与大尺度算法。Diagnostics：输出被极小化函数的检验信息。Display：输出指标。取值 off 时没有输出；取值 iter 时输出每次迭代的详细信息；取值 final 时只输出最后结果。MaxIter：允许迭代的最高次数。Large-Scale Algorithm Only：表示在计算中只允许使用大尺度算法。 例2.12 考虑下列优化问题：第一步，将其写为矩阵形式：其中第二步，在MatLab中写一个名称为opt_quadprog_1的M文件：H = 1 -1; -1 2 c = -2; -6A = 1 1; -1 2; 2 1b = 2; 2; 3lb = zeros(2,1)x,fval,exitflag,output,lambda = quadprog(H,f,A,b,lb)存盘后，按F5键执行，得到结果如下： x = 0.6667 1.3333fval = -8.2222exitflag = 1output = iterations: 3 algorithm: medium-scale: active-setfirstorderopt: cgiterations: lambda.ineqlinans = 3.1111 0.4444 0lambda.lowerans = 0 0其中的lambda输出项lambda.ineqlinans = 3.1111 0.4444 0表示问题中有三个不等式约束条件，利用乘子法求解，对应的三个乘子的值为3.111，0.4444；还有一个lambda输出项lambda.lowerans = 0 0表示问题中有两个等式约束条件，利用乘子法求解，对应的两个乘子的值都为0。例2.13 考虑下列优化问题：第一步，将其写为矩阵形式：其中第二步，在MatLab中写一个名称为opt_quadprog_2的M文件：H = 6 -1; -1 2 c= 0; 0.4A = -1.1 0.9; 0 1b = -1.1; 0.7Aeq=1 1Beq=1x,fval,exitflag,output = quadprog(H,c,A,b,Aeq,beq)存盘后，按F5键执行，得到结果如下：x = 0.66670.3333fval = 1.3556exitflag = 1output = iterations: 1algorithm: medium-scale: active-setfirstorderopt: cgiterations: 参考文献1 Forsythe, G. E., M. A. Malcolm, and C. B. Moler, Computer Methods for Mathematical Computations, Prentice-Hall, 1976.2 Lagarias, J.C., J. A. Reeds, M. H. Wright, and P. E. Wright, Convergence Properties of the Nelder-Mead Simplex Method in Low Dimensions, SIAM Journal of Optimization, Vol. 9 Number 1, pp. 112-147, 1998.3 Brent, R., Algorithms for Minimization Without Derivatives, Prentice-Hall, 1973. 4 Forsythe, G. E., M. A. Malcolm, and C. B. Moler, Computer Methods for Mathematical5 Lawson, C.L. and R.J. Hanson, Solving Least Squares Problems, Prentice-Hall, 1974, Chapter 23, p. 161.6 Coleman, T.F. and Y. Li, An Interior, Trust Region Approach for Nonlinear Minimization Subject to Bounds, SIAM Journal on Optimization, Vol. 6, pp. 418-445, 1996. 7 Coleman, T.F. and Y. Li, On the Convergence of Reflective Newton Methods for Large-Scale Nonlinear Minimization Subject to Bounds, Mathematical Programming, Vol. 67, Number 2, pp. 189-224, 1994. 8 Gill, P.E., W. Murray, and M.H. Wright, Practical Optimization, Academic Press, London, 1981. 9 Han, S.P., A Globally Convergent Method for Nonlinear Programming, Journal of Optimization Theory and Applications, Vol. 22, p. 297, 1977.10 Powell, M.J.D.,