第5章非线性规划

《第5章非线性规划》由会员分享，可在线阅读，更多相关《第5章非线性规划（191页珍藏版）》请在文档大全上搜索。

1、第五章第五章 非线性规划非线性规划Nonlinear Programming5.1 非线性规划的基本概念和定理非线性规划的基本概念和定理一、什么是非线性规划一、什么是非线性规划? 前面我们已经讨论过线性规划问题，其目标函数和前面我们已经讨论过线性规划问题，其目标函数和约束条件都是自变量的线性函数。还有一类比线性约束条件都是自变量的线性函数。还有一类比线性规划问题范围更广的数学规划，这就是非线性规划规划问题范围更广的数学规划，这就是非线性规划问题。什么是非线性规划呢问题。什么是非线性规划呢?我们先来看一个例子：我们先来看一个例子：例例1：已知立式圆柱型油罐的容积为已知立式圆柱型油罐的容积为V，设

2、油罐各层，设油罐各层圈板厚度与底板和顶板厚度相同，确定油罐的高度圈板厚度与底板和顶板厚度相同，确定油罐的高度与直径使耗钢量最少。与直径使耗钢量最少。非线性规划的基本概念和定理非线性规划的基本概念和定理解：因各圈壁板与顶板、底板厚度相等，故油罐的耗钢解：因各圈壁板与顶板、底板厚度相等，故油罐的耗钢量与其总表面积成正比。量与其总表面积成正比。 设油罐的底半径为设油罐的底半径为x，高为，高为y，则，则V=x2y，如果近似，如果近似把顶做为平板计算，则油罐的表面积为：把顶做为平板计算，则油罐的表面积为： S=2x2+2xy 该问题的数学模型为：该问题的数学模型为： 0,.22 min22yxVyxts

