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

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

第一章 引论

§1.1引言

一、历史与现状

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

二、最优化问题的一般形式

1、无约束最优化问题

min()nxRfx （1.1）

2、约束最优化问题

min()()0, ..()0, iifxcxiEstcxiI （1.2）

这里E和I均为指标集。

§1.2数学基础

一、范数

1.向量范数

maxixx（l范数） （1.3）

11niixx（1l范数） （1.4）

12221()niixx（2l范数） （1.5） 2 / 30 11()nppipixx（pl范数） （1.6）

12()TAxxAx（A正定） （椭球范数） （1.7）

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

2．矩阵范数

定义1.1方阵A的范数是指与A相关联并记做A的一个非负数，它具有下列性质：

①对于0A都有0A，而0A时0A；

②对于任意kR，都有kAkA；

③ABAB；

④ABAB；

若还进一步满足：

⑤ppAxAx

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

0maxxAxAx （这里x是某一向量范数） （1.8）

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

11maxnijjiAa（列和的最大者） （1.9）

1maxnijijAa（行和的最大者） （1.10）

122()TAAA（TAA表示TAA的特征值的最大者） (1.11)

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

对于由向量诱导的方阵范数，总有： 3 / 30 101minxAAxx ，1I（I为单位阵）

对于方阵范数，除了上述由向量范数诱导的范数之外，还有常用的Frobenius范数，简称F-范数：1122211()[tr()]nnTijFijAaAA (1.12)

及加权Frobenius范数和加权2l范数:

,MFFAMAM(1.13)

,22MAMAM(1.14)

其中M为对称正定矩阵。

3.范数的等价性

定义1.2 设与是nR上的两个范数，若存在12,0，使得

12xxx， nxR (1.15)

则称范数与是等价的。

容易证明：

212xxnx (1.16)

2xxnx (1.17)

1xxnx (1.18)

21xxx (1.19)

122nAxxx (1.20)

其中1是A的最大特征值，而n是A的最小特征值。由此可见，nR中的常用向量范数均等价，事实上还可证明：nR中所有向量范数均等价。

4.关于范数的几个重要不等式。

①Cauchy-Schwarz不等式

Txyxy（当且仅当x和y线性相关时，等式成立） (1.21) ②设A是正定矩阵，则

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

由(,)TxyxAy是一种内积，以及一般内积的Cauchy-Schwarz不等式即得。

③设A是nn正定矩阵，则

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

111TTAAAAxyxAAyxAyxy(1.24)

其中的不等号由②可得。

④Young不等式：假定p与q都是大于1的实数，且满足111pq，则,xyR，有

pqxyxypq， (1.25)

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

11()()pqpqpqxyxyxypq（算术－几何不等式）

⑤Hölder不等式

1111()()pqnnpqTiipqiixyxyxy (1.26)

其中p与q都是大于1的实数，且满足111pq，其证明利用Young不等式可得。

⑥Minkowski不等式

pppxyxy，（1p）(1.27)

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

二、矩阵求逆与广义逆

1.Von-Neumann引理

定理1.3(Von-Neumann引理)设nnER，nnIR是单位阵，是满足1I的相容矩阵范数。如果1E，则()IE非奇异，且 10()kKIEE， 11()1IEE

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

1110()kkBIABA， 1111()ABAAB.

证明：因为1E，故2kkSIEEE定义了一个Cauchy序列，因而收敛。由

1()kkSIEIE

可得1lim()lim()kkkkSIEIEI

故有 10lim()kkkkESIE

进一步有101()1kkIEEE。

再令1EIAB，

知11()1EIABAAB

由上面结论可得，

11110()()()kkIEABIAB

所以有 1110()kkBIABA

进一步有 111111100()1()kkkkABIABAAABAAAB。

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

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

定理1.4 设A,nnBR，A可逆，1A。若AB，且1，则B可逆，且

11B。

证明：只需注意到11()1ABAABA，再由上述Von-Neumann引理即得。 2.广义逆

定义1.5 设mnAC，若nmAC满足：

**,(),(),AAAAAAAAAAAAAAAA (1.28)

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

广义逆的求法

①设mnAC，秩()Ar，若A直交分解为*AQRP，其中Q，P分别为,mmnn酉矩阵，mnRC，11000RR，其中11R是rr非奇异的上三角矩阵。则A的广义逆为：

*APRQ其中 111000RR (1.29)

②若A的奇异值分解为*AUDV，其中U，V均为酉矩阵，000mnDC，而1(,,),0ridiag是A的非零奇异值，则A的广义逆为：

*AVDU，其中1000D (1.30)

③若A的最大秩分解为ABC，则A的广义逆为：

**1*1*()()ACCCBBB. (1.31)

三、 矩阵的Rayleigh商

定义1.6 A是nnHermite矩阵，nuC，则称

**()uAuRuuu（0u） (1.32)

为矩阵A的Rayleigh商

定理1.7 设A是nnHermite矩阵，则Rayleigh商具有下列性质：

1)齐次性：()()RuRu （0）

2)极性：2**1*10maxmaxuuuAuuAuuu 7 / 30 2***10minminnuuuAuuAuuu

这里1，n分别对应于矩阵A的最大与最小特征值。这表明Rayleigh商具有有界性：

1()nRu

3）极小残量性质：对任意nuC，

(())()ARuIuAIu，R。

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

2）由A是Hermite矩阵，故存在酉矩阵T，使1*nTAT

又令uTy，且21u，故21y

则22****11nnuAuyTATyyyyy

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

3）令()()suAuRuu，(0)u，则()()AusuRuu，可直接验证

(),()0suRuu，

由于**((),)((),)()0suuAuRuuuuAuRuuu

注意到()Ruu是与u共线的，故()su与()Ruu正交。即()Ruu与()su是Au的正交分解。因而()Ruu是Au在Lu上的直交投影，因而具有极小残量性质。

四、矩阵的秩一校正

当矩阵A变到TAuv时，即在A上加了一个秩为1的矩阵，称为秩一校正。下面讨论如何求秩一校正的逆，行列式，特征值及矩阵分解。