非线性规划 (2)2精选文档.ppt

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

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

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

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

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

5、对精度：斐波那契数：553421138532119876543210本讲稿第二十二页，共七十七页本讲稿第二十三页，共七十七页步骤本讲稿第二十四页，共七十七页例5：本讲稿第二十五页，共七十七页2.0.618法法区别：每次取点得比例是定值0.168，即每次区间内两 点得位置均在区间相对长度得0.328和0.168处。特点：简单，更易于应用；效果也比较好。本讲稿第二十六页，共七十七页3.近似最佳步长公式近似最佳步长公式本讲稿第二十七页，共七十七页例6：本讲稿第二十八页，共七十七页三、梯度法和共轭梯度法1.梯度法梯度法本讲稿第二十九页，共七十七页 一般步骤(1)(2)(3)(4)本讲稿第三十页，共七十

6、七页例7:本讲稿第三十一页，共七十七页上例中，目标函数是同心圆族。无论初始点选在何处，在该点的负梯度方向总是指向圆心，而圆心就是极小点，故沿负梯度方向搜索一步便可得极小点。但对于一般的函数，若每次迭代均采用负梯度方向，则由于这些方向是彼此正交的，很可能形成开头几步下降较快，但后来便产生直角锯齿状的“拉锯”现象，收敛速度很慢。可以证明，梯度法是线性收敛的。注：本讲稿第三十二页，共七十七页2.共轭梯度法共轭梯度法基本概念本讲稿第三十三页，共七十七页 这一性质说明采用共轭方向作为搜索方向，对二次函数求极小可以有限步终止。由此可构造二次函数的共轭方向算法。共轭方向算法用于二次函数时均具有二次终止性。由

7、于一般函数在一点附近的性质往往与二次函数很相似，因此共轭方向算法一般也可用于其他非线性函数，并且至少是线性收敛的。本讲稿第三十四页，共七十七页一般步骤 本讲稿第三十五页，共七十七页本讲稿第三十六页，共七十七页例8：本讲稿第三十七页，共七十七页本讲稿第三十八页，共七十七页四、牛顿法与拟牛顿法1.牛顿法牛顿法牛顿方向本讲稿第三十九页，共七十七页本讲稿第四十页，共七十七页一般步骤 当一维搜索是精确的，牛顿法为二阶收敛。本讲稿第四十一页，共七十七页缺点：计算海赛阵的逆的工作量很大。要求f(X)的二阶导存在且海赛阵是正定的(以保证H的逆阵存在和算法是下降的);改进：构造一个矩阵 代替牛顿方向中的 ，使

8、满足：正定 只用到f(X)的一阶导信息随着k的增加，充分接近于称 为尺度阵。由于它每次都在变，故称以 代替牛顿法中的 的算法为变尺度法。本讲稿第四十二页，共七十七页2.拟牛顿法拟牛顿法拟牛顿法是尺度阵 满足 的一类变尺度法;拟牛顿法一般是超线性收敛的;DFP是一种著名的拟牛顿法;当f(X)为二次函数时，DFP法是共扼方向法，且具有二 次终止性。本讲稿第四十三页，共七十七页DFP方法的一般步骤 本讲稿第四十四页，共七十七页例9:本讲稿第四十五页，共七十七页本讲稿第四十六页，共七十七页本讲稿第四十七页，共七十七页第三节第三节 约束极值问题约束极值问题一般模型本讲稿第四十八页，共七十七页1.基本概念

9、和性质基本概念和性质起作用约束本讲稿第四十九页，共七十七页可行下降方向本讲稿第五十页，共七十七页可行下降方向的条件本讲稿第五十一页，共七十七页本讲稿第五十二页，共七十七页2.最优性条件最优性条件（K-T条件）本讲稿第五十三页，共七十七页本讲稿第五十四页，共七十七页本讲稿第五十五页，共七十七页定理定理(K-T条件)本讲稿第五十六页，共七十七页例10：利用KT条件求解下面的非线性规划本讲稿第五十七页，共七十七页为解此方程组，可分几种情况考虑：本讲稿第五十八页，共七十七页例11:考虑非线性规划并验证它为凸规划，用KT条件求解本讲稿第五十九页，共七十七页计算目标和约束函数的海赛阵本讲稿第六十页，共七十

10、七页本讲稿第六十一页，共七十七页3.二次规划二次规划一般模型本讲稿第六十二页，共七十七页本讲稿第六十三页，共七十七页思考:能否在此基础上构想基于线性规划求解的方法?本讲稿第六十四页，共七十七页本讲稿第六十五页，共七十七页本讲稿第六十六页，共七十七页例12:求解二次规划解本讲稿第六十七页，共七十七页本讲稿第六十八页，共七十七页 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/

11、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 1 1 0 0 0 0 0 0本讲稿第六十九页，共七十七页求得的结果是：本讲稿第七十页，共七十七页4.罚函数罚函数基本思想：将约束与目标组合在一起，化为无约束 极值问题求解。内点法：从可行域的内部逐步逼近最优解。外点法：从可行域的外部逐步逼近最优解。本讲稿第七十一页，共七十七页外点法的关键是基于（NLP）构造一个新的目标函数P（X，M），称为罚函数。当X是可行点时，罚项为0当X不是可行点时，罚项是很大的整数。对P（X，M）求极小，可采用无约束优化方法，罚项能保证X逐步趋近可行域。本讲稿第七十二页，共七十七页一般步骤：本讲稿第七十三页，共七十七页例13：求解非线性规划解 构造罚函数本讲稿第七十四页，共七十七页本讲稿第七十五页，共七十七页例14：求解非线性规划解 构造罚函数本讲稿第七十六页，共七十七页本讲稿第七十七页，共七十七页