最优化理论与算法（第一章）

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

第一章 引论

§1.1 引言

一、历史与现状

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

minf(x) （1.1）

x?Rn2、约束最优化问题

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）

nx1??i?1xi （l1范数） （1.4）

n12x2?(?xi)2 （l2范数） （1.5）

i?1 1

n1pxpp?(?xi) （lp范数） （1.6） i?11xA?(xAx)2 （A正定） （椭球范数） （1.7）

T事实上1－范数、2－范数与?2．矩阵范数

?范数分别是 p－范数当 p＝1、2和p??时情形。

定义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?0Axx （这里x是某一向量范数） （1.8）

可证这样定义的范数是与向量范数?相协调的，通常称之为由向量范数?诱导的方阵范数。特别地，对方阵A?(aij)n?n，有：

nA1?max?aij（列和的最大者） （1.9）

ji?1nA??max?aij（行和的最大者） （1.10）

ij?11A2?(?ATA)2（?ATT表示AA的特征值的最大者） (1.11) A称为谱范数（注：方阵A的特征值的模的最大者称为A的谱半径，记为?(A)）。

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

2

A?1?minx?01Axx ，I?1（I为单位阵）

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

nn12ij2T1AF?(?i?1?aj?1)?[tr(AA)]2 (1.12)

及加权Frobenius范数和加权l2范数:

AAM,F?MAM?MAMF (1.13)

M,22 (1.14)

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

定义1.2 设??与??是Rn上的两个范数，若存在?1,?2?0，使得

?1x??x???2x?， ?x?Rn (1.15)

则称范数??与??是等价的。 容易证明：

xx2?x?x1??nxnx2 (1.16) (1.17)

?2?xx??x?x1?nx? (1.18)

?2?x1 (1.19)

A?nx2?x??1x2 (1.20)

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

① Cauchy-Schwarz不等式

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

3

② 设A是正定矩阵，则

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

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

xy?xTTTAy?1A?1（仅当x与A?1y线性相关时，等式成立） (1.23)

Ay?1xy?xAAy?xAA?xAyA?1 (1.24)

其中的不等号由②可得。

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

1p?1q?1，则?x,y?R，有

? xy?xpp?yqq， (1.25)

当且仅当xp?yq 时，等式成立。其证明由算术－几何不等式直接给出，事实上

11qqxy?(x)(y)?ppxpp?yqq（算术－几何不等式）

⑤ H?lder不等式

n1xy?xTpyq?(?xii?1pn1)(p?i?1yi)q (1.26)

q其中p与q都是大于1的实数，且满足

1p?1q?1，其证明利用Young不等式可得。

⑥ Minkowski不等式

x?yp??xp?yp，（p?1） (1.27)

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

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

定理1.3 (Von-Neumann引理) 设E?Rn?n，I?Rn?n是单位阵，?是满足I?1的相容矩阵范数。如果E?1，则(I?E)非奇异，且

4

?(I?E)?1??K?0kE， (I?E)?1?11?E

若A非奇异，A?1(A?B)?1,则B非奇异，且

?B?1??(I?Ak?0?1B)Ak?1， B?1?A?1?1.

1?A(A?B)证明：因为E?1，故 Sk?I?E?E2???Ek 定义了一个Cauchy序列，因而收敛。由 Sk(I?E)?I?Ek?1 可得 limSk(I?E)?lim(I?Ek??k???k?1)?I

故有 ?Ek?limSk?(I?E)?1

k?0k???进一步有 (I?E)?1??k?0Ek?11?E。

再令 E?I?A?1B，

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

?(I?E)?1?(AB)?1?1??(I?Ak?0?1?1B)

k?所以有 B?1??(I?Ak?0??1B)Ak

A?1?1进一步有 B?1??k?0I?AB?1k?A?1??k?0A(A?B)?1kA?1?1?A(A?B)。

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

上述定理还可以写成下面形式：

定理1.4 设A,B?Rn?n，A可逆，A?1??。若A?B??，且???1，则B可逆，且

?1B??1???。

证明：只需注意到A?1(B?A)?A?1B?A????1，再由上述Von-Neumann引理即得。

5

2. 广义逆

