第5章 优化问题

1、第5章 优化问题5.1 线性规划问题线性规划问题是目标函数和约束条件均为线性函数的问题，MATLAB6.0解决的线性规划问题的标准形式为：min sub.to： 其中f、x、b、beq、lb、ub为向量，A、Aeq为矩阵。其它形式的线性规划问题都可经过适当变换化为此标准形式。在MATLAB6.0版中，线性规划问题（Linear Programming）已用函数linprog取代了MATLAB5.x版中的lp函数。当然，由于版本的向下兼容性，一般说来，低版本中的函数在6.0版中仍可使用。函数 linprog格式 x = linprog(f,A,b) %求min f *x sub.to 线性规划的

2、最优解。x = linprog(f,A,b,Aeq,beq) %等式约束，若没有不等式约束，则A= ，b= 。x = linprog(f,A,b,Aeq,beq,lb,ub) %指定x的范围，若没有等式约束 ，则Aeq= ，beq= x = linprog(f,A,b,Aeq,beq,lb,ub,x0) %设置初值x0x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options) % options为指定的优化参数x,fval = linprog() % 返回目标函数最优值，即fval= f *x。x,lambda,exitflag = linprog() % lamb

3、da为解x的Lagrange乘子。x, lambda,fval,exitflag = linprog() % exitflag为终止迭代的错误条件。x,fval, lambda,exitflag,output = linprog() % output为关于优化的一些信息说明 若exitflag0表示函数收敛于解x，exitflag=0表示超过函数估值或迭代的最大数字，exitflagf = -5; -4; -6;A = 1 -1 1;3 2 4;3 2 0;b = 20; 42; 30;lb = zeros(3,1);x,fval,exitflag,output,lambda = linpro

4、g(f,A,b,lb)结果为：x = %最优解 0.0000 15.0000 3.0000fval = %最优值 -78.0000exitflag = %收敛 1output = iterations: 6 %迭代次数 cgiterations: 0 algorithm: lipsol %所使用规则lambda = ineqlin: 3x1 double eqlin: 0x1 double upper: 3x1 double lower: 3x1 double lambda.ineqlinans = 0.0000 1.5000 0.5000 lambda.lowerans = 1.0000 0

5、.0000 0.0000表明：不等约束条件2和3以及第1个下界是有效的5.2 非线性规划问题5.2.1 有约束的一元函数的最小值单变量函数求最小值的标准形式为 sub.to 函数 fminbnd格式 x = fminbnd(fun,x1,x2) %返回自变量x在区间上函数fun取最小值时x值，fun为目标函数的表达式字符串或MATLAB自定义函数的函数柄。x = fminbnd(fun,x1,x2,options) % options为指定优化参数选项x,fval = fminbnd() % fval为目标函数的最小值x,fval,exitflag = fminbnd() %xitflag为终

6、止迭代的条件x,fval,exitflag,output = fminbnd() % output为优化信息说明 若参数exitflag0，表示函数收敛于x，若exitflag=0，表示超过函数估计值或迭代的最大数字，exitflag x,fval,exitflag,output=fminbnd(x3+cos(x)+x*log(x)/exp(x),0,1)x = 0.5223fval = 0.3974exitflag = 1output = iterations: 9 funcCount: 9 algorithm: golden section search, parabolic interp

7、olation例5-3 在0，5上求下面函数的最小值解：先自定义函数：在MATLAB编辑器中建立M文件为：function f = myfun(x)f = (x-3).2 - 1;保存为myfun.m，然后在命令窗口键入命令： x=fminbnd(myfun,0,5)则结果显示为：x = 35.2.2 无约束多元函数最小值多元函数最小值的标准形式为其中：x为向量，如命令 利用函数fminsearch求无约束多元函数最小值函数 fminsearch格式 x = fminsearch(fun,x0) %x0为初始点，fun为目标函数的表达式字符串或MATLAB自定义函数的函数柄。x = fmins

