运筹学第5章-非线性规划课件.pptx

1、7/28/2022第第5 5章章 非线性规划非线性规划1 CONTENTS目录7/28/20225.1 概述5.2 非线性规划问题的解5.3 凸函数和凸规划5.4 下降迭代算法5.5 一维搜索5.6 无约束极值问题的求解算法5.7 约束极值问题的最优性条件5.8 约束极值问题的求解算法25.1 概述例例5.1 曲线拟合曲线拟合问题问题7/28/20225.1.1 非线性规划问题举例312c tcc te(1)47/28/20225.1.1 非线性规划问题举例解解:按题意，根据最小二乘原理，有3123212,1min inc tiicccicc te 5例例5.3 构件设计问题构件设计问题7/2

2、8/20225.1.1 非线性规划问题举例67/28/20225.1.1 非线性规划问题举例2222122211212min 213 s.t.,0rhrr rhr hr hVh har h h77/28/20225.1.2 非线性规划数学模型 非线性规划非线性规划数学模型的一般形式是数学模型的一般形式是：可行域可行域 特别当特别当R=En,称为无约束优化问题称为无约束优化问题ljxxxgmixxxhtsxxxfMinnnn,.,2,1 0),.,(,.,2,1 0),.,(.),.,(21j21i21,.,1;,.,2,1;0)(,0)(|ljmiXgXhEXRjin85.2 非线性规划问题的

3、解7/28/20225.2.1 解（极值点）的定义107/28/20225.2.1 解（极值点）的定义117/28/20225.2.2 多元函数极值点的存在条件利用可行方向的定义，下面给出局部极小点所满足的条件。利用可行方向的定义，下面给出局部极小点所满足的条件。127/28/20225.2.2 多元函数极值点的存在条件137/28/20225.2.2 多元函数极值点的存在条件(b)局部极大点(b)局部极大点(c)鞍点014147/28/20225.2.2 多元函数极值点的存在条件157/28/20225.2.2 多元函数极值点的存在条件165.3 凸函数和凸规划7/28/20225.3.1

4、凸函数的定义若将上述式中的不等号反向，那么就得到凹函数凹函数（Concave Function）和严格凹函数严格凹函数（Strict Concave Function）的定义。187/28/20225.3.1 凸函数的定义197/28/20225.3.2 凸函数的性质207/28/20225.3.2 凸函数的性质217/28/20225.3.3 凸函数的判定条件要判定一个函数是否是凸函数，可以直接根据5.3.1节的定义。而如果函数 是可微的，则还有下面两个性质。227/28/20225.3.4 凸规划 性质性质5.7 凸规划的最优解具有下述特殊性质：（1）如果最优解存在，那么最优解集为凸集；（

5、2）任何局部最优解也就是全局最优解；（3）如果目标函数为严格凸函数且最优解存在，那么最优解唯一。235.4 下降迭代算法7/28/20225.4.1 下降迭代算法257/28/20225.4.2 下降迭代算法的步骤265.5 一维搜索7/28/2022 黄金分割法（0.618法）The Golden Section Search Method基本思想：基本思想：对称取点，等比例的缩小区间，除第一次外，每次只需计算对称取点，等比例的缩小区间，除第一次外，每次只需计算一次函数值，可使区间缩小。一次函数值，可使区间缩小。b0a0t11t12b1a1f(t11)f(t12)t22t215.5.1 斐波

6、那契法和黄金分割法287/28/20225.5.1 斐波那契法和黄金分割法特点：特点：l具有相同的区间缩短率具有相同的区间缩短率0.618；l精度不如精度不如Fobonacci分数法；分数法；l适用于不可微、不连续函数，可以先用适用于不可微、不连续函数，可以先用“成功成功-失败失败”法法搜索到一个包含极小点的区间。搜索到一个包含极小点的区间。297/28/2022 斐波那契法The Fibonacci Search MethodThe Fibonacci Search Method 问题：问题：l如何选择实验点，计算如何选择实验点，计算n次函数值能得到多大的区间缩短次函数值能得到多大的区间缩短

7、率？率？l换句话说，计算换句话说，计算n次函数值能将多大的区间缩短到次函数值能将多大的区间缩短到1。答案：答案：l若对称取点，利用上次已有的实验点的函数值，计算若对称取点，利用上次已有的实验点的函数值，计算n次次函数值可获得函数值可获得1/Fn区间缩短率。区间缩短率。5.5.1 斐波那契法和黄金分割法307/28/20225.5.1 斐波那契法和黄金分割法 Fibonacci 数列数列(Fibonacci Sequence)F0=1,F1=1,F2=2,F3=3,F4=5,Fk=Fk-1+Fk-2 特点：特点：l需要预先确定迭代次数需要预先确定迭代次数n;l在计算在计算n次函数值情况下，该方法

8、获得最大的区间缩次函数值情况下，该方法获得最大的区间缩短率，精度最高；短率，精度最高；l适用于不可微、不连续函数。适用于不可微、不连续函数。317/28/20225.5.2 牛顿法（切线法）基本思想：基本思想：l适合二阶连续可微的函数，求导数为适合二阶连续可微的函数，求导数为0的方程根的方程根。特点特点l适用于二阶可微函数；适用于二阶可微函数；l最快的收敛速度，二阶收敛速度；最快的收敛速度，二阶收敛速度；l初始点要求接近极小点；初始点要求接近极小点；l可与可与“成功成功-失败失败”法联合使用。法联合使用。327/28/20225.5.3 函数逼近法基本思想：基本思想：在极小点附近以插值多项式来

9、逼近目标函数的一种方法。事实上，上面的牛顿法就是在 附近用一阶Taylor展式来近似目标函数 的。函数逼近法（插值法）函数逼近法（插值法）335.6 无约束极值问题的求解算法7/28/2022 最速下降法（梯度法）最速下降法（梯度法）The Steepest descent method（The Gradient Method）基本思想：基本思想：以负梯度负梯度方向作为寻优方向 特点：特点：l迭代过程简单，存储量少，计算量小；l即使是正定二次函数也不能有限步收敛；l相邻两次寻优方向是垂直的;l寻优路线呈锯齿状（Zig-Zag)，在极小点附近收敛缓慢;5.6.1 梯度法357/28/20225.

