第七章 非线性规划

《第七章 非线性规划》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章非线性规划非线性规划(NonlinearProgramming，简记为NP)研究的对象是非线性函数的数值最优化问题，是运筹学的最重要分支之一，20世纪50年代形成一门学科，其理论和应用发展十分迅猛，随着计算机的发展，非线性规划应用越来越广泛，针对不同的问题提出了特别的算法，到目前为止还没有适合于各种非线性规划问题的一般算法，有待人们进一步研究.§1非线性规划基本概念一、引例例7.1一容器由圆锥面和圆柱面围成.表面积为，圆锥部分高为，和圆柱部分高之比为,为圆柱底圆半径.求使面积最大.解：由条件所以，数学模型为：s.t.例7.2某高校学生食堂用餐，拟购三种食品，馒头0.3元/个，肉

2、丸子1元/个，青菜0.6/碗.该学生的一顿饭支出不能够超过5元.问如何花费达到最满意？解：设该学生买入馒头，肉丸子，青菜的数量分别为；个人的满意度函数即为效用函数为.于是数学模型为s.t.为非负整数二、数学模型称如下形式的数学模型为数学规划（MathematicalProgramming简称MP）（7.1）（MP）（7.2）（7.3）其中是维欧几里得空间中的向量（点），为目标函数，为约束条件.称满足约束条件的向量32为（MP）问题的一个可行解，全体可行点组成的集合称为可行域.=如果均为线性函数，就是前面所学的线性规划问题(LP).如果至少有一个为非线性函数称为非线性规划问题.由于等式

3、约束等价于下列两个不等式约束所以(MP)问题又可表示为s.t.（7.4）三、数学基础1、线性代数知识考虑二次型，为维向量正定的二次型：若对于任意，有；半正定的二次型：若对于任意，有；负定的二次型：若对于任意，有；半负定的二次型：若对于任意，有；不定二次型：，有，又，有.二次型为正定的充要条件是它的矩阵的左上角各阶主子式都大于零.二次型为负定的充要条件是它的矩阵的左上角各阶主子式负正相间.2、分析数学知识（1）方向导数和梯度(二维为例)考虑函数，及方向梯度：；方向导数：考虑等值线上一点梯度方向即为法线方向.如果二次可微，称为在点处的Hesse矩阵.32（2）多元函数泰勒公式：若在点处的

4、某个领域具有二阶连续偏导数，则有四、最优解的类型定义7.1(MP)问题的一个可行点被称为整体极小点，如果对于任意的可行点，都有不等式成立.如果对于任意可行点均有，称点是的可行解集上的严格整体极小点.定义7.2问题(MP)的一个可行点被称为一个局部极小点，如果存在一个正数使得对于所有满足关系式的可行点都有成立.如果对任意的可行点，，存在一个正数使得对于所有满足关系式的可行点都有成立.则称是在上的一个局部严格极小点.显然整体极小点一定是局部极小点，反之不然.五、凸规划定义7.3集合被称为中的一个凸集，如果对于中任意两点和任一实数，点.几何解释：当一个集合是凸集时，连接此集合中任意两点的线

5、段也一定包含在此集合内，规定空集是凸集.定义7.4凸函数：是凸集上的实值函数，如果对于中任意两点和任意实数有不等式成立.严格凸函数：是凸集上的实值函数，如果对于中任意两点，和任意实数，有不等式成立.定义7.5是定义在凸集上的实值函数，如果是上凸函数，称是凹函数.定理7.1设是凸集上的凸函数，则在中的任一局部极小点都是它的整体极小点.证明：设是一局部极小点而非整体极小点，则必存在可行点(可行域).对任一，由于的凸性，有当时，与充分接近，与是局部极小矛盾.证毕.定义7.6设有(MP)问题，若可行域是凸集，是上的凸函数，则称此规划问题为凸规划.32定理7.2凸规划的任一局部极小解为整体极小

6、解.六、非线性规划问题的求解方法考虑(MP)问题：（7.5）一般来说，MP问题难以求得整体极小点，只能求得局部极小点.以后我们说求(MP)问题，指的是求局部极小点.1、无约束极小化问题（UMP）（7.6）这里是定义在上的一个实值函数定理7.3（一阶必要条件）如果是可微函数.是上述无约束问题（UMP）的一个局部极小点或局部极大点的必要条件是：.满足的点称为平稳点或驻点.定理7.4设为定义在上的二阶连续可微函数，如果是的一个局部极小点，必有这里表示在处的Hesse矩阵.证明：，根据在点处的展开式有若，当充分小时，有有.这和是的极小矛盾.定理7.5设是定义在上的二阶连续可微函数，如果点满足

7、，而且存在的一个邻域，则是的一个局部极小点.在高等数学中求解极值点方法先求出满足的点及不可导点.在这些点判断是否取得极小值.2、等式约束的极小化问题考虑（7.7）定义7.7如果在点处线性无关，则称点是此约束条件的一个正则点.Langrange乘子法：32引进拉格朗日函数其中被称为拉格朗日乘子向量.定理7.6设是连续可微函数，是在可行集中的一个局部极小点.在是正则点的假定下必存在一个拉格朗日乘子向量，使得满足方程组对等式约束，用拉格朗日乘子法求解出平稳点，判