运筹学非线性规划

1、第三章 非线性规划,请回顾线性规划: ,其目标与约束函数 均为线性的。线性规划具有相对完美的理论与方法，应用也很广泛，但它终究不能穷尽各种优化问题，因为世界是非线性的。 非线性规划（Nonlinear Programming）研究具有非线性构成函数的优化问题，是运筹学中相对活跃的重要研究分支。,第一节 基本概念,一、非线性规划问题与模型,投资决策问题,2.模型,二 、模型的解及相关概念,1.可行解与最优解,可行解：约束集D中的X。,最优解：如果有 ，对于任意的 ， 都有 ，则称 为（NLP）的最优 解，也称为全局最小值点。,局部最优解：如果对于 ，使得在 的邻 域 中的任意 都有 ，则称 为（

2、NLP）的局部最 优 解，也称为局部最小值点。,例1：考虑非线性问题,如果约束改为 呢？,2.梯度、海塞阵与泰勒公式,梯度,海塞阵,泰勒公式,例2：写出 在 点的二阶泰勒展开式,解:,3.极值的条件,对于无约束极值问题，可以利用微积分的知识给出局部极值点的条件。将n(n1)元函数 与一元函数 的极值条件加以对比并归纳如下：,例3：求 的极小值点,解,4.凸规划,注：判断一个可导函数f(X)是否是凸函数的方法 一元函数f(x) ：二阶导大于等于零; 多元函数f(X) ：海塞阵半正定。,凸规划,性质：约束集是凸集； 最优解集是凸集； 任何局部最优解也是全局最优解； 若目标函数是严格凸函数，且最优解

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

4、收敛性,衡量标准：,二阶收敛超线性收敛线性收敛,二、一维搜索,1.分数法（斐波那契法）,基本思想,怎样在区间中取点最好？,基本概念,步骤,例5：,2. 0.618法,区别：每次取点得比例是定值0.168，即每次区间内两 点得位置均在区间相对长度得0.328和0.168处。,特点：简单，更易于应用； 效果也比较好。,3.近似最佳步长公式,例6：,三、梯度法和共轭梯度法,1.梯度法,一般步骤,(1),(2),(3),(4),例7:,上例中，目标函数是同心圆族。无论初始点选在何处，在该点的负梯度方向总是指向圆心，而圆心就是极小点，故沿负梯度方向搜索一步便可得极小点。,但对于一般的函数，若每次迭代均采

5、用负梯度方向，则由于这些方向是彼此正交的，很可能形成开头几步下降较快，但后来便产生直角锯齿状的“拉锯”现象，收敛速度很慢。可以证明，梯度法是线性收敛的。,注：,2.共轭梯度法,基本概念,这一性质说明采用共轭方向作为搜索方向，对二次函数求极小可以有限步终止。由此可构造二次函数的共轭方向算法。共轭方向算法用于二次函数时均具有二次终止性。由于一般函数在一点附近的性质往往与二次函数很相似，因此共轭方向算法一般也可用于其他非线性函数，并且至少是线性收敛的。,一般步骤,例8：,四、牛顿法与拟牛顿法,1.牛顿法,牛顿方向,一般步骤,当一维搜索是精确的，牛顿法为二阶收敛。,缺点：,2.拟牛顿法,DFP方法的一般步骤,例9:,第三节 约束极值问题,一般模型,1.基本概念和性质,起作用约束,可行下降方向,可行下降方向的条件,2.最优性条件（K-T条件）,定理 (K-T条件),例10：利用KT条件求解下面的非线性规划,为解此方程组，可分几种情况考虑：,例11:考虑非线性规划并验证它为凸规划，用KT条件求解,计算目标和约束函数的海赛阵,3.二次规划,一般模型,思考:能否在此基础上构想基于线性规划求解的方法?,例12: 求解二次规划,解,求得的结果是：,4.罚函数,外点法的关键是基于（NLP）构造一个新的目标函数P（X，M），称为罚函数。,当X是可行点时，罚项为0,当X不是可行点时