非线性规划方法.pptx

第4章 非线性规划方法2012 统计学 在科学管理和其他领域中，大量应用问题可以归结为线性规划问在科学管理和其他领域中，大量应用问题可以归结为线性规划问题，但是，也有另外许多问题，其目标函数和（或）约束条件很难用题，但是，也有另外许多问题，其目标函数和（或）约束条件很难用线性函数表达。如果目标函数和（或）约束条件中包含有自变量的非线性函数表达。如果目标函数和（或）约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。线性函数，则这样的规划问题就属于非线性规划。非线性规划是运筹学的重要分支之一。最近非线性规划是运筹学的重要分支之一。最近3030多年来发展很快，多年来发展很快，不断提出各种算法，而其应用范围也越来越广泛。比如在各种预报、不断提出各种算法，而其应用范围也越来越广泛。比如在各种预报、管理科学、最优设计、质量控制、系统控制等领域得到广泛且不短深管理科学、最优设计、质量控制、系统控制等领域得到广泛且不短深入的应用。入的应用。一般来说，求解非线性规划问题比线性规划问题困难得多。而且，一般来说，求解非线性规划问题比线性规划问题困难得多。而且，也不象线性规划那样有单纯形法这一通用的方法。非线性规划的各种也不象线性规划那样有单纯形法这一通用的方法。非线性规划的各种算法大都有自己特定的使用范围，都有一定的局限性。到目前为止还算法大都有自己特定的使用范围，都有一定的局限性。到目前为止还没有没有适合于各种问题的一般算法适合于各种问题的一般算法，这是需要深入研究的一个领域。我，这是需要深入研究的一个领域。我们只是对一些模型及应用作简单介绍。们只是对一些模型及应用作简单介绍。（1）数学规划模型的一般形式：）数学规划模型的一般形式：其中其中,简记为简记为MP(Mathematical Programming)非线性规划问题的数学模型非线性规划问题的数学模型（2）简记形式：）简记形式：引入引入向量函数向量函数符号：符号：（3）数学规划问题的分类：）数学规划问题的分类：若若 为线性函数，即为为线性函数，即为线性规划线性规划(LP)；若若 至少一个为非线性至少一个为非线性,即为即为非线性规划非线性规划(NLP)；对于非线性规划，对于非线性规划，若没有若没有 ,即即X=Rn,称为称为 无约束非线性规划无约束非线性规划或或无约束最优化问题无约束最优化问题；否则称为否则称为约束非线性规划或约束最优化问题约束非线性规划或约束最优化问题。凸规划的定义及其性质：凸规划的定义及其性质：凸规划定义：凸规划定义：（4）可行域和可行解：）可行域和可行解：称称为为MP问题的问题的约束集约束集或或可行域可行域。若若x在在X内，称内，称x为为MP的的可行解可行解或者或者可行点可行点。（5）最优解和极小点）最优解和极小点对于非线性规划（对于非线性规划（MP），若），若 ，并且有，并且有如果有如果有定义定义:如果有如果有定义定义则称则称 x*是是(MP)的的局部最优解或或局部极小解,（6.1）微分学方法的局限性：）微分学方法的局限性：实际的问题中，函数可能是不连续或者不可微的。需要解复杂的方程组，而方程组到目前仍没有有效的算法。实际的问题可能含有不等式约束，微分学方法不易处理。(6)(6)非线性规划方法概述非线性规划方法概述（6.2）数值方法的基本思路：迭代给定初始点x0根据x0,依次迭代产生点列xkxk的最后一点为最优解xk有限xk无限xk收敛于最优解迭代格式迭代格式xkxk+1pk称称pk为第为第k轮轮搜索方向搜索方向，tk为第为第k轮沿轮沿pk方向的方向的步长步长。产生产生tk和和pk的不同方法，形成了不同的算法。的不同方法，形成了不同的算法。定义定义：特殊搜索方向：特殊搜索方向下降方向下降方向定义：定义：特殊搜索方向特殊搜索方向可行可行可行可行下降方向下降方向解非线性规划问题，关键在于解非线性规划问题，关键在于找到某个方向，使得在此方向找到某个方向，使得在此方向上，目标函数得到下降，同时上，目标函数得到下降，同时还是可行方向。还是可行方向。这样的方向称为这样的方向称为可行下降方向。可行下降方向。定义：算法收敛、下降迭代算法定义：算法收敛、下降迭代算法集合集合S上的迭代算法：上的迭代算法：（1）初始点）初始点；（2）按照某种搜索方向）按照某种搜索方向pk产生下一个迭代点产生下一个迭代点（i）如果点列）如果点列收敛于最优解收敛于最优解，则称此，则称此算法收敛算法收敛。（ii）如果）如果，则称此算法为，则称此算法为下降迭代算法下降迭代算法。.（6.3）下降迭代算法步骤）下降迭代算法步骤（1）给出初始点）给出初始点，令，令；（2）按照某种规则确定下降搜索方向）按照某种规则确定下降搜索方向；（3）按照某种规则确定搜索步长）按照某种规则确定搜索步长，使得，使得；（4）令）令 ，；（5）判断）判断是否满足是否满足停止条件停止条件。是则停止，否则转第。是则停止，否则转第2步。步。搜索步长确定方法：搜索步长确定方法：称称为为最优步长最优步长，且有对，且有对 k的梯度的梯度（6.4）终止条件终止条件（6.5）常用的收敛性判别准则）常用的收敛性判别准则:（）点收敛准则（）点收敛准则:(可取可取Rn中任一种模中任一种模)。e e-)1()(kkxx（）目标函数值准则：（）目标函数值准则：（绝对差）。（绝对差）。e e-)()()1()(kkffxx（）目标函数值准则：（）目标函数值准则：（相对差）。（相对差）。e e-)()()()()1()(kkkfffxxx取其中之一取其中之一,也可同时取也可同时取(1)与与(2);(1)与与(3);或或(1),(2)和和(3)等。等。（6.6）算法的收敛速度）算法的收敛速度则称则称 的收敛阶为的收敛阶为 。设算法所得的点列为设算法所得的点列为，如果，如果1.线性收敛（当线性收敛（当k充分大时）：充分大时）：2.超线性收敛：超线性收敛：3.二阶收敛：二阶收敛：（*）式中）式中 =2时成立。时成立。（*）n梯度法（最速下降法）梯度法（最速下降法）n牛顿法与拟牛顿法牛顿法与拟牛顿法n变尺度法变尺度法(DFP(DFP法法)n共轭梯度法共轭梯度法无约束非线性规划的解法：无约束非线性规划的解法：约束非线性规划的解法：约束非线性规划的解法：n外点法（惩罚函数法）外点法（惩罚函数法）n内点法（障碍函数法）内点法（障碍函数法）例例.某公司有某公司有6个建筑工地，位置坐标为个建筑工地，位置坐标为(ai,bi)(单位：单位：公里公里),水泥日用量水泥日用量di(单位：吨）单位：吨）1）现有）现有2料场，位于料场，位于A(5,1),B(2,7),记记(xj,yj),j=1,2,日储量日储量ej各有各有20吨吨,制定每天的供制定每天的供应计划，即从应计划，即从A,B两料场分别向各工地运送多少两料场分别向各工地运送多少吨水泥，使总的吨公里数最小吨水泥，使总的吨公里数最小.假设：假设：料场和工地之间有直线道路料场和工地之间有直线道路决策变量：决策变量：ci j(料场料场j到到工地工地i的运量）的运量）12维维总吨公里数为总吨公里数为136.2选址问题：选址问题：NLPNLP2）改建两个新料场，需要确定新料场位置）改建两个新料场，需要确定新料场位置(xj,yj)和运量和运量cij，在其它条件不变下使总吨公里数最小。，在其它条件不变下使总吨公里数最小。决策变量：决策变量：ci j，(xj,yj)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(.);1、二次规划、二次规划例例1 1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t.x1+x22 -x1+2x22 x10,x20 MATLAB（youh1）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,A,b,Aeq,beq,VLB,VUB)3、运算结果运算结果为：x=0.6667 1.3333 z=-8.2222s.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=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法更新拉格朗日Hessian矩阵。3 fmincon函数可能会给出局部最优解，这与初值X0的选取有关。1、写成标准形式写成标准形式：s.t.2x1+3x2 6 s.t x1+4x2 5 x1,x2 0例例22、先建立先建立M-文件文件 fun3.m:function f=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=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=0.7647 1.0588 fval=-2.0294 非线性规划的Matlab解法,Matlab中非线性规划的数学模型写成以下形式 改建两个新料场，要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小。这是非线性规划问题。非线性规划模型为：