8、earch(fun,x0,options) % options查optimsetx,fval = fminsearch() %最优点的函数值x,fval,exitflag = fminsearch() % exitflag与单变量情形一致x,fval,exitflag,output = fminsearch() %output与单变量情形一致注意：fminsearch采用了Nelder-Mead型简单搜寻法。例5-4 求的最小值点解：X=fminsearch(2*x(1)3+4*x(1)*x(2)3-10*x(1)*x(2)+x(2)2, 0,0)结果为X = 1.0016 0.8335或在M

9、ATLAB编辑器中建立函数文件function f=myfun(x)f=2*x(1)3+4*x(1)*x(2)3-10*x(1)*x(2)+x(2)2;保存为myfun.m，在命令窗口键入 X=fminsearch (myfun, 0,0) 或 X=fminsearch(myfun, 0,0)结果为：X = 1.0016 0.8335命令 利用函数fminunc求多变量无约束函数最小值函数 fminunc格式 x = fminunc(fun,x0) %返回给定初始点x0的最小函数值点x = fminunc(fun,x0,options) % options为指定优化参数x,fval = fmi

10、nunc() %fval最优点x处的函数值x,fval,exitflag = fminunc() % exitflag为终止迭代的条件，与上同。x,fval,exitflag,output = fminunc() %output为输出优化信息x,fval,exitflag,output,grad = fminunc() % grad为函数在解x处的梯度值x,fval,exitflag,output,grad,hessian = fminunc() %目标函数在解x处的海赛（Hessian）值注意：当函数的阶数大于2时，使用fminunc比fminsearch更有效，但当所选函数高度不连续时，使

11、用fminsearch效果较好。例5-5 求的最小值。 fun=3*x(1)2+2*x(1)*x(2)+x(2)2; x0=1 1; x,fval,exitflag,output,grad,hessian=fminunc(fun,x0)结果为：x = 1.0e-008 * -0.7591 0.2665fval = 1.3953e-016exitflag = 1output = iterations: 3 funcCount: 16 stepsize: 1.2353 firstorderopt: 1.6772e-007 algorithm: medium-scale: Quasi-Newton

12、line searchgrad = 1.0e-006 * -0.1677 0.0114hessian = 6.0000 2.0000 2.0000 2.0000或用下面方法： fun=inline(3*x(1)2+2*x(1)*x(2)+x(2)2)fun = Inline function: fun(x) = 3*x(1)2+2*x(1)*x(2)+x(2)2 x0=1 1； x=fminunc(fun,x0)x = 1.0e-008 * -0.7591 0.26655.2.3 有约束的多元函数最小值非线性有约束的多元函数的标准形式为：sub.to 其中：x、b、beq、lb、ub是向量，A

13、、Aeq为矩阵，C(x)、Ceq(x)是返回向量的函数，f(x)为目标函数，f(x)、C(x)、Ceq(x)可以是非线性函数。在MATLAB5.x中，它的求解由函数constr实现。函数 fmincon格式 x = fmincon(fun,x0,A,b)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,fval

14、= fmincon()x,fval,exitflag = fmincon()x,fval,exitflag,output = fmincon()x,fval,exitflag,output,lambda = fmincon()x,fval,exitflag,output,lambda,grad = fmincon()x,fval,exitflag,output,lambda,grad,hessian = fmincon()参数说明：fun为目标函数，它可用前面的方法定义；x0为初始值；A、b满足线性不等式约束，若没有不等式约束，则取A= ，b= ；Aeq、beq满足等式约束，若没有，则取Aeq

15、= ，beq= ；lb、ub满足，若没有界，可设lb= ，ub= ；nonlcon的作用是通过接受的向量x来计算非线性不等约束和等式约束分别在x处的估计C和Ceq，通过指定函数柄来使用，如：x = fmincon(myfun,x0,A,b,Aeq,beq,lb,ub,mycon)，先建立非线性约束函数，并保存为mycon.m：function C,Ceq = mycon(x)C = % 计算x处的非线性不等约束的函数值。Ceq = % 计算x处的非线性等式约束的函数值。lambda是Lagrange乘子，它体现哪一个约束有效。output输出优化信息；grad表示目标函数在x处的梯度；hess

