运筹学——非线性规划课件.ppt

《运筹学——非线性规划课件.ppt》由会员分享，可在线阅读，更多相关《运筹学——非线性规划课件.ppt（76页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、非线性规划非线性规划非线性规划Non-linear ProgrammingNon-linear Programming第六章第六章 非线性规划非线性规划非线性规划第一节第一节 基本概念基本概念1、非线性规划模型：、非线性规划模型：数学规划模型的一般形式：数学规划模型的一般形式：其中其中,x=(x1,x2,xn)T，f(x),gi(x),hj(x)为为x的实值函数的实值函数简记为简记为MP(Mathematical Programming)退 出前一页后一页非线性规划非线性规划非线性规划v基本概念基本概念v凸函数和凸规划凸函数和凸规划v一维搜索方法一维搜索方法v无约束最优化方法无约束最优化方法v

2、约束最优化方法约束最优化方法非线性规划基本概念基本概念v非线性规划问题非线性规划问题v非线性规划方法概述非线性规划方法概述非线性规划非线性规划问题非线性规划问题例例1 曲线的最优拟合问题曲线的最优拟合问题非线性规划例例2 构件容积问题构件容积问题非线性规划2、非线性规划方法概述、非线性规划方法概述微分学方法的局限性：微分学方法的局限性：实际的问题中，函数可能是不连续或者不可微的。实际的问题中，函数可能是不连续或者不可微的。需要解复杂的方程组，而方程组到目前仍没有有效需要解复杂的方程组，而方程组到目前仍没有有效的算法。的算法。实际的问题可能含有不等式约束，微分学方法不易实际的问题可能含有不等式约

3、束，微分学方法不易处理。处理。退 出前一页后一页非线性规划非线性规划方法概述非线性规划方法概述非线性规划非线性规划基本迭代格式非线性规划基本迭代格式非线性规划凸规划及其性质凸规划及其性质约束集如果如果(MP)(MP)的约束集的约束集X X是凸集，目标函数是凸集，目标函数f f是是X X上的上的凸函数，则凸函数，则(MP)(MP)叫做叫做非线性凸规划非线性凸规划，或简称为，或简称为凸规划凸规划。非线性规划定理定理 4.2.6 凸规划的任一局部最优解都是它的整体最凸规划的任一局部最优解都是它的整体最优解。优解。非线性规划一维搜索方法一维搜索方法精确一维搜索方法精确一维搜索方法 0.6180.618

4、法法 NewtonNewton法法非精确一维搜索方法非精确一维搜索方法 GoldsteinGoldstein法法 ArmijoArmijo法法非线性规划0.618法（近似黄金分割法）法（近似黄金分割法）非线性规划非线性规划Newton法法非线性规划基本思路：基本思路：迭代迭代给定初始点给定初始点x0根据根据x0,依次迭代产生点列依次迭代产生点列xkxk的最后一点为最优解的最后一点为最优解xk有限有限xk无限无限xk收敛于最优解收敛于最优解退 出前一页后一页非线性规划迭代格式迭代格式xkxk+1pk称称p pk k为第为第k k轮轮搜索方向搜索方向，t tk k为第为第k k轮沿轮沿p pk k

5、方向的方向的步长步长。产生产生t tk k和和p pk k的不同方法，形成了不同的算法。的不同方法，形成了不同的算法。退 出前一页后一页非线性规划定义：下降方向定义：下降方向退 出前一页后一页非线性规划定义定义解非线性规划问题，关键在于解非线性规划问题，关键在于找到某个方向，使得在此方向找到某个方向，使得在此方向上，目标函数得到下降，同时上，目标函数得到下降，同时还是可行方向。还是可行方向。这样的方向称为这样的方向称为可行下降方向。可行下降方向。退 出前一页后一页非线性规划第二节第二节 凸函数和凸规划凸函数和凸规划1、凸函数及其性质：、凸函数及其性质：定义定义退 出前一页后一页非线性规划退 出

6、前一页后一页非线性规划定理定理:关于凸函数的一些结论关于凸函数的一些结论定理定理:是凸集。是凸集。函数函数f在集合在集合S上关于上关于c的水平集的水平集课下练习：证明上述定理课下练习：证明上述定理退 出前一页后一页非线性规划定理定理n=1时几何意义：可微函数是凸的等价于切线不在函数图时几何意义：可微函数是凸的等价于切线不在函数图像上方。像上方。?还有什么方法判断一个函数是凸函数呢？还有什么方法判断一个函数是凸函数呢？退 出前一页后一页非线性规划退 出前一页后一页非线性规划2、凸规划及其性质：、凸规划及其性质：凸规划定义：凸规划定义：退 出前一页后一页非线性规划凸规划性质凸规划性质：凸规划的任一

