运筹学非线性规划.pptx

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

1、第一节 基本概念一、非线性规划问题与模型1.问题生产计划问题x:产量;P(x):价格;C(x)成本第1页/共77页 投资决策问题第2页/共77页 2.模型第3页/共77页 二、模型的解及相关概念1.可行解与最优解可行解：约束集D中的X。最优解：如果有 ，对于任意的 ，都有 ，则称 为（NLP）的最优 解，也称为全局最小值点。局部最优解：如果对于 ，使得在 的邻 域 中的任意 都有 ，则称 为（NLP）的局部最 优 解，也称为局部最小值点。第4页/共77页例1：考虑非线性问题如果约束改为 呢？第5页/共77页2.梯度、海塞阵与泰勒公式 梯度第6页/共77页海塞阵第7页/共77页泰勒公式第8页/共

2、77页例2：写出 在 点的二阶泰勒展开式解:第9页/共77页3.极值的条件对于无约束极值问题，可以利用微积分的知识给出局部极值点的条件。将n(n1)元函数 与一元函数 的极值条件加以对比并归纳如下：充分条件 必要条件第10页/共77页例3：求 的极小值点解第11页/共77页4.凸规划凸函数：f(X)是定义在凸集D上且满足对任意 有下式成立的函数：若不等式中严格不等号成立，则称f(X)为严格凸函数注：判断一个可导函数f(X)是否是凸函数的方法一元函数f(x)：二阶导大于等于零;多元函数f(X)：海塞阵半正定。第12页/共77页凸规划性质：约束集是凸集；最优解集是凸集；任何局部最优解也是全局最优解

3、；若目标函数是严格凸函数，且最优解存在，则 其最优解是唯一的。在非线性规划模型（NLP）中，若目标函数f（X）是凸函数，不等式约束函数 为凹函数，等式约束函数 为仿射函数，则称（NLP）是一个凸规划。第13页/共77页例4：判断下面的非线性规划是否为凸规划标准化第14页/共77页第二节 无约束极值问题一般模型：求解（f(X)可微）：应用极值条件求解，往往得到一个非线 性的方程组，求解十分困难。因此，求 解无约束问题一般 采用迭代法，称为下降类算法。第15页/共77页一、下降类算法的基本步骤与算法收敛性1.基本思想第16页/共77页2.基本步骤(1)(2)(3)(4)注：不同的搜索方向，就形成了

4、不同的算法，不 同的算法所产生的点列收敛于最优解的速度 也不一样。第17页/共77页3.收敛性衡量标准：二阶收敛超线性收敛线性收敛第18页/共77页二、一维搜索第19页/共77页1.分数法（斐波那契法）基本思想怎样在区间中取点最好？第20页/共77页基本概念满足绝对精度：满足相对精度：斐波那契数：553421138532119876543210第21页/共77页第22页/共77页步骤第23页/共77页例5：第24页/共77页法区别：每次取点得比例是定值0.168，即每次区间内两 点得位置均在区间相对长度得0.328和0.168处。特点：简单，更易于应用；效果也比较好。第25页/共77页3.近似

5、最佳步长公式第26页/共77页例6：第27页/共77页三、梯度法和共轭梯度法1.梯度法第28页/共77页 一般步骤(1)(2)(3)(4)第29页/共77页例7:第30页/共77页上例中，目标函数是同心圆族。无论初始点选在何处，在该点的负梯度方向总是指向圆心，而圆心就是极小点，故沿负梯度方向搜索一步便可得极小点。但对于一般的函数，若每次迭代均采用负梯度方向，则由于这些方向是彼此正交的，很可能形成开头几步下降较快，但后来便产生直角锯齿状的“拉锯”现象，收敛速度很慢。可以证明，梯度法是线性收敛的。注：第31页/共77页2.共轭梯度法基本概念第32页/共77页 这一性质说明采用共轭方向作为搜索方向，

6、对二次函数求极小可以有限步终止。由此可构造二次函数的共轭方向算法。共轭方向算法用于二次函数时均具有二次终止性。由于一般函数在一点附近的性质往往与二次函数很相似，因此共轭方向算法一般也可用于其他非线性函数，并且至少是线性收敛的。第33页/共77页一般步骤 第34页/共77页第35页/共77页例8：第36页/共77页第37页/共77页四、牛顿法与拟牛顿法1.牛顿法牛顿方向第38页/共77页第39页/共77页一般步骤 当一维搜索是精确的，牛顿法为二阶收敛。第40页/共77页缺点：计算海赛阵的逆的工作量很大。要求f(X)的二阶导存在且海赛阵是正定的(以保证H的逆阵存在和算法是下降的);改进：构造一个矩

7、阵 代替牛顿方向中的 ，使 满足：正定 只用到f(X)的一阶导信息随着k的增加，充分接近于称 为尺度阵。由于它每次都在变，故称以 代替牛顿法中的 的算法为变尺度法。第41页/共77页2.拟牛顿法拟牛顿法是尺度阵 满足 的一类变尺度法;拟牛顿法一般是超线性收敛的;DFP是一种著名的拟牛顿法;当f(X)为二次函数时，DFP法是共扼方向法，且具有二 次终止性。第42页/共77页DFP方法的一般步骤 第43页/共77页例9:第44页/共77页第45页/共77页第46页/共77页第三节 约束极值问题一般模型第47页/共77页1.基本概念和性质起作用约束第48页/共77页可行下降方向第49页/共77页可行

8、下降方向的条件第50页/共77页第51页/共77页2.最优性条件（K-T条件）第52页/共77页第53页/共77页第54页/共77页定理(K-T条件)第55页/共77页例10：利用KT条件求解下面的非线性规划第56页/共77页为解此方程组，可分几种情况考虑：第57页/共77页例11:考虑非线性规划并验证它为凸规划，用KT条件求解第58页/共77页计算目标和约束函数的海赛阵第59页/共77页第60页/共77页3.二次规划一般模型第61页/共77页第62页/共77页思考:能否在此基础上构想基于线性规划求解的方法?第63页/共77页第64页/共77页第65页/共77页例12:求解二次规划解第66页/

9、共77页第67页/共77页 1 1 3/13-2/13-4/39 1 4/13 0 9/26-3/13-9/26 3/13 2/13 133/13 0 132/13 0 2/3 1-2/3-4/9-26/9 3 1/3 2/3 1 2 033/13 1-2/3 -1 2/3 4/9 26/9 22/3 1 1/3-1/3 1-2/9-4/9 4/3 0 1 1 -5 1/3-2/3 1/3 2/3 1 2 0 5 1 -1 2 2 10 1 4/3 1 -1 3-2/3-4/3 4 1 1 1 -5 -2 -2 2 1 2 3 6 0 1 -1 2 2 10 1 4 1 -1 3 2 8 1

10、1 1 0 0 0 0 0 0第68页/共77页求得的结果是：第69页/共77页4.罚函数基本思想：将约束与目标组合在一起，化为无约束 极值问题求解。内点法：从可行域的内部逐步逼近最优解。外点法：从可行域的外部逐步逼近最优解。第70页/共77页外点法的关键是基于（NLP）构造一个新的目标函数P（X，M），称为罚函数。当X是可行点时，罚项为0当X不是可行点时，罚项是很大的整数。对P（X，M）求极小，可采用无约束优化方法，罚项能保证X逐步趋近可行域。第71页/共77页一般步骤：第72页/共77页例13：求解非线性规划解 构造罚函数第73页/共77页第74页/共77页例14：求解非线性规划解 构造罚函数第75页/共77页第76页/共77页感谢您的观看！第77页/共77页