3、xyxS 非线性规划的基本概念和定理非线性规划的基本概念和定理分析该数学模型，可以发现，目标函数不是线性函数，分析该数学模型，可以发现，目标函数不是线性函数，而是决策变量的二次函数，约束条件也不是线性的，而而是决策变量的二次函数，约束条件也不是线性的，而是三次函数。这是一个非线性规划问题。是三次函数。这是一个非线性规划问题。miXgtsXfSi1 0)( .)( min 非线性规划的定义：非线性规划的定义：只要目标函数或约束条件中含有一只要目标函数或约束条件中含有一个非线性函数，则称这种规划为非线性规划问题。非线个非线性函数，则称这种规划为非线性规划问题。非线性规划问题的一般形式为：性规划问题

4、的一般形式为：非线性规划的基本概念和定理非线性规划的基本概念和定理*其中其中X=(xl,x2,xn)T为为n维欧式空间中的向量，维欧式空间中的向量，f(X)、gi(X)为向量函数。为向量函数。gi(X)0为由为由m个非线性等式或不等式组成的约束条件。个非线性等式或不等式组成的约束条件。 “”有三层含义：有三层含义： “=”；“或或”；“或或0，函数，函数f(X)为定义在为定义在D上的凸函数。上的凸函数。性质性质2：有限个凸函数的非负组合仍为凸函数。即：有限个凸函数的非负组合仍为凸函数。即为为凸凸函函数数 1 0)()()(2211 niXfXfXfinn 是凸集。是凸集。 )X(f ,DXXS

5、性质性质3：设：设f(X)是定义在凸集是定义在凸集D上的凸函数，则对于任意上的凸函数，则对于任意实数实数，集合，集合非线性规划的基本概念和定理非线性规划的基本概念和定理3、凸函数的判定、凸函数的判定定理定理1：(一阶条件，即用一阶导数判断一阶条件，即用一阶导数判断)设设f(X) 在开凸在开凸集集D上可微，则上可微，则f(X)为为D上凸函数的充要条件是：上凸函数的充要条件是：对于任意对于任意X(1)、X(2)，恒有，恒有 )1()2( )1()1()2()()()(XXXfXfXfT (即每一点的切线在图形的下方即每一点的切线在图形的下方)列列向向量量，处处的的一一阶阶偏偏导导数数构构成成的的在

6、在为为其其中中)1()1()()(XXfXf 即梯度向量：即梯度向量：TnxXfxXfxXfXf )(,)(,)()()1(2)1(1)1()1(开凸集是指不包括边界的凸集。开凸集是指不包括边界的凸集。非线性规划的基本概念和定理非线性规划的基本概念和定理DX 定理定理2：(二阶条件，用二阶导数判断二阶条件，用二阶导数判断)设设f(X)在开凸集在开凸集D上上二阶可微，则二阶可微，则f(X)为为D上凸函数的充要条件是：对上凸函数的充要条件是：对于所有于所有 ，其海森矩阵为半正定。若为正定，其海森矩阵为半正定。若为正定，则为严格凸函数。则为严格凸函数。4、凸函数的极值、凸函数的极值 对于凸函数的极值

7、，有以下两个重要的结论：对于凸函数的极值，有以下两个重要的结论： 凸函数的任一局部极小值等于全局极小值；若是严格凸凸函数的任一局部极小值等于全局极小值；若是严格凸函数，则局部极小点是唯一的。函数，则局部极小点是唯一的。 凸函数的极小点形成一个凸集。凸函数的极小点形成一个凸集。非线性规划的基本概念和定理非线性规划的基本概念和定理根据凸函数极值的性质，如果我们能预先证明目标函数根据凸函数极值的性质，如果我们能预先证明目标函数f(X)在可行域在可行域D内是凸函数，则可以肯定所求得的局部极内是凸函数，则可以肯定所求得的局部极小点就是全局极小点，而不用求出其所有的极小点并进小点就是全局极小点，而不用求出

8、其所有的极小点并进行比较。行比较。5、凸规划、凸规划 在非线性规划模型在非线性规划模型miXgtsXfSi1 0)( .)( min 中，如果中，如果f(X)和和-gi(X)都是凸函数，或者说都是凸函数，或者说f(X)为凸函数，为凸函数， gi(X)为凹函数，则称这种规划为凸规划。为凹函数，则称这种规划为凸规划。非线性规划的基本概念和定理非线性规划的基本概念和定理凸规划具有如下性质：凸规划具有如下性质：可行解集为凸集；可行解集为凸集；最优解集为凸集最优解集为凸集(若最优解存在的话若最优解存在的话)；任何局部最优解均为其全局最优解；任何局部最优解均为其全局最优解；若目标函数为严格凸函数，且最优解

9、存在，则最优解必唯一。若目标函数为严格凸函数，且最优解存在，则最优解必唯一。根据凸规划的定义，线性规划是一种凸规划。根据凸规划的定义，线性规划是一种凸规划。 非线性规划的基本概念和定理非线性规划的基本概念和定理例：判断下列非线性规划是否为凸规划例：判断下列非线性规划是否为凸规划? ? 0)(0)(01)(02)(.44)(min2413221221112221xXgxXgxxXgxxXgtsxxxXf非线性规划的基本概念和定理非线性规划的基本概念和定理解：先验证约束条件解：先验证约束条件gi(X)为凹函数。为凹函数。g1(X)、g3(X) 、 g4(X)均为自变量的线性函数，为凹函数；均为自变

10、量的线性函数，为凹函数；g2(X)的的海森阵为：海森阵为：为半负定，故为半负定，故g2(X)为凹函数；为凹函数； f(X)的海森阵为：的海森阵为： 0002)(22Xg为正定，故为正定，故f(X)为凸函数，上述规划为凸规划，有为凸函数，上述规划为凸规划，有唯一极小点唯一极小点X*=(0.58，1.34)T，f(X*)3.8。 2002)(2Xf5.2 无约束非线性规划寻优方法概述无约束非线性规划寻优方法概述无约束非线性规划问题的寻优方法大致可分为两类：无约束非线性规划问题的寻优方法大致可分为两类：一、间接寻优方法一、间接寻优方法(也称为解析法也称为解析法) 利用求导数寻求函数极值的方法即古典的

11、微分法就属于利用求导数寻求函数极值的方法即古典的微分法就属于这一类。这类方法要求把一个非线性规划问题用数学方这一类。这类方法要求把一个非线性规划问题用数学方程式描述出来。然后按照函数极值的必要条件用数学分程式描述出来。然后按照函数极值的必要条件用数学分析的方法求出其解析解，再按照充分条件或者问题的实析的方法求出其解析解，再按照充分条件或者问题的实际物理意义间接地确定是否最优解，因此称为间接法。际物理意义间接地确定是否最优解，因此称为间接法。这类间接寻优方法适用于目标函数具有简单而明确的数这类间接寻优方法适用于目标函数具有简单而明确的数学形式的非线性规划问题，而对于目标函数比较复杂，学形式的非线