最优化理论与算法(第一章)

1、最优化理论与算法（数学专业研究生）第一章引论§ 1.1引言一、历史与现状最优化理论最早可追溯到古老的极值问题，但成为一门独立的学科则是在20世纪四十年代末至五十年代初。其奠基性工作包括Fritz John最优性条件（1948）, Kuhn-Tucker最优性条件（1951）,和Karush最优性条件（1939）。近几十年来最优化理论与算法发展十分迅速，应用也越来越广泛。现 在已形成一个相当庞大的研究领域。关于最优化理论与方法，狭义的主要指非线性规划的相关内容，而广义的则涵盖：线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规 划甚至还包括变分、最优控制等动态优化内

2、容。本课程所涉及的内容属于前者。二、最优化问题的一般形式1、无约束最优化问题min f （x）（ 1.1）x. Rn2、约束最优化问题m in f （x）C（x） =0, i E（ 1.2）s.t.Ci （x） Z0, i E I这里E和I均为指标集。§ 1.2数学基础一、 范数1. 向量范数|x| = max Xj（ 1閃范数）（1.3）n|xL =无Xi（ 11 范数）（1.4）i ztn 1x2=（VXi2）2（ I2范数）（1.5）i z±X pXip)pi J（打范数）(1.6 )1x A = (x Ax )2( A 正定)（椭球氾数）(1.7 )事实上1范数、2

3、 范数与 :范数分别是p 范数当p = 1、2和p）：:时情形。n12. 矩阵范数定义1.1方阵A的范数是指与 A相关联并记做 A的一个非负数，它具有下列性质： 对于A = 0都有 A 0，而A=0时A=0 ； 对于任意k乏R，都有kA = k岡； A B乞A B ; AB , A B ；若还进一步满足： |ax|a|x|p则称之为与向量范数IJ相协调（相容）的方阵范数。若令A =maxl!A单（这里|x|是某一向量范数）（1.8）可证这样定义的范数是与向量范数二相协调的，通常称之为由向量范数诱导的方阵范数。特别地,对方阵A =（aj ）n n，有：n|A=max送aij （列和的最大者）（1

4、.9）j i仝n| A=max送aij （行和的最大者）（1.10）i j壬A 2 =（ 'aTa）2 （ ' ata表示AT A的特征值的最大者）（1.11）称为谱范数（注：方阵A的特征值的模的最大者称为A的谱半径，记为 J（A）。对于由向量诱导的方阵范数，总有：AxI =1 （ I为单位阵）对于方阵范数，除了上述由向量范数诱导的范数之外，还有常用的Frobenius范数，简称F-范数：nn11A F =（工:二a/）2二tr（ AT A）2（1.12）ij _1及加权Frobenius范数和加权l2范数：Am,f = MAMf(1.13)Am,2二MAM2(1.14)其中M

5、为对称正定矩阵。3. 范数的等价性定义1.2设二与一是Rn上的两个范数，若存在叫2 7，使得J x|：,|x J x ：，* Rn（行5）则称范数 二与If是等价的。容易证明：x2乞x!乞订X 2(1佝x| J |x 2 n X :(1.17)x| J |xn x ；;(行8)XFX2-!(1.19)l n X 2 乞 X 人 1 x 220)其中1是A的最大特征值，而'n是A的最小特征值。由此可见，Rn中的常用向量范数均等价，事 实上还可证明：Rn中所有向量范数均等价 。4. 关于范数的几个重要不等式。 Cauchy-Schwarz 不等式(1.21)xTy勻（当且仅当x和y线性相关