定义1.5 设A?Cm?n，若A??Cn?m满足：

AAA?A,AAA?A,(AA)?????*?AA,(AA)??*?AA (1.28)

?则称A?是A的广义逆。其中A*是A的共轭转置。 广义逆的求法

① 设A?Cm?n，秩(A)?r，若A直交分解为A?Q*RP，其中Q，P分别为m?m,n?n酉矩阵，

m?nR?C，R???R11?00??，其中R11是r?r非奇异的上三角矩阵。则A的广义逆为： 0???1?R11?*?A?PRQ 其中 R???00?? (1.29) 0????00?m?n，而??C0?② 若A的奇异值分解为A?UDV*，其中U，V均为酉矩阵，D????diag(?1,?,?r),?i?0是A的非零奇异值，则A的广义逆为：

?1????*A?VDU，其中D???0?0?? (1.30) 0?③ 若A的最大秩分解为A?BC，则A的广义逆为：

A?C(CC)(BB)B. (1.31)

?**?1*?1*

三、 矩阵的Rayleigh商

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

uAuuu**nR?(u)? （u?0） (1.32)

为矩阵A的Rayleigh商

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

*2) 极性： ?1?maxuAu?maxu2uAuuu**?1u?0

6

?n?minuAu?minu2*uAuuu**

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

(A?R?(u)I)u?(A??I)u，???R。

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

??1?*2）由A是Hermite矩阵，故存在酉矩阵T，使TAT?????????? ??n???又令 u?Ty，且u***2?1，故y*2?1

22则 uAu?yTATy?y?y??1y1????nyn

当取y?(1,0,?,0)时达到最大值?1，当取y?(0,0,?0,1)时，达到最小值?n。

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的矩阵，称为秩一校正。下面讨论如何求秩一校正的逆，行列式，特征值及矩阵分解。

u,v?R是任意向量。定理1.8 设A?Rm?n是非奇异的，若1?vAu?0，则A的秩一校正A?uvnTTT非奇异，其逆矩阵可以表示为

7

(A?uv)T?1?A?1?AuvAT?1T?11?vAu?1 (1.33)

证明：可直接验证。

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

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

(A?UV)*?1?A?1?AU(I?VAU)VA?1*?1?1*?1 (1.34)

下面介绍关于秩一校正的行列式定理 定理1.10 1）det(I?uvT)?1?vTu

2）det(I?u1u2T?u3u4T)?(1?u1Tu2)(1?u3Tu4)?(u1Tu4)(u2Tu3)

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

(I?uv)w??w

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

T 进一步，平行于u的特征向量只有一个（线性无关），而垂直于v的线性无关的向量有n?11?vu。

个，它们均为I?uvT属于特征值1的特征向量，即特征值1是(n?1)重根， 而1?vTu是单根。

Tn?1TT故有 det(I?uv)??1????n?1(1?vu)?1?vu。

TTTT?1T?2） 对I?u1u2?u3u4?(I?u1u2)??I?(I?u1u2)u3u4?

使用上面结果，故有：

TTTTT?1det(I?u1u2?u3u4)?(I?u1u2)?1?u(I?uu)u3?412??

??T??u1u2T(1?uu2)?1?u4(I?)u3? T1?uu?12?T1TTTT(1?u1u2)(1?u3u4)?(u1u4)(u2u3)。

关于秩一校正矩阵的特征值定理。

定理1.11设A是对称矩阵，其特征值为?1??2????n，又设A?A??uu，其特征值为

T?1??2????n，那么

1） 若??0，则?1??1??2??2???n??n

8

2） 若??0，则?1??1??2??2???n??n

五、函数与微分

1.多元函数的梯度与Hessian矩阵 梯度 ?f(x)?(?f?x12,?,?f?xn) (1.35)

T????Hessian矩阵 ?2f(x)???????f?x12?????f?xnx122?f???x1xn???? (1.36) 2?f??2?xn??方向导数：（设d为一方向向量，即长度为1的单位向量，显然与范数的取法有关）

?f?x?lim???0f(x??d)?f(x)???f(x)d (1.37)