16、ian表示目标函数在x处的Hessiab值。例5-6 求下面问题在初始点（0，1）处的最优解min sub.to 解：约束条件的标准形式为sub.to 先在MATLAB编辑器中建立非线性约束函数文件：function c, ceq=mycon (x)c=(x(1)-1)2-x(2);ceq= ; %无等式约束然后，在命令窗口键入如下命令或建立M文件：fun=x(1)2+x(2)2-x(1)*x(2)-2*x(1)-5*x(2); %目标函数x0=0 1;A=-2 3; %线性不等式约束b=6;Aeq= ; %无线性等式约束beq= ;lb= ; %x没有下、上界ub= ;x,fval,exit

17、flag,output,lambda,grad,hessian=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,mycon)则结果为x = 3 4fval = -13exitflag = %解收敛 1output = iterations: 2 funcCount: 9 stepsize: 1 algorithm: medium-scale: SQP, Quasi-Newton, line-search firstorderopt: cgiterations: lambda = lower: 2x1 double %x下界有效情况，通过lambda.lower可查看。 upp

18、er: 2x1 double %x上界有效情况，为0表示约束无效。 eqlin: 0x1 double %线性等式约束有效情况，不为0表示约束有效。 eqnonlin: 0x1 double %非线性等式约束有效情况。 ineqlin: 2.5081e-008 %线性不等式约束有效情况。 ineqnonlin: 6.1938e-008 %非线性不等式约束有效情况。grad = %目标函数在最小值点的梯度 1.0e-006 * -0.1776 0hessian = %目标函数在最小值点的Hessian值 1.0000 -0.0000 -0.0000 1.0000例5-7 求下面问题在初始点x=(

19、10, 10, 10)处的最优解。Min Sub.to 解：约束条件的标准形式为sub.to fun= -x(1)*x(2)*x(3); x0=10,10,10; A=-1 -2 -2;1 2 2; b=0;72; x,fval=fmincon(fun,x0,A,b)结果为：x = 24.0000 12.0000 12.0000fval = -34565.2.4 二次规划问题二次规划问题（quadratic programming）的标准形式为：sub.to 其中，H、A、Aeq为矩阵，f、b、beq、lb、ub、x为向量其它形式的二次规划问题都可转化为标准形式。函数 quadprog格式 x

20、 = quadprog(H,f,A,b) %其中H,f,A,b为标准形中的参数，x为目标函数的最小值。x = quadprog(H,f,A,b,Aeq,beq) %Aeq,beq满足等约束条件。x = quadprog(H,f,A,b,Aeq,beq,lb,ub) % lb,ub分别为解x的下界与上界。x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) %x0为设置的初值x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options) % options为指定的优化参数x,fval = quadprog() %fval为目标函数最优值x,f

21、val,exitflag = quadprog() % exitflag与线性规划中参数意义相同x,fval,exitflag,output = quadprog() % output与线性规划中参数意义相同x,fval,exitflag,output,lambda = quadprog() % lambda与线性规划中参数意义相同例5-8 求解下面二次规划问题sub.to 解：则，在MATLAB中实现如下：H = 1 -1; -1 2 ;f = -2; -6;A = 1 1; -1 2; 2 1;b = 2; 2; 3;lb = zeros(2,1);x,fval,exitflag,outp

22、ut,lambda = quadprog(H,f,A,b, , ,lb)结果为：x = %最优解 0.6667 1.3333fval = %最优值 -8.2222exitflag = %收敛 1output = iterations: 3 algorithm: medium-scale: active-set firstorderopt: cgiterations: lambda = lower: 2x1 double upper: 2x1 double eqlin: 0x1 double ineqlin: 3x1 double lambda.ineqlinans = 3.1111 0.444

