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

最优化理论与算法（数学专业研究生）

第一章 引论

§1.1 引言

一、历史与现状

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

minf(x) （1.1） nxR2、约束最优化问题

minf(x)

ci(x)0, iE （1.2）

s..tci(x)0, iI这里E和I均为指标集。

§1.2数学基础

一、 范数 1. 向量范数

xmaxxi （l范数） （1.3）

x1xi （l1范数） （1.4）

i1nx2(xi) （l2范数） （1.5）

i1n122精品文档

精品文档

1ppxp(xi) （lp范数） （1.6）

i1nxA(xAx) （A正定） （椭球范数） （1.7）

T12事实上1－范数、2－范数与范数分别是 p－范数当 p＝1、2和p时情形。 2．矩阵范数

定义1.1 方阵A的范数是指与A相关联并记做A的一个非负数，它具有下列性质： ① 对于A0都有A0，而A0时A0； ② 对于任意kR，都有kAkA； ③ ABAB； ④ ABAB； 若还进一步满足： ⑤ AxpAxp

p则称之为与向量范数相协调（相容）的方阵范数。若令

Amaxx0Ax （这里x是某一向量范数） （1.8） x相协调的，通常称之为由向量范数

诱导的方阵范数。特别地，

可证这样定义的范数是与向量范数对方阵A(aij)nn，有：

A1maxaij（列和的最大者） （1.9）

ji1nnAmaxaij（行和的最大者） （1.10）

ij1A2(ATA)2（ATA表示ATA的特征值的最大者） (1.11)

称为谱范数（注：方阵A的特征值的模的最大者称为A的谱半径，记为(A)）。

对于由向量诱导的方阵范数，总有：

1精品文档

精品文档

A11Axminx0x ，I1（I为单位阵）

对于方阵范数，除了上述由向量范数诱导的范数之外，还有常用的Frobenius范数，简称F-范数：

AF(aij)[tr(AA)] (1.12)

Ti1j1nn12212及加权Frobenius范数和加权l2范数:

AM,FMAMF (1.13)

AM,2MAM2 (1.14)

其中M为对称正定矩阵。 3. 范数的等价性 定义1.2 设

与

是Rn上的两个范数，若存在1,20，使得

1x则称范数

x2x， xRn (1.15)

与

是等价的。

容易证明：

x2x1nx2 (1.16) xx2nx (1.17)

xxx1nx (1.18) x2x1 (1.19)

nx2xA1x2 (1.20)

其中1是A的最大特征值，而n是A的最小特征值。由此可见，R中的常用向量范数均等价，事实上还可证明：R中所有向量范数均等价。 4. 关于范数的几个重要不等式。

① Cauchy-Schwarz不等式

nnxTyxy（当且仅当x和y线性相关时，等式成立） (1.21)

精品文档

精品文档

② 设A是正定矩阵，则

xTAyxTAyA（当且仅当x与y线性相关时，等式成立） (1.22)

由(x,y)xAy是一种内积，以及一般内积的Cauchy-Schwarz不等式即得。 ③ 设A是nn正定矩阵，则

xTyxAyA1（仅当x与Ay线性相关时，等式成立） (1.23)

1xTyxTAA1yx其中的不等号由②可得。

AA1yAxAyA1 (1.24)

④ Young不等式：假定p与q都是大于1的实数，且满足

111，则x,yR，有 pqxpyq xy， (1.25) pq当且仅当xy 时，等式成立。其证明由算术－几何不等式直接给出，事实上

pqxy(x⑤ Hölder不等式

p)(y)q1p1qxpyq（算术－几何不等式） pqxyxTpyq(xi)(yi)q (1.26)

pn1pn1qi1i1其中p与q都是大于1的实数，且满足⑥ Minkowski不等式

111，其证明利用Young不等式可得。 pqxyp（p1） (1.27) xpyp，

后面将利用凸函数理论予以证明。

二、矩阵求逆与广义逆 1. Von-Neumann引理

定理1.3 (Von-Neumann引理) 设ER如果E1，则(IE)非奇异，且 精品文档

nn，IRnn是单位阵，

是满足I1的相容矩阵范数。

精品文档

(IE)Ek， (IE)11K01

1E若A非奇异，A1(AB)1,则B非奇异，且

B1(IA1B)kA1， B1k02证明：因为E1，故 SkIEEA11A1(AB).

Ek 定义了一个Cauchy序列，因而收敛。由

k1 Sk(IE)IE

可得 limSk(IE)lim(IEkk1k)I

故有

Ek0klimSk(IE)1

k进一步有 (IE)1Ek0k1。

1E再令 EIAB，

知 EIA1BA1(AB)1 由上面结论可得，

1(IE)(AB)(IA1B)k

