第4章非线性规划方法

1、第4章 非线性规划方法2012 统计学 在科学管理和其他领域中，大量应用问题可以归结为线性规划问在科学管理和其他领域中，大量应用问题可以归结为线性规划问题，但是，也有另外许多问题，其目标函数和（或）约束条件很难题，但是，也有另外许多问题，其目标函数和（或）约束条件很难用线性函数表达。如果目标函数和（或）约束条件中包含有自变量用线性函数表达。如果目标函数和（或）约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。的非线性函数，则这样的规划问题就属于非线性规划。 非线性规划是运筹学的重要分支之一。最近非线性规划是运筹学的重要分支之一。最近3030多年来发展很快，多年来发展很快，不

2、断提出各种算法，而其应用范围也越来越广泛。比如在各种预报、不断提出各种算法，而其应用范围也越来越广泛。比如在各种预报、管理科学、最优设计、质量控制、系统控制等领域得到广泛且不短管理科学、最优设计、质量控制、系统控制等领域得到广泛且不短深入的应用。深入的应用。 一般来说，求解非线性规划问题比线性规划问题困难得多。而且，一般来说，求解非线性规划问题比线性规划问题困难得多。而且，也不象线性规划那样有单纯形法这一通用的方法。非线性规划的各也不象线性规划那样有单纯形法这一通用的方法。非线性规划的各种算法大都有自己特定的使用范围，都有一定的局限性。到目前为种算法大都有自己特定的使用范围，都有一定的局限性。