23、4 0 lambda.lowerans = 0 0说明 第1、2个约束条件有效，其余无效。例5-9 求二次规划的最优解max f (x1, x2)=x1x2+3sub.to x1+x2-2=0解：化成标准形式： sub.to x1+x2=2在Matlab中实现如下：H=0,-1;-1,0;f=0;0;Aeq=1 1;b=2;x,fval,exitflag,output,lambda = quadprog(H,f, , ,Aeq,b)结果为：x = 1.0000 1.0000fval = -1.0000exitflag = 1output = firstorderopt: 0 iteration

24、s: 1 cgiterations: 1 algorithm: 1x58 charlambda = eqlin: 1.0000 ineqlin: lower: upper: 5.3 极小化极大（Minmax）问题极小化极大问题的标准形式为sub.to 其中：x、b、beq、lb、ub是向量，A、Aeq为矩阵，C(x)、Ceq(x)和F(x)是返回向量的函数，F(x)、C(x)、Ceq(x)可以是非线性函数。函数 fminimax格式 x = fminimax(fun,x0)x = fminimax(fun,x0,A,b)x = fminimax(fun,x0,A,b,Aeq,beq)x = f

25、minimax(fun,x0,A,b,Aeq,beq,lb,ub)x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)x,fval,maxfval = fminimax()x,fval,maxfval,exitflag = fminimax()x,fval,maxfval,exitflag,output = fminimax()x,fval,maxfval,exitflag,output,lambda = fminimax()参数说明：fun为目标

26、函数；x0为初始值；A、b满足线性不等约束，若没有不等约束，则取A= ，b= ；Aeq、beq满足等式约束，若没有，则取Aeq= ，beq= ；lb、ub满足，若没有界，可设lb= ，ub= ；nonlcon的作用是通过接受的向量x来计算非线性不等约束和等式约束分别在x处的值C和Ceq，通过指定函数柄来使用，如：x = fminimax(myfun,x0,A,b,Aeq,beq,lb,ub,mycon)，先建立非线性约束函数，并保存为mycon.m：function C,Ceq = mycon(x)C = % 计算x处的非线性不等约束的函数值。Ceq = % 计算x处的非线性等式约束的函数值。

27、options为指定的优化参数；fval为最优点处的目标函数值；maxfval为目标函数在x处的最大值；exitflag为终止迭代的条件；lambda是Lagrange乘子，它体现哪一个约束有效。output输出优化信息。例5-10 求下列函数最大值的最小化问题其中：解：先建立目标函数文件，并保存为myfun.m：function f = myfun(x)f(1)= 2*x(1)2+x(2)2-48*x(1)-40*x(2)+304; f(2)= -x(1)2 - 3*x(2)2;f(3)= x(1) + 3*x(2) -18;f(4)= -x(1)- x(2);f(5)= x(1) + x(

28、2) - 8;然后，在命令窗口键入命令：x0 = 0.1; 0.1; % 初始值x,fval = fminimax(myfun,x0)结果为：x = 4.0000 4.0000fval = 0.0000 -64.0000 -2.0000 -8.0000 -0.0000例5-11 求上述问题的绝对值的最大值最小化问题。目标函数为：解：先建立目标函数文件（与上例相同）然后，在命令窗口或编辑器中建立M文件：x0 = 0.1; 0.1; % 初始点options = optimset(MinAbsMax,5); % 指定绝对值的最小化x,fval = fminimax(myfun,x0, , , ,

29、, , , ,options)则结果为x = 4.9256 2.0796fval = 37.2356 -37.2356 -6.8357 -7.0052 -0.99485.4 最小二乘最优问题5.4.1 约束线性最小二乘有约束线性最小二乘的标准形式为sub.to 其中：C、A、Aeq为矩阵；d、b、beq、lb、ub、x是向量。函数 lsqlin 格式 x = lsqlin(C,d,A,b) %求在约束条件下，方程Cx = d的最小二乘解x。x = lsqlin(C,d,A,b,Aeq,beq) %Aeq、beq满足等式约束，若没有不等式约束，则设A= ，b= 。x = lsqlin(C,d,A

30、,b,Aeq,beq,lb,ub) %lb、ub满足，若没有等式约束，则Aeq= ，beq= 。x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0) % x0为初始解向量，若x没有界，则lb= ，ub= 。x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options) % options为指定优化参数例5-12 求解下面系统的最小二乘解系统：Cx=d约束：；先输入系统系数和x的上下界：C = 0.9501 0.7620 0.6153 0.4057; 0.2311 0.4564 0.7919 0.9354; 0.6068 0.0185 0.9218