6、时，等式成立） 设A是正定矩阵，则xTA <|XU|y|A (当且仅当X与y线性相关时，等式成立)(1.22)由(x, y) =xTAy是一种内积，以及一般内积的Cauchy-Schwarz不等式即得。 设A是n n正定矩阵，则 XTy|兰|x|A|y|A丄(仅当X与A-y线性相关时，等式成立)(1.23)乂川从划兰|虬卜叽十口比丄(仙)其中的不等号由可得。 You ng不等式：假定p与q都是大于1的实数，且满足丄+丄=1y/x,y R十，有p qp qx yxy，(1.25)p q当且仅当xp =yq时，等式成立。其证明由算术一几何不等式直接给出，事实上11p qxy =(xp)p(y

7、q)q岂 丄(算术_几何不等式)p q H?lder不等式n"p yq 十 xii ±)p(送 yii 1q)q(1.26)其中p与q都是大于1的实数，且满足1 11，其证明利用You ng不等式可得。5# Minkowski不等式(1.27)x y p x 卩 Ty p，( p -1)后面将利用凸函数理论予以证明。二、矩阵求逆与广义逆1. Von-Neumann 弓 I理定理1.3 (Von-Neuma nn引理)设E Rn n , I Rn n是单位阵，|£是满足I =1的相容矩阵范数。如果E ：:1，则(I -E)非奇异，且oO1k(IE ,K _0a111

8、-11A (A-b)I若A非奇异，a'(A-B) : 1 ,则B非奇异，且bQO1i k1B 一八(I -A B) A -,Sk(I-E证明：因为| E <1，故 Sk = 1 +E +E? +Ek定义了一个 Cauchy序列，因而收敛。由k _07#可得故有k -0=lim Skk_ j：:=(I-E)进一步有再令知-E)十送|Ek兰E =1 -AB ,E 二 I -aJbk +lim Sk(l E) = lim (I E ) = Ik 二J；,：#由上面结论可得,Q01111 k(I -E) =(A B)八(I - A B)k =0所以有B A = x' (IAB)k

9、 Ak z0进一步有bik俎qo八A(A-B)k =S#注：这个定理表明，若b充分接近一个可逆矩阵 a，则b也可逆，且逆矩阵可由a的逆矩阵来表示。上述定理还可以写成下面形式:定理1.4设A, B R曲，A可逆，| A*兰0(。若| A b|兰B，且胡<1，则B可逆，且B，<1 -：沖#证明：只需注意到|a4(B _A)|兰A| B _a| WaP <1，再由上述 Von-Neumann引理即得。#2.广义逆定义1.5设A Cm n，若A Cn m满足:AA A = A, A AA = A , (AA )* = AA ,(A A)* 二 A A(1.28)则称A是A的广义逆。其

10、中 A*是A的共轭转置。广义逆的求法设ACm沁，秩（A）=r，若A直交分解为A=QRP，其中Q , P分别为m x m, nn酉矩阵,R EC m>n , R =，其中R,是r r非奇异的上三角矩阵。则A的广义逆为:A” =P*R Q 其中 R =R；若A的奇异值分解为A二UDV *，其中0是A的非零奇异值,(1.29)均为酉矩阵，的广义逆为:Cm n，而A” =VD U *，其中D(1.30)若A的最大秩分解为A =BC，贝U A的广义逆为:-1A"二C (CC ) (B B)-1*B .(1.31)矩阵的Rayleigh商定义1.6 A是n n Hermite矩阵,u Cn

11、，则称#(1.32)u AuR.(u)u u为矩阵A的Rayleigh商定理1.7设A是n n Hermite矩阵，则 Rayleigh商具有下列性质:1）齐次性:RCu）= R,(u)(二仁乞0 )#2）极性：#u Au3)极小残量性质对任意u三C n = min u Au = min * u|b 2u -0 u u这里 ,，n分别对应于矩阵 a的最大与最小特征值。这表明Rayleigh商具有有界性:< R .(u9#|(AR 扎(u)l)u| W|(APl)u|，于卩 W R。证明：1)由定义直接可得。2) 由A是Hermite矩阵，故存在酉矩阵 T，使T* AT 一； =n又令 u

12、 =Ty，且 |u|2 =1，故 I y|2 =1u Au = y T ATy* 2=y Ay =入 y12+扎yn当取y =(1,o,0)时达到最大值'1，当取y =(0, 0,0,1)时，达到最小值3) 令 s(u)二 Au - R (u)u， (u = 0)，贝y Au = s(u) - R (u)u，可直接验证s(u), R,(u)u ,0 ,由于(s(u ), u ) = (Au R ,(u )u , u) =u Au R,(u)u u =0注意到R ,(u)u是与u共线的，故s(u)与R ,(u)u正交。即R ,(u)u与s(u)是Au的正交分解。因而R ,(u)u是Au在

