第三章非线性规划2

第三章

非线性规划请回顾线性规划:,其目标与约束函数均为线性的。线性规划具有相对完美的理论与方法，应用也很广泛，但它终究不能穷尽各种优化问题，因为世界是非线性的。

非线性规划（NonlinearProgramming）研究具有非线性构成函数的优化问题，是运筹学中相对活跃的重要研究分支。第一节基本概念一、非线性规划问题与模型1.问题⑴生产计划问题x:产量;P(x):价格;C(x)成本⑵投资决策问题

2.模型

二、模型的解及相关概念1.可行解与最优解★可行解：约束集D中的X。

★最优解：如果有，对于任意的，都有，则称为（NLP）的最优解，也称为全局最小值点。

★局部最优解：如果对于，使得在的邻域中的任意都有，则称为（NLP）的局部最优解，也称为局部最小值点。例1：考虑非线性问题如果约束改为呢？2.梯度、海塞阵与泰勒公式

★梯度★海塞阵★泰勒公式例2：写出在点的二阶泰勒展开式3.极值的条件对于无约束极值问题，可以利用微积分的知识给出局部极值点的条件。将n(n>1)元函数与一元函数的极值条件加以对比并归纳如下：

充分条件

必要条件例3：求的极小值点4.凸规划★凸函数：f(X)是定义在凸集D上且满足对任意有下式成立的函数：若不等式中严格不等号成立，则称f(X)为严格凸函数注：判断一个可导函数f(X)是否是凸函数的方法一元函数f(x)：二阶导大于等于零;多元函数f(X)：海塞阵半正定。★凸规划性质：★约束集是凸集；★最优解集是凸集；★任何局部最优解也是全局最优解；★若目标函数是严格凸函数，且最优解存在，则其最优解是唯一的。在非线性规划模型（NLP）中，若目标函数f（X）是凸函数，不等式约束函数为凹函数，等式约束函数为仿射函数，则称（NLP）是一个凸规划。例4：判断下面的非线性规划是否为凸规划标准化计算第二节无约束极值问题★求解（f(X)可微）：应用极值条件求解，往往得到一个非线性的方程组，求解十分困难。因此，求解无约束问题一般采用迭代法，称为下降类算法。一、下降类算法的基本步骤与算法收敛性1.基本思想2.基本步骤(1)(2)(3)(4)注：不同的搜索方向，就形成了不同的算法，不同的算法所产生的点列收敛于最优解的速度也不一样。3.收敛性衡量标准：①二阶收敛>超线性收敛>线性收敛二、一维搜索1.分数法（斐波那契法）⑴基本思想怎样在区间中取点最好？⑵基本概念★满足绝对精度：★满足相对精度：★斐波那契数：553421138532119876543210⑶步骤①②③④例5：2.0.618法★区别：每次取点得比例是定值0.168，即每次区间内两点得位置均在区间相对长度得0.328和0.168处。★特点：简单，更易于应用；效果也比较好。3.近似最佳步长公式例6：三、梯度法和共轭梯度法1.梯度法

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

④

⑤例8：四、牛顿法与拟牛顿法1.牛顿法⑴牛顿方向⑵一般步骤①

③

④②当一维搜索是精确的，牛顿法为二阶收敛。缺点：★计算海赛阵的逆的工作量很大。★要求f(X)的二阶导存在且海赛阵是正定的(以保证H的逆阵存在和算法是下降的;改进：构造一个矩阵代替牛顿方向中的，使满足：★正定★只用到f(X)的一阶导信息★随着k的增加，充分接近于称为尺度阵。由于它每次都在变，故称以代替牛顿法中的的算法为变尺度法。2.拟牛顿法★拟牛顿法是尺度阵满足的一类变尺度法;★拟牛顿法一般是超线性收敛的;★DFP是一种著名的拟牛顿法;★当f(X)为二次函数时，DFP法是共扼方向法，且具有二次终止性。DFP方法的一般步骤①③②④例9:第三节约束极值问题★一般模型1.基本概念和性质⑴起作用约束⑵可行下降方向⑶可行下降方向的条件2.最优性条件（K-T条件）定理(K-T条件)例10：利用K－T条件求解下面的非线性规划为解此方程组，可分几种情况考虑：例11:考虑非线性规划并验证它为凸规划，用K－T条件求解计算目标和约束函数的海赛阵3.二次规划★一般模型思考:能否在此基础上构想基于线性规划求解的方法?例12:求解二次规划求得的结果是：4.罚函数基本思想：将约束与目标组合在一起，化为无约束极值问题求解。★内点法：从可行域的内部逐步逼近最优解。★外点法：从可行域的外部逐步逼近最优解。★外点法的关键是基于（NLP）构造一个新的目