过程建模567-非线性规划

1、下篇下篇 非线性系统建模非线性系统建模 多年来，对多年来，对线性、时不变线性、时不变和和具有不确定参数具有不确定参数的对象的对象进行辨识的研究已取得很大进展。进行辨识的研究已取得很大进展。 然而，然而，非线性系统非线性系统大量存在于工程、经济、社会和大量存在于工程、经济、社会和生物系统中，应用传统的辨识方法很难解决这些非线性生物系统中，应用传统的辨识方法很难解决这些非线性时变系统的时变系统的辨识问题辨识问题。传统的线性系统辨识方法，在理。传统的线性系统辨识方法，在理论研究和实际应用中都存在极大的困难。论研究和实际应用中都存在极大的困难。5 非线性建模概述非线性建模概述非线性是研究、分析系统时常

2、常会遇到的一种现象。非线性是研究、分析系统时常常会遇到的一种现象。由于非线性现象从整体上非常复杂，处理起来较为困难，由于非线性现象从整体上非常复杂，处理起来较为困难，因此，常常为了简化问题而把研究的范围限制在系统的局因此，常常为了简化问题而把研究的范围限制在系统的局部性质，用泰勒展开式中的一次项来近似（线性）地描述部性质，用泰勒展开式中的一次项来近似（线性）地描述系统。系统。要对非线性系统进行正确的分析和综合，首先要正确地描要对非线性系统进行正确的分析和综合，首先要正确地描述非线性系统的整体行为，也就是要建立系统的非线性模述非线性系统的整体行为，也就是要建立系统的非线性模型。型。5 非线性建模

3、概述非线性建模概述非线性模型参数估计非线性模型参数估计5 非线性建模概述非线性建模概述有三种途径获得非线性模型的结构：有三种途径获得非线性模型的结构：u根据对象的机理（物理、化学原理和定律）或经验确根据对象的机理（物理、化学原理和定律）或经验确定模型结构；定模型结构；u根据已有先验知识，从各种典型非线性模型类中去选根据已有先验知识，从各种典型非线性模型类中去选择一个合适的结构；择一个合适的结构；u当模型先验知识十分缺乏时，可用某种一般形式的结当模型先验知识十分缺乏时，可用某种一般形式的结构去逼近非线性系统。构去逼近非线性系统。指数模型指数模型对数模型对数模型双线性模型双线性模型哈默斯模型哈默斯