13、L S 上的直交投影，因而具有极小残量性质。2四、矩阵的秩一校正当矩阵A变到A - uvT时，即在A上加了一个秩为1的矩阵，称为秩一校正。下面讨论如何求 秩一校正的逆，行列式，特征值及矩阵分解。定理1.8设AERm"是非奇异的，u,vRn是任意向量。若1+vTAu0，则A的秩一校正A+uv 非奇异，其逆矩阵可以表示为J T Jt iiAuv A_“ cc、(A uv ) - = A 厂(1.33)1 +v A_u证明：可直接验证。上述定理的可进一步推广为：定理1.9设A是非奇异矩阵，U ,V是n x：m矩阵，若I +V * AU可逆，则A +UV *可逆，且(A UV*)=A丄一 A

14、U(IV * A "U ) "V * A J(1.34)下面介绍关于秩一校正的行列式定理定理 1.10 1)det( I uvT) =1 vTuTTTTTT2丿 det( I - U1U2 - U3U4 )二(1 - U1 U2)(1 - U3 U4) _(山 U4)(u2 U3)证明： 1 )若u =0，则结论显然成立；若 u = 0，设w是(I uvT)的特征向量。贝U(I uv T ) - w易见w要么与v垂直，要么与u平行。若与v垂直，则特征值为1;若与u平行，则对应特征值为1 vTu。进一步，平行于u的特征向量只有一个(线性无关)，而垂直于v的线性无关的向量有 n

15、_1 个，它们均为IuvT属于特征值1的特征向量，即特征值1是(n-1)重根， 而1 - vTu是单根。故有det( I 亠uv T)=、二-n = 1n(1 亠 vT u) = 1 亠 vT u。2) 对 I +u1u2' +u3u： =(l +ue T 厂 I + (I + UtU：)u3u： I使用上面结果，故有：det( I +ue 2： +u3u4T) =( I +uu2) 1 +u4： (I +u1u2：) u3 I丄 TI,丄 T6U；=(1 +5 u2)1 +u4 (I T)U3-1+u22_-(1 u；u2)(1 u；u4)(u；u4)(u：u3)。关于秩一校正矩阵的

16、特征值定理。定理1.11设A是对称矩阵，其特征值为 _，2 -'n，又设A = A 二uuT，其特征值为_:，那么1）若二 7 ,则 1- 2 - - 'n2)若二：0，则 s _ s _ 2 一 2 一 n _ 'n五、函数与微分1.多元函数的梯度与Hessian矩阵梯度If (x)=(丄f)T(1.35)Hessian 矩阵(1.36)r2 f丸2方向导数：(设d为一方向向量，即长度为1的单位向量，显然与范数的取法有关)11#(1.37). f (X 5) - f(X)limf (x) d注：对欧氏范数(2 范数)而言，梯度方向是函数上升最快的方向，而负梯度方向则是

17、函数下降最 快的方向。正因为这个原因，使得梯度在最优化理论与算法中占有特殊重要的地位。若f ： Rn ； R在开凸集D上连续可微，则有(1.38)1f (x d ) = f (x)亠 I f (x td )T ddt = f (x)亠 f ( )T dL0其中三(x, x - d )。上式也可改写为:f (y) = f (x) I f (x t(y -x)T (y -x) t- (0,1)或f (y) = f (x) I f (x)T (y - x) o( y -x )若f在D上二阶连续可微，则对于任何x, x d ：= D，存在；：=(x, x - d )，使得1f (x d)二 f (x)

18、 I f (x)T d d 2 f ( ') d!= f(x) 、f(x)Td d- 2 f (x)d o( d )2!2.向量函数的微分设F ： Rn > Rm是一个向量函数，若其每个分量f'i =1，,m)都连续可微，则称F (x)连续可微。F (x)在x处的导数记为:CXiF(x)=-戲1次n:=J(x)(1.39 )：fm；：Xif m：Xn称之为F (x)在x处的Jacobi矩阵，而称I F(x) = (F (x)T为向量函数F (x)在x处的梯度。右F ： R r Rm在开凸集D上连续可微，则对任何 x, x亠d三D，有：1F (x d) F (x) = j

19、F (x td )ddt定义1.12 G：RnTRm>n在xDURn处称为Lipschitz连续的，若D，都有G(v) G(x)空 v x。若在D中每一点均Lipschitz连续，则称G在d上Lipschitz连续，记为G Lip (D )。其中，称为Lipschitz常数。定理1.13 (向量函数线性化近似的误差估计)设F : Rn； Rm在开凸集D上连续可微，F (x)在x的邻域证明:D中Lipschitz连续，则对于任何x d三D，有I II | 2F (x +d) F (x) F x)d 兰一|d|.Y1 'F (x d) F (x) F (x)d F '(x L

20、：;d)dd : - F (x)dL01-_F (x : d) - F (x) dd :-0从而F ( d)- F( x) F ( x)c)>d d13#1 1乞 0 (F (x ： d) F (x) d d：岂 0 F (x ： d) F (x)|d注：在1“咖d|d|'d 上 d2.上述证明过程中的第一个不等式并不平凡,它实际上要求，对一般向量函数的积分，下述命#题成立。命题：对可积向量函数f (t) = (f't), f2(t),fn(t)T，有 J f 吐 “ | f (t)|dt #证明：对于l1范数上述命题是成立的，这是因为:#bbbbf(t)dt = fi(

