[管理学]第三章非线性规划.pptVIP

第三章 非线性规划 第一节 基本概念 ⑵投资决策问题 2.模型 二 、模型的解及相关概念 例1：考虑非线性问题 2.梯度、海塞阵与泰勒公式 ★海塞阵 ★泰勒公式 例2：写出 在 点的二阶泰勒展开式 3.极值的条件 例3：求 的极小值点 4.凸规划 ★凸规划 例4：判断下面的非线性规划是否为凸规划 第二节 无约束极值问题 一、下降类算法的基本步骤与算法收敛性 2.基本步骤 3.收敛性 二、一维有哪些信誉好的足球投注网站 1.分数法（斐波那契法） ⑵基本概念 ⑶步骤 例5： 2. 0.618法 3.近似最佳步长公式 例6： 三、梯度法和共轭梯度法 ★一般步骤 例7: 2.共轭梯度法 ⑵一般步骤 例8： 四、牛顿法与拟牛顿法 ⑵一般步骤 2.拟牛顿法 DFP方法的一般步骤 例9: 第三节 约束极值问题 1.基本概念和性质 ⑵可行下降方向 ⑶可行下降方向的条件 2.最优性条件（K-T条件） 定理 (K-T条件) 例10：利用K－T条件求解下面的非线性规划 为解此方程组，可分几种情况考虑： 例11:考虑非线性规划并验证它为凸规划，用K－T条件求解 计算目标和约束函数的海赛阵 3.二次规划 例12: 求解二次规划 4.罚函数 一般步骤： 例13：求解非线性规划 例14：求解非线性规划 思考:能否在此基础上构想基于线性规划求解的方法? 解 1 1 3/13 -2/13 -4/39 1 4/13 0 9/26 -3/13 -9/26 3/13 2/13 1 33/13 0 1 32/13 0 2/3 1 -2/3 -4/9 -26/9 3 1/3 2/3 1 2 0 33/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 求得的结果是： 基本思想：将约束与目标组合在一起，化为无约束 极值问题求解。 ★ 内点法：从可行域的内部逐步逼近最优解。 ★ 外点法：从可行域的外部逐步逼近最优解。 ★ 外点法的关键是基于（NLP）构造一个新的目标函数P（X，M），称为罚函数。 当X是可行点时，罚项为0 当X不是可行点时，罚项是很大的整数。 对P（X，M）求极小，可采用无约束优化方法，罚项能保证X逐步趋近可行域。 ① ② ③ 上例中，目标函数是同心圆族。无论初始点选在何处，在该点的负梯度方向总是指向圆心，而圆心就是极小点，故沿负梯度方向有哪些信誉好的足球投注网站一步便可得极小点。 但对于一般的函数，若每次迭代均采用负梯度方向，则由于这些方向是彼此正交的，很可能形成开头几步下降较快，但后来便产生直角锯齿状的“拉锯”现象，收敛速度很慢。可以证明，梯度法是线性收敛的。 注： ⑴基本概念 ★ ★ 这一性质说明采用共轭方向作为有哪些信誉好的足球投注网站方向，对二次函数求极小可以有限步终止。由此可构造二次函数的共轭方向算法。共轭方向算法用于二次函数时均具有二次终止性。由于一般函数在一点附近的性质往往与二次函数很相似，因此共轭方向算法一般也可用于其他非线性函数，并且至少是线性收敛的。 ① ③ ② ④ ⑤ 1.牛顿法 ⑴牛顿方向 ① ③ ④ ② 当一维有哪些信誉好的足球投注网站是精确的，牛顿法为二阶收敛。 缺点： ★计算海赛阵的逆的工作量很大。 ★要求f(X)的二阶导存在且海赛阵是正定的(以保证H的逆阵存在和算法是下降的); 改进： 构造一个矩阵 代替牛顿方向中的 ，使 满足： ★ 正定 ★ 只用到f(X)的一阶导信息 ★随着k的增加，