东北财经大学：《运筹学》课程教学资源（教案讲义）第三篇 非线性规划 第一章 凸分析基础

第三篇非线性规划 第一章凸分析基础 §1非线性规划的一般形式 (一)非线性规划的例子 在决策和物理等科学中常常提出含有非线性函数的优化问题,请看下面的几个例子。 例1、某饲养场拟建一排五间的猪舍,平面布置如图1所示。由于资金及材料的限制,围墙和 隔墙的总长度不能超过54米,为使猪舍面积最大,应如何选择长宽尺寸? 设猪舍长为x1米,宽为x2米。根据题意,变量x1、x2应满足约束条件 2x1+6x2≤54 x1≥0,x2≥0 我们的目标是使总面积最大,即 max(x 2 于是化为如下规划问题 2x1+6x,≤54 x≥0,x2≥0 这里与线性规划不同的是,目标函数 f(x,x2)=xx2 是关于变量x12x2的非线性函数 例2、(确定经验公式)在经济或物理学中经常要根据实际或实验的观测值来确定出各种量之间 关系的公式来(称为经验公式)。假设变量Q随时间t变化,根据观测,我们得到如下一组数据及坐 标纸上的点(图2) t ee e2 e3 O 152

152 第三篇 非线性规划 第一章 凸分析基础 §1.非线性规划的一般形式 （一）非线性规划的例子 在决策和物理等科学中常常提出含有非线性函数的优化问题，请看下面的几个例子。 例 1、某饲养场拟建一排五间的猪舍，平面布置如图 1 所示。由于资金及材料的限制，围墙和 隔墙的总长度不能超过 54 米，为使猪舍面积最大，应如何选择长宽尺寸？ 1 x 2 x 图 1 设猪舍长为 1 x 米，宽为 2 x 米。根据题意，变量 1 x 、 2 x 应满足约束条件 1 2 1 2 2 6 54 0, 0 x x x x +    我们的目标是使总面积最大，即 max x x ( 1 2 ) 于是化为如下规划问题： ( 1 2 ) 1 2 1 2 2 6 54 0, 0 max x x x x x x +    这里与线性规划不同的是，目标函数 1 2 1 2 f x x x x ( , ) = 是关于变量 1 2 x x, 的非线性函数。 例 2、（确定经验公式）在经济或物理学中经常要根据实际或实验的观测值来确定出各种量之间 关系的公式来（称为经验公式）。假设变量 Q 随时间 t 变化，根据观测，我们得到如下一组数据及坐 标纸上的点（图 2）。 t 1 t 2 t 3 t i t m t Q Q1 Q2 Q3 Qi Qm

图2 注意随着时间的延伸,量Q的变化趋于平稳(即近似为常数),我们可以设想从如下形式的曲 线中找出一条曲线作为它的近似: x -xe 其中x1、x2、x为参数,根据图2可要求x、x2、x3>0,并希望 ne=0 (1) 实际上,由于观测数据有误差,当m>3时,不管如何选择x、x2、x3,(1)式一般都不会成立。 只能退而求其次,即选择那样的x、x2、巧使得由(1)算得的理论值与实际值尽量接近。通常大 多采用最小平方和意义下的求解方法。即求解如下的规划问题 m∑Q-(x-x2e)2 (2) x1x2,x3>0 (2)中的目标函数也是非线性的 例3、(最优存贮问题)设各种商品的年需求量为D,l=1…,n,为节约资金,减少存贮量,宜 分批进货。已知每次订货费为C1,年单位存贮费为C2,仓库容量为0,各种产品的单位价格为P, 希望存贮和订货的总费用不超过f°,问如何安排批量Q,使之占用的资金总额S最少 容易看出,占用资金总额等于年均存贮量(/2)与价格之积 而总费用为订货费与存贮费之和 分3, 若用v表示单位第i中材料所占用仓库容量,则有如下的模型:

153 1 t 2 t m 0 t t Q 图 2 注意随着时间的延伸，量 Q 的变化趋于平稳（即近似为常数），我们可以设想从如下形式的曲 线中找出一条曲线作为它的近似： 3 1 2 { } x t x x e − + − 其中 1 x 、 2 x 、 3 x 为参数，根据图 2 可要求 1 x 、 2 x 、 3 x >0，并希望 3 1 2 , 1, , i x t i x x e Q i m − − = = （1） 实际上，由于观测数据有误差，当 m>3 时，不管如何选择 1 x 、 2 x 、 3 x ，（1）式一般都不会成立。 只能退而求其次，即选择那样的 1 x 、 2 x 、 3 x 使得由（1）算得的理论值与实际值尽量接近。通常大 多采用最小平方和意义下的求解方法。即求解如下的规划问题： 3 2 1 2 1 1 2 3 [ ( )] , , 0 i m x t i i min Q x x e x x x − =   − −      （2） （2）中的目标函数也是非线性的。 例 3、（最优存贮问题）设各种商品的年需求量为 , 1, , D i n i = ，为节约资金，减少存贮量，宜 分批进货。已知每次订货费为 C1i ，年单位存贮费为 C2i ，仓库容量为 0 V ，各种产品的单位价格为 Pi ， 希望存贮和订货的总费用不超过 0 f ，问如何安排批量 Qi ，使之占用的资金总额 S 最少。 容易看出，占用资金总额等于年均存贮量 ( ) 2 Qi 与价格之积： 1 2 n i i i PQ S = =  而总费用为订货费与存贮费之和： 1 2 1 ( ) 2 n i i i i i i D Q f C C = Q = +  若用 i v 表示单位第 i 中材料所占用仓库容量，则有如下的模型：

min s= D ∑vQ≤ Q≥0,i=1,2,…,n (3)中的一个约束函数∑(、D+C2)是非线性的 (二)一般形式 上面叙述的几个例子都是求一组变量,例如n个变量x,x2…xn,使其在满足由一些等式或不 等式所限定的约束条件下,求某一个目标函数∫(x,x2,…xn)的最大值或最小值。并且,其中目标 函数和约束函数里至少有一个是非线性的。这样的规划问题称为非线性规划。它的一般形式为: min f(x) 81(x 0,x∈O(x,d)∩S,都有 f(x)≤f(x) (7) 则称x为∫(x)的局部最优解。其中O(x',δ)是x的δ_邻域。特别如果对于x≠x,都有

154 1 0 1 2 1 0 1 2 . . ( ) 2 0, 1,2, , n i i i n i i i i i i n i i i i PQ min S D Q s t C C f Q v Q V Q i n = = =  =     +          =    （3） （3）中的一个约束函数 1 2 1 ( ) 2 n i i i i i i D Q C C = Q  + 是非线性的。 （二）一般形式 上面叙述的几个例子都是求一组变量，例如 n 个变量 1 2 , , , n x x x ，使其在满足由一些等式或不 等式所限定的约束条件下，求某一个目标函数 1 2 ( , , , )n f x x x 的最大值或最小值。并且，其中目标 函数和约束函数里至少有一个是非线性的。这样的规划问题称为非线性规划。它的一般形式为： ( ) . . ( ) 0, 1, , ( ) 0, 1, , i j min f x s t g x i m h x j l     =  = =  （4） 其中 n x R  ， , ,i j f g h 都是多元函数： n R R → ，它们中至少有一个是非线性的。记（4）的可行解 集为 S ： { | ( ) 0, 1, , , ( ) 0, 1, , } S x g x i m h x j l =  = = = i j （5） 则（4）可简写成 ( ) n min f x x S R   （6） 求极大可以转换成求极小： max ( ) min[ ( )] x S x S f x f x   = − − 众所周知，整个世界在本质上是非线性的，因此实际中的非线性规划问题相对的要比线性规划 问题更多、更普遍，也更复杂。因此，对它们的研究也显得更重要。非线性规划，又称最优化方法， 其实际应用很广泛，主要表现在以下几个方面： A 最有控制，B 结构设计，C 机械设计，D 电子网络，E 水资源管理，F 随机资源分配，G 设施 位置确定等。 （三）最优解 关于最优解，有以下定义。 定义 1、设 : n f S R R  → ， x S   ，若存在数   0， x O x S ( , )      ，都有 f x f x ( ) ( )   （7） 则称 x  为 f x( ) 的局部最优解。其中 O x( , )   是 x  的  _邻域。特别如果对于 x x   ，都有

f(x<f(x), xEO(,Ons (8) 则称x为∫(x)的严格局部极小点或严格局部最优解。 若(⑦)式对Ⅴx∈S都成立,则称x为全局(或整体)极小点或全局最优解。若(8)式对Ⅵx∈S x≠x都成立,则称x*为严格全局极小点 实际问题都是求全局极小点,但目前大多都是用求局部极小点近似代替之。 §2多元函数和向量值函数 在微积分中已介绍过多元函数。例如对二元函数a=f(x)=f(x12x2),其可微性定义为 △=f(x+△x,x2+△x2)-f(x42,x2) A△x1+BAx2+O (9) 上式可等价的写成 △M=LP+o(P") (9) 其中L=(A,By,P=(Ax,Ax2y,叫=A+Ax,(9)及(9)的含义是 dy vonn (r+Ar, x,+Ax2,)-f(x x%)-(AAx+ BAx2) 2→0 △x2+Ax2 f(x+P)-f(x°)-LP m 0 据此,对多元函数a=f(x)=f(x1…xn),自然可以给出如下形式的可微性定义: 定义2:设f:ScR"→R,且x°∈S,如果存在L∈R",VP∈R"都有 f(x+P)-f(x°)-LP (10) 成立,则称∫(x)在x°可微 (有的文献称上述可微性为F-可微,还有所谓G-可微:Vh≠0,h∈R",t∈R, mf(x+h)-/(x)-m=0 由F可微→G_可微,反之则不然)。(10)的等价形式为 55

155 f x f x ( ) ( )   ， x O x S ( , )     （8） 则称 x  为 f x( ) 的严格局部极小点或严格局部最优解。 若（7）式对  x S 都成立，则称 x  为全局（或整体）极小点或全局最优解。若（8）式对  x S ， x x   都成立，则称 x  为严格全局极小点。 实际问题都是求全局极小点，但目前大多都是用求局部极小点近似代替之。 §2.多元函数和向量值函数 在微积分中已介绍过多元函数。例如对二元函数 1 2 u f x f x x = = ( ) ( , ) ，其可微性定义为 0 0 0 0 1 1 2 2 1 2  = +  +  − u f x x x x f x x ( , ) ( , ) ＝ 2 2 1 2 1 2 A x B x o x x  +  +  +  ( ) （9） 上式可等价的写成 ( ) T  = + u L P o P （ 9 ） 其中 ( , )T L A B = ， 1 2 ( , )T P x x =   ， 2 2 P x x =  +  1 2 ，（9）及（ 9 ）的含义是 1 2 0 0 0 0 1 1 2 2 1 2 1 2 0, 0 2 2 1 2 ( , ) ( , ) ( ) lim x x f x x x x f x x A x B x x x  →  → +  +  − −  +   +  ＝ 0 0 0 ( ) ( ) lim 0 T P f x P f x L P → P + − − = 据此，对多元函数 1 ( ) ( , , ) u f x f x x = = n ，自然可以给出如下形式的可微性定义： 定义 2：设 f : S  R n → R 1 ,且x 0  S,如果存在L R n ,P  R n都有 0 ( ) ( lim 0 0 0 = + − − → P f x P f x L P T P ） （10） 成立，则称 f (x) 在 0 x 可微。 （有的文献称上述可微性为 F-可微，还有所谓 G-可微： h  0，h  R n ，t  R， 0 ( ) ( ) lim 0 0 0 = + − − → t f x th f x L th T t 由 F−可微  G− 可微，反之则不然）。（10）的等价形式为

f(r+ P)-f(r)=LP+o(PD (11) 易证L(x)=(9(x2….9(x2 (12) 称L(x0)为f(x)在点x0的导数或梯度,记为v(x°),于是(11)变成 f(X°+P)=F(X)+V(X°)yP+oP (13) 定义(3)设F:ScR"→R,且x∈S,如果F(X)的所有分量f(x)i=1.…,m在x0点都可微,则称 向量值函数F(X)在x点可微,即 f(x)-Vf(x°)P 它等价于 lm F(x +P)-F(r)-VF()P 0 其中称VF(x°)为向量值函数F(X)在点x0的导数或 Jacobi矩阵,其具体形式如下: 1(X)骈.. VF(X on(x)an(x)an(X°) 令g(x)=V(x)=(…,y,则gx定义了一个在区域ScR→的向量值函数,若gX)于S上可 微,则对于多元函数f(X)而言,它便在S上二次可微,Vg(x)就是fx)的二阶导数,由(15)得: a(x) a(x a(x) Vg(X)=Vf(x)= (16) a(x) 8/( a(x) 故f(x)的二阶导数是n阶矩阵,称(16)为f(x)的Hese矩阵,记为H(x)=v2f(x) 当八(x)的所有二阶偏导数连续时,O=可,/=1… ax, ar, ar ax, 此时H(X)对称 例1 次函数 f()=XAX+bx+C=2a,xx+2bx,+C 其中,A是对称矩阵,则Vf(x)=Ax+b,V2f(x)=A 例2已知o(x)=f(X+P),其中∫:R"→R,g=R2→R,P∈R",求证 o'(a)=V(X+AP)'P o'()=PV(+AP)P 证:由连锁规则得 56

156 ( ) ( ) ( ) 0 0 f X P f X L P P T + − = + （11） 易证 T n x f X x f X L X ) ( ) , , ( ) ( ) ( 0 1 0 0     =  （12） 称 ( ) 0 L X 为 f (X ) 在点 0 X 的导数或梯度，记为 ( ) 0 f X ，于是（11）变成 ( ) ( ) ( ) ( ) 0 0 0 f X P F X f X P o P T + = +  + （13） 定义（3）设 n m F : S  R → R ，且 X S 0 ，如果 F(X)的所有分量 f i (X),i =1,  ,m 在 0 X 点都可微，则称 向量值函数 F(X)在 0 X 点可微，即 i m P f X P f X f X P T i I i P 0 1, ( ) ( ) ( ) lim 0 0 0 0 = = + − −  → (14) 它等价于 0 ( ) ( ) ( ) lim 0 0 0 0 = + − −  → P F X P F X F X P P 其中称 ( ) 0 F X 为向量值函数 F(X)在点 0 X 的导数或 Jacobi 矩阵，其具体形式如下：                              = n m m m n x f X x f X x f X x f X x f X x f X F X ( ) ( ) ( ) ( ) ( ) ( ) ( ) 0 2 0 1 0 0 1 2 0 1 1 0 1 0      (15) 令 T n x f x f g(x) f (x) ( , , ) 1     =  =  ，则 g(x)定义了一个在区域 n n S  R → R 的向量值函数，若 g(X)于 S 上可 微，则对于多元函数 f(X)而言，它便在 S 上二次可微， g(X ) 就是 f(X)的二阶导数，由（15）得：                                    =  = 2 2 2 2 1 2 0 2 2 1 2 2 1 2 0 2 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) n n n n x f X x x f X x x f X x x f X x x f X x f X g X f X      (16) 故 f (X ) 的二阶导数是 n 阶矩阵，称(16)为 f (X ) 的 Hesse 矩阵，记为 ( ) ( ) 2 H X =  f X 当 f (X ) 的所有二阶偏导数连续时， i j n x x f x x f i j j i , , 1, , 2 2 =     =    此时 H (X ) 对称。 例1， 二次函数 f X X AX b X C a x x b x C i i j i i i j i j T T = + + =  +  + 2 , 1 2 1 ( ) 其中，A 是对称矩阵，则 ( ) , ( ) . 2 f x = Ax + b  f x = A 例 2 已知 () = f (X + P) ，其中 1 f : R R n → ， 1 1  = R → R , n P  R ,求证: f X P P T () =  ( +  ) (17) P f X P P T ( ) ( ) 2   =  +  (18) 证：由连锁规则得：

()=∑ af(X+aP a(x, +AnP,=vf(r+aP)'P a2 o(k ox,+Ap) FRiar +Ap )a(x +dp)2p=pv/(+/P)P 定理1设∫:R"→R具有二阶连续偏导数,则 f(X+P)=f()V()'P+-PV2(X)P (19) 其中=X+P,0<0<1(X在X和X+P的连线上) 证:设o(4)=f(X+AP),按一元函数的 Taylor展开式把o(4)在λ=0展开,并注意(17)(18)式得 9(4)=9(0)+'(0)元+g°(4)2,0<6<1 令元=1,即得(19),公式(19)还可写成 f(X +P)=f(X)+v()P+P/(X)P+o(P) (20) 若vf(X)连续,则中值公式成立(考虑∞(1)-9(0)) f(X+P)-f(X)=Vf(X+6P)P,0<6<1 3凸集 定义3集合ScR"称为凸的,如果x,x2∈S总有 ax2+(1-a)x2∈S,0≤a≤1 (21) 这表明,对于凸集中的任意两点,连结这两点的直线段仍位于此集合之内。 设ScR是凸集,称x为凸集S的顶点,如x2,x2∈S及0<a<1,x=ax2+(1-a)x2 则必有x=x1=x2。这表明,集合S的顶点不能位于S中的任何直线段的内部。 例R"中的超平面:H={px=a,x∈R"}是一个凸集,其中非零向量P称为超平面的法向 量,a是实数。由超平面H所决定的闭(开)半空间H={Px2ax∈R (H={xP2x<a,x∈R"})均为凸集。 定理2集合ScR"是凸集的充要条件是:对于任意正整数k≥2,若点x'∈S,=1…,k,则它们 的凸组合 λ1x2+…+λx∈S (22) 其中,A1≥0, 15

157 p f X P P x p f X P T n i i i i ( ) ( ) ( ) ( ) 1      =  +  +  +  = = P P P f X P P x p x p f X P p x p f X P d d T j i n i n j j j i i n i i i i ( ) ( ) ( ) ( ) ] ( ) ( ) ( ) [ 2 1 1 2 1          =  +  +  +  + =  +  +  =   = = = 定理 1 设 1 f : R R n → 具有二阶连续偏导数，则 f X P f X f X P P f X P T T ( ) 2 1 ( ) ( ) ( ) 2 + = +  +  （19） 其中 X = X + P,0    1 （ X 在 X 和 X+P 的连线上） 证：设 () = f (X + P) ，按一元函数的 Taylor 展开式把 () 在  = 0 展开，并注意（17）（18）式得 ( ) ,0 1 2 1 ( ) (0) (0) 2   =  +  +        令  = 1 ，即得（19），公式（19）还可写成 ( ) ( ) 2 1 ( ) ( ) ( ) 2 2 f X P f X f X P P f X P o P T T + = +  +  + (20) 若 f (X ) 连续，则中值公式成立（考虑 (1) −(0) ）: f (X + P) − f (X ) = f (X + P) P,0    1 T 3.凸集 定义 3 集合 n S  R 称为凸的，如果 x x  S 1 2 , 总有 x + − x  S 1 2  (1 ) ，0  1 （21） 这表明，对于凸集中的任意两点，连结这两点的直线段仍位于此集合之内。 设 n S  R 是凸集，称 x 为凸集 S 的顶点，如 x x  S 1 2 , 及 0  1， 1 2 x =x + (1−)x ， 则必有 1 2 x = x = x 。这表明，集合 S 的顶点不能位于 S 中的任何直线段的内部。 例 n R 中的超平面：   T n H = x P x = a, x  R 是一个凸集，其中非零向量 P 称为超平面的法向 量， a 是实数。由超平面 H 所决定的闭（开）半空间   T n H = x P x  a x  R + , （   T n H = x P x  a x  R − , ）均为凸集。 定理 2 集合 n S  R 是凸集的充要条件是：对于任意正整数 k  2 ，若点 x S,i 1, , k, i  =  则它们 的凸组合 x x S k  ++ k  1 1 （22） 其中， 0, 1 1   = = k i i i

证:充分性显然(只需取k=2)。现证必要性(数学归纳法) k=2时,结论显然成立,假定k=m时,结论成立,令x=∑λ,x, 其中,≥0∑λ=1,不妨设mn≠1,于是上式可写成 x=(1-am4Dy+amx m+l 其中 ,,十 注意 ≥0,i=1, =1,故由归纳假设y∈S,因S为凸集,必有x∈S 证毕 定理3设S1,S2是凸集,则下列集合亦然 (1)S+S2=(=x+yx∈S1,y∈S2} (2) |=x-y,x∈S1,y∈ S (3)S==x∈S,∈R (4)任意多个凸集之交集仍为凸集。(证明留给读者) 设集合ACR",包含A的最小凸集被称为A的凸包,记作cOmA。由定理3之(4)可知,A 的凸包就是所有包含A的凸集之交。由定理2,A的凸包是A的一切凸组合的集合。换言之 x∈cOm当且仅当x=∑1x2,∑1=1,λ20,x∈Ai=1…k。进一步还有以下定理 定理4设集合AcR",则cO4中的每一点可用A中至多n+1个点的凸组合来表示。 证:假设 xE comA,x=∑ax,∑a,=1a1>0,x∈A ,如果m>n+1,只 须证明x也可以用m-1个点的凸组合表示。事实上,因m-1>n,故存在不全为零的实数 使c1(x2-x") 令Cn=-( +cm-1),则c1x+…+cmxm=0,c1+…+Cn=0。选取正数E,使得 an+B≥0,i=1…,m且a+BCb=0,1≤≤m 则有 158

158 证： 充分性显然（只需取 k = 2 ）。现证必要性（数学归纳法）。 k = 2 时，结论显然成立，假定 k = m 时，结论成立，令  + = = 1 1 m i i i x  x ， 其中， o, i  1 1 1  = + = m i i ，不妨设  m+1  1 ，于是上式可写成 1 1 1 (1 ) + = − + + + m m m x  y  x ， 其中 + + − = + 1  1 1 1 y x  m  m m m x 1−  +1  。 注意 0 1 1  − m+ i   ，i = 1,  ,m，= + = − m i m i 1 1 1 1   ，故由归纳假设 y  S ，因 S 为凸集，必有 xS ， 证毕。 定理 3 设 1 2 S ,S 是凸集，则下列集合亦然： （1） S1 + S2 = z z = x + y, xS1 , y S2  （2） S1 − S2 = z z = x − y, xS1 , y S2  （3）   1 1 1 S = z z = x, x  S ,  R （4）任意多个凸集之交集仍为凸集。（证明留给读者） 设集合 n A  R ，包含 A 的最小凸集被称为 A 的凸包，记作 convA 。由定理 3 之（4）可知， A 的凸包就是所有包含 A 的凸集之交。由定理 2， A 的凸包是 A 的一切凸组合的集合。换言之， xconvA 当且仅当 , 1 = = k i i i x  x 1, 1 = = k i i 0, x A, i i   i = 1,  , k 。进一步还有以下定理： 定理 4 设集合 n A  R ，则 convA 中的每一点可用 A 中至多 n +1 个点的凸组合来表示。 证： 假设 xconvA， , 1 = = m i i i x  x 1, 1 = = m i  i 0, x A, i  i   i = 1,  ,m ，如果 m  n +1 ，只 须证明 x 也可以用 m−1 个点的凸组合表示。事实上，因 m−1 n ，故存在不全为零的实数 1 1 , , m− c  c ，使 ( ) ( ) 0 1 1 1 1 − + + − = − − m m m m c x x  c x x 。 令 ( ) m = − 1 + + m−1 c c  c ，则 0 1 1 + + = m m c x  c x ，c1 ++ cm = 0 。选取正数  ，使得 +  0, i i  c i = 1,  ,m, 且 i + c i = 0,1 i 0  m 0 0   ， 则有

x=x+ cx=∑(a1+Ec)x 注意上式右端是x2,…,xm的凸组合,且其中至少有一个系数是0。证毕 R中有限个点x,…,x的凸包称为一个多胞形;若x xk+-x1是线性无关的(意 味k0使x∈S,px>a>0 证:取集合T=x∈R"≤a使得S⌒T≠d。由于S∩T是有界闭集,所以连续函数 f(x)=在S∩T上某点x达到最小值,即0a>0 证毕。 定理6(承托超平面定理)若S是一个非空凸集,y是S的边界点,则存在非0向量p∈R",使对 x∈S闭包,有py≤px,亦即存在超平面H(p,a)它通过点y,且使S包含在它的某半闭空 间之中(称H为凸集S的承托超平面) 证:因y是集合S的边界点,故存在点列y≠S闭包y→y(k→>∞),由定理5可找到p∈R 159

159 = +  = = m i i i x x c x 1  = + m i i i i c x 1 (  ) 注意上式右端是 m x , , x 1  的凸组合，且其中至少有一个系数是 0。 证毕。 n R 中有限个点 1 1 , , k+ x  x 的凸包称为一个多胞形；若 2 1 1 1 x x , , x x k − −  + 是线性无关的（意 味 k  n +1 ），则此凸包称为具有顶点 1 1 , , k+ x  x 的一个单纯形。 设 n S1、S2  R 是非空集合， H z p z a T = = 为超平面，如果 1 2 xS , yS 都有 p x a p y a T T  ,  ，则称 H(p, a) 分离 S1、S2 （若二不等式严格成立，则称严格分离）。 定理 5 设 n S  R 是非空闭凸集，且原点 0S ，则必存在超平面 H ( p, a) 严格分离 0 和 S .即存在 p  0， a  0 使 x  S, p x  a  0. T 证： 取集合 T = x  R x   n 使得 S T   。由于 S T 是有界闭集，所以连续函数 f (x) = x 在 S T 上某点 0 x 达到最小值，即 0 , , 0  x  x x  S T 注意到 T 是以原点为中心的超球的特性:若 , , . 0 0 x T x  x 则必有x T 故知 xS ，均有 . 0 x  x ，由于 S 的凸性，又有 (1 ) ,0 1, 0 x + −  x  S    从而 (1 ) . 0 0 x + −  x  x 由此可得 ( ) ( ) 2 ( ) 0 2 0 0 0 0 x − x x − x + x x − x  T T   此式对充分小的正数  亦成立，故必有 0 0 0 x x x x T T  取 0 2 0 2 1 a = x , p = x ，便有 p x  a  0. T 证毕。 定理 6 （承托超平面定理）若 S 是一个非空凸集，y 是 S 的边界点，则存在非 0 向量 n p  R ，使对 xS 闭包，有 p y p x T T  ，亦即存在超平面 H ( p, a) 它通过点 y，且使 S 包含在它的某半闭空 间之中（称 H 为凸集 S 的承托超平面）。 证： 因 y 是集合 S 的边界点，故存在点列 y S k  闭包 y → y(k → ), k 由定理 5 可找到 k n p  R

p2|=1,使超平面H(p,a2)严格分离点y和S闭包,即 x> ,Vx∈S闭包 由于{是有界序列,故可设p→P(→∞),于是便有 px≥p2y vx∈S闭包。 证毕。 推论:若S是非空凸集,点yS,则必存在p≠0,P∈R",使得x∈S闭包有 Py≤pX 定理7:若S1和S是R"中两非空凸集,S1∩S2=Φ,则存在一非0向量p,使x∈S1闭包,vy∈S2 闭包,有 py≤P x 证:令S=S-S==x-y,x∈Sy∈S2)由定理6之推论知存在p∈R",p≠0,使v∈S 有p0≤p,即有py≤px,Wx∈S1,vy∈S2,于是亦有 s甲p{y∈S2}≤nf{px∈S} 故对所有x∈S闭包,y∈S2闭包,有py≤px 证毕。 作为分离定理的应用,现证明下面两个择一性定理,它们在数学规划中很有用。 定理8:( Farkas定理)若A是m×n矩阵,c是n维列向量,则下面二系统有且只有一个有解。 系统1:Ax≤0,c2x>0,x∈ 系统2:Ay=c,且y≥0,y∈Rm 证:若系统2有解,即存在y∈Rm,y≥0,使得Ay=c,如果存在x∈R"使得Ax≤0,则 c'x=(4y)3x=yAx≤0,故系统1无解。 若系统2无解,作集合S={=4yy20,则CS,显然S是非空闭凸集,由定理5 知存在向量p≠0,使得V∈S有pc0,又由p2==pAy>pc,而y≥0可任取,故必pA≥0,即 A(-p)≤0,从而-p是系统1的解 推论1下面二系统有且只有一个有解: 系统1:Ax≤0,x≥0,cx>0,x∈R 160

160 = 1 k p ，使超平面 ( , ) k k H p a 严格分离点 k y 和 S 闭包，即 k Tk Tk p x  p y ， xS 闭包 由于   k p 是有界序列，故可设 p → p(i → ) i k ，于是便有 p x p y T T  ， xS 闭包 。 证毕。 推论： 若 S 是非空凸集，点 y  S ，则必存在 p  0， n p  R ，使得 xS 闭包有 p y p x T T  。 定理 7：若 S1 和 S2 是 n R 中两非空凸集， S1  S2 =  ，则存在一非 0 向量 p，使 S1 x 闭包， S2 y  闭包，有 p y p x T T  证： 令 S=S1-S2=z z = x − y, xS1 , y S2  由定理 6 之推论知存在 n p  R ， p  0 ,使 z S 有 p p z T T 0  ，即有 p y p x T T  ， S1 x ， S2 y  ，于是亦有 supp y y S2  inf p x x S1 T T    故对所有 S1 x  闭包， S2 y  闭包，有 p y p x T T  。 证毕。 作为分离定理的应用，现证明下面两个择一性定理，它们在数学规划中很有用。 定理 8：（Farkas 定理）若 A 是 m×n 矩阵，c 是 n 维列向量，则下面二系统有且只有一个有解。 系统 1： Ax  0, c x  0 T ， n x  R . 系统 2： A y c, T = 且 y  0， m y  R . 证： 若系统 2 有解，即存在 m y  R ， y  0 ，使得 A y c, T = 如果存在 n x  R 使得 Ax  0, 则 c x T = (A y) x = y Ax  0, T T T 故系统 1 无解。 若系统 2 无解，作集合 S = {z z = A y, y  0} T ，则 cS ，显然 S 是非空闭凸集，由定理 5， 知存在向量 p  0 ，使得 z S 有 p c p z T T  ，因 0S ，故 p c  0 T ，从而 c (−p)  0 T ，又由 p z p A y p c T T T T =  ，而 y  0 可任取，故必  0 T T p A ，即 A(− p)  0 ，从而 − p 是系统 1 的解。 推论 1 下面二系统有且只有一个有解： 系统 1： T n Ax  0, x  0, c x  0, x  R

系统2:4y≥c,y≥0,y∈R"(提示:用(A,-1)代替4) 推论2下面结论恰有一个成立 1)存在0≤x∈Rn,使得Ax≤c 2)存在0≤y∈Rm,使得Ay≥0,cy<0(提示:以(-1)乘1)、2)中不等式即变成推 论1)。 定理9:( Gordan定理)设A=Ax,则下列二系统有只有一个有解。 系统1:Ax<0.x∈R 系统2:Ay=0,y≥0,y≠0,y∈Rm 证:设系统1有解,即存在x∈R",满足Ax<0,用反证法。假定系统2也有解,即存在y∈Rm, y≥0,y≠0,使Ay=0,这时由Ax<0,及y≥0,y≠0,可得y4x<0,即xAy<0,因之 Ay≠0,矛盾,故系统2无解 反之,若系统1无解,令S=4x=yS2=<0则S与s是非空凸集,S∩S2=④ 从而由定理7,存在向量p≠0,使得pAx≥pz(Vx∈R"),当z→0时,得pAx≥0 (x∈R"),又由z0及其任意性,立知p≥0,令x=A(-p)=-Ap得 p4x=-pAp=-4p≥20,所以Ap=0,可见p是系统2的解 §4凸函数 凸函数定义 定义4.设∫(x)是定义在非空凸集ScR"上的函数,若x,y∈S,不等式 ∫(x+(1-)y)≤4(x)+(1-4)f(y) 对于0≤A≤1的一切λ都成立,则称f(x)为S上的凸函数。若对0<A<1的一切,当 x≠y时, f(x+(1-A)y)<4(x)+(1-)f(y) (24) 总成立,则称f(x)是S上的严格凸函数。 若-f(x)是凸(严格凸)函数,则称f(x)为凹(严格凹)函数,对于凹函数类(23)、(24)

161 系统 2： T m A y  c, y  0, y  R （提示：用 (A I) T , − 代替 T A ）。 推论 2 下面结论恰有一个成立： 1）存在 n 0  x  R ，使得 Ax  c 。 2）存在 m 0  y  R ，使得 A y  0, c y  0 T T （提示：以 (−1) 乘 1）、2）中不等式即变成推 论 1）。 定理 9： （Gordan 定理）设 A=Am×n,则下列二系统有只有一个有解。 系统 1： Ax  0, n x  R . 系统 2： A y = 0, T y  0， y  0， m y  R . 证： 设系统 1 有解，即存在 n x  R ，满足 Ax  0, 用反证法。假定系统 2 也有解，即存在 m y  R ， y  0， y  0 ，使 A y = 0, T 这时由 Ax  0, 及 y  0 , y  0 ,可得 y Ax  0, T 即 x A y  0, T T 因之 A y  0, T 矛盾，故系统 2 无解。 反之，若系统 1 无解，令  ,  0, S1 = y Ax = y S2 = z z  则 S1 与 S2 是非空凸集， S1  S2 =  ， 从而由定理 7，存在向量 p  0 ,使得 p Ax p z T T  （  n x  R ），当 z →0 时，得 p Ax  0 T （  n x  R ），又由 z<0 及其任意性，立知 p  0 ，令 x A p A p T T = (− ) = − 得 0 2 p Ax = − p AA p = − A p  T T T T ，所以 A p = 0 T ，可见 p 是系统 2 的解。 §4.凸函数 一、凸函数定义 定义 4. 设 f (x) 是定义在非空凸集 n S  R 上的函数,若 x, y  S, 不等式 f (x + (1− ) y)  f (x) + (1− ) f ( y) (23) 对于 0   1 的一切  都成立,则称 f (x) 为 S 上的凸函数 。若对 0   1 的一切  ，当 x  y 时， f (x + (1− ) y)  f (x) + (1− ) f ( y) （24） 总成立，则称 f (x) 是 S 上的严格凸函数。 若 − f (x) 是凸（严格凸）函数，则称 f (x) 为凹（严格凹）函数，对于凹函数类（23）、（24）