T注：对欧氏范数（2－范数）而言，梯度方向是函数上升最快的方向，而负梯度方向则是函数下降最快的方向。正因为这个原因，使得梯度在最优化理论与算法中占有特殊重要的地位。

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

f(x?d)?f(x)??10?f(x?td)ddt?f(x)??f(?)d （1.38）

TT其中??(x,x?d)。上式也可改写为：

f(y)?f(x)??f(x?t(y?x))(y?x) t?(0,1)

T或 f(y)?f(x)??f(x)(y?x)?o(y?x)

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

f(x?d)?f(x)??f(x)d??f(x)??f(x)d?TTT12!12!d?f(?)d d?f(x)d?o(dT22T2)

2.向量函数的微分

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

微。F(x)在x处的导数记为：

9

????F?(x)???????f1?x1?????fm?x1?f1???xn????J(x) （1.39） ??fm???xn??称之为F(x)在x处的Jacobi矩阵，而称?F(x)?(F?(x))T为向量函数F(x)在x处的梯度。

若F:Rn?Rm在开凸集D上连续可微，则对任何x,x?d?D，有：

F(x?d)?F(x)??10F?(x?td)ddt

定义1.12 G:Rn?Rm?n在x?D?Rn处称为Lipschitz连续的，若?v?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，有

F(x?d)?F(x)?F?(x)d??2d2.

证明： F(x?d)?F(x)?F?(x)d???10F(x??d)dd??F?(x)d

'??F?(x??d)?F?(x)?dd?

01从而 F(x?d)? ? ?F(x?)?F(x)?d??01?F?(?x?)d?(?F?)x dd??1010(F?(x??d)?F?(x))dd???10F?(x??d)?F?(x)dd?

12??ddd???d2?10?d???d2.

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

命题：对可积向量函数f(t)?(f1(t),f2(t),?,fn(t))，有证明：对于l1范数上述命题是成立的，这是因为：

T?baf(t)dt??baf(t)dt.

10

???baf(t)dt1??baf1(t)dt??baf2(t)dt???ba?bafn(t)dt

?babaf1(t)dt??baf2(t)dt????fn(t)dt??ba(f1(t)?f2(t)???fn(t))dt

?f(t)dt

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

ba2n ?baf(t)dtbn??(?i?1banfi(t)dt)?2???i?1nabbafi(t)fi(s)dtdsn???(?ai?1fi(t)fi(s))dtds?2ban??abba?i?1bafi(t)n2?i?12fi(s)dtds2ba22

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

定理1.14 设f:Rn?R在开凸集D?Rn上二次连续可微，?2f(x)在x的邻域D上Lipschitz连续。则对于任何x?d?D有：

1T2???Tf(x?d)??f(x)??f(x)d?d?f(x)d??d26??3

T证明： f(x?d)?fx(?)?fx(d)?121d?fxd( )t0T2???01t0d?f(x??d)dd?dt?T2T2T2??0d?f(x)dd?dt

T2????01t0t0d?f(x??d)d?d?f(x)dd?dt

d2??01??dd?dt??dnm3??01t0?d?dt?16?d3

定理1.15 设F:R?R在开凸集D?Rn上连续可微，则对任何x,u,v?D，有

??F(u)?F(v)?F?(x)(u?v)?supF?(v?t(u?v))?F?(x)u?v，

???0?t?1?若进一步F?在D中Lipschitz连续，则有：

F(u)?F(v)?F?(x)(u?v)??u?x?v?x2u?v.

11

证明：F(u)?F(v)?F?(x)(u?v)????F?(v?t(u?v))?F?(x)?(u?v)dt01

?10F?(v?t(u?v))?F?(x)u?vdt （由此式即可得第一部分结论）

1???0v?t(u?v)?xu?vdt??10?10(1?t)(v?x)?t(u?x)u?vdt ????0tdt??1??u?v?v?x???(1?t)dt?u?xu?x?v?x2?1u?v.

定理1.16设F,F?满足上面定理条件，假定矩阵?F?(x)?存在（这蕴含着F?(x)是方阵，即。则存在??0,????0，使得?u,v?D，当maxF(x):R?R）

?u?v?F(u)?F(v)???u vnn?u?x,v?x?? ?时，有：

证明：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)F?(x)(u?v)?F?(x)?1?1F?(x)(u?v)）

