文档介绍：第七章非线性规划
非线性规划(Nonlinear Programming,简记为NP)研究的对象是非线性函数的数值最优化问题,是运筹学的最重要分支之一,20世纪50年代形成一门学科,其理论和应用发展十分迅猛,随着计算机的发展,非线性规划应用越来越广泛,针对不同的问题提出了特别的算法,到目前为止还没有适合于各种非线性规划问题的一般算法,有待人们进一步研究.
§1 非线性规划基本概念
解:设该学生买入馒头,肉丸子,青菜的数量分别为x1,x2,x3;个人的满意度函数即为效用函数为u(x1,x2,x3)=
某高校学生食堂用餐,拟购三种食品,,肉丸子1元/个,.问如何花费达到最满意?
显然,此模型即为非线性.
一容器由圆锥面和圆柱面围成. 表面积为,圆锥部分高为, 和圆柱部分高之比为, 使面积最大.
解: 由条件
所以,数学模型为:
.
二、数学模型
称如下形式的数学模型为数学规划(Mathematical Programming 简称MP)
n是维欧几里得空间Rn中的向量(点),f(x)
称满足约束条件的向量x为(MP)问题的一个可行解,全体可行点组成的集合称为可行域.
如果f(x),gi(x),hi(x)均为线性函数,就是前面所学的线性规划问题(LP).如果至少有一个为非线性函数称为非线性规划问题.
由于等式约束hi(x)=0等价于下列两个不等式约束
所以(MP)问题又可表示为
1、线性代数知识
考虑二次型ZTAZ,Z为n维向量
正定的二次型:若对于任意Z≠0,有ZTAZ>0;
半正定的二次型:若对于任意Z≠0,有ZTAZ≥0;
负定的二次型:若对于任意Z≠0,有ZTAZ<0;
半负定的二次型:若对于任意Z≠0,有ZTAZ≤0;
不定的二次型:存在Z≠0,有ZTAZ>0,又存在Z≠0,有ZTAZ<0.
二次型ZTAZ为正定的充要条件是它的矩阵A的左上角各阶主子式都大于零.
二次型ZTAZ为负定的充要条件是它的矩阵A的左上角各阶主子式负正相间.
三、数学基础
为f(x)在点x处的Hesse矩阵.
2、分析数学知识
(1)方向导数和梯度(二维为例)
四、最优解的类型
(MP)问题的一个可行点x*被称为整体极小点,如果对于任意的可行点x∈K,都有不等式f(x)≥f(x*)成立. 如果对于任意可行点x∈K, x≠x*,均有f(x)>f(x*),称点x*是f(x)的可行解集K上的严格整体极小点.
(MP)问题的一个可行点x*被称为局部极小点,如果存在一个正数ε使得对于所有满足关系式‖x- x*‖<ε的可行点x都有 f(x)≥f(x*)成立. 如果对任意的可行点x∈K, x≠x*,存在一个正数ε使得对于所有满足关系式‖x- x*‖<ε的可行点x都有 f(x)>f(x*)*是f(x),反之不然.
五、凸规划
集合被称为中的一个凸集,如果对于中任意两点和任一实数,点.
几何解释:当一个集合是凸集时,连接此集合中任意两点的线段也一定包含在此集合内,规定空集是凸集.
凸函数: 是凸集上的实值函数,如果对于中任意两点和任意实数有不等式
成立.
严格凸函数: 是凸集上的实值函数,如果对于中任意两点,和任意实数,有不等式
成立.
是定义在凸集上的实值函数,如果是上凸函数,称是凹函数.
设是凸集上的凸函数,则在中的任一局部极小点都是它的整体极小点.
证明: 设是一局部极小点而非整体极小点,则必存在可行点(可行域) .对任一,由于的凸性,有
当时, 与充分接近,与是局部极小矛盾. 证毕.
设有(MP)问题,若可行域是凸集, 是上的凸函数,则称此规划问题为凸规划.
凸规划的任一局部极小解为整体极小解.
六、非线性规划问题的求解方法—迭代法
考虑(MP)问题:
一般来说,MP问题难以求得整体极小点,(MP)问题,指的是求局部极小点.
1、无约束极小化问题
(UMP) ()
这里是定义在上的一个实值函数
()