4、模型Volterra级数及其离散形式神经网络模型神经网络模型支持向量机模型5 非线性建模概述非线性建模概述非线性模型参数估计非线性模型参数估计 假设已知非线性动态系统模型结构：假设已知非线性动态系统模型结构：) 1 (,uxfdtdx其中其中f是已知非线性函数，是已知非线性函数， 是待估计的参数向量。是待估计的参数向量。对该连续动态系统，从初始点对该连续动态系统，从初始点 出发可以得到模型的解出发可以得到模型的解 00 xtx)2(,0uxy 因此，对于如（因此，对于如（1）式的）式的非线性动态系统参数辨识问题，往往归非线性动态系统参数辨识问题，往往归结为式（结为式（2）的）的 非线性静态模型

5、参数估计问题非线性静态模型参数估计问题。其误差平方和最小准则为：其误差平方和最小准则为： NkkktxtyJ120,5 非线性建模概述非线性建模概述非线性模型参数估计非线性模型参数估计 在获得的或假定的模型结构上，通过某个误差准则函数来确定模型在获得的或假定的模型结构上，通过某个误差准则函数来确定模型的参数。若采用误差平方和最小准则，则称为非线性最小二乘问题。的参数。若采用误差平方和最小准则，则称为非线性最小二乘问题。求解的方法主要是运用求解的方法主要是运用最优化方法最优化方法求解。如求解。如l微分法微分法l单纯形搜索单纯形搜索l牛顿牛顿- -拉夫森算法拉夫森算法l最速下降法最速下降法l遗传算

6、法遗传算法l模拟退火算法模拟退火算法非线性规划非线性规划智能优化方法智能优化方法5 非线性建模概述非线性建模概述的约束条件 NkkktxtyJ120,minmin如果因变量与其影响因素之间不呈现线性关系，而根据如果因变量与其影响因素之间不呈现线性关系，而根据机理分析发现它们之间可以用非线性模型来描述，此时，机理分析发现它们之间可以用非线性模型来描述，此时，需要考虑非线性回归问题。需要考虑非线性回归问题。许多非线性回归问题可以转化为线性回归问题，其基本许多非线性回归问题可以转化为线性回归问题，其基本思路如下：思路如下：6 非非线性回归线性回归配曲线配曲线变量置换变量置换线性回归线性回归非线性规划

7、非线性规划例例: 出钢时所用的盛钢水的钢包，由于钢水对耐火材料的侵蚀，容积不断增大.我们希望知道使用次数与增大的容积之间的关系.对一钢包作试验，测得的数据列于下表：使用次数增大容积使用次数增大容积234567896.428.209.589.509.7010.009.939.991011121314151610.4910.5910.6010.8010.6010.9010.766 非非线性回归线性回归6.1 配曲线配曲线24681012141666.577.588.599.51010.511散点图此即非线性回归非线性回归或曲线回归曲线回归 问题（需要配曲线）6 非非线性回归线性回归6.1 配曲线配

8、曲线配曲线配曲线的一般方法是：的一般方法是：6 非非线性回归线性回归6.1 配曲线配曲线通常选择的六类曲线如下：（1）双双曲曲线线xbay1（2）幂幂函函数数曲曲线线y=abx, 其中 x0,a0（3）指指数数曲曲线线 y=abxe其中参数 a0.（5）对对数数曲曲线线y=a+blogx,x0（6）S型型曲曲线线xbeay16 非非线性回归线性回归6.1 配曲线配曲线6 非非线性回归线性回归6.1 配曲线配曲线在非线性回归分析中，根据散点图选配曲线后，针对曲在非线性回归分析中，根据散点图选配曲线后，针对曲线的非线性回归方程，需要通过变量置换法将其转化为线的非线性回归方程，需要通过变量置换法将其

9、转化为线性方程，最后按照线性回归的方法求解。线性方程，最后按照线性回归的方法求解。我们讲过，对本质线性的过程，都可以将其输入输出方我们讲过，对本质线性的过程，都可以将其输入输出方程转化为最小二乘格式（或者说线性回归模型），因此程转化为最小二乘格式（或者说线性回归模型），因此可用线性回归分析求解。可用线性回归分析求解。6 非非线性回归线性回归6.2 变量置换法变量置换法 利用变量置换法求解非线性回归方程简单易行，但是理利用变量置换法求解非线性回归方程简单易行，但是理论上存在缺陷。论上存在缺陷。 原始模型的噪声在变量置换中如何映射到新的模型不清原始模型的噪声在变量置换中如何映射到新的模型不清楚，难

10、以进行相关分析和统计检验。此外，有些变量的取值楚，难以进行相关分析和统计检验。此外，有些变量的取值限制了变量置换法的使用，如变量可以取负值就不能对它取限制了变量置换法的使用，如变量可以取负值就不能对它取对数或者开平方。对数或者开平方。 虽然变量置换也可看成一种映射，但是一般来讲这种映虽然变量置换也可看成一种映射，但是一般来讲这种映射很难用解析的形式表达，很难从原始样本空间的概率特性射很难用解析的形式表达，很难从原始样本空间的概率特性演绎出新样本空间的概率特性，当然更无法分析参数空间的演绎出新样本空间的概率特性，当然更无法分析参数空间的概率特性。概率特性。变量置换法的问题：变量置换法的问题：6

11、非非线性回归线性回归6.2 变量置换法变量置换法对于不能采取线性化方法回归的非线性回归问题，可用对于不能采取线性化方法回归的非线性回归问题，可用非线性规划非线性规划来描述：来描述：6 非非线性回归线性回归6.3 非线性规划法非线性规划法设已知变量设已知变量 ，可用非线性回归模型描述，配，可用非线性回归模型描述，配曲线为：曲线为：,.,21xxy,.,21mxxxfy 求解合理的模型参数求解合理的模型参数 ，使，使达到极小值。达到极小值。221,.,mxxxfyJ6 非非线性回归线性回归6.3 非线性规划法非线性规划法因此，非线性回归的问题可以转化为如下因此，非线性回归的问题可以转化为如下非线性

12、规划非线性规划问问题进行求解：题进行求解：的约束条件 nimxxxfyJ1221,.,minmin7 非非线性规划线性规划7.1 数学规划基本概念数学规划基本概念 从前面第从前面第5 5和第和第6 6章的介绍，我们知道，本质非线性系章的介绍，我们知道，本质非线性系统的建模，在模型结构确定情况下，无论静态系统还是动统的建模，在模型结构确定情况下，无论静态系统还是动态系统，都最终归结为用非线性规划法求解模型的参数。态系统，都最终归结为用非线性规划法求解模型的参数。 事实上，在实际工业过程中，还有许多直接使用数学事实上，在实际工业过程中，还有许多直接使用数学规划建立最优化模型的应用，如规划建立最优化

13、模型的应用，如最优路径问题、资源分配最优路径问题、资源分配问题、生产计划与调度问题、投资问题、装载问题以及生问题、生产计划与调度问题、投资问题、装载问题以及生产过程最优控制产过程最优控制等。等。 本章从本章从最优化最优化与与数学规划数学规划建模开始进行介绍。建模开始进行介绍。 数学规划（数学规划（MP, Mathematical Programming) )俗称最优化俗称最优化, ,首先是一种理念首先是一种理念, ,其次才是一种方法其次才是一种方法, ,它所追求的是一种它所追求的是一种“至善至善”之道之道, ,一种追求卓越一种追求卓越的精神。的精神。7 非非线性规划线性规划7.1 数学规划基本