故有 F(u)?F(v)??F(x)?(u?v)F?(u)?)?F(vF?(x) (u v)??1??(u?x?v?x)?u?v ???12F?(x)??????1????u?v??u?v ???1?F(x)????因此，若取??1F?(x)?1?，且令??1F?(x)?1??? (?0)，则得左边不等式结论。

由1?F?(x)?1F?(x)?F?(x)?1F?(x)，可得

1?1F?(x)?F?(x)，从而有????0。

六、差商（偏差商）

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

12

商）

fi(x?hej)?fix() aij?

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

F(x?hej)?F(x)hA?j?

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

定理1.17 设F:Rn?Rm在开凸集D上连续可微，F?(x)在D中Lipschitz连续，则 A?j?J(x)?j?若采用的范数是l1范数，则有：A?J(x)?21h ??2h

证明： 将定理1.13中的d取为hej，则有

F(x?hej)?F(x)?J(x)hej?F(x?hej)?F(x)?J(x)?jh??2hej2??2h

2两边同除h，则有

A?j?J(x)?j??2h.

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

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

ai?f(x?hei)?f(x?hei)2h2

则 ai??f(x)i?如采用l?范数，则a??f(x)?证明：由定理1.14有：

?6?62h

T2h ，其中a?(a1,?,an).

T f(x?d)?fx(?)?fx(d)?12T2d?fxd(?)?6d3

令d?hei，则有

13

f(x?hei)?f(x)?h?f(x)i?12h?f(x)ii?22?63h

再令d??hei，又有

1222f(x?hei)?f(x)?h?f(x)i?h?f(x)ii??63h

令上两式中左端绝对值内的部分分别为?,?，则有 ????f(x?hie)?f(x?ih)e?2由此即得：

f(x?hei)?f(x?hei)2hh?(fi)x?????3?

3h??f(x)i?ai??f(x)i??62h

由l?范数的定义，有

a??f(x)??6?h.

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

ej?1，(i?1,?,n)，假定x,x?hei,x?hej,x?hei?hej?D(i,j?1,?,n)。定义：

aij?f(x?hei?hej)?f(x?hei)?f(x?hej)?f(x)h22

则有： aij??f(x)ij?53?h

若采用矩阵范数是l1,l?或F-范数，则 A??f(x)?253?hn（这里A?(aij)是Hessian矩阵的离散形式）。

T证明：令??f(x?hei?hej)?f(x)?(hei?hej)?f(x)?(?)he(i ??f(x?hei)?fxT12(hei?hej)?f(x)(hei?hej)

)T21T2?)fx(?)hei(?)fxhe(i )(212(hej)?f(x)(hej)

T2??f(x?hej)?f(x)?(hej)?f(x)?T经简单计算有： 又由定理1.14有， ???????h2?(aij??2f(x)ij )

?6hei?hej3?86?h

3 14

?? ???6heihej3??16163?h

?633?h

进而有 aij??2f(x)ij??????h2?1h2(?????)?106?h?53?h

再由矩阵l1,l?及F-范数的定义立即可得：

A??f(x)?253?hn

§1.3 凸集与凸函数

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

定义1.20 设S?Rn，若?x1,x2?S，都有

?x1?(1??)x2?S ????0,1? 则称S是凸集。

定理1.21 Rn的子集S为凸集的充分必要条件是?x1,x2,?,xm?S有

m

??i?1ixi?S

m其中?i?0 (i?1,?,m)且??i?1。

i?1凸集的例子：n维球、半空间、超平面、?xAx?b,x?0?等均为凸集。 定理1.22 若S1,S2是Rn中的凸集，则

1） S1?S2是凸集；（事实上，任意多个凸集的交仍为凸集） 2） S1?S2??x1?x2x1?S1,x2?S2?也是凸集 2．凸包 集合S的凸包的定义如下： ? Conv(S)??xx??mm??ixi,xi?S,??i?1,?i?0,m?1,2,??

i?1i?1??由定义知，集合S的凸包由S中元素所有可能的凸组合构成。还可证明：它是所有包含集合S的凸

15

本文来源：https://www.bwwdw.com/article/29kd.html