非线性规划 (2)2优秀课件.ppt

《非线性规划 (2)2优秀课件.ppt》由会员分享，可在线阅读，更多相关《非线性规划 (2)2优秀课件.ppt（77页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

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

3、是否是凸函数的方法一元函数f(x)：二阶导大于等于零;多元函数f(X)：海塞阵半正定。第13页，本讲稿共77页凸规划性质：约束集是凸集；最优解集是凸集；任何局部最优解也是全局最优解；若目标函数是严格凸函数，且最优解存在，则 其最优解是唯一的。在非线性规划模型（NLP）中，若目标函数f（X）是凸函数，不等式约束函数 为凹函数，等式约束函数 为仿射函数，则称（NLP）是一个凸规划。第14页，本讲稿共77页例4：判断下面的非线性规划是否为凸规划标准化计算第15页，本讲稿共77页第二节第二节 无约束极值问题无约束极值问题一般模型：求解（f(X)可微）：应用极值条件求解，往往得到一个非线 性的方程组，求

4、解十分困难。因此，求 解无约束问题一般 采用迭代法，称为下降类算法。第16页，本讲稿共77页一、下降类算法的基本步骤与算法收敛性1.基本思想基本思想第17页，本讲稿共77页2.基本步骤基本步骤(1)(2)(3)(4)注：不同的搜索方向，就形成了不同的算法，不 同的算法所产生的点列收敛于最优解的速度 也不一样。第18页，本讲稿共77页3.收敛性收敛性衡量标准：二阶收敛超线性收敛线性收敛第19页，本讲稿共77页二、一维搜索第20页，本讲稿共77页1.分数法分数法（斐波那契法）基本思想怎样在区间中取点最好？第21页，本讲稿共77页基本概念满足绝对精度：满足相对精度：斐波那契数：55342113853

5、2119876543210第22页，本讲稿共77页第23页，本讲稿共77页步骤第24页，本讲稿共77页例5：第25页，本讲稿共77页2.0.618法法区别：每次取点得比例是定值0.168，即每次区间内两 点得位置均在区间相对长度得0.328和0.168处。特点：简单，更易于应用；效果也比较好。第26页，本讲稿共77页3.近似最佳步长公式近似最佳步长公式第27页，本讲稿共77页例6：第28页，本讲稿共77页三、梯度法和共轭梯度法1.梯度法梯度法第29页，本讲稿共77页 一般步骤(1)(2)(3)(4)第30页，本讲稿共77页例7:第31页，本讲稿共77页上例中，目标函数是同心圆族。无论初始点选在

6、何处，在该点的负梯度方向总是指向圆心，而圆心就是极小点，故沿负梯度方向搜索一步便可得极小点。但对于一般的函数，若每次迭代均采用负梯度方向，则由于这些方向是彼此正交的，很可能形成开头几步下降较快，但后来便产生直角锯齿状的“拉锯”现象，收敛速度很慢。可以证明，梯度法是线性收敛的。注：第32页，本讲稿共77页2.共轭梯度法共轭梯度法基本概念第33页，本讲稿共77页 这一性质说明采用共轭方向作为搜索方向，对二次函数求极小可以有限步终止。由此可构造二次函数的共轭方向算法。共轭方向算法用于二次函数时均具有二次终止性。由于一般函数在一点附近的性质往往与二次函数很相似，因此共轭方向算法一般也可用于其他非线性函

7、数，并且至少是线性收敛的。第34页，本讲稿共77页一般步骤 第35页，本讲稿共77页第36页，本讲稿共77页例8：第37页，本讲稿共77页第38页，本讲稿共77页四、牛顿法与拟牛顿法1.牛顿法牛顿法牛顿方向第39页，本讲稿共77页第40页，本讲稿共77页一般步骤 当一维搜索是精确的，牛顿法为二阶收敛。第41页，本讲稿共77页缺点：计算海赛阵的逆的工作量很大。要求f(X)的二阶导存在且海赛阵是正定的(以保证H的逆阵存在和算法是下降的);改进：构造一个矩阵 代替牛顿方向中的 ，使 满足：正定 只用到f(X)的一阶导信息随着k的增加，充分接近于称 为尺度阵。由于它每次都在变，故称以 代替牛顿法中的

8、的算法为变尺度法。第42页，本讲稿共77页2.拟牛顿法拟牛顿法拟牛顿法是尺度阵 满足 的一类变尺度法;拟牛顿法一般是超线性收敛的;DFP是一种著名的拟牛顿法;当f(X)为二次函数时，DFP法是共扼方向法，且具有二 次终止性。第43页，本讲稿共77页DFP方法的一般步骤 第44页，本讲稿共77页例9:第45页，本讲稿共77页第46页，本讲稿共77页第47页，本讲稿共77页第三节第三节 约束极值问题约束极值问题一般模型第48页，本讲稿共77页1.基本概念和性质基本概念和性质起作用约束第49页，本讲稿共77页可行下降方向第50页，本讲稿共77页可行下降方向的条件第51页，本讲稿共77页第52页，本讲

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

10、稿共77页第66页，本讲稿共77页例12:求解二次规划解第67页，本讲稿共77页第68页，本讲稿共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

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