数学建模第二章非线性规划

第三章非线性规划3.1非线性规划3.1.1非线性规划的实例与定义

如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题。，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。下面通过实例归纳出非线性规划数学模型的一般形式例1（投资决策问题）某企业有n个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金A元，投资于第i(i=1,….,n)个项目需花资金

ai元，并预计可收益

bi元。试选择最佳投资方案。解设投资决策变量为则投资总额为，投资总收益为

因为该公司至少要对一个项目投资，并且总的投资金额不能超过总资金A，故有限制条件由于)xi(i=1,….,n

只取值0或1，所以还有

最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为：

上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题，其中至少有一个非线性函数，这类问题称之为非线性规划问题。可概括为一般形式其中x=[x1…..xn]T称为模型的决策变量，f称为目标函数，gi(i=1,….P

)和)hj(j=1,…..q)称为约束函数。另外，0)gi(x)=0(i=1,….P

)称为等式约束，hj(x)≤0(j=1,…..q)称为不等式的约束。线性规划与非线性规划的区别如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到。3.1.2非线性规划的Matlab解法Matlab中非线性规划的数学模型写成以下形式其中f(x)

是标量函数，Beq,Aeq,B,A是相应维数的矩阵和向量，C(x),Ceq(x)是非线性向量函数。Matlab中的命令是X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)LB≤x≤UB