31、0.9169; 0.4859 0.8214 0.7382 0.4102; 0.8912 0.4447 0.1762 0.8936;d = 0.0578; 0.3528; 0.8131; 0.0098; 0.1388;A = 0.2027 0.2721 0.7467 0.4659; 0.1987 0.1988 0.4450 0.4186; 0.6037 0.0152 0.9318 0.8462;b = 0.5251; 0.2026; 0.6721;lb = -0.1*ones(4,1);ub = 2*ones(4,1);然后调用最小二乘命令：x,resnorm,residual,exitflag

32、,output,lambda = lsqlin(C,d,A,b, , ,lb,ub);结果为：x = -0.1000 -0.1000 0.2152 0.3502resnorm = 0.1672residual = 0.0455 0.0764 -0.3562 0.1620 0.0784exitflag = 1 %说明解x是收敛的output = iterations: 4 algorithm: medium-scale: active-set firstorderopt: cgiterations: lambda = lower: 4x1 double upper: 4x1 double eql

33、in: 0x1 double ineqlin: 3x1 double通过lambda.ineqlin可查看非线性不等式约束是否有效。5.4.2 非线性数据（曲线）拟合非线性曲线拟合是已知输入向量xdata和输出向量ydata，并且知道输入与输出的函数关系为ydata=F(x, xdata)，但不知道系数向量x。今进行曲线拟合，求x使得下式成立：函数 lsqcurvefit格式 x = lsqcurvefit(fun,x0,xdata,ydata)x = lsqcurvefit(fun,x0,xdata,ydata,lb,ub)x = lsqcurvefit(fun,x0,xdata,ydata

34、,lb,ub,options)x,resnorm = lsqcurvefit()x,resnorm,residual = lsqcurvefit()x,resnorm,residual,exitflag = lsqcurvefit()x,resnorm,residual,exitflag,output = lsqcurvefit()x,resnorm,residual,exitflag,output,lambda = lsqcurvefit()x,resnorm,residual,exitflag,output,lambda,jacobian =lsqcurvefit()参数说明：x0为初始解

35、向量；xdata，ydata为满足关系ydata=F(x, xdata)的数据；lb、ub为解向量的下界和上界，若没有指定界，则lb= ，ub= ；options为指定的优化参数；fun为拟合函数，其定义方式为：x = lsqcurvefit(myfun,x0,xdata,ydata)，其中myfun已定义为 function F = myfun(x,xdata)F = % 计算x处拟合函数值fun的用法与前面相同；resnorm=sum (fun(x,xdata)-ydata).2)，即在x处残差的平方和；residual=fun(x,xdata)-ydata，即在x处的残差；exitfla

36、g为终止迭代的条件；output为输出的优化信息；lambda为解x处的Lagrange乘子；jacobian为解x处拟合函数fun的jacobian矩阵。例5-13 求解如下最小二乘非线性拟合问题已知输入向量xdata和输出向量ydata，且长度都是n，拟合函数为即目标函数为其中：初始解向量为x0=0.3, 0.4, 0.1。解：先建立拟合函数文件，并保存为myfun.mfunction F = myfun(x,xdata)F = x(1)*xdata.2 + x(2)*sin(xdata) + x(3)*xdata.3;然后给出数据xdata和ydataxdata = 3.6 7.7 9.

