第六章 非线性规划

第六章 非线性规划由前几章知道，线性规划的目标函数和约束条件都是其自变量的线性函数，如果目标函数或约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。

第一节 基本概念一、 非线性规划的数学模型非线性规划数学模型的一般形式是⎪⎩⎪⎨⎧=≥==),,2,1(0)(),,2,1(0)()(min l j x g m i x h x f ji （6.1）其中，X=（n χχχ,,,21 ）T 是n 维欧氏空间E n 中的点（向量），目标函数)(X f 和约束函数)()(X j X i g h 、为X 的实函数。

有时，也将非线性规划的数学模型写成 ⎩⎨⎧=≥),,2,1(0)()(min l j X g X f j (6.2)即约束条件中不出现等式，如果有某一约束条件为等式0)(=X g j ，则可用如下两个不等式约束替代它： ⎩⎨⎧≥-≥0)(0)(X g X g jj模型（6.2）也常表示成另一种形式：{}⎩⎨⎧=≥=⊂∈),,2,1(,0)(|),(min l j X g X R E R X X f j n (6.3)上式中R 为问题的可行域。

若某个约束条件氏“≤”不等式的形式，只需用“-1”乘这个约束的两端，即可将其变成“≥”的形式。

此外，由于[])(m in )(m ax x f X f --=，且这两种情况下求出的最优解相同（如有最优解存在），故当需使目标函数极大化时，只需求其负函数极小化即可。

二、二维问题的图解当只有两个自变量时，求解非线性规划也可像对线性规划那样借助于图解法。

考虑非线性规划问题⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥≥-+=-+-+-=000505)1()2()(min 212122212221x x x x x x x x x X f (6.4)如对线性规划所作的那样，在21Ox x 坐标平面画出目标函数的等值线，它是以点（2.1）为圆心的同心圆，再根据约束条件画出可行域，它是抛物线段ABCD （图6-1）。

现分析当自变量再可行域内变化时目标函数值的变化情况。

令动点从A 出发沿抛物线ABCD 移动，当动点从A 移向B 时，目标函数值下降；当动点有B 移向C 时，目标函数值上升。

从而可知，在可行域AC 这一范围内，B 点的目标函数值)(B f 最小，因而点B 时一个极小点。

当动点由C 向D 移动时，目标函数值再次下降，在D点（其坐标为（ 4.1））目标函数值最小。

在本例中，目标函数值)(B f 仅是目标函数)(X f 在一部分可行域上的极小值，而不是在整个可行域上的极小值，这样的极小值称为局部极小值（或相对极小值）。

像B 这样的点称为局部极小点（或相对极小点）。

)(D f 是整个可行域上的极小值，称全局极小值（最小值），或绝对极小值；像D 这样的点称全局极小值（最小点），或绝对极小点。

全局极小点当然也是局部极小点，但局部极小点不一定是全局极小点。

三、几个定义下面给出有关局部极小和全局极小的定义。

设)(x f 为定义在n 维欧氏空间n E 的某一区域R 上的n 元实函数（可记为)(X f ：R 1E E n →⊂），对于R X ∈*，如果存在某个0>ε，使所有与X *的距离小于ε的X R ∈（即X R ∈且ε *XX -），都有)()(*X f X f ≥，则称X *为)(X f 在R 上的局部极小点， )(*X f 为局部极小值。

若对于所有X *X ≠且X *的距离小于ε的R X ∈,都有)()(*x f x f >，则称X *为)(X f 在R 上的严格局部极小点，)(*X f 为严格局部极小值。

设)(X f 为定义在n E 的某一区域R 上的n 元实函数，若存在R X ∈*，对所有X R ∈都有)()(*X f X f ≥，则称X *为)(X f 在R 上的全局极小点，)(*X f 为全局极小值。

若对于所有X R ∈且X *X ≠，都有)()(*x f x f >，则称X *为)(X f 在R 上的严格全局极小点，)(*X f 为严格全局极小值。

如将上述定义中的不等号反问，即可得到相应极大点和极大值的定义。

下面仅就极小点和极小值加以说明，而且主要研究局部极小值。

四、多元函数极值点存在的条件二阶可微的一元函数 极值点存在的条件如下：必要条件：0)('=x f充分条件：对于极小点：0)('=x f 且0)(">x f 对于极大点：0)('=x f 且0)("<x f对于无约束多元函数，其极值点存在的必要条件和充分条件，与一元函数极值点的相应条件类似。

1. 必要条件下述定理1给出了n 元实函数)(X f 在X *点取得极值的必要条件。

定理1 设R 是n 维欧氏空间n E 上的某一开集，)(X f 在R 上有连续一阶偏导数，且在点R X ∈*取得局部极值，则必有0)()()(*2*1*=∂∂==∂∂=∂∂nx X f x X f x X f (6.5)或写成0)(*=∇X f (6.6) 此处Tn x X f x X f x X f X f ⎪⎪⎭⎫ ⎝⎛∂∂∂∂∂∂=∇)(,,)(,)()(*2*1**(6.7)为函数)(X f 在X *点处的梯度。

这个定理是显然的。

像一元函数那样，称满足条件（6.5）的点为稳定点（驻点）。

函数)(X f 的梯度)(X f ∇有两个十分重要的性质：（1）函数)(X f 在某点)0(X的梯度)()0(X f ∇必与函数过该点的等值面（或等值线）正交（设)()0(X f ∇不为零）；（2）梯度向量的方向是函数值（在该点处）增加最快的方向，而负梯度方向则是函数值（在该点处）减少最快的方向。

2. 二次型二次型是Tn x x x X ),,,(21 =的二次齐次函数：2223223222211211221112222)(nnn n n n n x a x x a x x a x a x x a x x a x a X f +++++++++= =AX X x x aT n i nj j i ij=∑∑==11(6.8)式中，ji ij a a =，A 为n n ⨯对称矩阵。

若A 的所有元素都是实数，则称上述二次型为实二次型。

一个二次型惟一对应一个对称矩阵A ；反之，一个对称矩阵A 也惟一确定一个二次型。

若对任意X 0≠（即X 的元素不全等于零），实二次型AX X X f T=)(总为正，则称该二次型是正定的。

若对任意X 0≠，实二次型AX X X f T=)(总为负，则称该二次型是负定的。

若对某些X 0≠，实二次型0)(>=AX X X f T；而对另一些X 0≠，实二次型0)(<=AX X X f T ，即它非正定，又非负定，则称它是不定的。

若对任意X 0≠，总有0)(≥=AX X X f T ，即对某些X 0≠，0)(>=AX X X f T ，对另外一些X 0≠，0)(==AX X X f T ，则称该实二次型半正定。

类似地，若对任意X 0≠，总有0)(≤=AX X X f T ，则称其为半负定。

如果实二次型X TAX 为正定、负定、不定、半正定或半负定，则称它的对称矩阵A 分别为正定负定、不定、半正定或半负定。

由线性代数学知道，实二次型X TAX 为正定的充要条件，是它的矩阵A 的左上角各阶主子式都大于零。

即,011>a 22211211a a a a >0,333231232221131211a a a a a a a a a >0,nnn na a a a 1111,>0实二次型X TAX 为负定的充要条件是，它的矩阵A 的左上角顺序各阶主子式负、正相间，即,011<a 22211211a a a a >0,333231232221131211a a a a a a a a a <0,nnn nn a a a a 1111)1(,->0 例1 判定以下矩阵的正定性：A=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡---402062225 B=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--031301110 解 对矩阵A ：,0266225,052221121111>=--=<-=a a a a a,08042062225<-=---=A 故A 负定。

对矩阵B ： ,10110,02221121111-===b b b b b故知B 不定。

3. 多元函数的泰勒（Taylor ）公式 设n 元实函数)(X f 在)0(X 的某一邻域内有连续二阶偏导数，则可写出它在)0(X处的泰勒展开式如下：))(()(21)()()()()0(2)0()0()0()0(X X X f X X X X X f X f x f T T -∇-+-∇+= (6.9)其中，.10),()0()0(<<-+=θθX X X X若以X=X)0(+P 代入，则式（6.9）变为P X f P P X f X f P X f T T )(21)()()(2)0()0()0(∇+∇+=+ （6.10）其中，P XX θ+=)0(.也可将式（6.9）写成)())(()(21)()()()(2)0()0()0(2)0()0()0()0(X X X X X f X X XX Xf Xf X f T T-+-∇-+-∇+=ο (6.11) 其中，当)0(XX →时，⎪⎭⎫ ⎝⎛-2)0(XX ο是2)0(X X -的高阶无穷小，即0)(lim 2)0(2)0()0(=--→XX XX xx ο4. 充分条件*X 是)(X f 的极小点的充分条件由下面的定理2给出。

（定理2证明略） 定理2 设R 是n 维欧氏空间n E 上的某一开集，)(X f 在R 上具有连续二阶偏导数，若0)(*=∇X f ，且)(*2X f ∇正定，则R X ∈*为)(X f 的严格局部极小点。

此处)(*2X f ∇=2*22*21*22*222*212*21*221*221*2)()()()()()()()()(nn n n n x X f x X f x X f x x X f x X f x x X f x x X f x x X f x X f ∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂（6.11） 为)(X f 在点*X 处的黑塞（Hesse ）矩阵。

若将)(*2X f ∇正定改为负定，定理2就变成了*X 为)(X f 的严格局部极大点的充分条件。

例2 研究函数2221)(x x X f -=是否存在极值点。

解 先由极值点存在的必要条件求出稳定点：112)(x x X f =∂∂ 222)(x x X f -=∂∂ 令0)(=∇X f ，即：021=x 和022=-x ，得稳定点 X=TTx x )0,0(),(21= 再用充分条件进行检验：2)(212=∂∂x X f 2)(222-=∂∂x X f 0)()(1222122=∂∂∂=∂∂∂x x X f x x X f 从而⎪⎪⎭⎫⎝⎛-=∇2002)(2X f 由于其黑塞矩阵)(2X f ∇不定，故TX )0,0(=不是极值点，而是一个鞍点。