14、概念数学规划基本概念 小明同学，烧一壶水要小明同学，烧一壶水要8 8分钟，灌开水要分钟，灌开水要1 1分钟，取分钟，取牛奶和报纸要牛奶和报纸要5 5分钟，整理书包要分钟，整理书包要6 6分钟，为了尽快做完这分钟，为了尽快做完这些事，怎样安排才能使时间最少？最少需要几分钟？些事，怎样安排才能使时间最少？最少需要几分钟？ 10 10个人各提一只水桶，同时到水龙头前打水。设水个人各提一只水桶，同时到水龙头前打水。设水龙头注满第一个人的桶需要龙头注满第一个人的桶需要1 1分钟，注满第二个人的桶需分钟，注满第二个人的桶需要要2 2分钟，依此类推，注满第几个人的桶就需要几分钟，分钟，依此类推，注满第几个人

15、的桶就需要几分钟，如果只有一只水龙头，适当安排这如果只有一只水龙头，适当安排这1010个人的顺序，就可以个人的顺序，就可以使每个人所费的时间总和尽可能少，问这个总费时至少是使每个人所费的时间总和尽可能少，问这个总费时至少是几分钟？几分钟？ 7 非非线性规划线性规划7.1 数学规划基本概念数学规划基本概念 数学规划数学规划(最优化最优化)作为一门学科孕育于作为一门学科孕育于20世纪世纪的的30年代年代,诞生于第二次世界大战弥漫的硝烟中。诞生于第二次世界大战弥漫的硝烟中。 数学规划指在一系列客观或主观限制条件下，数学规划指在一系列客观或主观限制条件下，寻求合理分配有限资源使所关注的某个或多个指标寻

16、求合理分配有限资源使所关注的某个或多个指标达到最大（或最小）的数学理论和方法达到最大（或最小）的数学理论和方法，是运筹学，是运筹学里一个十分重要的分支。里一个十分重要的分支。 7 非非线性规划线性规划7.1 数学规划基本概念数学规划基本概念数学规划数学规划模型的一般形式模型的一般形式为：为： （1）（2）约约束束条条件件决策变量决策变量min( ). .( )0,1,.,( )0,1,.,ijnf xs th ximgxjlxD 规划问题：求目标函数在约束条件下的最值规划问题：求目标函数在约束条件下的最值同时获得决策变量的最优解同时获得决策变量的最优解目标函数目标函数7 非非线性规划线性规划7