111k01所以有 B(IA1B)kA1k0

进一步有 B1IA1Bk0kA1A1(AB)k0kA1A11A1(AB)。

注：这个定理表明，若B充分接近一个可逆矩阵A，则B也可逆，且逆矩阵可由A的逆矩阵来表示。

上述定理还可以写成下面形式： 定理1.4 设A,BRnn，A可逆，A1。若AB，且1，则B可逆，且

B1。

111证明：只需注意到A(BA)A精品文档

BA1，再由上述Von-Neumann引理即得。

精品文档 2. 广义逆 定义1.5 设ACmn，若ACnm满足：

AAAA,AAAA,(AA)*AA,(AA)*AA (1.28)

则称A是A的广义逆。其中A*是A的共轭转置。 广义逆的求法 ① 设ACmn，秩(A)r，若A直交分解为AQRP，其中Q，P分别为mm,nn酉矩阵，

*R0RCmn，R11，其中R11是rr非奇异的上三角矩阵。则A的广义逆为：

001R110APRQ 其中 R (1.29)

00*② 若A的奇异值分解为AUDV，其中U，V均为酉矩阵，D*00mnC，而0diag(1,,r),i0是A的非零奇异值，则A的广义逆为：

*10AVDU，其中D (1.30)

00③ 若A的最大秩分解为ABC，则

A的广义逆为：

AC*(CC*)1(B*B)1B*. (1.31)

三、 矩阵的Rayleigh商

定义1.6 A是nn Hermite矩阵，uC，则称

nu*AuR(u)* （u0） (1.32)

uu为矩阵A的Rayleigh商

定理1.7 设A是nn Hermite矩阵，则Rayleigh商具有下列性质： 1) 齐次性： R(u)R(u) （0）

u*Au2) 极性： 1maxuAumax*

u21u0uu*精品文档

精品文档

u*AunminuAumin*

u21u0uu*这里1，n分别对应于矩阵A的最大与最小特征值。这表明Rayleigh商具有有界性： nR(u)1 3）极小残量性质：对任意uC，

n(AR(u)I)u(AI)u，R。

证明：1）由定义直接可得。

1*2）由A是Hermite矩阵，故存在酉矩阵T，使TAT又令 uTy，且u*** n21，故y21

*2则 uAuyTATyyy1y1当取y(1,0,nyn

0,1)时，达到最小值n。