21、t)dt + f2(t)dt 十- +fn(t)dt11bbbb< J； fi(t)dt + f2(t)dt 叶 + 仁水=(fi(t) +|f2(t)叶 +1 f n (t)dtba 3严对于I 2范数上述命题也成立。事实上，II 2门bnb b(f(t)dt =瓦(fi(t)dt)2=£ f(t)fi(s)dtdsiidb b nb b(送 fi(t)fi(s)dtds E J送 fi2(t)J送 fi2(s)dtdsi 2d17Al/_k2-I a-Z fi2(s)ds =( J送 fi2(t)dt)2 =( | f (t)dt|dt)i 4i ±对于一般范数，

22、需借助于Banach空间弱Riemann积分理论进行证明。定理1.13给出了线性近似的误差界，下面考虑二次近似的误差界。定理1.14设f ： Rn r在开凸集D Rn上二次连续可微， 2 f (x)在x的邻域D上Lipschitz连 续。则对于任何 x D有：_T1丁厂2f|3f(x+d)-.|f(x)+Nf(x) d+d 可 f(x)d 兰一|d|证明：f (x +d )- f xx(T(d 一dTW2f x d )21 t1 t=d T 可2 f (x d )dd adt d 丁可2 f (x)dd adtT 2T 2d ' f (x Ud)d -d ' f (x)d|-：

23、；d d ： dti ti i y.d ： dt dod3定理1.15设F ：R -； R在开凸集D二R上连续可微，则对任何 x,u,vD，有F(u) -F(v) -F (x)(u -v)F (v t(u - v) - F (x)若进一步F在D中Lipschitz连续，则有:F(u) -F(v) -F (x)(u -v) <215证明:F (u) - F (v) -F (x)(u v)1=f f "(v+t(u _v) F &) (u _v)dt 01兰F "(v +t(u -v) -F "(x)”u - v dt(由此式即可得第一部分结论)1_&#

24、176;v t(u-v)-x|u-vdt1=0 (1 -t)(v x) t(u x) u - V dt1-X 0(1-t)dt U -X#1定理1.16设F , F 满足上面定理条件，假定矩阵If (x)存在(这蕴含着 F (x)是方阵，即F(x):R“t Rn)° 则存在名:>0,，使得 F u, v D ，当 max | -x v -x 兰名时，有:二 |u V F U- H 匹：-u V证明:F(u) F(v)| |F (x)(u _v)| 亠|F(u) F(v) F (x)(u v)_ 1彳|f Yx)| +?(|u -x|-V#勿 F &)|+Y町|u v|=

25、:u -v|(令：=F (x);)从而右边不等式得证。另一方面，注意到：|u v| =|f f(x)F F(x)(u v)| m|fL(x)(u v)|)故有 |F(u) F(v)X| F(x)4u|DF4u) F( v) F-(x)(u v)F(U#1 1因此，若取；：:：1 I ,且令1- ；( 0)，则得左边不等式结论。|f(x)牛|Fx)1()-F (x)，从而有> :Z > 0。由 1 二 F (x) °F (x)岂 F (x)| F (x)，可得六、差商(偏差商)设F(x)=(匚&)，fm(x)T是一个向量函数，其Jacobi矩阵的第i行j列元素可用差

26、商(偏差商)fi (x he j) - f 伙) aijh近似。由偏差商构成的矩阵A = (a )m n称为f (x)的差商矩阵。显然差商矩阵的第j列为F (x he" -F (x)h关于差商矩阵与 Jacobi矩阵有如下误差估计式定理1.17设F ： R“ T Rm在开凸集D上连续可微，F "(x)在D中Lipschitz连续，则 |AjJ(x)2|h若采用的范数是I,范数，则有：|AJ(x)Lmh证明：将定理1.13中的d取为hej，则有hejF (x he)_F (x) _J(x)hej 二 F (x he)-F (x) _ J (x)两边同除h，则有Aj-J(x)丄

27、一1<-h217#类似地，也可以用中心差分来近似梯度和Hessian矩阵，并有如下误差估计结果。定理1.18设f ： Rn r R在开凸集D上二次连续可微，I 2f (x)在D上Lipschitz连续，又设所采用的范数满足ej=1， (i =1,，n)，定乂 f (x)在x处的中心偏差商为:aif (x hej) f ( x hej)ai如采用I：:范数，则2h1 2 -Vf (x» 兰_ h6-V 26a -Nf (x)兰一h其中a =何，aJT 证明:由定理1.14有:f (x d )- f x 八 f x(T d-丄 d：2f2令d = hei，则有#1 2 2 f (x

28、 hej - f (x) -h I f (x)ihl f2(X) iiyJ 3_ -h6再令d = -hei，又有1 2f (x hej f (x)亠h ：计(x)i h :：/ f2(X) ii令上两式中左端绝对值内的部分分别为j则有x jh )e 2h (fi )x 冬 | 片一由此即得:f ( x hej) - f (x - hej)2hW (x)i =由l. 一范数的定义，有定理1.19设f (x)在开凸集D上二次连续可微， 2f (x)在D上Lipschitz连续，采用的范数满足ej=1 ，(i =1,，n),假定 x, x hei, x ' hej, x hei hej D

29、 (i, j =1,，n)。定义:f (x 亠 hei he)一f (x hei) f (x he) f (x)aj则有:aijWf(x)ij| 中h19#A f (x) _ 5 hn3若采用矩阵范数是IJ：或F-范数，则 (这里A =(aj)是Hessian矩阵的离散形式)。1证明： 令】-f ( x 亠hej 亠 he j) - f (x) - (he- he ：)- f (x) (he-he：)- 2 f (x)( he-he ：) jj2jj1 T 2 (T hej (I f x heG )()2T1T 2=f (x 亠 he ：) - f (x) - (he：) I f (x) (h

30、e ：) '、f (x)( he：)o( - P- n _2:=f (x 亠 hej ) - f x ) hei T I) f x经简单计算有:h2f ( x)ij)#又由定理1.14有,- hei he ：618 h36#进而有V",3 =汁361II31n< he j :二6j II6ai_2-勺 f (X)ijh31< (ah105+ P 十口)= Yh=-Yh63再由矩阵-丨一一及F-范数的定义立即可得：1 COA _ '、2 f (x)5 hn§ 1.3凸集与凸函数一、凸集(Convex Set)1 凸集的概念 定义1.20设S Rn，

31、若-x1, x S，都有:-Xt (1 -匚)x2 ：= S 一匚 0,1则称S是凸集。定理1.21 Rn的子集S为凸集的充分必要条件是-X-X2，Xm S有m其中、©丄0 (i =1,，m)且疋二人=1 。凸集的例子：i z1n维球、半空间、超平面、:x Ax =b,x _0f等均为凸集。定理1.22若S,S2是Rn中的凸集，则1 )0 S2是凸集；(事实上，任意多个凸集的交仍为凸集)2 ) S±S2 =& ± X2 % 乏 S,X2 E S2 也是凸集2.凸包 集合S的凸包的定义如下：mmConv( S)=彳 x x =迟 阿备,乂严 s,瓦 8=1,

32、8 兰0, m =1,2,i zfci =fcS的凸由定义知，集合S的凸包由S中元素所有可能的凸组合构成。还可证明：它是所有包含集合 集的交，即它是包含集合 S的最小凸集。3 锥、凸锥 定义1.23设K二Rn，若-x三K , -，. 0，有，x K，则称K为锥；若锥K还是凸集，则称之 为凸锥。容易证明：K是凸锥的充要条件是，K对正组合运算封闭。定理1.23若c Rn是凸集，则C的闭包C也是凸集。证明：-X, y：=C，则存在序列XkWk；=C，使得lim xk = x， lim yk = yk ： ： k-:从而有丨 i m 仇 G1 yj = ) x ：卜一'( 1y ,10,1 I

33、k注意到Xk (仁 yj = c及c的闭性，可知 x (1 '；)y 三 C这就证明了 C是凸集。4.极点与极方向定义1.24设S Rn是非空凸集，x S，若x不在S中任何线段的内部，则称x是凸集S的极点。 显然，多边形顶点、圆周上的点均为极点。定义1.25设S Rn是闭凸集，d为非零向量，若对任意 x S，当 _0时，总有xS ,则称d为S的方向；若S中的某方向d不能表示为该集合的两个不同方向的正的线性组合，则称d为S的极方向。极点与极方向是凸多面体中非常重要的概念，在线性规划中有重要应用，关于这些方面的详细 讨论，可参阅有关线性规划教材。二、凸函数定义1.26设S Rn是非空凸集，

34、f是定义在S上的函数，若对任意的 X-X2，S都有：f (a x + (1 a % 芦a f (x )(壬 f) 2x( ) Fa E ( 0 , 1 )则称f是S上的凸函数。凸函数的另一等价定义是:f (7Xi)，if (Xi)i ±i An其中，7打=1_0。若X.PX2时，不等式严格成立，则称f在S上是严格凸的。若_f在S上i 2是凸(严格凸)，则称f在S上是凹(严格凹)。定理1.27设f (x)是定义在凸集S上的凸函数，1) 若_ 0 ,则f (x)是S上的凸函数；2) 若匚2是S上的凸函数，贝U f1 - f2也是凸函数。m由此立即可得：若 ft，fm是S上的凸函数，二，&

35、gt;m_0，则:-ifi也是S上的凸函数。i <凸函数的一阶特征定理1.28设SRn是非空开凸集，f是定义在S上的可微函数，则f为凸函数的充要条件是：f(y)_f(x) f(xf(y_x)_x, y S证明：必要性，设f是凸函数，则对任意的：(0,1)，有f (: y (1 - )x )_ : f (y )(壬 f) x("亠f(x + a(y_x)_ f ( x)因此有f(y)- f ( x)a令一；0 得、f(x)T (y- x)乞 f ( y)- f ( x即f ( y) _ f ( x)，、f (；)(y x必要性得证。充分性：设 f ( y)兰 f (x) + W

36、(x)T (y x) , Vx, y E S 成立。任取 Xt, x2 S 及：£ 三(0,1)，令 x = Xt (1 -)X2，于是有：f(xj 一 f(x) Vf (x)T(xx)f (X2 ) _ f (x)八、f (X)T(X2X)于是有：f ( X )(1 ： f X -) f X 八 fT x:) 1 x ¥ 1 2 x)- x=f ( x) = f ( ： Xi (1 -一)X2)即f © x + ()为)兰。f (X 旷 (七 f) 2x()亦即f (x)是凸函数，充分性得证。几何解释：凸函数图像位于割线之下，切线之上。凸函数的二阶特征定理1.2

37、9设S二Rn是非空开凸集，f是定义在S上的二次可微函数，则f为凸函数的充要条件是S上的每一点的 Hessian矩阵半正定。证明：充分性，设V/ 2故一 p 2 f (x) p 0( p 02两边除以 2并令0，则有T 2pf (x ) p 丄 0即、2f(x)半正定。注：对严格凸函数有类似的一阶与二阶特征，但要注意一些细微的差别。定理1.30设S Rn是非空开凸集，f是定义在S上的可微函数，则f为严格凸的充要条件是f ( y) f ( x) l f (Tx) (y ,x -x, y S,x = y证明：充分性证明与前述凸函数情形完全类似，故从略。必要性的证明如下：f (x)在每一点x E S均

38、半正定。任取x, y S，由中值定理有：f (y)= f X 八 f x(T )y 4x TyxT'2f y(x»()_ f ( x)亠f ( x) ( y - x)(其中 在以x, y为端点的线段上)所以，f (x)是凸函数。必要性，设f (x)是凸函数，则任取 x S，对任意的p Rn，充分小时有f ( x 丁 .；，p) _ f( x)r，'f( Tx)p-2另一方面f(x+p)=f x "W X(Tp+pP2f x p 巧 I >L(p ()21设f(X)在S上严格凸，-x,yws且x = y，令z=_x -21y，则显然z .= S。由于f(

39、 x)严格凸，211故有f(z) ： f(x) f(y)由上两式有f ( z)_ f ( X) I f (Tx)(z11f(x) f (y) . f(x)22111f ( y) f ( x)222'、f(x)T (z X)f (Tx) (y x)2223#因此有定理1.31设是非空开凸集,f是定义在S上的二次可微函数，若 -xS,' 2f(x)正定，则f (y) f (x)、f (x)T(y x).#f (x)为严格凸函数。注：严格凸不能推出I 2f(X)正定,因此I 2 f(X)正定是严格凸的充分条件，但不是必要条件。如4”f(x)二 X ， f (x)2卄二 12x ， f

40、 (0)不正定，但它是严格凸的。定理1.32设SRn是非空开凸集,f是定义在S上的凸函数，是一个 实数，则水平集#x ：二S, f (x) 芒；是凸集。证明：略那么所以定理进一步，若f (x)是连续凸函数，则f(x)=f ( l i XV =) lfi kk_jDCx L.，故L：.为闭集。1.33L.是闭凸集。_(； ；)设f (x)是s二Rn上二次连续可微的凸函数,T 2.u f (x) u - m事实上，设且存在常数- x L (x0)， u Rn:Xk ；二 L 一，且 lim Xk = x k_, -m - 0，使得#则水平集L (x0) - ；x x S, f (x) _ f (x

41、0) ?是有界闭凸集。证明：由上面讨论可知，L (x0)是闭凸集，因而仅需 证明L(x0)是有界的。由于L (x0)是凸的，因而y2x_x, y L( ox), x ： (y x)y (1 - ： )x L(x°)，从而有 (y-x)： f(x枚 (y-为)(尸 x)冷 m由Taylor展开式,TT 2f(y) =f(x) f(x) (y _x) .o.o(y_x) f(x ：.(y_x)(y_x)d：.dt1f(x) lf(x)T(y x) omy._x二 f ( x) I f ( (y _ x)12可知,-y L (Xo), y = X。，有25#T 1 |f (y) - f(X

42、。)_ '、f (Xo) (y -x°) m y2 111-m y x2再由f ( y) f (ox ) ,o#故有XinXii 土p/p+ (送 yip/i去1I f(X。)m y _x2|y Xo| 兰一|Rf (Xo)|m由y是L (x0)中任一向量，所以L (x0)有界，因而L (x0)是有界闭凸集。x y卩空x卩 y卩，即:定理1.34(Minkowski不等式)对p _1，有#证明：当x或y为零向量时，结论显然成立。当p = 1时，也易证明。以下设 x, y = 0，且p>1。p考虑函数w(t)=tp， t>0由于®"(t)= p

43、(L 供,0故®(t)严格凸。注意到拥p丄|y|p1+=1IIXL+IMIp IXL+IMIp由函数-:(t)的凸性，于是有,#因此,Xi yiln<zi韭_Xp_JXip_ypyip#pp =1Xp yp ypxL y p|x|由定义立即可知：一致凸=严格凸二.凸。致凸函数的判别定理定理1.36设f (x)是非空开凸集D上连续可微函数，则f (x)在D上一致凸的充要条件是存在常数-0，使得证明:f(y) -f (x) _、f(x)T(y -x)y -x先证必要性。若f (x) 一致凸,2 ，一x, y Dppn由此即得y Xj + yji 2三、一致凸函数定义1.35设f是非

44、空凸集D上的函数，若存在一个常数1.0，使得对任意的x, y . D，及任意很三(0,1)。均有:f (x) (1 - :) f ( y) - f (x (1 -)y) _ (1 - : ) |则称f (x)在凸集D上一致凸。#:f (x) (1 -)f (y)f (x (1 -)y) _ (1 -)J* xy从而:f (x) f (x) (1 - ： ) f (y) _ f (： x (1 - ： ) y) - f (x)(1)|x y因此f(y)f(x)_f(：x (1 =)y) f(x) xy*)f (、；x (1 - : ) y) = f (x (1 -)( y - x)=f (x)

45、+(1 G) W (x)T (y x) +o(|(1 G)( y x)|)将上式代入(*)即得:#f (y)(x),f(x)T(y_x)皿 922 x_y1 _a2272#f (y)(x)-、'、f (x)T (y x)亠| y x再证充分性。任取x,D，令x = ： x亠(1 - ： ) y，：丄三(0,1)。由D是凸集，故 x -D，因而有:f (x)-f (X):-j yf (x)T (x _x)丄X _xf (y)-f (X)小f(x)T (y 一刃：计 y x2#2#两式分别乘:-和(1 -二)再相加，则有X_X 2 (1 _：) y _x 1 2:f (x) (1 一)f

46、(y) - f (壬)_ l-：,:-1将x = ： x亠(1 - ：) y代入即得结论:-f (x) - (1二)f (y) f (： X (1二)y) _ (1二)、川 x -y2#2#定理1.37设f (x)是开凸集D上连续可微函数，则f(x)在D上一致凸的充要条件是:-7-、-存在常数2#2#1 - 0，使得 、f ( y) _、f (x)T(y _x)；“：讨 y _x证明：参见徐成贤等著近代优化方法P15。定理1.38设f (x)在开凸集D上二阶连续可微，则f(x)在D上一致凸的充要条件是:-7-八、-P7.存在常数2#2#m 0，使得:2u " u 1令m，则2 f (

47、x)u，-X D， - U Rn 证明：充分性：-x, y三D，有1f (y) - f(X)八 f(X)T (y -X) (y_x)T、2f( )(yx)22#2#其中=x r( yx)， (0：:V ：: 1)。由于D是凸集，故-D。因此,2#2#()(y - x)2#2#f (y) f (X)-yf (x)T(y2#2#必要性：设f (x)在D上一致凸。任取x D，uRn且u 0，则有2#2291 1I 2 f (x) u = lim I f (x .；”u) - I f (x)T u = lim 2 f (x.；”u) - I f (x)T ；/. j0 Jlim。丄u2 八 u2.J治

48、。疔四、凸集的分离与支撑凸集的分离与支撑定理在研究约束最优化问题的最优性条件时具有基本的重要性，起着十分关键的作用。定理1.39设S二Rn是非空闭凸集，y - S，则存在唯一的点 厂S，它与y的距离最短。进一步 x与y距离最短的充要条件是：(x 一 * (x - y) _ ,0 - x S证明：先证定理的第一部分 存在性 任取一点x°三S，则集合D = x |y xm|yx0|,x S为一非空有界闭集， 而y-x是x的连续函数，故它必在D的某一点x上取得最小值，此x即为所 求。注意到x S，而y y S，必有| X - y = r . 0。唯一性 假定还有乂隹S，满足 | y 冈彳y

49、二* =。由S的凸性，贝y- S2考虑y -x|+环一打=r2 | 22由r是S中点到y的最小距离，故上式必取等式。因而必有n Fy x = (y x )再由若=-1，则得y-x = y-x，得 二 1。y-x - - y 亠 x： 2 y 二x 亠 x ,与y F S矛盾。因而只能是 =1，即y_k=y_X，或x = X，唯一性得证。再证定理第二部分 若-x三S，都有T(x -x) (x - y) _ 0，y-x42 2二 y_x| x_xx -(x y>* X 习 y- x即x与y有极小距离。反之，若-x三S，都有X -y 一 |x - y由于对充分小的因此另一方面,y _x - '(x _x)2-y所以xxyJ|x x|2，(xx)x y)-Tx -) x( x_) y两边同除，并令0 ,即得所要的结果。点与凸集的分离定理定理1.40设SRn是非空闭凸集,则存在向量p = 0和实数爲，使得pTx_，- xS，并且同时满足即超平面pTx = 严格分离点y和闭凸集S 。证明：由于S是闭凸集， X S。故定理1