7、局部最优解都是它的整体最优解。凸规划的任一局部最优解都是它的整体最优解。凸规划是以后重点讨论的一类非线性规划凸规划是以后重点讨论的一类非线性规划凸函数凸函数线线性性函函数数退 出前一页后一页非线性规划解：解：（1）目标函数是不是凸函数？）目标函数是不是凸函数？（2）gi(x)是不是凸函数？是不是凸函数？退 出前一页后一页非线性规划第第三节三节 一维搜索方法一维搜索方法t为实数为实数一维搜索问题指目标函数为单变量的非线性规划问题。一维搜索问题指目标函数为单变量的非线性规划问题。又称线性搜索问题。其模型为：又称线性搜索问题。其模型为：什么叫一维搜索问题？什么叫一维搜索问题？或或一般一维搜索问题一般

8、一维搜索问题有效一维搜索问题有效一维搜索问题退 出前一页后一页非线性规划一维搜索问题的算法分类：一维搜索问题的算法分类：精确一维搜索（最优一维搜索）精确一维搜索（最优一维搜索）非精确一维搜索（可接受一维搜索）非精确一维搜索（可接受一维搜索）本节内容：本节内容：两种精确一维搜索方法：两种精确一维搜索方法：0.618法，法，Newton法。法。两种非精确一维搜索方法：两种非精确一维搜索方法：Goldstein法法,Armijo法。法。退 出前一页后一页非线性规划1、0.618法（近似黄金分割法）法（近似黄金分割法）问题：问题：凸函数是不是单谷函数？严格凸函数是不是凸函数是不是单谷函数？严格凸函数是

9、不是单谷函数？单谷函数是不是凸函数？单谷函数？单谷函数是不是凸函数？单谷函数单谷函数退 出前一页后一页非线性规划搜索法求解：搜索法求解：或或基本过程：基本过程：给出给出a,b,a,b,使得使得t t*在在a,ba,b中。中。a,ba,b称为称为搜索区间搜索区间。迭代缩短迭代缩短a,ba,b的长度。的长度。当当a,ba,b的长度小于某个预设的值，或者导数的绝对的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止。值小于某个预设的正数，则迭代终止。退 出前一页后一页非线性规划假定：已经确定了单谷区间假定：已经确定了单谷区间a,bt1t2ababt1t2新搜索区间为新搜索区间为a,