2,0)时达到最大值1，当取y(0,0,3）令s(u)AuR(u)u，(u0)，则Aus(u)R(u)u，可直接验证

s(u),R(u)u0，

**由于 (s(u),u)(AuR(u)u,u)uAuR(u)uu0

注意到R(u)u是与u共线的，故s(u)与R(u)u正交。即R(u)u与s(u)是Au的正交分解。因而

R(u)u是Au在Lu上的直交投影，因而具有极小残量性质。

四、矩阵的秩一校正

当矩阵A变到Auv时，即在A上加了一个秩为1的矩阵，称为秩一校正。下面讨论如何求秩一校正的逆，行列式，特征值及矩阵分解。 定理1.8 设ARmnTu,vR是任意向量。是非奇异的，若1vAu0，则A的秩一校正AuvnTT非奇异，其逆矩阵可以表示为

精品文档

精品文档

A1uvTA1(Auv)A (1.33)

1vTA1uT11证明：可直接验证。

上述定理的可进一步推广为：

定理1.9 设A是非奇异矩阵，U,V是nm矩阵，若IVAU可逆，则AUV可逆，且

*1*(AUV*)1A1A1U(IV*A1U)1V*A1 (1.34)

下面介绍关于秩一校正的行列式定理 定理1.10 1）det(Iuv)1vu

TTTTTT2）det(Iu1u2u3u4)(1u1u2)(1u3u4)(u1u4)(u2u3)

TT证明： 1）若u0，则结论显然成立；若u0，设w是(Iuv)的特征向量。则

T(IuvT)ww

易见w要么与v垂直，要么与u平行。若与v垂直，则特征值为1；若与u平行，则对应特征值为

1vTu。 进一步，平行于u的特征向量只有一个（线性无关），而垂直于v的线性无关的向量有n1个，它们均为Iuv属于特征值1的特征向量，即特征值1是(n1)重根， 而1vu是单根。

T故有 det(Iuv)1TTn1n1(1vTu)1vTu。

TTTT1T2） 对Iu1u2u3u4(Iu1u2)I(Iuu)uu1234 使用上面结果，故有：

TT1det(Iu1u2Tu3u4T)(Iu1Tu2)1u(Iuu)u3412

Tu1u2T(1uu2)1u4(I)u3 T1uu12T1TTTu4)(u1u4)(u2u3)。 (1u1Tu2)(1u3关于秩一校正矩阵的特征值定理。

定理1.11设A是对称矩阵，其特征值为12n，又设AAuuT，其特征值为

12n，那么

nn

1） 若0，则1122精品文档

精品文档

2） 若0，则1122

五、函数与微分

1.多元函数的梯度与Hessian矩阵 梯度 f(x)(nn

f,x1,fT) (1.35) xn2f2x12Hessian矩阵 f(x)2fxnx12fx1xn (1.36) 2fxn2方向导数：（设d为一方向向量，即长度为1的单位向量，显然与范数的取法有关）

ff(xd)f(x)Tlimf(x)d (1.37) 0x注：对欧氏范数（2－范数）而言，梯度方向是函数上升最快的方向，而负梯度方向则是函数下降最快的方向。正因为这个原因，使得梯度在最优化理论与算法中占有特殊重要的地位。

若f:RR在开凸集D上连续可微，则有

nf(xd)f(x)f(xtd)Tddtf(x)f()Td （1.38）

01其中(x,xd)。上式也可改写为：

f(y)f(x)f(xt(yx))T(yx) t(0,1)

或 f(y)f(x)f(x)(yx)o(yx)

若f在D上二阶连续可微，则对于任何x,xdD，存在(x,xd)，使得

Tf(xd)f(x)f(x)Td1T2df()d 2!12f(x)f(x)TddT2f(x)do(d)

2!2.向量函数的微分

nm设F:RR是一个向量函数，若其每个分量fi(i1,,m)都连续可微，则称F(x)连续可

微。F(x)在x处的导数记为： 精品文档

精品文档

f1x1F(x)fmx1f1xnJ(x) （1.39） fmxnT称之为F(x)在x处的Jacobi矩阵，而称F(x)(F(x))为向量函数F(x)在x处的梯度。

若F:RR在开凸集D上连续可微，则对任何x,xdD，有：

nmF(xd)F(x)F(xtd)ddt

01定义1.12 G:RRnmn在xDR处称为Lipschitz连续的，若vD，都有

nG(v)G(x)vx。

若在D中每一点均Lipschitz连续，则称G在D上Lipschitz连续，记为GLip(D)。其中，称为Lipschitz常数。

定理1.13 （向量函数线性化近似的误差估计）设F:RR在开凸集D上连续可微，F(x)在x的邻域D中Lipschitz连续，则对于任何xdD，有

nmF(xd)F(x)F(x)d证明： F(xd)F(x)F(x)d2d.

210F'(xd)ddF(x)d

F(xd)F(x)dd

01从而 F(xd)F(x)F(x)d  F(xd)F(x)dd0101

10(F(xd)F(x))ddF(xd)F(x)dd

10dddd210dd.

122注：在上述证明过程中的第一个不等式并不平凡，它实际上要求，对一般向量函数的积分，下述命题成立。

命题：对可积向量函数f(t)(f1(t),f2(t),,fn(t))，有

Tbaf(t)dtf(t)dt.

ab证明：对于l1范数上述命题是成立的，这是因为：

精品文档

精品文档

babaf(t)dt1babaf1(t)dtbaf2(t)dtbababafn(t)dt

fn(t))dt

