第二章 优化问题与计算

《第二章 优化问题与计算》由会员分享，可在线阅读，更多相关《第二章 优化问题与计算（18页珍藏版）》请在装配图网上搜索。

1、第二章 优化问题与计算我们在Matlab65软件包中讨论问题。2.1 Matlab 内部优化命令(1) fminbnd此命令的功能是在一个指定的区间a, b中求一元函数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)

2、 x = fminbnd( fun,a, b )为基本调用格式，功能是在一个指定的区间la, b中求一元函数f(x)极小值。 x = fminbnd( fun, a, b, options )表示添加选项options的调用格式，选项options 的参数在函数optimiset中定义，例如，是输出每次迭代的细节(此时选择iter), 还是仅仅输出最后的结果(此时选择final)，另外，还可以选择最大的迭代次数 等等；如果没有选项，则可以令 options= 。 x = fminbnd( fun, a, b, options, Pl, P2,.)中的Pl, P2,是目标函数中的其它参 变量。解

3、释(1.2) x,fval = fminbnd(.)表示显示计算结果中的解x和解x处的目标函数值fval。 x,fval,exitflag = fminbnd(.)表示显示计算结果中的解x和解x处的目标函数 值fval,以及返回指标exitflag, exitflag 0表示目标函数收敛到解x； exitflag = 0表示已经达到规定的最高迭代次数；exitflag 0表示目标函数不收敛。 x,fval,exitflag,output = fminbnd(.) 表示除了显示(2)中返回结果以外，还 要返回“o utput ”项目中的内容，包括被使用的算法、目标函数被计算的次数、 迭代的次数等

4、等。解释(1.3) x = fminbnd(myfun,xO)表示调用自定义函数myfun作为目标函数。 可以利用 inline 函数直接定义一元目标函数。例如，在区间In,2中求目标函数f二x3-2x-5的最小值。首先写一个名字为opt_fminbnd_l 的 M一文件：f = inline(x.A3-2*x-5);x,fval,exitflag,output = fminbnd(f, 0, 2)存盘后按 F5 键执行，得到结果：x =0.8l65fval =-6.0887exitflag =loutput =iterations: 9funcCount: llalgorithm: gold

5、en 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,x

6、0)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,

7、options) 表示带有选项 options 的优化问题，目标函数是 fun,起点是xO,其中选项options可以在函数optimiset中设定。 x = fminsearch(fun,x0,options,Pl,P2,.)中的 Pl, P2,是目标函数中的其它参 变量。 返回形式有如下几种：x,fval = fminsearch(.) 、x,fval,exitflag = fminsearch(.) 、x,fval,exitflag,output = fminsearch(.)。还可以调用M一文件中的函数myfun,调用格式如下：x = fminsearch(myfun,xO,A,b)

8、如果是一元目标函数，可以直接使用inline函数设定，格式如下：x = fminsearch(inline(sin(x*x),xO,A,b); Other arguments are described in the syntax descriptions above.例 2.1一 X 2多元优化问题有一个著名的 Rosenbrock 香蕉函数：05505100101 10500000在-10 x 10, -10 y 10范围内，f的图像如下:30050.60.8其最小值在(X，y) = (1，1)处达到， 以下在Matlab6.5中求解：第一步 写一个名字为banana的M文件:10.811

9、.21.4最小值是0。通常的搜索起点是(-1.2,1)。0.6在0.5 x 1.5, 0.5 y 0，表示搜索得到零点X。exitflagvO,表示没有发现时的函数值符号正负变化的区间。Exitflag=NaN or Inf表示在搜索过程中，发现函数值符号正负变化的区间, 但没有找到零点，或者在函数值符号正负变化的区间中，零点是复数。 x,fval,exitflag,output = fzero(.)增加了更多的返回信息 output。例2.3在3的附近搜索sin(x)的零点。程序如下：x = fzero(sin,3) 执行后得到结果：x =3.l4l6例2.4在区间1, 2之间搜索函数cos

10、(x)的零点。程序如下：x = fzero(cos,l 2) 执行后得到结果：x =1.5708注意： cos(1) 和 cos(2) 符号不同。例2.5求一个自定义函数的零点。首先写一个名称为f.m的M文件： function y = f(x)y = x.A3-2*x-5;存盘后，寻找这个函数在 2 附近的零点。程序如下 z = fzero(f,2) 执行后得到结果：z =2.09464)fmincon此命令求解下列形式的有约束非线性极小问题：minc(x) 0ceq(x )= 0s.t.Ax bAeq.x = beqLb x Ub其调用格式如下：x = fmincon(fun,x0,A,b

11、)x = fmincon(fun,x0,A,b,Aeq,beq)x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub)x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2, .) 或者x,fval = fmincon(.)x,fval,exitflag = fmincon(.)x,fval,exitflag,outpu

