《运筹学——非线性规划课件.ppt》由会员分享，可在线阅读，更多相关《运筹学——非线性规划课件.ppt（76页珍藏版）》请在三一办公上搜索。
1、Non-linear Programming,第六章 非线性规划,第一节 基本概念,1、非线性规划模型：,数学规划模型的一般形式：,其中,x=(x1 ,x2, xn)T，f(x),gi(x),hj(x)为x的实值函数,简记为MP(Mathematical Programming),退 出,前一页,后一页,非线性规划,基本概念凸函数和凸规划一维搜索方法无约束最优化方法约束最优化方法,基本概念,非线性规划问题非线性规划方法概述,非线性规划问题,例1 曲线的最优拟合问题,例2 构件容积问题,2、非线性规划方法概述,微分学方法的局限性：,实际的问题中，函数可能是不连续或者不可微的。需要解复杂的方程组，
2、而方程组到目前仍没有有效的算法。实际的问题可能含有不等式约束，微分学方法不易处理。,退 出,前一页,后一页,非线性规划方法概述,非线性规划基本迭代格式,凸规划及其性质,一维搜索方法,0.618法（近似黄金分割法）,Newton法,基本思路：迭代,给定初始点x0,根据x0,依次迭代产生点列xk,xk的最后一点为最优解,xk收敛于最优解,退 出,前一页,后一页,迭代格式,xk,xk+1,称pk为第k轮搜索方向，tk为第k轮沿pk方向的步长。,产生tk和pk的不同方法，形成了不同的算法。,退 出,前一页,后一页,定义：下降方向,退 出,前一页,后一页,定义,解非线性规划问题，关键在于找到某个方向，使
3、得在此方向上，目标函数得到下降，同时还是可行方向。这样的方向称为可行下降方向。,退 出,前一页,后一页,第二节 凸函数和凸规划,1、凸函数及其性质：,定义,退 出,前一页,后一页,退 出,前一页,后一页,定理:,关于凸函数的一些结论,定理:,是凸集。,函数f在集合S上关于c的水平集,课下练习：证明上述定理,退 出,前一页,后一页,定理,n=1时几何意义：可微函数是凸的等价于切线不在函数图像上方。,? 还有什么方法判断一个函数是凸函数呢？,退 出,前一页,后一页,退 出,前一页,后一页,2、凸规划及其性质：,凸规划定义：,退 出,前一页,后一页,凸规划性质：,凸规划的任一局部最优解都是它的整体最
4、优解。,凸规划是以后重点讨论的一类非线性规划,线性函数,退 出,前一页,后一页,解：,（1）目标函数是不是凸函数？（2）gi(x)是不是凸函数？,退 出,前一页,后一页,第三节 一维搜索方法,t为实数,一维搜索问题指目标函数为单变量的非线性规划问题。又称线性搜索问题。其模型为：,什么叫一维搜索问题？,或,退 出,前一页,后一页,一维搜索问题的算法分类：,精确一维搜索（最优一维搜索）非精确一维搜索（可接受一维搜索）,本节内容：,两种精确一维搜索方法：0.618法，Newton法。两种非精确一维搜索方法：Goldstein法,Armijo法。,退 出,前一页,后一页,1、0.618法（近似黄金分割
5、法）,问题：凸函数是不是单谷函数？严格凸函数是不是单谷函数？单谷函数是不是凸函数？,单谷函数,退 出,前一页,后一页,搜索法求解：,或,基本过程：给出a,b,使得t*在a,b中。a,b称为搜索区间。迭代缩短a,b的长度。当a,b的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止。,退 出,前一页,后一页,假定：已经确定了单谷区间a,b,新搜索区间为a,t2,新搜索区间为t1,b,退 出,前一页,后一页,区间缩小比例的确定：,区间缩短比例为(t2-a)/(b-a),缩短比例为(b-t1)/(b-a),缩短比例满足：每次插入搜索点使得两个区间a,t2和t1,b相等；每次迭代都以
6、相等的比例缩小区间。,退 出,前一页,后一页,确定a,b,计算探索点t1=a+0.382(b-a)t2=a+0.618(b-a),0.618法解题步骤：,停止，输出t1,以a,t2为新的搜索区间,停止，输出t2,以t1,b为新的搜索区间,退 出,前一页,后一页,例：,解：,1、第一轮：t1=1.146, t2=1.854,t200.5,退 出,前一页,后一页,2、第二轮：t2=1.146, t1=0.708,t20=1.1460.5,3、第三轮：t1=0.438, t2=0.708,b-t1=1.146-0.4380.5,退 出,前一页,后一页,4、第四轮：t2=0.876, t1=0.708
7、,b-t1=1.146-0.7080.5,输出：t*=t2=0.876为最优解，最优值为-0.0798,课下练习：仔细分析上述迭代过程，体会0.618法的实质。,退 出,前一页,后一页,2、Newton法,Newton法基本思想：,用探索点tk处的二阶Taylor展开式近似代替目标函数，以展开式的最小点为新的探索点。,课下练习：画图理解Newton法的几何意义,退 出,前一页,后一页,解题步骤：,给定初始点t1和精度,停止，输出t1,停止，解题失败,停止，输出t2,退 出,前一页,后一页,例：,解：,取t1=1,计算：,迭代过程如下表：,退 出,前一页,后一页,非精确一维搜索法,数值方法的关键
8、是从一个点迭代到下一个点。,确定下一个点的关键是确定搜索方向和步长,如果已经确定了搜索方向pk,则只要确定一个最佳的步长即可。,所谓的最佳步长即是在pk方向上走一个最好的长度使得目标函数下降的最多，即下述的最优化问题：,这样的最优化问题不需要太高的精度，只要满足某些更宽松的精度要求即可。这样的搜索方法称之为非精确一维搜索方法,退 出,前一页,后一页,Goldstein法原理：,Y=(0)+ (0)t,Y=(0)+ m2(0)t,Y=(0)+ m1(0)t,退 出,前一页,后一页,是,Goldstein算法,确定m1,m2,t0, a=0,b=+,(t0) (0)+m1 (0)t0,(t0) (
9、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法原理：,退 出,前一页,后一页,第四节 无约束最优化方法,本节课讨论n元函数的无约束非线性规划问题：,求解此类模型(UMP)的方法称为无约束最优化方法。,无约束最优化方法通常有两类：解析法：要使用导数的方法；直接法：无须考虑函数是否可导，直接使用函数值。,退 出,前一页,后一页,本节课内容：无约束问题的最优性条件最速下降法（一种解析法）,退 出,前一页,后一页,1、无约束问题的最优性条件,定理1
10、,定理2,梯度为0的点称为函数的驻点。驻点可能是极小点，也可能是极大点，也可能即不是极大也不是极小，这时称为函数的鞍点。定理2说明：UMP问题的局部最优解必是目标函数的驻点。,注：,退 出,前一页,后一页,定理3,定理4,课下练习：画图理解定理1、2、4的几何意义。,退 出,前一页,后一页,例,解：1、先求出目标函数的全部驻点；2、利用充分条件判断驻点是不是最优点。,退 出,前一页,后一页,关于梯度的复习：梯度是一个向量。n元函数f(x1 ,x2 ,xn)在某点x处的梯度为：,梯度的方向与函数f的等值线的一个法线方向相同，从较低的等值线指向较高的等值线。,梯度的方向就是函数f的值增加最快的方向
11、，其相反方向就是函数值降低最快的方向。,2、最速下降法,退 出,前一页,后一页,最速下降法又称为梯度法，由Cauchy于1847年给出。,最速下降法解决的是具有连续可微的目标函数的UMP问题。,最速下降法的基本思想：从当前点xk出发寻找使得目标函数下降最快的方向，即负梯度方向。,退 出,前一页,后一页,最速下降法计算步骤：,选区初始点x0和精度,计算,停止，输出x0,求p0=,计算t0,使,计算x1= x0+ t0 p0,退 出,前一页,后一页,例,解：,退 出,前一页,后一页,说明：观察P119的图，可以发现x1 x0垂直于目标函数的等值线（图中的虚线）在x0的切线；最速下降方法相邻的两个搜
12、索方向是相互垂直的，即x1 x0垂直x1 x2；最速下降法解决UMP的缺陷：迭代点越靠近最优解则目标函数下降的速度越慢；优点：迭代点列总是收敛的，而且计算过程简单。,退 出,前一页,后一页,第五节 约束最优化方法,本节课讨论约束非线性规划问题MP,其中,x=(x1 ,x2, xn)T，f(x),gi(x),hj(x)为x的实值函数,求解此类模型(MP)的方法称为约束最优化方法。,退 出,前一页,后一页,本节课内容：约束问题的最优性条件惩罚函数法,退 出,前一页,后一页,1、约束最优化问题的最优性条件,对于MP问题：,退 出,前一页,后一页,若x*有变化，则约束条件可能没有破坏,若x*有变化，则
13、约束条件一定被破坏,令J表示MP的全部等式约束的下标集合，即J=1,2q,I表示MP的全部不等式约束的下标集合，即I=1,2p,x*的积极约束的下标集合,退 出,前一页,后一页,定理1,对于,若x*是局部最优解,则,退 出,前一页,后一页,定理1的说明：,2、称下述表达式为MP的Kuhn-Tucker条件，简称K-T条件,满足K-T条件的点称为MP的K-T点，定理1说明MP的局部最优解一定是MP的K-T点。,为了求出MP的最优解，可以先找出MP的K-T点，再做进一步的判断。,退 出,前一页,后一页,3、定理1的实例说明,定理1表明：若(x1,x2)T是局部最优解，g1和g2为积极约束，则：,退
14、 出,前一页,后一页,4、定理1的特例1,退 出,前一页,后一页,5、定理1的特例2,退 出,前一页,后一页,6、定理1的改进：,对于,若x*是局部最优解,则,互补松紧条件,退 出,前一页,后一页,7、实例说明改进后的定理1：,定理1改进后表明：若(x1,x2)T是局部最优解，则：,退 出,前一页,后一页,互补松紧条件,退 出,前一页,后一页,定理2,对于,注：定理2表明，在凸性条件下，K-T点是整体最优解。,退 出,前一页,后一页,例：写出K-T条件;求出相应的K-T点;判断K-T点是不是问题的最优解,解：由于全部函数都是连续可微的，所以应用以下K-T条件,退 出,前一页,后一页,首先写出原
15、MP问题的K-T条件：,根据定理1,K-T点还应该满足原问题的约束条件,互补松紧条件,退 出,前一页,后一页,利用互补松紧条件，可以求出K-T点：,利用定理2，由于全部函数都连续可微，并且f和g都是凸函数，h是线性函数，所以K-T点就是整体最优解。,退 出,前一页,后一页,2、惩罚函数法,惩罚函数法的基本思想：利用原问题的中的约束函数构造适当的惩罚函数，并和原问题的目标函数相加，得到带参数的增广目标函数，从而将原问题题转换为一系列无约束非线性规划问题。惩罚函数法的分类：罚函数法（外部惩罚法），障碍函数法（内部惩罚法）,退 出,前一页,后一页,(1) 罚函数法,罚函数法基本原理：,考虑：,构造惩
16、罚函数：,很大的正数,无约束最优化问题min F(x)=f(x)+p(x)的最优解必定是原问题的最优解。,退 出,前一页,后一页,可选的惩罚函数：,惩罚函数法的经济解释：f(x)为产品成本，约束条件为产品质量约束；如果违反质量约束，就给予一定的惩罚p(x)；追求的目标就是成本f(x)和惩罚量p(x)的总和最小（即构造的无约束最优化问题）；如果惩罚条件很苛刻，最好的结果就是不违反质量约束（无约束最优化问题的最优解为MP的最优解）,退 出,前一页,后一页,(2) 障碍函数法,障碍函数法基本原理：构造一个新的目标函数，它在可行区域的边界筑起一道墙；当迭代点靠近边界时，新的目标函数迅速增加；迭代点被档在可行区域的内部；迭代得到的点列就只可能在可行区域的内部。,退 出,前一页,后一页,可选的惩罚函数：,考虑：,构造最优化问题：,或：,当x靠近边界时，至少有一个gi(x)趋近于零，则F(x)将无限增大，从而使得迭代点保持在可行区域的内部。,退 出,前一页,后一页,本章结束！,点击这里进入第七章“动态规划”的学习,
