《运筹学》 课件 第5章-非线性规划

7/16/2024第5章非线性规划1CONTENTS目录7/16/20245.1

概述5.2

非线性规划问题的解5.3

凸函数和凸规划5.4

下降迭代算法5.5

一维搜索5.6

无约束极值问题的求解算法5.7

约束极值问题的最优性条件5.8约束极值问题的求解算法25.1概述例5.1曲线拟合问题

7/16/20245.1.1非线性规划问题举例

(1)47/16/20245.1.1非线性规划问题举例解:按题意，根据最小二乘原理，有

5例5.3构件设计问题

7/16/20245.1.1非线性规划问题举例67/16/20245.1.1非线性规划问题举例

77/16/20245.1.2非线性规划数学模型非线性规划数学模型的一般形式是：—可行域

—特别当R=En,称为无约束优化问题85.2非线性规划问题的解7/16/20245.2.1解（极值点）的定义

107/16/20245.2.1解（极值点）的定义

117/16/20245.2.2多元函数极值点的存在条件

利用可行方向的定义，下面给出局部极小点所满足的条件。127/16/20245.2.2多元函数极值点的存在条件

137/16/20245.2.2多元函数极值点的存在条件

(b)局部极大点(b)局部极大点(c)鞍点

014147/16/20245.2.2多元函数极值点的存在条件

157/16/20245.2.2多元函数极值点的存在条件

165.3凸函数和凸规划7/16/20245.3.1凸函数的定义

若将上述式中的不等号反向，那么就得到凹函数（ConcaveFunction）和严格凹函数（StrictConcaveFunction）的定义。187/16/20245.3.1凸函数的定义197/16/20245.3.2凸函数的性质

207/16/20245.3.2凸函数的性质

217/16/20245.3.3凸函数的判定条件

要判定一个函数是否是凸函数，可以直接根据5.3.1节的定义。而如果函数

是可微的，则还有下面两个性质。227/16/20245.3.4凸规划

性质5.7凸规划的最优解具有下述特殊性质：（1）如果最优解存在，那么最优解集为凸集；（2）任何局部最优解也就是全局最优解；（3）如果目标函数为严格凸函数且最优解存在，

那么最优解唯一。235.4下降迭代算法7/16/20245.4.1下降迭代算法

257/16/20245.4.2下降迭代算法的步骤

265.5一维搜索7/16/2024黄金分割法（0.618法）

TheGoldenSectionSearchMethod基本思想：对称取点，等比例的缩小区间，除第一次外，每次只需计算一次函数值，可使区间缩小。b0a0t11t12b1a1f(t11)<f(t12)t22t215.5.1斐波那契法和黄金分割法287/16/20245.5.1斐波那契法和黄金分割法特点：具有相同的区间缩短率0.618；精度不如Fobonacci分数法；适用于不可微、不连续函数，可以先用“成功-失败”法搜索到一个包含极小点的区间。297/16/2024斐波那契法

TheFibonacciSearchMethod问题：如何选择实验点，计算n次函数值能得到多大的区间缩短率？换句话说，计算n次函数值能将多大的区间缩短到1。答案：若对称取点，利用上次已有的实验点的函数值，计算n次函数值可获得1/Fn区间缩短率。5.5.1斐波那契法和黄金分割法307/16/20245.5.1斐波那契法和黄金分割法Fibonacci数列(FibonacciSequence)F0=1,F1=1,F2=2,F3=3,F4=5,……Fk=Fk-1+Fk-2特点：需要预先确定迭代次数n;在计算n次函数值情况下，该方法获得最大的区间缩短率，精度最高；适用于不可微、不连续函数。317/16/20245.5.2牛顿法（切线法）基本思想：适合二阶连续可微的函数，求导数为0的方程根。特点适用于二阶可微函数；最快的收敛速度，二阶收敛速度；初始点要求接近极小点；可与“成功-失败”法联合使用。327/16/2024

5.5.3函数逼近法基本思想：在极小点附近以插值多项式来逼近目标函数的一种方法。事实上，上面的牛顿法就是在附近用一阶Taylor展式来近似目标函数的。函数逼近法（插值法）335.6无约束极值问题的求解算法7/16/2024最速下降法（梯度法）

TheSteepestdescentmethod（TheGradientMethod））基本思想：以负梯度方向作为寻优方向特点：迭代过程简单，存储量少，计算量小；即使是正定二次函数也不能有限步收敛；相邻两次寻优方向是垂直的;寻优路线呈锯齿状（Zig-Zag)，在极小点附近收敛缓慢;5.6.1梯度法357/16/20245.6.1梯度法

36X0P0P1X1X2P2P3X3X*X47/16/20245.6.1梯度法377/16/20245.6.2牛顿法牛顿法（Newton’smethod)

在搜索方向上比梯度法有所改进。利用了目标函数在搜索点的梯度（一阶导数）利用了目标函数的二阶导数不但考虑了函数的梯度，还考虑了梯度的变化趋势，收敛速度快。缺点：计算复杂，每步迭代都需要计算目标函数的二阶偏导数（Hessian矩阵）和矩阵的逆。387/16/20245.6.2牛顿法

397/16/20245.6.3拟牛顿法拟牛顿法（Quasi-Newtonmethod）（变尺度法（VariableMetricMethod)）

405.7约束极值问题的最优性条件7/16/20245.7.1起作用约束

427/16/20245.7.2可行方向和可行下降方向

437/16/20245.7.2可行方向和可行下降方向

447/16/20245.7.3库恩-塔克条件库恩-塔克（Kuhn-Tucker）条件，简称K-T条件，是非线性规划领域中最重要的理论成果之一，是由H.W.Kuhn和A.W.Tucker在1951年发表的关于最优性条件的论文中提出的。K-T条件是确定某点为局部最优解的一阶必要条件，只要是最优点（同时是正则点）就必须满足这个条件。但一般来说，它不是充分条件，即满足这个条件的点不一定是最优点。不过对于凸规划来说，库恩-塔克条件既是必要条件，也是充分条件。455.8约束极值问题的求解7/16/20245.8.1外点法和内点法

外点法（罚函数法）

外点法和内点法都是通过构造某种罚函数，将有约束的优化问题转换为一系列无约束的优化问题来进行求解，因此称之为序列无约束极小化技术（SequentialUnconstrainedMinimizationTechnique,SUMT）。极限意义下，无约束优化问题的解将最终收敛到有约束优化问题的解。477/16/20245.8.1外点法和内点法

内点法（障碍函数法）

和外点法从可行域外部逐渐靠近最优解不同，内点法的主要思想是：在可行域的边界上筑起一道很高的“围墙”，当迭代点从可行域内部靠近边界时，目标函数陡然增大，以示惩罚，阻止迭代点穿越边界，因此搜索过程始终在可行域内，每一个迭代点都是严格可行的。显然，内点法要求优化问题的可行域