12、t = fmincon(.)x,fval,exitflag,output,lambda = fmincon(.) x,fval,exitflag,output,lambda,grad = fmincon(.) x,fval,exitflag,output,lambda,grad,hessian = fmincon(.)例 2.6 求解下列问题：min f = x 2 * x * x 21 2 3x厂x + x + x 10s.t. 123解： 第一步x 2 x + x 1123将问题写为向量的形式minf = x 2 * x * x 2x123s.t.x2(x )1(10 ) 0s.t. x1

13、 + 2x2 + 2x3 7210、搜索起点为x二10。10丿首先，为目标函数写一个名称为opt_myfun_2的M一文件：function f = myfun(x) f = -x(1) * x(2) * x(3);将此文件存盘。第二步，将约束条件改写为的标准形式J - xl - 2x2 - 2x3 至 0| xl + 2x2 + 2x3 72将其写成矩阵形式：(x1 -1 - 2 - 2、(0 )x 222丿x3V 丿72丿第三步，写一个名称为opt_fmincon_2用于计算的M一文件: A=-l,-2,-2;l,2,2;B=0;72;x0 = l0; l0; l0;% Starting

14、guess at the solutionx,fval = fmincon(myfun,x0,A,b) 存盘后按F5键执行，得到最优解：x =24.0000l2.0000l2.0000 以及目标函数最小值 fval =-3.4560e+03 验算可知，所求最优解使得约束条件 0 ： A*x-b=-7202.2 无约束条件的极小问题例2.8考虑以下无约束极小问题：(、min imize f (x )= ex4 x 2 + 2 x 2 + 4 x x + 2 x +1l2l 22x第一步 创建一个名称为objfunl.m的目标函数的M一文件： function f = objfun(x)f = e

15、xp(x(1)*(4*x(1)人2+2*x(2)人2+4*x(1)*x(2)+2*x(2)+1);第二步调用Matlab软件包内部无约束优化函数fminunc,创建一个名称为 opt_1.m 的计算文件：x0 = -1,1;% Starting guessoptions = optimset(LargeScale,off); x,fval,exitflag,output = fminunc(objfun1,x0,options)其中x0=-1,1;表示初始迭代取值为x =-1,x = 1，输入不同的初始值，会得到不同的优化结果。% Starting guess是说明语句，意思为“初始假设” o

16、ptions 表示优化选项，LargeScale表示按大尺度法计算，of表示不显示计算过程。无约束优化函数fminunc(objfun1,x0,options)中的选项objfun1表示调用名称为objfun1.m的目标函数的M一文件，初始点选在x0处，按照options中规 定的选项计算。然后点击F5键，选择Run，即可得到计算结果：x =0.5000 -1.0000fval =1.3030e-10exitflag =1output =iterations: 7funcCount: 40stepsize: 1firstorderopt: 8.1997e-004algorithm: mediu

17、m-scale: Quasi-Newton line search其中， x = 0.5000-1.0000 表示以 x0 为起点开始搜索的局部极小点为x = 0.5,兀2 =-1，目标函数的极小值为 f 二 1.3030x 10-io u 0 (代入 Mathematica软件包中计算，结果为 0)， exitflag = 1 表示输出的解为局部极优解。2.3 非线性不等式约束的优化问题例2.9考虑以下具有非线性不等式约束的优化问题：、min imize f (x )= ex4 x 2 + 2 x 2 + 4 x x + 2 x +1 1 2 1 2 2-1.5x换如下：min imize

18、f(x)=ex1(4x2 +2x 2 +4x x +2x +1) 1 2 1 2 2xx x x x 1.5 0s.t. 1 212I- x x - 10 012I x x - x - xs.t. -1012此种优化问题我们要调用Matlab软件包内部有约束优化函数fmincon,根据函数fmincon的规定，需要将约束条件都化成C 0的形式，所以将原问题转第一步 创建一个名称为objfun1.m的目标函数的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);第二步 对约束条件编写一

19、个名称为confun2.m的M一文件:function c, ceq = confun(x)% Nonlinear inequality constraints c = 1.5 + x(1)*x(2) - x(1) - x(2);-x(1)*x(2) - 10;% Nonlinear equality constraints ceq = ;第三步 调用Matlab软件包内部有约束优化函数fmincon,创建一个名称为 opt_2.m 的计算文件：x0 = -1,1;% Make a starting guess at the solutionoptions = optimset(LargeSc

20、ale,off);x, fval = . fmincon(objfun1,x0,confun,options)运算后得到优化结果：x =-9.5474 1.0474 fval =0.0236这表示以x0为起点开始搜索的局部极优解为:x =(x ,x )=C 9.5474, 1.0474) f 二 f (x)= 0.0236min2.4 变量有界的有约束优化问题 第一步 创建一个名称为objfun1.m的目标函数的M文件：例2.10 考虑以下变量有界且具有非线性不等式约束的优化问题 min imize f C )=s.t. ex1 4x 2 + 2x 2 + 4x x + 2x +1 1 1 2

