第六章-非线性规划基本概念与基本原理

第六章非线性规划基本概念与基本原理本章讲授非线性规划的基本概念、非线性规划的最优解所满足的必要条件和充分条件，这些条件是非线性规划的各种数值算法的推导和分析提供必不可少的理论基础。本章还将讲授非线性规划问题数值算法的基本迭代形式和收敛性准则。6.1非线性规划的数学模型和基本概念6.1.1非线性规划问题举例非线性规划问题是一类优化问题，在这类问题中，目标函数或约束函数至少有一个不是决策变量的线性函数。显然，非线性规划问题相对于线性规划问题而言更具一般性，在工程实际中也更普遍．例6-1某公司专门生产储藏用的容器，订货合同要求该公司制造一种敞口的长方体容器，容积恰好为12立方米,该种容器的底必须为正方形，容器总重量不超过68公斤，已知用做容器四壁的材料为每平方米10元，重3公斤；用做容器底的材料每平方米20元，重2公斤．试问制造该容器所需的最小费用是多少？列出数学模型．设该容器的底边长和高分别为x1米和x2米，则有目标函数：minf(x)=40x1x2+20x12约束条件：x12x2=1212x1x2+2x12≤68x1≥0,x2≥0记为minf(x)=40x1x2+20x12s.tx12x2=1212x1x2+2x12≤68x1≥0x2≥0其中s.t是subjectto（受约束于）的缩写，min是minimize（最小化）的缩写．例6-2定位问题假设要选定一个供应中心的位置，由这个中心向城市中位置固定的m个用户提供服务中心供应的商品，可以是电、水、牛奶和其他货物，供应中心的设置定位准则是使从中心到用户的“距离”最小．例如，可以是使中心到各用户的最大距离为最小，假定在这个城市里货物必须沿互相垂直的路线（街道）供应，那么合适的距离函数就是矩形距离．下面列出其数学模型：设（x1,x2）表示供应中心的待定位置（坐标），而（ai，bi）是第i个用户的所在位置，则问题的目标函数是]}[{211,21xbxaiimixxmaxmin这个式子意昧着，首先对（x1,x2）的每个可能值求出指标I，使方括号中的矩形距离最大；其次在依赖于（x1,x2）的所有最大距离中求出最小的．如果每一位置（x1,x2）都可以接受，那么问题是无约束的；如果还有其他限制，例如供应中心到某几个用户的距离必须在某个范围内．则问题是有约束的．例6-3设要设什一个如图6.1.1所示的半球形和圆柱形相连接的构件，要求在构件体积为一定的条件下确定构件的尺寸，使其表面积最小．图6.1.1半球形和圆柱形相连接的构件构件的大小取决于其中圆住体的底半径和高，今设该圆柱体的底毕径为x1，高为x2，由于构件的表面由半球顶面、侧面和底面构成，因此其表面积为21212122xxxxS构件的体积为半球体和圆住体之和，所以若要使构件的体积为定值V0，应该满足条件02213132Vxxx又构件的底半径和圆柱体之高显然非负，故还要求x1≥0,x2≥0因此本例的数学模型为min21212122xxxxSs.t.02213132Vxxxx1≥0，x2≥06.1.2非线性规划问题的一般数学模型一般非线性规划的数学模型可表示为()..()0(1,2,,)()0(1,2,,)ijminfxsthximgxjlLL(6-1)式中12(,,,)TnnxxxxRL，是n维向量，),,2,1(),,,2,1(,ljgmihfji都是nRR的映射（即自变量是n维向量，因变量是实数的函数关系）．6.1.3基本概念6.1.3．1局部极值与全局极值定义6-1设x*∈Rn,δ0，集合},|{*xxRxxn且称为x*的δ邻域，记为N(x*，δ)，其中*xx表示x与x*之间的距离（通常为欧几里德距离）．定义6-2设f(x)为定义在n维欧氏空间En中的某一区域S上的n元实函数，其中Tnxxxx),,,(21．对于x*∈S，若存在某个ε0，对任意的x∈N(x*，δ)∩S均有f(x)≥f(x*)，则称x*为f(x)在S上的局部极小点，f(x*)为局部极小值．若对于所有x∈N(x*，δ)∩S且x≠x*都有f(x)f(x*)，则称x*为f(x)在S上的严格局部极小点，f(x*)为严格局部极小值．定义6-3设f(x)为定义在n维欧氏空间Rn中的某一区域S上的n元实函数，其中Tnxxxx),,,(21．对于x*∈S，若存在某个ε0，对任意的x∈S均有f(x)≥f(x*)，则称x*为f(x)在S上的全局极小点，f(x*)为全局极小值．若对于所有x∈S且x≠x*都有f(x)f(x*)，则称x*为f(x)在S上的严格全局极小点，f(x*)为严格全局极小值．如果将定义6-2和6-3中的不等式反向，即可得到相应的极大点和极大值的定义．本教材主要就极小点和极小值进行讨论，而且主要研究局部极小．对于极大化问题可通过恒等式maxf(x)=－min(－f(x))转化为极小化问题．6.1.3.２．梯度可微函数f(x)的梯度，记为▽f(x),它是以f(x)对),,2,1(nixi的偏导数为元素的n维向量(本书规定为列向量),于是有Tnxxfxxfxxfxf))(,,)(,)(()(21(6-6)梯度又称为函数f(x)关于向量x的一阶导数．函数f(x)在某一点x(0)的梯度就是将x(0)的各分量代入(6-6)即可，即Tnxxfxxfxxfxf))(,,)(,)(()()0(2)0(1)0()0((6-7)特别地，一元函数的梯度就是一阶导数．梯度两个重要性质，假设在所考察的区间内梯度是连续的．性质1：函数f(x)在某一点x(0)的梯度▽f(x(0))，必与过该点的等值面（其方程为f(x)=f(x(0))）的切平面相垂直（假定▽f(x(0))≠0）．或者说▽f(x(0))表示过x(0)的f(x)的等值面在x(0)处的法向量．性质2：梯度方向是函数值增加最快的方向，即函数变化率最大的方向，而负梯度方向则是函数值减小最快的方向．如果采用欧几里德距离，函数f(x)在x(0)处的梯度的模取为：2)0(22)0(21)0()0()()()()(nxxfxxfxxfxf(6-8)如果不用欧几里德度量而选用某些别的距离，则梯度方向就未必是函数值增加最快的方向．满足的▽f(x*)=0的点x*称为驻点或平稳点，在定义域内部可微函数的极值点必为驻点，反之未必．6．1．3．3海赛矩阵(Hesse)假定函数f(x)二阶可微，则以其二阶偏导数为元素构成的下述n×n矩阵称为f(x)的海赛矩阵，记为▽2f(x)，有22221222222122122122122)()()()()()()()()()(nnnnnxxfxxxfxxxfxxxfxxfxxxfxxxfxxxfxxfxf(6-9)它又称为n元函数f(x)对向量x的二阶导数，即▽f(x)对向量x的一阶导数．特别地，一元函数的海赛矩阵就是二阶导数．在微积分中已经证明过，当f(x)的二阶偏导数连续时，混合偏导数与求导顺序无关，即),,2,1;,,2,1()()(22njnixxxfxxxfijji此时，▽2f(x)是对称矩阵．函数在某一点x(0)处的海赛矩阵就是将x(0)的各分量值代入(6-9)中矩阵各元素（二阶偏导函数）即可．特别地，当f(x)是二次函数时，则f(x)必可写成下列形式：CxBAxxxfTT21)((6-10)这里A是n×n实对称矩阵，B为n维列向量，C为常数．容易验证，函数f(x)的海赛矩阵为▽2f(x)=A，即二次函数的海赛矩阵是一个常数矩阵，它与x的位置无关．反过来，如果要把一个二次函数化为(6-10)的形式，可以通过求该二次函数的海赛矩阵和梯度求出相应的A，B和C即可．6．1．3．4．实对称矩阵的正定性、负定性、半定性和不定性设有实对称矩阵nnnnnnaaaaaaaaaA212222111211方阵A的行列式用detA表示，其各阶顺序主子式为Ai，则一阶顺序主子式A1=a11二阶顺序主子式12212211222112112aaaaaaaaA三阶顺序主子式2322131231333213122133322322113332312322211312113aaaaaaaaaaaaaaaaaaaaaaaaA其余各阶顺序主子式依此类推．表6-1给出了各矩阵的定义及充分必要条件．表6-1名称定义充分必要条件正定矩阵特征值都大于零的实对称矩阵所有各阶顺序主子式都大于零，即),,2,1(0detniAi半正定矩阵特征值都不小于零的实对称矩阵0detA)1,,2,1(0detniAi且负定矩阵特征值都小于零的实对称矩阵),,2,1()(0)(0detniiiAi为偶数为奇数半负定矩阵特征值都不大于零的实对称矩阵0detA)1,,2,1()(0)(0detniiiAi为偶数为奇数且不定矩阵特征值既有大于零又有小于零的实对称矩阵有两个奇数阶顺序主子式，其中一个为正，另一个为负6.2凸函数和凸规划回顾一下凸集的概念：定义：设集合SRn，若x(1),x(2)S,[0,1]，必有x(1)＋(1-)x(2)S，则称S为凸集。规定：单点集{x}为凸集，空集为凸集。注:x(1)＋(1-)x(2)=x(2)＋(x(1)-x(2))是连接x(1)与x(2)的线段。凸集非凸集非凸集6.2.1凸函数定义与性质1、凸函数及水平集定义:设集合SRn为凸集，函数f:SR若x(1),x(2)S,(0,1)，均有f(x(1)＋(1-)x(2))≤f(x(1))+(1-)f(x(2))，则称f(x)为凸集S上的凸函数。若进一步有上面不等式以严格不等式成立，则称f(x)为凸集S上的严格凸函数。•当-f(x)为凸函数（严格凸函数）时，则称f(x)为凹函数（严格凹函数）。严格凸函数凸函数严格凹函数•定理：f(x)为凸集S上的凸函数S上任意有限点的凸组合的函数值不大于各点函数值的凸组合。•思考：设f1,f2是凸函数，1)设1,20,1f1+2f2,1f1-2f2是否凸函数？2)f(x)=max{f1(x),f2(x)},g(x)=min{f1(x),f2(x)}是否凸函数？凸函数的性质利用凸函数的定义可以研究凸函数的性质．性质1设f(x)为定义在凸集S上的凸函数，则对任意实数β≥0，函数βf(x)也是定义在凸集S上的凸函数．性质2设f1(x)和f2(x)都是定义在凸集S上的凸函数，则f1(x)＋f2(x)也是定义在凸集S上的凸函数．•定义：设集合SRn，函数f:SR，βR，称•Sβ={xS∣f(x)≤β}•为f(x)在S上的β水平集。•注：水平集的概念相当于在地形图中，海拔高度不高于某一数值的区域。性质3设f(x)为定义在凸集S上的凸函数，则对任意实数β，集合})(,|{xfSxxS是凸集．上述命题的逆不真。考虑分段函数f(x)=1(x≥0)或0(x0)，函数非凸，但任意水平集是凸集。性质4若f(x)是定义在凸集S上的凸函数，则f(x)的任一个极小点就是它在S上的全局极小点，而且所有极小点的集合是凸集．性质4的证明：利用性质3来证明性质4．设x*是f(x)的一个局部极小点，即存在δ0，在x*的δ邻域N(x*，δ)内，所有的x都满足：f(x)≥f(x*)．在S中任取一点x(0)，连x(0)和x*，则存在一个λ∈(0，1)，使),()1(*)0(*xNxx记x(1)=(1－λ)x*+λx(0)，则有)())1(()(*)0(*)1(xfxxfxf(6-13)又因f(x)是S上的凸函数，所以有)()()1())1(()0(*)0(*xf