17、.1 数学规划基本概念数学规划基本概念数学规划模型三要素：数学规划模型三要素：7 非非线性规划线性规划7.1 数学规划基本概念数学规划基本概念决策变量决策变量( (decision variables):decision variables):它们是决策者所控制的那它们是决策者所控制的那些数量，它们取什么数值需要决策者来决策，规划些数量，它们取什么数值需要决策者来决策，规划问题的问题的求解就是找出决策变量的最优取值求解就是找出决策变量的最优取值约束条件约束条件( (constraints)constraints)：它们是决策变量在现实世界中所：它们是决策变量在现实世界中所受到的限制，或者说决策

18、变量在这些限制范围之内取值才受到的限制，或者说决策变量在这些限制范围之内取值才有实际意义有实际意义目标函数目标函数(objective function):(objective function):它代表决策者希望对其进它代表决策者希望对其进行优化的那个指标。行优化的那个指标。（2 2）所确定的）所确定的x x的范围称为的范围称为可行域可行域满足（满足（2 2）的解）的解x x称为称为可行解可行解同时满足（同时满足（1 1）（）（2 2）的解）的解x x称为称为最优解最优解整个可行域上的最优解称为整个可行域上的最优解称为全局最优解全局最优解可行域中某个领域上的最优解称为可行域中某个领域上的最优

19、解称为局部最优解局部最优解最优解所对应的目标函数值称为最优解所对应的目标函数值称为最优值最优值7 非非线性规划线性规划7.1 数学规划基本概念数学规划基本概念数学规划模型的分类数学规划模型的分类 （一）按有无约束条件（一）按有无约束条件可分为：可分为：1.无约束规划无约束规划(unconstrained programming)。2.约束规划约束规划(constrained programming)。大部分实际问题都是约束优化问题。大部分实际问题都是约束优化问题。 7 非非线性规划线性规划7.1 数学规划基本概念数学规划基本概念（二）（二）按决策变量取值是否连续按决策变量取值是否连续可分为：可

20、分为：1.连续规划连续规划。可继续划分为可继续划分为线性规划线性规划( (LP)LP)和和非线性规划非线性规划( (NLP)NLP)。在非线性规划中有一种规划叫做在非线性规划中有一种规划叫做二次规划二次规划(QP, Quadratic (QP, Quadratic programming)programming)，目标为二次函数，约束为线性函数。，目标为二次函数，约束为线性函数。2.离散规划离散规划。包含：包含：整数规划整数规划(IP, Integer programming)(IP, Integer programming)，整数规划中又包含很重要的一类规划：整数规划中又包含很重要的一类规划

21、：0-10-1（整数）规划（整数）规划，这类规划问题的决策变量只取这类规划问题的决策变量只取0 0或者或者1 1。7 非非线性规划线性规划7.1 数学规划基本概念数学规划基本概念（三）（三）按规划目标的多少按规划目标的多少可分为：可分为： 1.单目标规划。单目标规划。 2.多目标规划。多目标规划。（四）（四）按模型中参数和变量是否具有不确定性按模型中参数和变量是否具有不确定性可分为：可分为： 1.确定性规划。确定性规划。 2.不确定性规划。不确定性规划。（五）（五）按按问题求解问题求解的特性的特性可分为：可分为： 1.目标规划。目标规划。 2.动态规划。动态规划。 3.多层规划。多层规划。 4

22、.网络优化。网络优化。 5.等等。等等。7 非非线性规划线性规划7.1 数学规划基本概念数学规划基本概念7 非非线性规划线性规划7.2 非线性规划的求解非线性规划的求解凡目标函数或约束条件中包含有非线性函数的凡目标函数或约束条件中包含有非线性函数的数学规划问题都称为非线性规划问题。数学规划问题都称为非线性规划问题。它可分为无约束非线性规划与约束非线性规划。它可分为无约束非线性规划与约束非线性规划。较之线性规划模型而言，较之线性规划模型而言，非线性规划模型更能真非线性规划模型更能真实地反映问题的实质。实地反映问题的实质。7 非非线性规划线性规划7.2 非线性规划的求解非线性规划的求解1. 1.

