第6讲 非线性规划

数学建模与数学实验非线性规划实验目的实验内容2．掌握用数学软件求解优化问题．1．直观了解非线性规划的基本内容．1．非线性规划的基本理论．4．实验作业．2．用数学软件求解非线性规划．3．钢管订购及运输优化模型．*非线性规划的基本解法非线性规划的基本概念非线性规划返回定义如果目标函数或约束条件中至少有一个是非线性函数,则最优化问题就叫做非线性规划问题．非现性规划的基本概念一般形式:（1）其中，是定义在Rn上的实值函数，简记:Xfminjihgf,,其它情况:求目标函数的最大值，或约束条件小于等于零两种情况，都可通过取其相反数化为上述一般形式．1nj1ni1nR:h,R:g,R:RRRfnTnRxxxX=,,,21L===.,...,2,10m;1,2,...,0..ljXhiXgtsji定义1把满足问题（1）中条件的解称为可行解（或可行点），所有可行点的集合称为可行集（或可行域）．记为D．即问题(1)可简记为．XfDXmin定义2对于问题(1),设,若存在,使得对一切,且,都有,则称X*是f(X)在D上的局部极小值点（局部最优解）．特别地,当时，若,则称X*是f(X)在D上的严格局部极小值点（严格局部最优解）．DX*0DX*XX*XXXfXf*XfXf*定义3对于问题(1),设,若对任意的,都有则称X*是f(X)在D上的全局极小值点（全局最优解）．特别地,当时，若,则称X*是f(X)在D上的严格全局极小值点（严格全局最优解）．DX*DX*XXXfXf*返回)(nRX{}njiRXXhXgXD==,0,0|,XfXf*非线性规划的基本解法SUTM外点法SUTM内点法（障碍罚函数法）1．罚函数法2．近似规划法返回罚函数法罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解．这类方法称为序列无约束最小化方法．简称为SUMT法．其一为SUMT外点法，其二为SUMT内点法．)2(,0min,1212===ljjmiiXhMXgMXfMXT可设：R1min,(3)nXTXM将问题（）转化为无约束问题：其中T(X,M)称为罚函数，M称为罚因子，带M的项称为罚项，这里的罚函数只对不满足约束条件的点实行惩罚:当时，满足各，故罚项为0，不受惩罚．当时,必有约束条件，故罚项大于0，要受惩罚．DX0,0=XhXgiiDX00XhXgii或SUTM外点法min01,2,...,;s.t.(1)01,2,...,.ijfXgXimhXjl===对一般的非线性规划：罚函数法的缺点：每个近似最优解Xk往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着Mk的增大，可能导致错误．1．任意给定初始点X0，取M11，给定允许误差，令k=1；2．求无约束极值问题的最优解，设Xk=X(Mk)，即；3．若存在，使,则取MkM(),令k=k+1返回（2），否则，停止迭代．得最优解．计算时也可将收敛性判别准则改为．0Rmin,nXTXMRmin,(,)nkkXTXMTXM=mii1kiXg10,1==MMk0,0min12=miiXgMkXX*kiXgSUTM外点法(罚函数法)的迭代步骤min(1)s.t.01,2,...,ifXgXim=考虑问题：{}00|0,1,2,,iDXgXimD==设集合，是可行域中所有严格内点的集合.01min,kkkXDIXrXr这样问题（）就转化为求一系列极值问题：得（）.SUTM内点法（障碍函数法）为障碍因子.为障碍项，或其中称或：构造障碍函数rXgrXgrXgrXfrXIXgrXfrXIrXImiimiimiimii======11111ln1)(),(ln,,内点法的迭代步骤(1)给定允许误差0，取10,01r；(2)求出约束集合D的一个内点00DX，令1=k；(3)以01DXk为初始点，求解kDXrXI,min0，其中0DX的最优解设为0DrXXkk=；(4)检验是否满足=mikiXgr1ln或=miikXgr11，若满足，停止迭代，令kXX*；否则取kkrr1=，令1=kk，返回(3）．近似规划法的基本思想：将问题(3)中的目标函数和约束条件近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解之，把其符合原始条件的最优解作为(3)的解的近似．Xf0(1,...,);0(1,,)ijgXimhXjl===近似规划法每得到一个近似解，都从这点出发，重复以上步骤．这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解．近似规划法的算法步骤如下：(2)在点kX处，将Xf，XhXgji,按泰勒级数展开并取一阶近似，得到近似线性规划问题：TminkkkfXfXfXXX01,,TkkkiiigXgXgXXXim=T0j1,,kkkjjjhXhXhXXXl==；(1)给定初始可行点{}112111,,,nxxxXL=，步长限制njj,,11L=，步长缩小系数1,0，允许误差0，令k=1；5)判断精度：若njkj,,1L=，则点1kX为近似最优解；否则，令njkjkj,,11L==，k=k+1，返回步骤(2)．(3)在上述近似线性规划问题的基础上增加一组限制步长的线性约束条件．因为线性近似通常只在展开点附近近似程度较高，故需要对变量的取值范围加以限制，所增加的约束条件是：njxxkjkjj,,1L=求解该线性规划问题，得到最优解1kX；(4)检验1kX对原约束是否可行.若1kX对原约束可行，则转步骤(5)；否则，缩小步长限制，令njkjkj,,1L==，返回步骤(3)，重解当前的线性规划问题；返回用MATLAB软件求解,其输入格式如下:1．x=quadprog(H,C,A,b);2．x=quadprog(H,C,A,b,Aeq,beq);3．x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB);4．x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0);5．x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0,options);6．[x,fval]=quaprog(…);7．[x,fval,exitflag]=quaprog(…);8．[x,fval,exitflag,output]=quaprog(…);1．二次规划标准型为：minZ=21XTHX+cTXs.t.AX≤bbeqXAeq=VLB≤X≤VUB例1minf(x1,x2)=-2x1-6x2+x12-2x1x2+2x22s.t.x1+x2≤2-x1+2x2≤2x1≥0,x2≥0MATLAB（youh1）1．写成标准形式：2．输入命令：H=[1-1;-12];c=[-2;-6];A=[11;-12];b=[2;2];Aeq=[];beq=[];VLB=[0;0];VUB=[];[x,z]=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)3．运算结果为：x=0．66671．3333z=-8．2222T1112221-12min(,)126xxzxxxx=121211212200xxxxs.t.1．首先建立M文件fun.m,用来定义目标函数F（X）:functionf=fun(X);f=F(X);2．一般非线性规划标准型为：minF(X)s.t．AXbbeqXAeq=G(X)0Ceq(X)=0VLBXVUB其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其他变量的含义与线性规划、二次规划中相同．用MATLAB求解上述问题，基本步骤分三步：2.若约束条件中有非线性约束:G(X)0或Ceq(X)=0,则建立M文件nonlcon.m定义函数G(X)与Ceq(X):function[G,Ceq]=nonlcon(X)G=…Ceq=…3．建立主程序.求解非线性规划的函数是fmincon,命令的基本格式如下：(1)x=fmincon(‘fun’,X0,A,b)(2)x=fmincon(‘fun’,X0,A,b,Aeq,beq)(3)x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB)(4)x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’)(5)x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’,options)(6)[x,fval]=fmincon(…)(7)[x,fval,exitflag]=fmincon(…)(8)[x,fval,exitflag,output]=fmincon(…)输出极值点M文件迭代的初值参数说明变量上下限注意：[1]fmincon函数提供了大型优化算法和中型优化算法．默认时:若在fun函数中提供了梯度（options参数的GradObj设置为’on’），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法．当既有等式约束又有梯度约束时，使用中型算法．[2]fmincon函数的中型算法使用的是序列二次规划法．在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hesse矩阵．[3]fmincon函数可能会给出局部最优解，这与初值X0的选取有关．1．写成标准形式：s.t.00546322121xxxx2100xx22212121212minxxxxf=22212121212minxxxxf=2x1+3x26s.t.x1+4x25x1,x20例22．先建立M-文件fun3．m:functionf=fun3(x);f=-x(1)-2*x(2)+(1/2)*x(1)^2+(1/2)*x(2)^2MATLAB(youh2)3．再建立主程序youh2．m：x0=[1;1];A=[23;14];b=[6;5];Aeq=[];beq=[];VLB=[0;0];VUB=[];[x,fval]=fmincon('fun3',x0,A,b,Aeq,beq,VLB,VUB)4．运算结果为：x=0．76471．0588fval=-2．02941．先建立M文件fun4．m定义目标函数:functionf=fun4(x);f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);12212122()e(42421)xfxxxxxx=x1+x2=0s.t.1.5+x1x2-x1-x20-x1x2–100例32．再建立M文件mycon．m定义非线性约束：function[g,ceq]=mycon(x)g=[x(1)+x(2);1．5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10];3．主程序youh3．m为:x0=[-1;1];A=[];b=[];Aeq=[11];beq=[0];vlb=[];vub=[];[x,fval]=fmincon('fun4',x0,A,b