37、3 4.1 8.6 2.8 1.3 7.9 10.0 5.4;ydata = 16.5 150.6 263.1 24.7 208.5 9.9 2.7 163.9 325.0 54.3;x0 = 10, 10, 10; %初始估计值x,resnorm = lsqcurvefit(myfun,x0,xdata,ydata)结果为：Optimization terminated successfully:Relative function value changing by less than OPTIONS.TolFunx = 0.2269 0.3385 0.3021resnorm = 6.295

38、05.4.3 非线性最小二乘非线性最小二乘（非线性数据拟合）的标准形式为其中：L为常数在MATLAB5.x中，用函数leastsq解决这类问题，在6.0版中使用函数lsqnonlin。设则目标函数可表达为其中：x为向量，F(x)为函数向量。函数 lsqnonlin格式 x = lsqnonlin(fun,x0) %x0为初始解向量；fun为，i=1,2,m，fun返回向量值F，而不是平方和值，平方和隐含在算法中，fun的定义与前面相同。x = lsqnonlin(fun,x0,lb,ub) %lb、ub定义x的下界和上界：。x = lsqnonlin(fun,x0,lb,ub,options)

39、 %options为指定优化参数，若x没有界，则lb= ，ub= 。x,resnorm = lsqnonlin() % resnorm=sum(fun(x).2)，即解x处目标函数值。x,resnorm,residual = lsqnonlin() % residual=fun(x)，即解x处fun的值。例5-14 求下面非线性最小二乘问题初始解向量为x0=0.3, 0.4。解：先建立函数文件，并保存为myfun.m，由于lsqnonlin中的fun为向量形式而不是平方和形式，因此，myfun函数应由建立： k=1,2,10function F = myfun(x)k = 1:10;F = 2

40、 + 2*k-exp(k*x(1)-exp(k*x(2);然后调用优化程序：x0 = 0.3 0.4；x,resnorm = lsqnonlin(myfun,x0) 结果为：Optimization terminated successfully:Norm of the current step is less than OPTIONS.TolXx = 0.2578 0.2578resnorm = %求目标函数值 124.36225.4.4 非负线性最小二乘非负线性最小二乘的标准形式为：sub.to 其中：矩阵C和向量d为目标函数的系数，向量x为非负独立变量。在MATLAB5.x中，用函数nn

41、ls求解这类问题，在6.0版中则用函数lsqnonneg。函数 lsqnonneg格式 x = lsqnonneg(C,d) %C为实矩阵，d为实向量x = lsqnonneg(C,d,x0) % x0为初始值且大于0x = lsqnonneg(C,d,x0,options) % options为指定优化参数x,resnorm = lsqnonneg() % resnorm=norm (C*x-d)2x,resnorm,residual = lsqnonneg() %residual=C*x-dx,resnorm,residual,exitflag = lsqnonneg()x,resnorm

42、,residual,exitflag,output = lsqnonneg()x,resnorm,residual,exitflag,output,lambda = lsqnonneg()例5-15 一个最小二乘问题的无约束与非负约束解法的比较。先输入数据：C = 0.0372 0.2869; 0.6861 0.7071; 0.6233 0.6245; 0.6344 0.6170;d = 0.8587; 0.1781; 0.0747; 0.8405; Cd, lsqnonneg(C,d)ans = -2.5627 0 3.1108 0.6929注意：1。当问题为无约束线性最小二乘问题时，使用M

43、ATLAB下的“”运算即可以解决。2对于非负最小二乘问题，调用lsqnonneg(C,d)求解。5.5 非线性方程(组)求解5.5.1 非线性方程的解非线性方程的标准形式为f(x)=0函数 fzero格式 x = fzero (fun,x0) %用fun定义表达式f(x)，x0为初始解。x = fzero (fun,x0,options)x,fval = fzero() %fval=f(x)x,fval,exitflag = fzero()x,fval,exitflag,output = fzero()说明 该函数采用数值解求方程f(x)=0的根。例5-16 求的根解： fun=x3-2*x-5; z=fzer