运筹学课件：非线性规划

5/9/2025非线性规划1CONTENTS目录5/9/20255.1

概述5.2

非线性规划问题的解5.3

凸函数和凸规划5.4

下降迭代算法5.5

一维搜索5.6

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

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

5/9/20255.1.1非线性规划问题举例

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

5例5.3构件设计问题

5/9/20255.1.1非线性规划问题举例65/9/20255.1.1非线性规划问题举例

75/9/20255.1.2非线性规划数学模型非线性规划数学模型的一般形式是：—可行域

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

105/9/20255.2.1解（极值点）的定义

115/9/20255.2.2多元函数极值点的存在条件

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

135/9/20255.2.2多元函数极值点的存在条件

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

014145/9/20255.2.2多元函数极值点的存在条件

155/9/20255.2.2多元函数极值点的存在条件

165.3凸函数和凸规划5/9/20255.3.1凸函数的定义

若将上述式中的不等号反向，那么就得到凹函数（ConcaveFunction）和严格凹函数（StrictConcaveFunction）的定义。185/9/20255.3.1凸函数的定义195/9/20255.3.2凸函数的性质

205/9/20255.3.2凸函数的性质

215/9/20255.3.3凸函数的判定条件

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

是可微的，则还有下面两个性质。225/9/20255.3.4凸规划

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

那么最优解唯一。235.4下降迭代算法5/9/20255.4.1下降迭代算法

255/9/20255.4.2下降迭代算法的步骤

265.5一维搜索5/9/2025黄金分割法（0.618法）

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

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

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

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

36X0P0P1X1X2P2P3X3X*X45/9/20255.6.1梯度法375/9/20255.6.2牛顿法牛顿法（Newton’smethod)

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

395/9/20255.6.3拟牛顿法拟牛顿法（Quasi-Newtonmethod）（变尺度法（VariableMetricMethod)）

405.7约束极值问题的最优性条件5/9/20255.7.1起作用约束

425/9/20255.7.2可行方向和可行下降方向

435/9/20255.7.2可行方向和可行下降方向

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

外点法（罚函数法）

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

内点法（障碍函数法）

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