23、无约束的非线性规划模型无约束的非线性规划模型其中，其中，f 是是12,Tnxxxx的的非线性函数，非线性函数， ,nR 称为可行域。称为可行域。min( )s.t.f xx7 非非线性规划线性规划7.2 非线性规划的求解非线性规划的求解2. 2. 约束的非线性规划模型约束的非线性规划模型其中，其中，的的非线性函数。非线性函数。(1,2,),(1,2, )和ijfh imgjl中至少有一个是中至少有一个是 x x min( )s.t.( )0 ,1,2,0,1,2,ijf xh ximgxjlx估计最小二乘准则下的非线性系统模型参数估计最小二乘准则下的非线性系统模型参数 ，可转化，可转化为上式的

24、非线性规划问题。即求满足约束条件为上式的非线性规划问题。即求满足约束条件, , 且使模且使模型输出误差平方和最小的型输出误差平方和最小的 。决策变量决策变量 待估计的非线性模型参数待估计的非线性模型参数目标函数目标函数 输出误差平方和输出误差平方和约束条件约束条件 待估计参数的可取值范围待估计参数的可取值范围非线性系统参数估计问题的描述非线性系统参数估计问题的描述：7 非非线性规划线性规划7.2 非线性规划的求解非线性规划的求解. .nstD NkkktxtyJ120,minminx f x J求解无约束非线性规划问题的方法：求解无约束非线性规划问题的方法：（1 1）微分法）微分法，根据目标函