10、6.1 梯度法36X0P0P1X1X2P2P3X3X*X47/28/20225.6.1 梯度法377/28/20225.6.2 牛顿法牛顿法（牛顿法（Newtons method)在搜索方向上比梯度法有所改进。利用了目标函数在搜索点的梯度（一阶导数）利用了目标函数的二阶导数不但不但考虑了函数的梯度，还考虑了梯度的变化考虑了函数的梯度，还考虑了梯度的变化趋势趋势，收敛速度，收敛速度快快。缺点：缺点：计算复杂，每步迭代都需要计算目标函数的二阶偏导数（Hessian矩阵）和矩阵的逆。387/28/20225.6.2 牛顿法397/28/20225.6.3 拟牛顿法拟牛顿法（拟牛顿法（Quasi-Ne

11、wton method）（变尺度法（变尺度法 （Variable Metric Method)）405.7 约束极值问题的最优性条件7/28/20225.7.1 起作用约束427/28/20225.7.2 可行方向和可行下降方向437/28/20225.7.2 可行方向和可行下降方向447/28/20225.7.3 库恩-塔克条件库恩库恩-塔克（塔克（Kuhn-Tucker）条件）条件，简称K-T条件条件，是非线性规划领域中最重要的理论成果之一，是由H.W.Kuhn和A.W.Tucker在1951年发表的关于最优性条件的论文中提出的。K-T条件是确定某点为局部最优解的一阶必要条件，只要是最优点

12、（同时是正则点）就必须满足这个条件。但一般来说，它不是充分条件，即满足这个条件的点不一定是最优点。不过对于凸规划来说，库恩-塔克条件既是必要条件，也是充分条件。455.8 约束极值问题的求解7/28/20225.8.1 外点法和内点法 外点法（罚函数法外点法（罚函数法）外点法和内点法都是通过构造某种罚函数，将有约束的优化问题转换为一系列无约束的优化问题来进行求解，因此称之为序列无约束极小化技术序列无约束极小化技术（Sequential Unconstrained Minimization Technique,SUMT）。极限意义下，无约束优化问题的解将最终收敛到有约束优化问题的解。477/28

13、/20225.8.1 外点法和内点法 内点内点法法（障碍函数（障碍函数法法）和外点法从可行域外部逐渐靠近最优解不同，内点法的主要思想是主要思想是：在可行域的边界上筑起一道很高的“围墙”，当迭代点从可行域内部靠近边界时，目标函数陡然增大，以示惩罚，阻止迭代点穿越边界，因此搜索过程始终在可行域内，每一个迭代点都是严格可行的。显然，内点法要求优化问题的可行域内部非空，因而其不适显然，内点法要求优化问题的可行域内部非空，因而其不适用于等式约束的优化问题。用于等式约束的优化问题。487/28/20225.8.2 增广拉格朗日乘子法为克服这个缺点，Hestenes和Powell于1969年首先提出了针针对等式约束优化问题的乘子法对等式约束优化问题的乘子法。Rockafellar于1973年将其推广到不等式约束的优化问题不等式约束的优化问题。本节将介绍在罚函数基础上提出的增广拉格朗日乘子法（又称增广拉格朗日乘子法（又称“乘子罚函数法乘子罚函数法”）。49