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

1最优化理论与算法（数学专业研究生）第一章引论§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）211()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）。对于由向量诱导的方阵范数，总有：3101minxAAxx，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)4②设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非奇异，且510()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引理即得。62.广义逆定义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.6A是nnHermite矩阵，nuC，则称**()uAuRuuu（0u）(1.32)为矩阵A的Rayleigh商定理1.7设A是nnHermite矩阵，则Rayleigh商具有下列性质：1)齐次性：()()RuRu（0）2)极性：2**1*10maxmaxuuuAuuAuuu72***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的矩阵，称为秩一校正。下面讨论如何求秩一校正的逆，行列式，特征值及矩阵分解。定理1.8设mnAR是非奇异的，,nuvR是任意向量。若10TvAu，则A的秩一校正TAuv非奇异，其逆矩阵可以表示为811111()1TTTAuvAAuvAvAu(1.33)证明：可直接验证。上述定理的可进一步推广为：定理1.9设A是非奇异矩阵，,UV是nm矩阵，若*1IVAU可逆，则*AUV可逆，且*111*11*1()()AUVAAUIVAUVA(1.34)下面介绍关于秩一校正的行列式定理定理1.101）det()1TTIuvvu2）123412341423det()(1)(1)()()TTTTTTIuuuuuuuuuuuu证明：1）若0u，则结论显然成立；若0u，设w是()TIuv的特征向量。则()TIuvww易见w要么与v垂直，要么与u平行。若与v垂直，则特征值为1；若与u平行，则对应特征值为1Tvu。进一步，平行于u的特征向量只有一个（线性无关），而垂直于v的线性无关的向量有1n个，它们均为TIuv属于特征值1的特征向量，即特征值1是(1)n重根，而1Tvu是单根。故有11det()1(1)1TnTTnIuvvuvu。2）对11234121234()()TTTTTIuuuuIuuIIuuuu使用上面结果，故有：11234124123det()()1()TTTTTIuuuuIuuuIuuu12124312(1)1()1TTTTuuuuuIuuu12341423(1)(1)()()TTTTuuuuuuuu。关于秩一校正矩阵的特征值定理。定理1.11设A是对称矩阵，其特征值为12n，又设TAAuu，其特征值为12n，那么1）若0，则1122nn92）若0，则1122nn五、函数与微分1.多元函数的梯度与Hessian矩阵梯度1()(,,)Tnfffxxx(1.35)Hessian矩阵2221122221()nnnffxxxfxffxxx(1.36)方向导数：（设d为一方向向量，即长度为1的单位向量，显然与范数的取法有关）0()()lim()Tffxdfxfxdx(1.37)注：对欧氏范数（2－范数）而言，梯度方向是函数上升最快的方向，而负梯度方向则是函数下降最快的方向。正因为这个原因，使得梯度在最优化理论与算法中占有特殊重要的地位。若:nfRR在开凸集D上连续可微，则有10()()()()()TTfxdfxfxtdddtfxfd（1.38）其中(,)xxd。上式也可改写为：()()(())()Tfyfxfxtyxyx(0,1)t或()()()()()Tfyfxfxyxoyx若f在D上二阶连续可微，则对于任何,xxdD，存在(,)xxd，使得21()()()()2!TTfxdfxfxddfd221()()()()2!TTfxfxddfxdod2.向量函数的微分设:nmFRR