第讲非线性规划总结

1非线性规划讲义2定义如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题．非线性规划的基本概念一般形式:（1）其中，是定义在En上的实值函数，简记:Xfmin.,...,2,10m;1,2,...,0..ljXhiXgtsjinTnExxxX,,,21jihgf,,1nj1ni1nE:h,E:g,E:EEEf其它情况:求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式．3定义1把满足问题（1）中条件的解称为可行解（或可行点），所有可行点的集合称为可行集（或可行域）．记为D．即问题(1)可简记为．njiEXXhXgXD,0,0|)(nEXXfDXmin定义2对于问题(1)，设，若存在,使得对一切，且，都有，则称X*是f(X)在D上的局部极小值点（局部最优解）．特别地当时，若则称X*是f(X)在D上的严格局部极小值点（严格局部最优解）．DX*0DX*XX*XXXfXf*定义3对于问题(1),设,对任意的,都有则称X*是f(X)在D上的全局极小值点（全局最优解）．特别地当时，若，则称X*是f(X)在D上的严格全局极小值点（严格全局最优解）．DX*DXXfXf**XXXfXf*XfXf*4nA),,1(niiiaib（投资决策问题）某企业有个项目可供选择投资，元，投资于第个项目需花资金元，并预计可收益元。试选择最佳投资方案。并且至少要对其中一个项目投资。已知该企业拥有总资金),,1(niiiaib（投资决策问题）某企业有个项目可供选择投资，元，投资于第个项目需花资金元，并预计可收益元。试选择最佳投资方案。并且至少要对其中一个项目投资。已知该企业拥有总资金个项目决定不投资第，个项目决定投资第iixi0,1ni,,1niiixa1niiixb1解设投资决策变量为，则投资总额为投资总收益为AniiiAxa10),,1(nixi.,,1,0)1(nixxii因为该公司至少要对一个项目，故有限制条件另外，由于只取值0或1，所以还有投资，并且总的投资金额不能超过总资金5最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为：niiiniiixaxbQ11maxniiiAxa10.,,1,0)1(nixxiis.t.6对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点：（i）确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。（ii）提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。（iii）给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或“坏”的价值标准，并用某种数量形式来描述它。（iv）寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示。7非线性规划的基本解法SUTM内点法（障碍罚函数法）SUTM外点法1、罚函数法2、近似规划法3、Matlab解法线性规划与非线性规划的区别如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到。8罚函数法罚函数法求解非线性规划问题的思想是，利用问题中的约束函数作出适当的罚函数，由此构造出带参数的增广目标函数，把问题转化为无约束非线性规划问题。主要有两种形式，一种叫SUMT外点法，另一种叫SUMT内点法，利用罚函数法，可将非线性规划问题的求解，转化为求解一系列无约束极值问题，因而也称这种方法为序列无约束最小化技术，简记为SUMT(SequentialUnconstrainedMinizationTechnique)。9)2(,0min,1212ljjmiiXhMXgMXfMXT可设：)3(,min1MXTnEX）转化为无约束问题：将问题（其中T(X,M)称为罚函数，M称为罚因子，带M的项称为罚项，这里的罚函数只对不满足约束条件的点实行惩罚：当时，满足各，故罚项=0，不受惩罚．当时，必有的约束条件，故罚项0，要受惩罚．DX0,0XhXgiiDX00XhXgii或SUMT外点法)1(.,...,2,10m;1,2,...,0..minljXhiXgtsXfji对一般的非线性规划：10罚函数法的缺点是：每个近似最优解Xk往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着Mk的增大，可能导致错误．1、任意给定初始点X0，取M11，给定允许误差，令k=1；2、求无约束极值问题的最优解，设为Xk=X(Mk)，即；3、若存在，使，则取MkM()令k=k+1返回（2），否则，停止迭代．得最优解.计算时也可将收敛性判别准则改为.0MXTnEX,min),(,minkkEXMXTMXTnmii1kiXg10,1MMk0,0min12miiXgMkXX*kiXgSUMT外点法的迭代步骤11)1(,...,2,10..minimXgtsXfi考虑问题：所有严格内点的集合。是可行域中，设集合00,,2,1,0|DmiXgXDi为障碍因子为障碍项，或其中称或：构造障碍函数rXgrXgrXgrXfrXIXgrXfrXIrXImiimiimiimii11111ln1)(),(ln,,）（得值问题：）就转化为求一系列极这样问题（kkkDXrXrXI,min10SUTM内点法（障碍函数法）12内点法的迭代步骤(1)给定允许误差0，取10,01r；(2)求出约束集合D的一个内点00DX，令1k；(3)以01DXk为初始点，求解kDXrXI,min0，其中0DX的最优解，设为0DrXXkk；(4)检验是否满足mikiXgr1ln或miikXgr11，满足，停止迭代，kXX*；否则取kkrr1，令1kk，返回(3）．13近似规划法的基本思想：将问题(3)中的目标函数和约束条件近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解之，把其符合原始条件的最优解作为(3)的解的近似．Xf),,1(0m);1,...,(0ljXhiXgji近似规划法每得到一个近似解后，都从这点出发，重复以上步骤．这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解。14近似规划法的算法步骤如下(2)在点kX处，将Xf，XhXgji,按泰勒级数展开并取一阶近似，得到近似线性规划问题：kTkkXXXfXfXfminmiXXXgXgXgkTkikii,,10lXXXhXhXhkTkjkjj,,1j0；(1)给定初始可行点112111,,,nxxxX，步长限制njj,,11，步长缩小系数1,0，允许误差，令k=1；155)判断精度：若njkj,,1，则点1kX为近似最优解；否则，令njkjkj,,11，k=k+1，返回步骤(2)．(3)在上述近似线性规划问题的基础上增加一组限制步长的线性约束条件．因为线性近似通常只在展开点附近近似程度较高，故需要对变量的取值范围加以限制，所增加的约束条件是：njxxkjkjj,,1求解该线性规划问题，得到最优解1kX；(4)检验1kX点对原约束是否可行。若1kX对原约束可行，则转步骤(5)；否则，缩小步长限制，令njkjkj,,1，返回步骤(3)，重解当前的线性规划问题；16用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(...);二次规划的Matlab解法标准型为：MinZ=21XTHX+cTXs.t.AX=bbeqXAeqVLB≤X≤VUB17例1minf(x1,x2)=-2x1-6x2+x12-2x1x2+2x22s.t.x1+x2≤2-x1+2x2≤2x1≥0,x2≥01、写成标准形式：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.222221212162211-1),(minxxxxxxzT212100222111xxxxs.t.181.首先建立M文件fun.m,定义目标函数F（X）:functionf=fun(X);f=F(X);一般非线性规划的Matlab解法标准型为：minF(X)s.tAX=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=...193.建立主程序.非线性规划求解的函数是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文件迭代的初值参数说明变量上下限其中exitflag描述函数计算的退出条件：若为正值，表示目标函数收敛