它的返回值是向量x，其中FUN是用M文件定义的函数f(x)；X0是x的初始值；A,B,Aeq,Beq定义了线性约束A*X≤B,Aeq*X=Beq，如果没有线性约束，则A=[],B=[],Aeq=[],Beq=[]；LB和UB是变量x的下界和上界，如果上界和下界没有约束，则LB=[]，UB=[]，如果x无下界，则LB的各分量都为-inf，如果x无上界，则UB的各分量都为inf；NONLCON是用M文件定义的非线性向量函数C(x),Ceq(x)；OPTIONS定义了优化参数，可以使用Matlab缺省的参数设置。例2求下列非线性规划解（i）%编写M文件fun1.m定义目标函数functionf=fun1(x);f=sum(x.^2)+8;（ii）编写M文件fun2.m定义非线性约束条件function[g,h]=fun2(x);G=-x(1)^2+x(2)-x(3)^2x(1)+x(2)^2+x(3)^3-20;%非线性不等式约束h=[-x(1)-x(2)^2+2x(2)+2*x(3)^2-3;%非线性等式约束（iii）编写主程序文件example2.m如下：options=optimset('largescale','off');[x,y]=fmincon('fun1',rand(3,1),[],[],[],[],zeros(3,1),[],...'fun2',options)就可以求得当x1=0.5522,x2=1.2033,x3=0.9478时，最小值y=10.6511。3.2Matlab求无约束极值问题3.2.2无约束极值问题的数值解在Matlab工具箱中，用于求解无约束极值问题的函数有fminunc和fminsearch，用法介绍如下。求函数的极小值其中x可以为标量或向量。Matlab中fminunc的基本命令是[X,FVAL]=FMINUNC(FUN,X0,OPTIONS,P1,P2,...)其中的返回值X是所求得的极小点，FVAL是函数的极小值，其它返回值的含义参见相关的帮助。FUN是一个M文件，当FUN只有一个返回值时，它的返回值是函数f(x)

；当FUN有两个返回值时，它的第二个返回值是f（x）的梯度向量；当FUN有三个返回值时，它的第三个返回值是f(x)的二阶导数阵（Hessian阵）。X0是向量x的初始值，OPTIONS是优化参数，可以使用缺省参数。P1，P2是可以传递给FUN的一些参数。例3.5解：编写M文件fun2.m如下：function[f,g]=fun2(x);f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;g=[-400*x(1)*(x(2)-x(1)^2)-2*(1-x(1));200*(x(2)-x(1)^2)];编写主函数文件example6.m如下：options=optimset('GradObj','on');[x,y]=fminunc('fun2',rand(1,2),options)即可求得函数的极小值。方法2：在求极值时，也可以利用二阶导数，编写M文件fun3.m如下：function[f,df,d2f]=fun3(x);f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;df=[-400*x(1)*(x(2)-x(1)^2)-2*(1-x(1));200*(x(2)-x(1)^2)];d2f=[-400*x(2)+1200*x(1)^2+2,-400*x(1)-400*x(1),200];编写主函数文件example62.m如下：options=optimset('GradObj','on','Hessian','on');[x,y]=fminunc('fun3',rand(1,2),options)即可求得函数的极小值。求多元函数的极值也可以使用Matlab的fminsearch命令，其使用格式为：[X,FVAL,EXITFLAG,OUTPUT]＝FMINSEARCH(FUN,X0,OPTIONS,P1,P2,...)例3.6求函数f(x)=sin(x)+3取最小值时的x值。解编写f(x)的M文件fun4.m如下：functionf=fun4(x);f=sin(x)+3;编写主函数文件example7.m如下：x0=2;[x,y]=fminsearch(@fun4,x0)运行主函数文件即求得在初值2附近的极小点及极小值。3.3约束极值问题

带有约束条件的极值问题称为约束极值问题，也叫规划问题。求解约束极值问题要比求解无约束极值问题困难得多。为了简化其优化工作，可采用以下方法：将约束问题化为无约束问题；将非线性规划问题化为线性规划问题，以及能将复杂问题变换为较简单问题的其它方法。

库恩—塔克条件是非线性规划领域中最重要的理论成果之一，是确定某点为最优点的必要条件，但一般说它并不是充分条件（对于凸规划，它既是最优点存在的必要条件，同时也是充分条件）。3.3.1二次规划

若某非线性规划的目标函数为自变量x的二次函数，约束条件又全是线性的，就称这种规划为二次规划。Matlab中二次规划的数学模型可表述如下：Matlab中求解二次规划的命令是[X,FVAL]=QUADPROG(H,f,A,b,Aeq,beq,LB,UB,X0,OPTIONS)返回值X是决策向量x的值，返回值FVAL是目标函数在x处的值。其中，H为实对称矩阵例3.9求解二次规划解编写如下程序：h=[4,-4;-4,8];f=[-6;-3];a=[1,1;4,1];b=[3;9];[x,value]=quadprog(h,f,a,b,[],[],zeros(2,1))3.3.2罚函数法利用罚函数法，可将非线性规划问题的求解，转化为求解一系列无约束极值问题，因而也称这种方法为序列无约束最小化技术，简记为SUMT(SequentialUnconstrainedMinizationTechnique)。

罚函数法求解非线性规划问题的思想是，利用问题中的约束函数作出适当的罚函数，由此构造出带参数的增广目标函数，把问题转化为无约束非线性规划问题。主要有两种形式，一种叫外罚函数法，另一种叫内罚函数法，下面介绍外罚函数法。取一个充分大的数M>0，构造函数Matlab中可以直接利用max、min和sum函数。）则以增广目标函数P(x,M)为目标函数的无约束极值问题对应的最优解x也是原问题的最优解。例3.10求下列非线性规划解(i)编写M文件test.mfunctiong=test(x);M=50000;f=x(1)^2+x(2)^2+8;g=f-M*min(x(1),0)-M*min(x(2),0)-M*min(x(1)^2-x(2),0)+...M*abs(-x(1)-x(2)^2+2);或者是利用Matlab的求矩阵的极小值和极大值函数编写test.m如下：functiong=test(x);M=50000;f=x(1)^2+x(2)^2+8;g=f-M*sum(min([x';zeros(1,2)]))-(ii)在Matlab命令窗口输入[x,y]=fminunc('test',rand(2,1))即可求得问题的解。注意非线性问题很难求得全局最优解，只能求得一个局部最优解在Matlab优化工具箱中，用于求解约束最优化问题的函数有：fminbnd、fmincon、quadprog、fseminf、fminimax，上面已经介绍了函数fmincon和quadprog。1fminbnd函数求单变量非线性函数在区间上的极小值Matlab的命令为[X,FVAL]=FMINBND(FUN,x1,x2,OPTIONS)它的返回值是极小点x和函数的极小值。这里fun是用M文件定义的函数或Matlab中的单变量数学函数。例3.11解(1)编写M文件fun5.mfunctionf=fun5(x);f=(x-3)^2-1;(2)在Matlab的命令窗口输入[x,y]=fminbnd('fun5',0,5)即可求得极小点和极小值。2fseminf函数上述问题的Matlab命令格式为X=FSEMINF(FUN,X0,NTHETA,SEMINFCON,A,B,Aeq,Beq)其中FUN用于定义目标函数F(x)

；X0为x的初始值；NTHETA是半无穷约束PHI(x,w)的个数；函数SEMINFCON用于定义非线性不等式约束C(x)，非线性等式约束Ceq(x)和半无穷约束PHI(x,w)的每一个分量函数，函数SEMINFCON有两个输入参量X和S，S是推荐的取样步长解（1）编写M文件fun6.m定义目标函数如下：functionf=fun6(x,s);f=sum((x-0.5).^2);（2）编写M文件fun7.m定义约束条件如下：function[c,ceq,k1,k2,s]=fun7(x,s);c=[];ceq=[];ifisnan(s(1,1))%s=[0.2,0;0.20];end%取样值w1=1:s(1,1):100;w2=1:s(2,1):100;%半无穷约束k1=sin(w1*x(1)).*cos(w1*x(2))-1/1000*(w1-50).^2-sin(w1*x(3))-x(3)-1;k2=sin(w2*x(2)).*cos(w2*x(1))-1/1000*(w2-50).^2-sin(w2*x(3))-x(3)-1;%画出半无穷约束的图形,此处可以不用plot(w1,k1,'-',w2,k2,'+');（3）调用函数fseminf在Matlab的命令窗口输入[x,y]=fseminf(@fun6,rand(3,1),2,@fun7)即可。3fminimax函数上述问题的Matlab命令为X=FMINIMAX(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON)例3.13解（1）编写M文件fun8.m定义向量函数如下：functionf=fun8(x);f=[2*x(1)^2+x(2)^2-48*x(1)-40*x(2)+304-x(1)^2-3*x(2)^2x(1)+3*x(2)-18-x(1)-x(2)x(1)+x(2)-8];（2）调用函数fminimax[x,y]=fminimax(@fun8,rand(2,1))4利用梯度求解约束优化问题