25、数的极值点所对应的一阶导数，根据目标函数的极值点所对应的一阶导数为零，解联立方程组：为零，解联立方程组：这是一个非线性方程组，一般很难用解析方法求解，必须用这是一个非线性方程组，一般很难用解析方法求解，必须用数值计算方法逐步求出其解。这样不如用数值计算方法直接数值计算方法逐步求出其解。这样不如用数值计算方法直接求目标函数的极值。求目标函数的极值。0)()()(, 0)(21nxxfxxfxxfxf7 非非线性规划线性规划7.2 非线性规划的求解非线性规划的求解（2 2）数值法数值法。可分为：。可分为：（参见（参见“最优化方法最优化方法”课程）课程） l 直接搜索法：直接搜索法：黄金分割法黄金分

26、割法(0.618法法)、梯度法、梯度法 l 迭代法：迭代法：牛顿法、拟牛顿法、共轭梯度法牛顿法、拟牛顿法、共轭梯度法 7 非非线性规划线性规划7.2 非线性规划的求解非线性规划的求解7 非非线性规划线性规划7.2 非线性规划的求解非线性规划的求解非线性规划问题的计算机求解非线性规划问题的计算机求解LINGOLINGO软件和软件和MATLABMATLAB软件软件 对于对于LINGOLINGO软件，线性优化求解程序通常使用软件，线性优化求解程序通常使用单纯形单纯形法法simplex methodsimplex method。非线性优化求解程序采用的是。非线性优化求解程序采用的是顺序顺序线性规划法线

27、性规划法，也可用，也可用顺序二次规划法顺序二次规划法(SQP)(SQP)、广义既约梯度、广义既约梯度法，另外可以使用多初始点（法，另外可以使用多初始点（LINGOLINGO中称中称multistartmultistart）找多）找多个局部最优解增加找全局最优解的可能，还具有全局求解程个局部最优解增加找全局最优解的可能，还具有全局求解程序序分解原问题成一系列的分解原问题成一系列的凸规划凸规划。 MATLABMATLAB软件的优化工具箱，提供了线性软件的优化工具箱，提供了线性/ /非线性规划、非线性规划、无约束无约束/ /约束规划一些列函数可供调用。约束规划一些列函数可供调用。7 非非线性规划线性

28、规划7.2 非线性规划的求解非线性规划的求解优化工具箱优化工具箱3.0 (MATLAB 7.0 R14)连续优化连续优化离散优化离散优化无约束优化无约束优化非线性非线性极小极小fminunc非光滑非光滑(不可不可微微)优化优化fminsearch非线性非线性方程方程(组组)fzerofsolve全局全局优化优化暂缺暂缺非线性非线性最小二乘最小二乘lsqnonlinlsqcurvefit线性规划线性规划linprog纯纯0-1规划规划 bintprog一般一般IP(暂缺暂缺)非线性规划非线性规划fminconfminimaxfgoalattainfseminf上下界约束上下界约束fminbndf

29、minconlsqnonlinlsqcurvefit约束线性约束线性最小二乘最小二乘lsqnonneglsqlin约束优化约束优化二次规划二次规划quadprog7 非非线性规划线性规划7.2 非线性规划的求解非线性规划的求解LINDO/LINGO软件软件线性规划线性规划非线性规划非线性规划二次规划二次规划连续优化连续优化整数规划整数规划 LINDOLINGO线性优化求解程序线性优化求解程序非线性优化求解程序非线性优化求解程序1. 单纯形算法单纯形算法2. 内点算法内点算法(选选)1、顺序线性规划法、顺序线性规划法(SLP) 2、广义既约梯度法、广义既约梯度法(GRG) (选选) 3、多点搜索

30、、多点搜索(Multistart) (选选) 7 非非线性规划线性规划7.2 非线性规划的求解非线性规划的求解LINDO 公司软件产品简要介绍公司软件产品简要介绍 美国芝加哥美国芝加哥(Chicago)大学的大学的Linus Schrage教授于教授于1980年前后年前后开发开发, 后来成立后来成立 LINDO系统公司（系统公司（LINDO Systems Inc.） 网址：网址：http:/ LINDO: Linear INteractive and Discrete Optimizer (V6.1)LINDO API: LINDO Application Programming Inter

31、face (V4.1)LINGO: Linear INteractive General Optimizer (V10.0)Whats Best!: (SpreadSheet e.g. EXCEL) (V8.0)演示演示(试用试用)版、高级版、超级版、工业版、扩展版、高级版、超级版、工业版、扩展版版 （求解（求解问题规模问题规模和和选件选件不同）不同）7 非非线性规划线性规划7.2 非线性规划的求解非线性规划的求解非线性规划模型的求解具有一定的难度，并且求非线性规划模型的求解具有一定的难度，并且求解非线性规划问题的方法是多种多样的，解非线性规划问题的方法是多种多样的，。一般来说，求解非线性规划

32、的全局最优解是困一般来说，求解非线性规划的全局最优解是困难的，通常所得到的是难的，通常所得到的是。还有还有, ,求解非线性规划问题的迭代常常是无限的，求解非线性规划问题的迭代常常是无限的，即在迭代中将产生一个无穷点列，换言之，所得到即在迭代中将产生一个无穷点列，换言之，所得到的结果一般是的结果一般是。7 非非线性规划线性规划7.3 约束非线性规划约束非线性规划相对于无约束非线性规划问题，约束非线性规划问题是相对于无约束非线性规划问题，约束非线性规划问题是更为普遍的一类数学规划问题，但其求解方法比前者要更为普遍的一类数学规划问题，但其求解方法比前者要复杂得多。复杂得多。解决约束非线性规划问题的最

33、常见方法，是将其转化为解决约束非线性规划问题的最常见方法，是将其转化为无约束非线性规划问题，然后用无约束规划方法求解。无约束非线性规划问题，然后用无约束规划方法求解。可行方向法可行方向法惩罚函数法惩罚函数法约束非线性规划问题的求解方法：约束非线性规划问题的求解方法：7 非非线性规划线性规划7.3 约束非线性规划约束非线性规划可行方向法可行方向法一类处理一类处理带线性约束带线性约束的非线性规划问题的非常有效的的非线性规划问题的非常有效的方法。这种方法是将无约束优化方法推广应用于约束问方法。这种方法是将无约束优化方法推广应用于约束问题，即产生一个可行点列题，即产生一个可行点列 ，满足，满足 使得使

34、得 收敛于约束问题的极小点。收敛于约束问题的极小点。为了使点保持可行，且满足目标函数不断下降的要求，为了使点保持可行，且满足目标函数不断下降的要求，在点在点 的搜索方向不仅像无约束搜索方向那样是一个下的搜索方向不仅像无约束搜索方向那样是一个下降方向，而且是一个降方向，而且是一个可行方向可行方向。所以，这类算法总称为。所以，这类算法总称为可行方向法。可行方向法。kx1()()kkf xf xkxkx设可行域设可行域 是非空集，是非空集， 。若对于某非零向量。若对于某非零向量 存在存在 ，使对，使对 均有均有 ，则称，则称 为为从点从点 出发的可行方向。出发的可行方向。 nRD DxnRd 0,

35、0tDtdxdx7 非非线性规划线性规划7.3 约束非线性规划约束非线性规划可行方向法的搜索策略可行方向法的搜索策略：由可行点：由可行点 出发，找一下降出发，找一下降的可行方向的可行方向 作为搜索方向，然后确定沿此方向移动的作为搜索方向，然后确定沿此方向移动的步长，得到下一迭代点步长，得到下一迭代点 。搜索方向的选择方式不同就形成了不同的可行方向法。搜索方向的选择方式不同就形成了不同的可行方向法。对于对于非线性约束非线性约束情况，可把约束函数在迭代点情况，可把约束函数在迭代点 处的处的一阶泰勒多项式代替，转化成线性约束。一阶泰勒多项式代替，转化成线性约束。kxkd1kxkx7 非非线性规划线性

36、规划7.3 约束非线性规划约束非线性规划惩罚函数法（常用）惩罚函数法（常用）构造某种构造某种“惩罚惩罚”项，然后把它加到目标函数中去，项，然后把它加到目标函数中去，使约束问题的求解，转化为一系列无约束问题的求解。使约束问题的求解，转化为一系列无约束问题的求解。外部惩罚函数法（外点法）外部惩罚函数法（外点法）。对违反约束的点在目标。对违反约束的点在目标函数中加入相应的函数中加入相应的“惩罚惩罚”，而对可行点不予惩罚。这，而对可行点不予惩罚。这种方法的迭代点一般在可行域外部移动。种方法的迭代点一般在可行域外部移动。内部惩罚函数法（内点法），内部惩罚函数法（内点法），又称障碍函数法。对企又称障碍函数

37、法。对企图从内部穿越可行域边界的点在目标函数中加入相应的图从内部穿越可行域边界的点在目标函数中加入相应的“障碍障碍”，从而保障迭代一直在可行域内部移动。，从而保障迭代一直在可行域内部移动。乘子法乘子法。在拉格朗日函数中加入相应的惩罚。在拉格朗日函数中加入相应的惩罚。kxkx7 非非线性规划线性规划7.3 约束非线性规划约束非线性规划针对约束非线性规划模型针对约束非线性规划模型以下分节对惩罚函数法进行介绍以下分节对惩罚函数法进行介绍7.3.1 外点法外点法7.3.2 内点法内点法7.3.3 乘子法乘子法mixgxfi, 1,0)(s.t.)(min)(xk 算算法法思思想想：构构造造）（且且满足

38、：满足： kxDxxfxDxxfxxkkkk)()()()()()( 可取：可取：。）（）（满足条件满足条件其中其中DxxpDxxpxpxpxfxkk 0)(2;0)(1:)(, )()()( )(min)(min)(min)(minxxxxfkRxRxRxDxnnn 21 )(21k 增广增广函数函数惩罚惩罚函数函数惩罚惩罚因子因子惩罚项惩罚项7 非非线性规划线性规划7.3.1 外点法外点法，事实上，这样，我们只需构造)(xp0)( xgj因因为为 mjjmjjxgxgxp12210),(max) 0),(max)(所所以以可可设设。和和满满足足恰恰前前面面的的条条件件显显然然)2()1()