10、ta,t2 2 新搜索区间为新搜索区间为tt1 1,b,b退 出前一页后一页非线性规划区间缩小比例的确定：区间缩小比例的确定：区间缩短比例为区间缩短比例为(t(t2 2-a)/(b-a)-a)/(b-a)缩短比例为缩短比例为(b-t(b-t1 1)/(b-a)/(b-a)缩短比例满足：缩短比例满足：每次插入搜索点使得两个区间每次插入搜索点使得两个区间a,ta,t2 2 和和tt1 1,b,b相等；相等；每次迭代都以相等的比例缩小区间。每次迭代都以相等的比例缩小区间。0.618法法t1t2ababt1t2退 出前一页后一页非线性规划确定确定a,b,计算探索点计算探索点t1=a+0.382(b-a

11、)t2=a+0.618(b-a)0.618法解题步骤：法解题步骤：是是否否是是停止，输出停止，输出t1否否以以a,t2为新的搜索区间为新的搜索区间是是停止，输出停止，输出t2否否以以t1,b为新的搜索区间为新的搜索区间退 出前一页后一页非线性规划例：例：解：解：t1t230t1、第一轮：、第一轮：t1=1.146,t2=1.854t200.5退 出前一页后一页非线性规划2、第二轮：、第二轮：t2=1.146,t1=0.708t20=1.1460.53、第三轮：、第三轮：t1=0.438,t2=0.708b-t1=1.146-0.4380.51.8540tt2t11.4160tt2t1退 出前一

12、页后一页非线性规划4、第四轮：、第四轮：t2=0.876,t1=0.708b-t1=1.146-0.7080.5输出：输出：t*=t2=0.876为最优解，最优值为为最优解，最优值为-0.0798课下练习：仔细分析上述迭代过程，体会课下练习：仔细分析上述迭代过程，体会0.618法的实法的实质。质。01.416tt1t2退 出前一页后一页非线性规划2、Newton法法Newton法基本思想：法基本思想：用用探索点探索点t tk k处的二阶处的二阶TaylorTaylor展开式近似代替目展开式近似代替目标函数，以展开式的最小点为新的探索点。标函数，以展开式的最小点为新的探索点。课下练习：课下练习：

13、画图理解画图理解NewtonNewton法的几何意义法的几何意义退 出前一页后一页非线性规划解题步骤：解题步骤：给定初始点给定初始点t1和精度和精度是是是是停止，输出停止，输出t1是是否否停止，解题失败停止，解题失败否否停止，输出停止，输出t2否否退 出前一页后一页非线性规划例：例：解：解：取取t1=1,计算：计算：迭代过程如下表：迭代过程如下表：1.1370.11630.11693-0.00106141.3258-0.5178-0.5708220.785411退 出前一页后一页非线性规划非非精精确确一一维维搜搜索索法法数值方法的关键是从一个点迭代到下一个点。数值方法的关键是从一个点迭代到下一

14、个点。确定下一个点的关键是确定搜索方向和步长确定下一个点的关键是确定搜索方向和步长如果已经确定了搜索方向如果已经确定了搜索方向p pk k,则只要确定一个最佳则只要确定一个最佳的步长即可。的步长即可。所谓的最佳步长即是在所谓的最佳步长即是在p pk k方向上走一个最好的长度方向上走一个最好的长度使得目标函数下降的最多，即下述的最优化问题使得目标函数下降的最多，即下述的最优化问题：这样的最优化问题不需要太高的精度，只要满足这样的最优化问题不需要太高的精度，只要满足某些更宽松的精度要求即可。某些更宽松的精度要求即可。这样的搜索方法称之为这样的搜索方法称之为非精确一维搜索方法非精确一维搜索方法退 出

15、前一页后一页非线性规划Goldstein法原理：法原理：yt0bcdaY=(0)+(0)tY=(0)+m2(0)tY=(0)+m1(0)t退 出前一页后一页非线性规划是是Goldstein算法算法确定确定m1,m2,t0,a=0,b=+(t0)(0)+m1 (0)t0(t0)(0)+m2(0)t0是是停止停止,输出输出t0否否a=a,b=t0,t1=(a+b)/2否否a=t0,b=b,t1=(a+b)/2(若若b=+,则则t1=a)退 出前一页后一页非线性规划Armijo法原理：法原理：yt0tkMtk退 出前一页后一页非线性规划第四节第四节 无约束最优化方法无约束最优化方法本节课讨论本节课讨

16、论n元函数的无约束非线性规划问题：元函数的无约束非线性规划问题：求解此类模型求解此类模型(UMP)(UMP)的方法称为的方法称为无约束最优化方法无约束最优化方法。无约束最优化方法通常有两类：无约束最优化方法通常有两类：解析法：解析法：要使用导数的方法；要使用导数的方法；直接法：直接法：无须考虑函数是否可导，直接使用函数值。无须考虑函数是否可导，直接使用函数值。退 出前一页后一页非线性规划本节课内容：本节课内容：无约束问题的最优性条件无约束问题的最优性条件最速下降法（一种解析法）最速下降法（一种解析法）退 出前一页后一页非线性规划1、无约束问题的最优性条件、无约束问题的最优性条件定理定理1定理定

17、理2梯度为梯度为0 0的点称为函数的的点称为函数的驻点。驻点。驻点可能是极小点，也可能是极大点，也可能即不是极大也驻点可能是极小点，也可能是极大点，也可能即不是极大也不是极小，这时称为函数的不是极小，这时称为函数的鞍点。鞍点。定理定理2 2说明：说明：UMPUMP问题的局部最优解必是目标函数的驻点。问题的局部最优解必是目标函数的驻点。注：注：退 出前一页后一页非线性规划定理定理3定理定理4课下练习课下练习：画图理解定理画图理解定理1 1、2 2、4 4的几何意义。的几何意义。退 出前一页后一页非线性规划例例解：解：1 1、先求出目标函数的全部驻点；、先求出目标函数的全部驻点；2 2、利用充分条

18、件判断驻点是不是最优点。、利用充分条件判断驻点是不是最优点。退 出前一页后一页非线性规划关于梯度的复习：关于梯度的复习：梯度是一个向量。梯度是一个向量。n n元函数元函数f(xf(x1 1,x,x2 2,x xn n)在某点在某点x x处的处的梯度为：梯度为：梯度的方向与函数梯度的方向与函数f f的等值线的一个法线方向相同，从的等值线的一个法线方向相同，从较低的等值线指向较高的等值线。较低的等值线指向较高的等值线。梯度的方向就是函数梯度的方向就是函数f f的值增加最快的方向，其相反方的值增加最快的方向，其相反方向就是函数值降低最快的方向。向就是函数值降低最快的方向。2、最速下降法、最速下降法退

19、 出前一页后一页非线性规划最速下降法又称为最速下降法又称为梯度法梯度法，由，由Cauchy于于1847年给出。年给出。最速下降法解决的是最速下降法解决的是具有连续可微的目标函数具有连续可微的目标函数的的UMP问题。问题。最速下降法的基本思想：从当前点最速下降法的基本思想：从当前点xk出发寻找使得出发寻找使得目标函数下降最快的方向，即目标函数下降最快的方向，即负梯度方向负梯度方向。退 出前一页后一页非线性规划最速下降法计算步骤：最速下降法计算步骤：选区初始点选区初始点x0和精度和精度计算计算是是否否停止，输出停止，输出x0求求p0=计算计算t0,使使计算计算x1=x0+t0 p0退 出前一页后一

20、页非线性规划例例解：解：退 出前一页后一页非线性规划说明：说明：观察观察P119P119的图，可以发现的图，可以发现x x1 1 x x0 0垂直于目标函数的等垂直于目标函数的等值线（图中的虚线）在值线（图中的虚线）在x x0 0的切线；的切线；最速下降方法相邻的两个搜索方向是相互垂直的，最速下降方法相邻的两个搜索方向是相互垂直的，即即x x1 1 x x0 0垂直垂直x x1 1 x x2 2；最速下降法解决最速下降法解决UMPUMP的缺陷：迭代点越靠近最优解的缺陷：迭代点越靠近最优解则目标函数下降的速度越慢；则目标函数下降的速度越慢；优点：迭代点列总是收敛的，而且计算过程简单。优点：迭代点

21、列总是收敛的，而且计算过程简单。退 出前一页后一页非线性规划第五节第五节 约束最优化方法约束最优化方法本节课讨论约束非线性规划问题本节课讨论约束非线性规划问题MP其中其中,x=(x1,x2,xn)T，f(x),gi(x),hj(x)为为x的实值函数的实值函数求解此类模型求解此类模型(MP)的方法称为的方法称为约束最优化方法约束最优化方法。退 出前一页后一页非线性规划本节课内容：本节课内容：约束问题的最优性条件约束问题的最优性条件惩罚函数法惩罚函数法退 出前一页后一页非线性规划1、约束最优化问题的最优性条件、约束最优化问题的最优性条件对于对于MP问题：问题：退 出前一页后一页非线性规划若若x*有

22、变化，则约束条件可能没有破坏有变化，则约束条件可能没有破坏若若x*有变化，则约束条件一定被破坏有变化，则约束条件一定被破坏令令J表示表示MP的全部等式约束的下标集合，即的全部等式约束的下标集合，即J=1,2q,I表示表示MP的全部不等式约束的下标集合，即的全部不等式约束的下标集合，即I=1,2px*的的积极约束的下标集合积极约束的下标集合退 出前一页后一页非线性规划定理定理1对于对于若若x*是是局部最优解局部最优解,则则退 出前一页后一页非线性规划定理定理1的说明：的说明：2、称下述表达式为、称下述表达式为MP的的Kuhn-Tucker条件，简称条件，简称K-T条件条件满足满足K-TK-T条件

23、的点称为条件的点称为MPMP的的K-TK-T点，定理点，定理1 1说明说明MPMP的局部最优解的局部最优解一定是一定是MPMP的的K-TK-T点。点。为了求出为了求出MPMP的最优解，可以先找出的最优解，可以先找出MPMP的的K-TK-T点，再做进一步的点，再做进一步的判断。判断。退 出前一页后一页非线性规划3、定理、定理1的实例说明的实例说明定理定理1表明：若表明：若(x1,x2)T是局部最优解，是局部最优解，g1和和g2为积极约束，为积极约束，则：则：退 出前一页后一页非线性规划4、定理、定理1的特例的特例1退 出前一页后一页非线性规划5、定理、定理1的特例的特例2退 出前一页后一页非线性

24、规划6、定理、定理1的改进的改进：对于对于若若x*是是局部最优解局部最优解,则则互补松紧条件互补松紧条件退 出前一页后一页非线性规划7、实例说、实例说明改进后的明改进后的定理定理1：定理定理1 1改进后表明：若改进后表明：若(x(x1 1,x,x2 2)T T是局部最优解，则：是局部最优解，则：退 出前一页后一页非线性规划互补松紧条件互补松紧条件退 出前一页后一页非线性规划定理定理2对于对于注：注：定理定理2 2表明，在凸性条件下，表明，在凸性条件下，K-TK-T点点是整体最优解。是整体最优解。退 出前一页后一页非线性规划例：例：写出写出K-TK-T条件条件;求出相应的求出相应的K-TK-T点

25、点;判断判断K-TK-T点是不是点是不是问题的最优解问题的最优解解：解：由于全部函数都是连续可微的，所以应用以下由于全部函数都是连续可微的，所以应用以下K-T条件条件退 出前一页后一页非线性规划首先写出原首先写出原MP问题的问题的K-T条件：条件：根据定理根据定理1,K-T点点还应该满足原问题的约束条件还应该满足原问题的约束条件互补松紧条件互补松紧条件退 出前一页后一页非线性规划利用互补松紧条件，可以求出利用互补松紧条件，可以求出K-T点：点：利用定理利用定理2，由于全部函数都连续可微，并且，由于全部函数都连续可微，并且f和和g都是凸函数，都是凸函数，h是线性函数，所以是线性函数，所以K-T点

26、就是整体最点就是整体最优解。优解。退 出前一页后一页非线性规划2、惩罚函数法、惩罚函数法惩罚函数法的基本思想：惩罚函数法的基本思想：利用原问题的中的约利用原问题的中的约束函数构造适当的惩罚函数，并和原问题的目标束函数构造适当的惩罚函数，并和原问题的目标函数相加，得到带参数的增广目标函数，从而将函数相加，得到带参数的增广目标函数，从而将原问题题转换为一系列无约束非线性规划问题。原问题题转换为一系列无约束非线性规划问题。惩罚函数法的分类：惩罚函数法的分类：罚函数法（外部惩罚法），罚函数法（外部惩罚法），障碍函数法（内部惩罚法）障碍函数法（内部惩罚法）退 出前一页后一页非线性规划(1)罚函数法罚函数

27、法罚函数法基本原理：罚函数法基本原理：考虑：考虑：构造惩罚函数：构造惩罚函数：很大的正数很大的正数无约束最优化问题无约束最优化问题min min F(x)=f(x)+p(x)F(x)=f(x)+p(x)的最优解必的最优解必定是原问题的最优解。定是原问题的最优解。退 出前一页后一页非线性规划可选的惩罚函数：可选的惩罚函数：惩罚函数法的经济解释：惩罚函数法的经济解释：f(x)f(x)为产品成本，约束条件为产品质量约束；为产品成本，约束条件为产品质量约束；如果违反质量约束，就给予一定的惩罚如果违反质量约束，就给予一定的惩罚p(x)p(x)；追求的目标就是成本追求的目标就是成本f(x)f(x)和和惩罚

28、量惩罚量p(x)p(x)的总和最小的总和最小（即构造的无约束最优化问题）；（即构造的无约束最优化问题）；如果惩罚条件很苛刻，最好的结果就是不违反质量如果惩罚条件很苛刻，最好的结果就是不违反质量约束（无约束最优化问题的最优解为约束（无约束最优化问题的最优解为MPMP的最优解）的最优解）退 出前一页后一页非线性规划(2)障碍函数法障碍函数法障碍函数法基本原理：障碍函数法基本原理：构造一个新的目标函数，它在可行区域的边界筑构造一个新的目标函数，它在可行区域的边界筑起一道墙；起一道墙；当迭代点靠近边界时，新的目标函数迅速增加；当迭代点靠近边界时，新的目标函数迅速增加；迭代点被档在可行区域的内部；迭代点被档在可行区域的内部；迭代得到的点列就只可能在可行区域的内部。迭代得到的点列就只可能在可行区域的内部。退 出前一页后一页非线性规划可选的惩罚函数：可选的惩罚函数：考虑：考虑：构造最优化问题：构造最优化问题：或：或：当当x x靠近边界时，至少有一个靠近边界时，至少有一个g gi i(x(x)趋近于零，则趋近于零，则F(x)F(x)将无限增大，从而使得迭代点保持在可行区域的内部。将无限增大，从而使得迭代点保持在可行区域的内部。退 出前一页后一页非线性规划点击这里进入第七章“动态规划”的学习