3、到目前为止还没有止还没有适合于各种问题的一般算法适合于各种问题的一般算法，这是需要深入研究的一个领，这是需要深入研究的一个领域。我们只是对一些模型及应用作简单介绍。域。我们只是对一些模型及应用作简单介绍。（1）数学规划模型的一般形式：）数学规划模型的一般形式：其中其中, 简记为简记为MP(Mathematical Programming) 非线性规划问题的数学模型非线性规划问题的数学模型 qjxhpixgxfii, 1 , 0)( , 1 , 0)( s.t.)( min的的实实值值函函数数，为为xxhxgxfxxxxjiTn)(),(),(,),(21 （2）简记形式：）简记形式：Tpxgx

4、gxg)(,),()(1 Tqxhxhxh)(,),()(1 引入引入向量函数向量函数符号：符号： qjxhpixgtsxfii, 1 , 0)( , 1 , 0)( .)( min 0)( 0)( .)( minxhxgtsxfXxxf )(min qjxhpixgRxXiin, 1, 0)(, 1, 0)(（3）数学规划问题的分类：）数学规划问题的分类： 0)( 0)( s.t.)( minxhxgxf若若 为线性函数，即为为线性函数，即为线性规划线性规划(LP)；若若 至少一个为非线性至少一个为非线性, 即为即为非线性规划非线性规划(NLP)；对于非线性规划，对于非线性规划，若没有若没有

5、 ,即即X=Rn,称为称为 无约束非线性规划无约束非线性规划或或无约束最优化问题无约束最优化问题；否则称为否则称为约束非线性规划或约束最优化问题约束非线性规划或约束最优化问题。)(),(),(xhxgxfji)(),(),(xhxgxfji)(),(xhxgji , 1 0 , 1 0 . miniqjxh pixgtsxfj）（）（）（凸规划的定义及其性质：凸规划的定义及其性质： , 1 0 , 1 0 qjxhpixgRxXjin）（）（,(MP),Xf若是凸集是X上的凸函数 称为非线性凸规划 简称凸规划。凸规划定义：凸规划定义：（4）可行域和可行解：）可行域和可行解： qjxhpixgR

6、xXiin, 1, 0)(, 1, 0)(称称为为MP问题的问题的约束集约束集或或可行域可行域。若若x在在X内，称内，称x为为MP的的可行解可行解或者或者可行点可行点。 qjxhpixgtsxfii, 1 , 0)( , 1 , 0)( .)( min（5）最优解和极小点）最优解和极小点对于非线性规划（对于非线性规划（MP），若），若 ，并且有，并且有Xx *Xxxfxf ),()(*极极小小值值。）的的整整体体最最优优值值或或整整体体是是（称称MP)(*xf如果有如果有*, ),()(xxXxxfxf 严严格格整整体体极极小小点点，）的的严严格格整整体体最最优优解解或或是是（称称MP*x严严

7、格格整整体体极极小小值值。）的的严严格格整整体体最最优优值值或或是是（称称MP)(*xf定义定义:极极小小点点，）的的整整体体最最优优解解或或整整体体是是（则则称称MP*x 使使的的邻邻域域并并且且存存在在若若）对对于于非非线线性性规规划划（ )( ,MP* xxRxxNxXxnXxNxxfxf)()()(* ，极极小小值值）的的局局部部最最优优值值或或局局部部是是（称称MP)(*xf如果有如果有* ,)()()(xxXxNxxfxf ，定义定义严严格格局局部部极极小小点点）的的严严格格局局部部最最优优解解或或是是（称称MP*x严严格格局局部部极极小小值值。）的的严严格格局局部部最最优优值值或

8、或是是（MP)(*xf则称则称 x* 是是(MP)的的局部最优解或或局部极小解,（6.1）微分学方法的局限性：）微分学方法的局限性：实际的问题中，函数可能是不连续或者不可微的。需要解复杂的方程组，而方程组到目前仍没有有效的算法。实际的问题可能含有不等式约束，微分学方法不易处理。(6) (6) 非线性规划方法概述非线性规划方法概述（6.2）数值方法的基本思路：迭代给定初始点x0根据x0,依次迭代产生点列xkxk的最后一点为最优解xk有限xk无限xk收敛于最优解迭代格式迭代格式xkxk+1kx kkkxxx 1pkkkkptx kkkxxx 1称称pk为第为第k轮轮搜索方向搜索方向，tk为第为第k

9、轮沿轮沿pk方向的方向的步长步长。产生产生tk和和pk的不同方法，形成了不同的算法。的不同方法，形成了不同的算法。，使使若若存存在在设设0, 0,:1 pRpRxRRfnnn), 0( ),()( txftpxf处处的的下下降降方方向向。在在点点是是函函数数则则称称向向量量xxfp)(处处下下降降最最快快的的方方向向。在在就就是是可可导导，则则在在若若xxfxfxxf)()(-)( 定义定义：特殊搜索方向：特殊搜索方向下降方向下降方向，使得，使得若存在若存在设设0t, 0, pRpXxRXnnXtpx 的的可可行行方方向向。关关于于处处是是点点则则称称向向量量Xxp定义：定义：特殊搜索方向特殊

10、搜索方向下降方向下降方向解非线性规划问题，关键在于解非线性规划问题，关键在于找到某个方向，使得在此方向找到某个方向，使得在此方向上，目标函数得到下降，同时上，目标函数得到下降，同时还是可行方向。还是可行方向。这样的方向称为这样的方向称为可行下降方向。可行下降方向。定义：算法收敛、下降迭代算法定义：算法收敛、下降迭代算法集合集合S上的迭代算法：上的迭代算法：（1）初始点）初始点0 x；（2）按照某种搜索方向）按照某种搜索方向pk产生下一个迭代点产生下一个迭代点.1kkkkpxx （i）如果点列）如果点列kx收敛于最优解收敛于最优解*x，则称此，则称此算法收敛算法收敛。（ii）如果）如果 )()(

11、)(10kxfxfxf，则称此算法为，则称此算法为下降迭代算法下降迭代算法。.0 x.1x.2x（6.3）下降迭代算法步骤）下降迭代算法步骤（1）给出初始点）给出初始点0 x，令，令0 k；（2）按照某种规则确定下降搜索方向）按照某种规则确定下降搜索方向kd；（3）按照某种规则确定搜索步长）按照某种规则确定搜索步长k ，使得，使得)()(kkkkxfdxf ；（4）令）令 kkkkdxx 1，1: kk；（5）判断）判断kx是否满足是否满足停止条件停止条件。是则停止，否则转第。是则停止，否则转第2步。步。搜索步长确定方法：搜索步长确定方法：)(min)(kkkkkdxfdxf 称称0)( kT

12、kkkddxf k 为为最优步长最优步长，且有对，且有对 k的梯度的梯度（6.4） 终止条件终止条件)(31 kkkkxxxx )(41 kkkkxfxfxfxf11 kkxx21)()( kkxfxf（6.5）常用的收敛性判别准则）常用的收敛性判别准则:（）点收敛准则（）点收敛准则: :( (可取可取Rn中任一种模中任一种模) )。 ) 1()(kkxx（）目标函数值准则：（）目标函数值准则：（绝对差）。（绝对差）。 )()() 1()(kkffxx（）目标函数值准则：（）目标函数值准则：（相对差）。（相对差）。 )()()()() 1()(kkkfffxxx取其中之一取其中之一,也可同时取

13、也可同时取(1)与与(2);(1)与与(3);或或(1),(2)和和(3)等。等。（6.6）算法的收敛速度）算法的收敛速度则称则称 的收敛阶为的收敛阶为 。设算法所得的点列为设算法所得的点列为kx，如果，如果,|*1 xxxxkk.0, kx1.线性收敛（当线性收敛（当k充分大时）：充分大时）： 2.超线性收敛：超线性收敛：3.二阶收敛：二阶收敛： （*）式中）式中 =2时成立。时成立。1|*)(*)1( xxxxkk0|lim*)(*)1( xxxxkkkn 梯度法（最速下降法）梯度法（最速下降法）n 牛顿法与拟牛顿法牛顿法与拟牛顿法n 变尺度法变尺度法(DFP(DFP法法) )n 共轭梯度

14、法共轭梯度法无约束非线性规划的解法：无约束非线性规划的解法：约束非线性规划的解法：约束非线性规划的解法：n 外点法（惩罚函数法）外点法（惩罚函数法）n 内点法（障碍函数法）内点法（障碍函数法）例例.某公司有某公司有6个建筑工地，位置坐标为个建筑工地，位置坐标为(ai, bi) (单位：单位：公里公里),水泥日用量水泥日用量di (单位：吨）单位：吨）ia1.258.750.55.7537.25b1.250.754.7556.57.75d35476111）现有）现有2料场，位于料场，位于A (5, 1), B (2, 7),记记(xj,yj),j=1,2, 日储量日储量ej各有各有20吨吨,制定

15、每天的供应制定每天的供应计划，即从计划，即从A, B两料场分别向各工地运送多少吨两料场分别向各工地运送多少吨水泥，使总的吨公里数最小水泥，使总的吨公里数最小 .2, 1,6,.,1,.)()(min612121612/122 jecidctsbyaxcjijiiijjjiijijij假设：假设：料场和工地之间有直线道路料场和工地之间有直线道路决策变量：决策变量：ci j (料场料场j到到工地工地i的运量）的运量）12维维i1234561 ic（料料场场A）3507012ic（料料场场B）0040610总吨公里数为总吨公里数为136.2选址问题：选址问题：NLPNLP2）改建两个新料场，需要确定

16、新料场位置）改建两个新料场，需要确定新料场位置(xj,yj)和和运量运量cij ，在其它条件不变下使总吨公里数最小。，在其它条件不变下使总吨公里数最小。2 , 1,6,.,1,. .)()(min612121612/122jecidctsbyaxcjijiiijjjiijijij决策变量：决策变量：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);

17、 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、二次规划、二次规划标准型为： Min Z= 21XTHX+cTX s.t. AX=b beqXAeq VLBXVUB 例例1 1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1

18、+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.2222212121622 11- 1 ),(minxxxxxxzT212100222 11 1 xxxxs.t. 1. 首先建立M文件fun.m,定义目标函数F（X）:function

19、f=fun(X);f=F(X);2、一般非线性规划、一般非线性规划标准型为： min F(X) s.t AX=b beqXAeq G(X)0 Ceq(X)=0 VLBXVUB 其中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,命令的基本格式

20、如下： (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函数提供了大型优化算法和中型优化算法。默认时