39、(xp0)0),(max2xgj的最优解。也是问题：）则。）（，即有最优解问题如果：结论)(min(, 2 , 10)()(2); )()(min: (1)*xfxmjxgDxxxDxkkjkkkRxn7 非非线性规划线性规划7.3.1 外点法外点法 0)(0)(s.t.)(minxhxgxf pjxhmixgxfji, 1, 0)(, 1, 0)(s.t.)(minq 一般模型的外点法一般模型的外点法lkmjjlkkmjjxhxgxhxgxpk12122121)(0),(max) )() 0),(max)(的惩罚函数我们不难想到构造如下q 7 非非线性规划线性规划7.3.1 外点法外点法内点

40、集内点集边界点集边界点集 DDDintD Dint（1 1）集合结构）集合结构; 0)(,| xgjxDj使使得得至至少少存存在在一一个个。,0)(|intjxgxDj 7 非非线性规划线性规划7.3.2 内点法内点法（2 2）算法思想）算法思想 内点法（障碍函数法）的迭代点是在可行域点集内内点法（障碍函数法）的迭代点是在可行域点集内部移动的，对接近可行域边界上的点施加越来越大的惩部移动的，对接近可行域边界上的点施加越来越大的惩罚，对可行域边界上的点施加无限大的惩罚，这好比边罚，对可行域边界上的点施加无限大的惩罚，这好比边界是一道障碍物，阻碍迭代点穿越边界。界是一道障碍物，阻碍迭代点穿越边界。

41、 内点法要求可行点集的内点集合非空，否则算法无法内点法要求可行点集的内点集合非空，否则算法无法运行。这样一来运行。这样一来内点法只对不等式约束的优化问题内点法只对不等式约束的优化问题才可能才可能有效。有效。7 非非线性规划线性规划7.3.2 内点法内点法, )()(xqxf(x)kk 构构造造函函数数0)()()()(min:21 kkkRxxqxfxn 转化为无约束优化问题转化为无约束优化问题（3 3）算法分析）算法分析DxxqDxxqxq if)(2intif0)(1:)(）（）（满足满足其中其中障碍障碍函数函数7 非非线性规划线性规划7.3.2 内点法内点法。等等或或等等或或 mjjmj

42、jmjmjjxgxqxgxqxgxqxgxqj11121)(ln()()(1ln)(;)(1)()(1)(（常常取取前前两两种种）一一般般取取以以下下形形式式的的函函数数)(xq求求问问题题的的极极小小点点。的的任任何何极极限限点点一一定定是是所所产产生生的的点点列列连连续续函函数数，则则由由内内点点法法上上的的都都是是）（、设设结结论论), 1()(2.knjxRmjxgxf 7 非非线性规划线性规划7.3.2 内点法内点法总结：罚函数法的缺点总结：罚函数法的缺点因而计算量大。因而计算量大。计算一系列无约束问题计算一系列无约束问题有困难；有困难；形式，在计算上形式，在计算上或或项项）时，惩罚

43、）时，惩罚（的的当外点法（或内点法）当外点法（或内点法） ,. 2)0)(0)(0 . 1 xqxpkk 7 非非线性规划线性规划7.3.2 内点法内点法1. x(0)intD2.2.等式约束不适用等式约束不适用3.3.障碍函数在障碍函数在D的可微阶数与的可微阶数与gi(x)相同相同( (可选用的无约束最优可选用的无约束最优化方法广化方法广) )4.迭代中迭代中x（k）R （随时可（随时可取取x（k）x*）5.5.非凸规划适用非凸规划适用1.任意任意x(0)Rn2.等式约束适用等式约束适用3.惩罚函数的二阶偏导在惩罚函数的二阶偏导在D的边界上不存在的边界上不存在 .非凸规划适用非

44、凸规划适用内点法内点法外点法外点法迭代中迭代中x（k）R 内、外点法的优缺点的比较内、外点法的优缺点的比较7 非非线性规划线性规划7.3.2 内点法内点法内、外点法的优缺点的比较（图解）内、外点法的优缺点的比较（图解）7 非非线性规划线性规划7.3.2 内点法内点法01s.t.31)(min3 xxxf问问题题函函数数法法）求求解解如如下下优优化化试试用用内内点点法法（内内部部惩惩罚罚1 2 3 x 1x2x3x*x331)(xxf o11200 11 102 xk *xO)(xf02s.t.)1()(min2 xxxf问问题题函函数数法法）求求解解如如下下优优化化试试用用外外点点法法（外外部部惩惩罚罚 约约束束构构成成。是是一一个个集集合合，常常由由简简单单nlnnRDDxRRhxhRRfxf:0)(s.t.:)(min liiixhvxfvxL1)()(),(:)(Lagrangexf函函数数代代替替用用为为罚罚因因子子。为为乘乘子子，其其中中：llliiiliiiRRvxhxhvxfvx 121)(