《非线性规划.ppt》由会员分享，可在线阅读，更多相关《非线性规划.ppt（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、非线性规划非线性规划 定义定义 如果目标函数或约束条件中至少有一个是非线性函数,则最优化问题就叫做非线性规划问题非线性规划问题非现性规划的基本概念非现性规划的基本概念 一般形式一般形式:（1）其中 ，是定义在 R Rn 上的实值函数，简记:其它情况其它情况:求目标函数的最大值，或约束条件小于等于零两种情况，都可通过取其相反数化为上述一般形式1nj1ni1nR :h ,R :g ,R :RRRf()nTnRxxxX=,21L()()=.,.,2,1 0 m;1,2,.,0.ljXhiXgtsji 定义定义1 1 把满足问题（1）中条件的解 称为可行解可行解（或可行（或可行点点），），所有可行点的
2、集合称为可行集可行集（或（或可行域可行域）记为D即 问题(1)可简记为 定义定义2 2 对于问题(1),设 ,若存在 ,使得对一切 ,且 ,都有 ,则称X*是f(X)在D上的局部极小值点局部极小值点（局部最优解局部最优解）特别地,当 时，若 ,则称X*是f(X)在D上的严格局部极小值点严格局部极小值点（严格局部最严格局部最优解优解）定义定义3 3 对于问题(1),设 ,若对任意的 ,都有则称X*是f(X)在D上的全局极小值点全局极小值点（全局最优解全局最优解）特别地,当 时，若 ,则称X*是f(X)在D上的严格全局极小值点严格全局极小值点（严格全局最优解严格全局最优解）返回返回)(nRX()(
3、)njiRXXhXg XD =,0,0|()(),Xf Xf*非线性规划的基本解法非线性规划的基本解法SUTM外点法外点法SUTM内点法（障碍罚函数法）内点法（障碍罚函数法）1 罚函数法罚函数法2 近似规划法近似规划法 返回返回 罚函数法罚函数法 罚函数法罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解这类方法称为序列无约束最小化方法序列无约束最小化方法简称为SUMTSUMT法法 其一为SUMTSUMT外点法外点法，其二为SUMTSUMT内点法内点法 其中T(X,M)称为罚函数罚函数，M称为罚因子罚因子，带M的项称为罚项罚项，这里的罚函数只对
4、不满足约束条件的点实行惩罚:当 时，满足各 ，故罚项为0，不受惩罚当 时,必有约束条件 ，故罚项大于0，要受惩罚SUTMSUTM外点法外点法 罚函数法的缺点缺点：每个近似最优解Xk往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着Mk的增大，可能导致错误1任意给定初始点 X0，取M11，给定允许误差 ，令k=1；2求无约束极值问题 的最优解，设Xk=X(Mk)，即 ；3若存在 ，使 ,则取MkM(),令k=k+1返回（2），否则，停止迭代得最优解 计算时也可将收敛性判别准则 改为 SUTM SUTM外点法外点法(罚函数法)的迭代
5、步骤迭代步骤SUTMSUTM内点法（内点法（障碍函数法）()()()()()()()为障碍因子.为障碍项，或其中称或：构造障碍函数rXgrXgrXgrXfrXIXgrXfrXIrXImiimiimiimii=+=+=11111 ln1)(),(ln,内点法的迭代步骤内点法的迭代步骤 用MATLAB软件求解,其输入格式输入格式如下:1x=quadprog(H,C,A,b);2x=quadprog(H,C,A,b,Aeq,beq);3x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB);4x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0);5x=quad
6、prog(H,C,A,b,Aeq,beq,VLB,VUB,X0,options);6x,fval=quaprog();7x,fval,exitflag=quaprog();8x,fval,exitflag,output=quaprog();1二次规划二次规划例例1 1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t.x1+x22 -x1+2x22 x10,x20 1写成标准形式写成标准形式：2输入命令输入命令：H=1-1;-1 2;c=-2;-6;A=1 1;-1 2;b=2;2;Aeq=;beq=;VLB=0;0;VUB=;x,z=quadprog(H,c,
7、A,b,Aeq,beq,VLB,VUB)3运算结果运算结果为：x=06667 13333 z=-82222s.t.1 首先建立M文件fun.m,用来定义目标函数F（X）:function f=fun(X);f=F(X);2一般非线性规划一般非线性规划 其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其他变量的含义与线性规划、二次规划中相同用MATLAB求解上述问题，基本步骤分三步：3 建立主程序.求解非线性规划的函数是fmincon,命令的基本格式如下：(1)x=fmincon(fun,X0,A,b)(2)x=fmincon(fun,X0,A,b,Aeq,beq)(3)x
8、=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函数中提供了梯度（optio
9、ns参数的GradObj设置为on），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法当既有等式约束又有梯度约束时，使用中型算法2 fmincon函数的中型算法使用的是序列二次规划法在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hesse矩阵3 fmincon函数可能会给出局部最优解，这与初值X0的选取有关1写成标准形式写成标准形式：s.t.2x1+3x2 6 s.t.x1+4x2 5 x1,x2 0例例22先建立先建立M-文件文件 fun3m:function f=fun3(x);f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)23再
10、建立主程序youh2m：x0=1;1;A=2 3;1 4;b=6;5;Aeq=;beq=;VLB=0;0;VUB=;x,fval=fmincon(fun3,x0,A,b,Aeq,beq,VLB,VUB)4运算结果为：运算结果为：x=07647 10588 fval=-202941 1先建立先建立M文件文件fun4m定义目标函数定义目标函数:function f=fun4(x);f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);x1+x2=0 s.t.1.5+x1x2-x1-x2 0 -x1x2 10 0例例3 2再建立再建立M文件文件mycon
11、m定义非线性约束：定义非线性约束：function g,ceq=mycon(x)g=x(1)+x(2);15+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;3主程序主程序youh3m为为:x0=-1;1;A=;b=;Aeq=1 1;beq=0;vlb=;vub=;x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb,vub,mycon)4 运算结果为运算结果为：x=-12250 12250 fval=18951 例4 1先建立先建立M文件文件funm定义目标函数定义目标函数:function f=fun(x);f=-2*x(1)-x(2);2再建立
12、再建立M文件文件mycon2m定义非线性约束：定义非线性约束：function g,ceq=mycon2(x)g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;3 主程序主程序fxxm为为:x0=3;25;VLB=0 0;VUB=5 10;x,fval,exitflag,output =fmincon(fun,x0,VLB,VUB,mycon2)4 运算结果为运算结果为:x=40000 30000fval=-110000exitflag=1output=iterations:4 funcCount:17 stepsize:1 algorithm:1x44 char firstorderopt:cgiterations:应用实例：应用实例：供应与选址供应与选址 某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：km）及水泥日用量d(t)由下表给出目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20t假设从料场到工地之间均有直线道路相连 （1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少水泥，可使总的吨千米数最小（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20t，问应建在何处，节省的吨千米数有多大？