21、 1 2 2xx x - x - x -1012x 01x 02此种优化问题我们要调用Matlab软件包内部有约束优化函数fmincon,根 据函数fmincon的规定，需要将约束条件都化成C 0的形式，所以将原问题转 换如下ex1 Cx 2 + 2x 2 + 4x x + 2x +1)1 1 2 1 2 2 xx x - x - x +1.5 01 2 1 2 -x x -10012- x 01- x 0min imize f C )=s.t. 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

22、);第二步 对约束条件编写一个名称为confun2.m的M一文件：function c, ceq = confun(x)% Nonlinear inequality constraintsc = 1.5 + x(1)*x(2) - x(1) - x(2);-x(1)*x(2) - 10;% Nonlinear equality constraintsceq = ;第三步调用Matlab软件包内部无约束优化函数fmincon,创建一个名称为 opt_3.m 的计算文件：x0 = -1,1;% Make a starting guess at the solutionlb = 0, 0;% Set

23、 lower boundsub = ;% No upper boundsoptions = optimset(LargeScale,off);x,fval = . fmincon(objfun1,x0,lb,ub,confun,options)c, ceq = confun(x)运算后得到优化结果：x =0 1.5000fval =8.5000c =0-10ceq = 这表示以x0为起点开始搜索的局部极优解为：x = (x , x )=(0, 1.5)ff(X )= 8.5min其中c = 0 -10表示将极优解代入前面两个约束条件计算，两个约束条件分别取 值0和10。2.5 具有非线性等式约

24、束的优化问题例2.11 考虑以下具有非线性不等式约束的优化问题：min imize f (x ) =ex(4x 2 + 2x 2 + 4x x + 2x +1)1 2 1 2 2xx 2 + x 1 = 0 s.t. 12I x x 一 10 012我们同样调用 Matlab 软件包内部有约束优化函数 fmincon 解决此类问题。第一步 创建一个名称为objfun1.m的目标函数的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);第二步 对约束条件编写一个名称为confuneq4

25、.m的M一文件：function c, ceq = confuneq(x)% Nonlinear inequality constraintsc = x(1)*x(2) - 10;% Nonlinear equality constraintsceq = x(1)A2 + x(2) - 1;第三步 调用Matlab软件包内部有约束优化函数fmincon,创建一个名称为opt_4.m 的计算文件：x0 = -1,1;% Make a starting guess at the solutionoptions = optimset(LargeScale,off);x,fval = fmincon(

26、objfun1,x0,.confuneq,options)c,ceq = confuneq(x) % Check the constraint values at x运算后得到优化结果x =-0.75290.4332fval =1.5093 c =-9.6739 ceq =2.7010e-010这表示以 x0 为起点开始搜索的局部极优解为：x = (x ,x )= (一 0.7529, 0.4332) f = f (x)= 1.5093min其中 c = -9.6739 表示将极优解代入 c = -x(1)*x(2) - 10 取值为-9.6793, ceq = 2.7010e-010 表示将

27、极优解代入 ceq = x(1)A2 + x(2) - 1 取值为 2.7010 x 10-10。2.6 二次规划问题的求解我们考虑以下二次规划问题：min xtHx +x 2fTxA.x bs.t. Aeq.x = beqlb x ub最优解的调用格式如下：x = quadprog(H,f,A,b):表示x是下列问题min xtHx +x 2fTxs.t. A.x b的最优解x = quadprog(H,f,A,b,Aeq,beq):表示 x 是下列问题min 1 xtHx +x 2I A.x bs.t.彳Aeq.x = beq的最优解x = quadprog(H,f,A,b,Aeq,beq

28、,lb,ub):表示 x 是下列问题min 1 xtHx +x 2fTxA.xbst. Aeq.x = beq lb x ub的最优解x = quadprog(H,f,A,b,Aeq,beq,lb,ub,xO)：表示x是以x0为起点开始搜索，下列问 题min 1 xtHx +x 2fTxA.xbst. Aeq.x = beq lb x ub的最优解x = quadprog(H,f,A,b,Aeq,beq,lb,ub,xO,options):表示 x 是以 x0 为起点开始搜索, 并且带有选项 options 的下列问题min xtHx +x 2fTxA.x bs.t. Aeq.x = beq

