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

非线性规划第1页，此课件共77页哦第一节第一节 基本概念基本概念一、非线性规划问题与模型1.问题问题生产计划问题x:产量;P(x):价格;C(x)成本第2页，此课件共77页哦 投资决策问题第3页，此课件共77页哦 2.模型模型第4页，此课件共77页哦 二、模型的解及相关概念1.可行解与最优解可行解与最优解可行解：约束集D中的X。最优解：如果有 ，对于任意的 ，都有 ，则称 为（NLP）的最优 解，也称为全局最小值点。局部最优解：如果对于 ，使得在 的邻 域 中的任意 都有 ，则称 为（NLP）的局部最 优 解，也称为局部最小值点。第5页，此课件共77页哦例1：考虑非线性问题如果约束改为 呢？第6页，此课件共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)是否是凸函数的方法一元函数f(x)：二阶导大于等于零;多元函数f(X)：海塞阵半正定。第13页，此课件共77页哦凸规划性质：约束集是凸集；最优解集是凸集；任何局部最优解也是全局最优解；若目标函数是严格凸函数，且最优解存在，则 其最优解是唯一的。在非线性规划模型（NLP）中，若目标函数f（X）是凸函数，不等式约束函数 为凹函数，等式约束函数 为仿射函数，则称（NLP）是一个凸规划。第14页，此课件共77页哦例4：判断下面的非线性规划是否为凸规划标准化计算第15页，此课件共77页哦第二节第二节 无约束极值问题无约束极值问题一般模型：求解（f(X)可微）：应用极值条件求解，往往得到一个非线 性的方程组，求解十分困难。因此，求 解无约束问题一般 采用迭代法，称为下降类算法。第16页，此课件共77页哦一、下降类算法的基本步骤与算法收敛性1.基本思想基本思想第17页，此课件共77页哦2.基本步骤基本步骤(1)(2)(3)(4)注：不同的搜索方向，就形成了不同的算法，不 同的算法所产生的点列收敛于最优解的速度 也不一样。第18页，此课件共77页哦3.收敛性收敛性衡量标准：二阶收敛超线性收敛线性收敛第19页，此课件共77页哦二、一维搜索第20页，此课件共77页哦1.分数法分数法（斐波那契法）基本思想怎样在区间中取点最好？第21页，此课件共77页哦基本概念满足绝对精度：满足相对精度：斐波那契数：553421138532119876543210第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页哦上例中，目标函数是同心圆族。无论初始点选在何处，在该点的负梯度方向总是指向圆心，而圆心就是极小点，故沿负梯度方向搜索一步便可得极小点。但对于一般的函数，若每次迭代均采用负梯度方向，则由于这些方向是彼此正交的，很可能形成开头几步下降较快，但后来便产生直角锯齿状的“拉锯”现象，收敛速度很慢。可以证明，梯度法是线性收敛的。注：第32页，此课件共77页哦2.共轭梯度法共轭梯度法基本概念第33页，此课件共77页哦 这一性质说明采用共轭方向作为搜索方向，对二次函数求极小可以有限步终止。由此可构造二次函数的共轭方向算法。共轭方向算法用于二次函数时均具有二次终止性。由于一般函数在一点附近的性质往往与二次函数很相似，因此共轭方向算法一般也可用于其他非线性函数，并且至少是线性收敛的。第34页，此课件共77页哦一般步骤 第35页，此课件共77页哦第36页，此课件共77页哦例8：第37页，此课件共77页哦第38页，此课件共77页哦四、牛顿法与拟牛顿法1.牛顿法牛顿法牛顿方向第39页，此课件共77页哦第40页，此课件共77页哦一般步骤 当一维搜索是精确的，牛顿法为二阶收敛。第41页，此课件共77页哦缺点：计算海赛阵的逆的工作量很大。要求f(X)的二阶导存在且海赛阵是正定的(以保证H的逆阵存在和算法是下降的);改进：构造一个矩阵 代替牛顿方向中的 ，使 满足：正定 只用到f(X)的一阶导信息随着k的增加，充分接近于称 为尺度阵。由于它每次都在变，故称以 代替牛顿法中的 的算法为变尺度法。第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页，此课件共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页，此课件共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 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页哦