f1(t)dtf2(t)dtbafn(t)dt(f1(t)f2(t)f(t)dt

1对于l2范数上述命题也成立。事实上，

babb2af(t)dtbn(fi(t)dt)2i1ai1nbbiaanbnba2bafi(t)fi(s)dtds(f(t)f(s))dtdsfaii1i1i(t)nfi1n2i(s)dtdsb

ai1nfi(t)dt2bai1nfi(s)ds(2bai1fi2(t)dt)2(af(t)dtdt)2对于一般范数，需借助于Banach空间弱Riemann积分理论进行证明。 定理1.13给出了线性近似的误差界，下面考虑二次近似的误差界。

n定理1.14 设f:RR在开凸集DR上二次连续可微，f(x)在x的邻域D上Lipschitz连

n2续。则对于任何xdD有：

13f(xd)f(x)f(x)TddT2f(x)dd

26T()fx(d)证明： f(xd)fx1T2dfxd( )210011t00dT2f(xd)dddttdT2f(x)dddt

00tdT2f(xd)ddT2f(x)dddt

100tddddtdnm231t00ddtd

163n定理1.15 设F:RR在开凸集DR上连续可微，则对任何x,u,vD，有

(vt(uv))F(x)uv， F(u)F(v)F(x)(uv)supF0t1若进一步F在D中Lipschitz连续，则有：

F(u)F(v)F(x)(uv)uxvxuv.

2精品文档

精品文档

证明：F(u)F(v)F(x)(uv)1F(vt(uv))F(x)(uv)dt011

F(vt(uv))F(x)uvdt （由此式即可得第一部分结论）

0vt(uv)xuvdt(1t)(vx)t(ux)uvdt

001uvvx10(1t)dtuxtdt01uxvxuv.

21定理1.16设F,F满足上面定理条件，假定矩阵F(x)存在（这蕴含着F(x)是方阵，即

F(x):RnRn）。则存在0,0，使得u,vD，当max

ux,vx 时，有：

uvF(u)F(v)uv

证明：F(u)F(v)F(x)(uv)F(u)F(v)F(x)(uv) F(x)(uxvx)uv

2 F(x)uv uv （令F(x)） 从而右边不等式得证。另一方面，注意到：

uvF(x)1F(x)(uv)F(x)1F(x)(uv)）

故有 F(u)F(v)F(x)(uv))F(u)F(v F(x) (uv)1 (uxvx12F(x))uv 1 uvuv 1F(x)因此，若取11，且令 (0)，则得左边不等式结论。 11F(x)F(x)1由1F(x)F(x)F(x)1F(x)，可得

1F(x)，从而有0。 1F(x)六、差商（偏差商）

设F(x)(f1(x),精品文档

,fm(x))T是一个向量函数，其Jacobi矩阵的第i行j列元素可用差商（偏差

精品文档 商）

aijfi(xhej)fi(x)h

近似。由偏差商构成的矩阵A(aij)mn称为F(x)的差商矩阵。显然差商矩阵的第j列为

AjF(xhej)F(x)h

关于差商矩阵与Jacobi矩阵有如下误差估计式

定理1.17 设F:RR在开凸集D上连续可微，F(x)在D中Lipschitz连续，则 AjJ(x)jnm2h

若采用的范数是l1范数，则有：AJ(x)1证明： 将定理1.13中的d取为hej，则有

2h

F(xhej)F(x)J(x)hejF(xhej)F(x)J(x)jh两边同除h，则有

AjJ(x)j2hej22h2

2h.

类似地，也可以用中心差分来近似梯度和Hessian矩阵，并有如下误差估计结果。

定理1.18 设f:RR在开凸集D上二次连续可微，f(x)在D上Lipschitz连续，又设所采用的范数满足ej1，(i1,n2,n)，定义f(x)在x处的中心偏差商为：

aif(xhei)f(xhei)

2h则 aif(x)i如采用l范数，则af(x)证明：由定理1.14有：

6h2

,an)T.