29、lb x ub的最优解x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options,p,p2,.) ：表示 x 是以 x0 为起点开 始搜索，并且带有选项 options 的下列问题min xtHx +x 2fTxA.xbst. Aeq.x = beq lb x 0,=0, 0表示 函数收敛到解x； Exitflag=0表示算法在计算时超过了最大迭代上限；ExitflagvO 表示函数不收敛到解x。参数 Lambda 表示 Lagrange 乘子所涉及到的结构。可能的解构有下列四种： Lower:表示具有下界lbUpper:表示具有上界ubIneqli n：表示具

30、有线性不等式约束 Eqlin：表示具有线性等式约束输出项Output包含最优化过程的信息内容，有以下几个方面： Iterations：迭代的次数Algorithm :所用的算法Cgiterations：当使用大尺度法时，PCG的迭代次数 Firstorderopt :当使用大尺度法时，首序最优性的度量(Measure of first-order optimality)。对于大尺度有界约束问题，首序最优性是v.*g的无穷平均，此处v被 定义为盒子约束( where v is defined as in Box Constraints)， g 是梯度。对于带有线性等式约束的大尺度问题，首序最优性

31、是导出前提共轭梯度 的标量剩余z = Mr的2-平均(参考前提共轭梯度算法或线性约束问题算 法)。Medium-Scale and Large-Scale Algorithms：表示在计算中允许同时使用中尺度与 大尺度算法。Diagnostics :输出被极小化函数的检验信息。Display:输出指标。取值off时没有输出；取值iter时输出每次迭代的详细 信息；取值 final 时只输出最后结果。MaxIter :允许迭代的最高次数。Large-Scale Algorithm Only：表示在计算中只允许使用大尺度算法。例 2.12 考虑下列优化问题:min1=x 2 + x 2 - x x

32、 - 2 x - 6 x2 1 2 1 2 1 2x + x 21 2x + 2 x 2 s.t. 122 x + x 0 12第一步，将其写为矩阵形式:-xtHx + ctx其中1、2 :c=x=I x2丿(1H =-1第二步，在MatLab中写一个名称为opt_quadprog_1的M一文件: H = 1 -1; -1 2c = -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 键执行，得到结果如下:0.66671.

33、3333fval =-8.2222exitflag =1output =iterations: 3algorithm: medium-scale: active-setfirstorderopt: cgiterations: lambda.ineqlinans =3.11110.44440lambda.lowerans =00其中的 lambda 输出项lambda.ineqlinans =3.11110.44440表示问题中有三个不等式约束条件，利用乘子法求解，对应的三个乘子的值为 3.111，0.4444；还有一个 lambda 输出项lambda.lowerans =00 表示问题中有两

34、个等式约束条件，利用乘子法求解，对应的两个乘子的值都为0例 2.13 考虑下列优化问题：min f c) =3x2 + y 2 一 xy + 0.4y1.2x + 0.9y 1.1x + y = 1s.t. y 07、x,y无下界限制第一步，将其写为矩阵形式：2xthx+ctx其中r 6 -1)r 0、H=,c =I-1 2 丿 0.4 丿AX bAeqX = beq1) beq = 1Aeq = Gr x (1.2-.91 b =r-1.1、 0.7 丿第二步，在MatLab中写一个名称为opt_quadprog_2的M一文件: H = 6 -1; -1 2c= 0; 0.4A = -1.1

35、 -.9; 0 1b = -1.1; 0.7Aeq=1 1Beq=1x,fval,exitflag,output = quadprog(H,c,A,b,Aeq,beq) 存盘后，按 F5 键执行，得到结果如下：x = 0.66670.3333 fval = 1.3556 exitflag = 1output = iterations: 1algorithm: medium-scale: active-set firstorderopt: cgiterations: 参考文献1 Forsythe, G. E., M. A. Malcolm, and C. B. Moler, Computer M

36、ethods 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 Minimizati

37、on 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 No

38、nlinear 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,

39、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., A Fast Algorithm for Nonlineary Constrained Optimizati

40、on Calculations, Numerical Analysis, ed. G .A. Watson, Lecture Notes in Mathematics, Springer Verlag, Vol. 630, 1978.11 Powell, M.J.D., The Convergence of Variable Metric Methods For Nonlinearly Constrained Optimization Calculations, Nonlinear Programming 3, (O.L. Mangasarian, R.R. Meyer, and S.M. R

41、obinson, eds.) Academic Press, 1978.12 Coleman, T. F. and Y. Li, A Reflective Newton Method for Minimizing a Quadratic Function Subject to Bounds on some of the Variables, SIAM Journal on Optimization, Vol. 6, Number 4, pp. 1040-1058, 1996.13 Gill, P. E. and W. Murray, and M.H. Wright, Practical Optimization, Academic Press, London, UK, 1981.