6h2 ，其中a(a1, f(xd)f(x)f(x)d令dhei，则有

T1T23df(x)dd 26精品文档

精品文档

1f(xhei)f(x)hf(x)ih22f(x)iih3

26再令dhei，又有

1f(xhei)f(x)hf(x)ih22f(x)iih3

26令上两式中左端绝对值内的部分分别为,，则有

f(xhei)f(xhei)2hf(x)ih3

3f(xhei)f(xhei)f(x)iaif(x)ih2

2h6由此即得：

由l范数的定义，有

af(x)6h2.

2定理1.19 设f(x)在开凸集D上二次连续可微，f(x)在D上Lipschitz连续，采用的范数满足

ej1，(i1,,n)，假定x,xhei,xhej,xheihejD(i,j1,aijf(xheihej)f(xhei)f(xhej)f(x)h22,n)。定义：

则有： aijf(x)ij5h 3若采用矩阵范数是l1,l或F-范数，则

5。 hn（这里A(aij)是Hessian矩阵的离散形式）

31TT2证明：令f(xheihej)f(x)(heihej)f(x)(heihej)f(x)(heihej)

21TT2 f(xhei)f(x)(hei)f(x)(hei)f(x)(hei)

21f(xhej)f(x)(hej)Tf(x)(hej)T2f(x)(hej)

2(aij2f(x)ij) 经简单计算有： 2h Af(x)2又由定理1.14有，

6heihej38h3 6精品文档

精品文档

6heihej23631h3 61h3 6进而有 aijf(x)ijh21105()hh h263再由矩阵l1,l及F-范数的定义立即可得：

5A2f(x)hn

3

§1.3 凸集与凸函数

一、凸集（Convex Set） 1．凸集的概念

定义1.20 设SR，若x1,x2S，都有

x1(1)x2S 0,1 则称S是凸集。

定理1.21 R的子集S为凸集的充分必要条件是x1,x2,

nn,xmS有

xS

iii1m其中i0 (i1,,m)且i1。

i1m凸集的例子：n维球、半空间、超平面、xAxb,x0等均为凸集。 定理1.22 若S1,S2是R中的凸集，则 1） S1nS2是凸集；（事实上，任意多个凸集的交仍为凸集）

2） S1S2x1x2x1S1,x2S2也是凸集 2．凸包 集合S的凸包的定义如下：

mm Conv(S)xxixi,xiS,i1,i0,m1,2,i1i1 由定义知，集合S的凸包由S中元素所有可能的凸组合构成。还可证明：它是所有包含集合S的凸精品文档

精品文档

集的交，即它是包含集合S的最小凸集。 3．锥、凸锥

定义1.23 设KRn，若xK,0，有xK，则称K为锥；若锥K还是凸集，则称之为凸锥。

容易证明：K是凸锥的充要条件是，K对正组合运算封闭。 定理1.23 若CR是凸集，则C的闭包C也是凸集。 证明：x,yC，则存在序列xk,ykC，使得

nlimxkx，limyky

kk从而有 lim(xk(1)yk)x(1)y，0,1

k注意到

xk(1)ykC及C的闭性，可知

x(1)yC

这就证明了C是凸集。 4．极点与极方向

定义1.24 设SR是非空凸集，xS，若x不在S中任何线段的内部，则称x是凸集S的极点。 显然，多边形顶点、圆周上的点均为极点。

定义1.25 设SR是闭凸集，d为非零向量，若对任意xS，当0时，总有xdS，则称d为S的方向；若S中的某方向d不能表示为该集合的两个不同方向的正的线性组合，则称d为S的极方向。

极点与极方向是凸多面体中非常重要的概念，在线性规划中有重要应用，关于这些方面的详细讨论，可参阅有关线性规划教材。

二、凸函数

定义1.26 设SR是非空凸集，f是定义在S上的函数，若对任意的x1,x2S都有： f(x1(1)x2)f(x1)(1)f(x2) (0,1 )则称f是S上的凸函数。凸函数的另一等价定义是：

nnn精品文档

精品文档

nnf(ixi)if(xi)

i1i1其中，

i1ni1,i0。若x1x2时，不等式严格成立，则称f在S上是严格凸的。若f在S上

是凸（严格凸），则称f在S上是凹（严格凹）。 定理1.27 设f(x)是定义在凸集S上的凸函数，

1） 若0，则f(x)是S上的凸函数；

2） 若f1,f2是S上的凸函数，则f1f2也是凸函数。 由此立即可得：若f1,凸函数的一阶特征

定理1.28 设SR是非空开凸集，f是定义在S上的可微函数，则f为凸函数的充要条件是：

n,fm是S上的凸函数，1,,m0，则ifi也是S上的凸函数。

i1mf(y)f(x)f(x)T(yx) x,yS

证明：必要性，设f是凸函数，则对任意的(0,1)，有 f(y(1)x)f(y)(1)f(x) 因此有

f(x(yx))f(x)Tf(y)f(x)

令0得 f(x)(yx)f(y)f(x) 即 f(y)f(x)f(x)(yx) 必要性得证。

充分性： 设f(y)f(x)f(x)(yx)，x,yS成立。

任取x1,x2S及(0,1)，令xx1(1)x2，于是有：

T f(x1)f(x)f(x)(x1x) T f(x2)f(x)f(x)(x2x)

TT于是有

f(x1)(1)f(x2)f(x)f(x)Tx1(1)x2x

精品文档

精品文档

f(x)f(x1(1)x2)

即 f(x1(1)x2)f(x1)(1)f(x2) 亦即f(x)是凸函数，充分性得证。

● 几何解释：凸函数图像位于割线之下，切线之上。 凸函数的二阶特征

定理1.29 设SR是非空开凸集，f是定义在S上的二次可微函数，则f为凸函数的充要条件是

nS上的每一点的Hessian矩阵半正定。

证明：充分性， 设 f(x)在每一点xS均半正定。任取x,yS，由中值定理有：

TT2(yx)f()(yx) f(y)f(x)f(x)(yx)122 f(x)f(x)(yx)，（其中在以x,y为端点的线段上） 所以，f(x)是凸函数。

必要性，设f(x)是凸函数，则任取xS，对任意的pR，充分小时有 f(xp)f(x)f(x)p 另一方面 f(xp)f(x)f(x)pTTnT22pT2f(x)p0(p)

2故

22pT2f(x)p0(p)0

2两边除以并令0，则有

2pT2f(x)p0

即 f(x)半正定。

注：对严格凸函数有类似的一阶与二阶特征，但要注意一些细微的差别。

定理1.30 设SR是非空开凸集，f是定义在S上的可微函数，则f为严格凸的充要条件是 f(y)f(x)f(x)(yx)， x,yS,xy

证明：充分性证明与前述凸函数情形完全类似，故从略。必要性的证明如下：

T2n精品文档

精品文档

设f(x)在S上严格凸，x,yS且xy，令z故有 f(z)11xy，则显然zS。由于f(x)严格凸，2211f(x)f(y) 22T及 f(z)f(x)f(x)(zx)

11f(x)f(y)f(x)f(x)T(zx) 22111 f(y)f(x)f(x)T(yx)

222由上两式有

因此有 f(y)f(x)f(x)(yx).

n定理1.31设SR是非空开凸集，f是定义在S上的二次可微函数，若xS,f(x)正定，则

2Tf(x)为严格凸函数。

注：严格凸不能推出f(x)正定，因此f(x)正定是严格凸的充分条件，但不是必要条件。如

22f(x)x4，f(x)12x2，f(0)0 不正定，但它是严格凸的。

定理1.32 设SR是非空开凸集，f是定义在S上的凸函数，是一个实数，则水平集

nLxxS,f(x)是凸集。

证明： 略

进一步，若f(x)是连续凸函数，则L是闭凸集。事实上，设xkL，且limxkx

k那么 f(x)f(limxk)limf(xk)

kk所以 xL，故L为闭集。

定理1.33 设f(x)是SR上二次连续可微的凸函数，且存在常数m0，使得

nT2 uf(x)umu xL(x0)，uR

n2则水平集L(x0)xxS,f(x)f(x0)是有界闭凸集。

证明：由上面讨论可知，L(x0)是闭凸集，因而仅需 证明L(x0)是有界的。由于L(x0)是凸的， 因而 x,yL(x0)，x(yx)y(1)xL(x0)， 从而有 (yx)f(x(yx))(yx)my x由Taylor展开式， 精品文档

T22精品文档

f(y)f(x)f(x)(yx)T f(x)f(x)(yx)T1001(yx)ttT2f(x(yx))(yx)ddt

200myxddt

f(x)f(x)(yx)可知，yL(x0),yx0，有

T12myx 212f(y)f(x0)f(x0)T(yx0)myx0

212f(x0)yx0myx0

2再由 f(y)f(x0)0， 故有 f(x0)即 yx01myx00 22f(x0) m由y是L(x0)中任一向量， 所以L(x0)有界，因而 L(x0)是有界闭凸集。 定理1.34 （Minkowski不等式） 对p1，有xypxpyp，即：

p1p(xiyi)i1np1p(xi)i1np1p(yi)i1n .

证明：当x或y为零向量时，结论显然成立。当p1时，也易证明。以下设x,y0，且p>1。 考虑函数 (t)t， t0 由于 (t)p(p1)t注意到

p2p0，故(t)严格凸。

ppxppxpyyxpy1

由函数(t)的凸性，于是有，

xpxyp因此，

pxipxpxpypypxpyiypxpyppxiypxxpyppppyi yppppxiyii1xpynpnxiyii1xpyxpxpyppxiypxxpyi1pnpyiyi1pn

精品文档

精品文档

xppnxxppppxpyyppyyppppxpypi1

由此即得

xyii1xpypp，

即 xy

三、一致凸函数

pxpyp .

定义1.35 设f是非空凸集D上的函数，若存在一个常数0，使得对任意的x,yD，及任意

(0,1)。均有

f(x)(1)f(y)f(x(1)y)(1)xy，

则称f(x)在凸集D上一致凸。

由定义立即可知：一致凸严格凸凸。 一致凸函数的判别定理

定理1.36 设f(x)是非空开凸集D上连续可微函数，则f(x)在D上一致凸的充要条件是存在常数

20，使得

f(y)f(x)f(x)T(yx)yx，x,yD

证明：先证必要性。若f(x)一致凸，

则 f(x)(1)f(y)f(x(1)y)(1)xy

从而 f(x)f(x)(1)f(y)f(x(1)y)f(x)(1)xy 因此 f(y)f(x)222f(x(1)y)f(x)2xy （﹡）

1而 f(x(1)y)f(x(1)(yx)) f(x)(1)f(x)(yx)o((1)(yx)) 将上式代入（﹡）即得：

T精品文档

精品文档

f(y)f(x)f(x)T(yx)o((1)(xy))2xy 1令1，得

f(y)f(x)f(x)T(yx)yx。

再证充分性。任取x,yD，令xx(1)y，(0,1)。由D是凸集，故xD，因而有：

2f(x)f(x)f(x)T(xx)xx f(y)f(x)f(x)T(yx)yx

两式分别乘和(1)再相加，则有

22f(x)(1)f(y)f(x)[xx(1)yx]

将xx(1)y代入即得结论：

22f(x)(1)f(y)f(x(1)y)(1)xy.

定理1.37 设f(x)是开凸集D上连续可微函数，则f(x)在D上一致凸的充要条件是：存在常数

20，使得 [f(y)f(x)]T(yx)yx，x,yD

证明：参见徐成贤等著《近代优化方法》P15。

定理1.38 设f(x)在开凸集D上二阶连续可微，则f(x)在D上一致凸的充要条件是：存在常数

2m0，使得： muuT2f(x)u，xD，uRn.

证明：充分性：x,yD，有

21f(y)f(x)f(x)T(yx)(yx)T2f()(yx)

2其中x(yx)，(01)。由于D是凸集，故D。因此，

112(yx)T2f()(yx)myx。 22令1m，则 2f(y)f(x)f(x)T(yx)yx。

必要性：设f(x)在D上一致凸。任取xD，uR且u0，则有 精品文档

n2精品文档

11uT2f(x)ulim[f(xu)f(x)]Tulim2[f(xu)f(x)]Tu00221lim2uu. 0

四、凸集的分离与支撑

凸集的分离与支撑定理在研究约束最优化问题的最优性条件时具有基本的重要性，起着十分关键的作用。

定理1.39 设SR是非空闭凸集，yS，则存在唯一的点xS，它与y的距离最短。进一步，

nx与y距离最短的充要条件是：

(xx)(xy)0，xS 证明：先证定理的第一部分 存在性 任取一点xS，则集合

0TDxyxyx0,xS

为一非空有界闭集，而yx是x的连续函数，故它必在D的某一点x上取得最小值，此x即为所求。注意到xS，而yS，必有xyr0。 唯一性 假定还有xS，满足 yxyx。r 由S的凸性，则

xxS 2xx11yxyxr 222考虑 y由r是S中点到y的最小距离，故上式必取等式。因而必有

yx(yx)

再由 yxyx，得1。

， 若1，则 yxyx2yxx得 yxxS 2精品文档

精品文档

与yS矛盾。因而只能是1，即 yxyx，或xx，唯一性得证。 再证定理第二部分 若xS，都有

(xx)T(xy)0，

则 yx2yxxxyxxx2(xx)T(yx)yx

2222即x与y有极小距离。反之，若xS，都有

xyxy

由于对充分小的0，有

22x(xx)S

因此 yx(xx)2yx2xx2(xx)T(xy)

222另一方面， yx(xx)所以

2yx

22xx2(xx)T(xy)0

两边同除，并令0，即得所要的结果。 点与凸集的分离定理

定理1.40 设SR是非空闭凸集，yR，yS，则存在向量p0和实数，使得

nnpTx，xS，并且同时满足 pTy

即超平面px严格分离点y和闭凸集S。

证明：由于S是闭凸集，yS。故定理1.39知，存在唯一的一点xS，使得

T(xx)T(xy)0，xS

取 p(yx)， 则 p(xx)0， 也即 pxpx。 再取 px，

TTTT精品文档

精品文档

则xS，有 px。

又 pypypxp(yx)

TTTTT(yx)T(yx)yx故有 py 定理证毕。

T20

定理1.41 （Farkas引理）设ARmn，cR，则下面两个等式与不等式系统有且仅有一个有解。 ① Ax0 cx0

② Ayc y0

T证明：若②有解，则存在y00，使Ay0c。下证①必无解。事实上，若x满足Ax0。 TTT那么 cxy0Ax0，（由y00，Ax0）

nTT故方程组①无解。若②无解，

记 SxxAy. y0

则S是非空闭凸集，且cS，由上面凸集的分离定理，存在pR，和R，使得

nTpTc，且pTx，xS

由于0S，故 0，

又 pxpAyyAp，y0

由于y0可任意大,而为固定常数，故必有Ap0。可见向量p满足

TTTTAp0，且cTp0

因而p是①的解，定理证毕。 凸集与凸集的分离定理

n定义1.42 设SR是非空集合，pR，xS（S的边界）。若

nSHxpT(xx)0 或 SHxpT(xx)0，

则称Hxp(xx)0是S在x处的支撑超平面；若SH，则称H为S在x处的正常支撑超平面。 精品文档

T精品文档

n定理1.43 设SR是非空凸集，xS。那么，在x存在一个支撑超平面。即存在非零向量p，使得 pTxx0，xS 这里S表示S的闭包。

证明：由于xS（是S的一个边界点），故存在序列yk，每个yk均不属于S，且ykx。 由定理1.40可知，对每个yk，存在pk，且pk1，使得

TT pkykpkx，xS。

由于pk有界，故存在收敛的子列pkK，设其极限为p（显然有p1，故p为非零向量）。对此子序列pkK，当kK时，有

TTpkykpkx，xS。

对每个固定xS，在上式中令k得：

pTxpTx，xS

这便是所需结论。

推论：设SR是非空凸集，若xS，则存在非零向量p，使得：

npT(xx)0，xS。

证明：⑴若xS，由定理1.40，存在超平面分离x和S。 ⑵若xS，由上面定理1.43即得。

n定义1.44 设S1,S2R是非空凸集，若有

pTx，xS1 且 pTx，xS2，

则称超平面Hxpx分离S1和S2；若S1TS2H，则称H正常分离S1与S2；若

pTx，xS1 且 pTx，xS2，

则称H严格分离S1与S2；若

pTx，xS1 且 pTx，xS2，（其中0）

则称H强分离S1与S2。 精品文档

精品文档

由定义容易推出：强分离严格分离正常分离分离。

n定理1.45 设S1,S2R是非空凸集，若S1S2，则存在超平面分离S1与S2，即存在非零向

量pR，使得

npTx1pTx2，x1S1，x2S2

证明：设 SS1S2x1x2x1S1,x2S2 由S是凸集，及0S（否则S1TTnS2），再由前面推论，存在非零向量pR，使得：

 pxp00，xS。 注意到S1S2S，由此可得

pTx1pTx2，x1S1，x2S2。

定理1.46 设S1和S2是闭凸集，且S1有界，若S1即存在非零向量p和0，使得

infpTxxS1suppTxxS2

证明：设SS1S2，可证S是闭的。事实上，设xkS，且xkx。由S的定义知：

S2，则存在一个超平面强分离S1和S2，

xkykzk，（ykS1，zkS2）

由于S1是紧的，故存在收敛子列ykkK，使得ykyS1。 由于kK时， yky，ykzkx 因而有 zkyxzS2 由yS1，zS2，进而得

xyzS1S2S，

即xS，故S为闭集。于是，存在非零向量p和实数，使得： px，xS 且 p0。 由0，及S的定义，我们有：

TT px1px2，x1S1，x2S2。

TT精品文档

精品文档 结果得证。

§1.4. 无约束问题的最优性条件

一、极小点的概念

1．局部极小点 2．严格局部极小点 3．全局（总体）极小点 4．严格全局（总体）极小点。

注：在非线性规划中，大多数算法都致力于求最优化问题的局部极小点，这是由于一般地求全局极小点极为困难，仅当问题为凸规划时，局部极小为全局极小。

二、最优性条件

定理1.47 （一阶必要条件）若x是局部极小点，则f(x)0。

定理1.48 （二阶必要条件）若x是局部极小点，则f(x)0，f(x)0。（半正定）

2定理1.49 （二阶充分条件）x是局部极小点的充分条件是：f(x)0，且f(x)正定。

2注：使f(x)0的点x称为函数的稳定点。稳定点可以是极大点，也可是极小点，也可两者均不是，此时称为鞍点。

定理1.50 若f(x):RR是连续可微的凸函数，则x是总体极小点的充要条件是f(x)0。

n证明：必要性由定理1.47，充分性则由f(x)f(x)f(x)(xx)直接可得。

§1.5. 最优化算法的结构

一、算法结构

最优化算法通常采用迭代形式，由算法产生一个有限或无限点列。一般地，需要证明迭代点列

Txk的聚点（子序列的极限点）为一局部极小点。算法的基本迭代格式为：

xk1xkkdk

它包含两个要素：步长因子k与搜索方向dk。在最优化算法中，dk通常是函数f在xk处的下降方

精品文档

精品文档 向，即dk满足：

Tdkf(xk)0，或 f(xkkdk)f(xk)。

基本结构

给定初始点x0； (1) 确定搜索方向dk；

(2) 确定步长因子k，使目标函数值有某种程度的下降；

(3) 令xk1xkkdk，若xk1满足某种终止条件，则迭代停止，得到近似最优解xk1；否则重复

以上步骤。

二、算法的收敛速度

定义1.51 假设算法产生的点列xk收敛于最优解x。 若存在实数0及一个与迭代次数k无

关的常数q0，使得

limkxk1xxkxq

则称算法产生的迭代点列xk具有阶收敛速度。特别地，

(1) 当1，q0时，称为线性收敛；

(2) 当12，q0或1，q0时，称超线性收敛；

(3) 当2时，称二阶收敛。

注：若一个算法应用于正定二次函数时，具有有限终止性质，则称该算法二次收敛。二次收敛与二阶收敛是完全不同的概念，不存在孰强孰弱的简单关系。但大量数值计算结果表明：具有二次收敛精品文档

精品文档

性质的算法，实际计算性能一般都较好，因而二次收敛也常作为一个好算法的标志。

三、关于常用算法的终止条件

定理1.52 若序列xk超线性收敛到x，那么



lim证明：略

xk1xkxkxk1.

此定理的意义在于：当算法具有超线性收敛性质时，可用xk1xk替代xkx作为算法停止准则。事实上，在实际应用中，即使不知道算法是否超线性收敛，也常用它作为停止准则。

常用的算法终止准则有： (1) xk1xk； (2) f(xk1)f(xk)； (3) f(xk)。

精品文档