《最优化理论与算法(第一章).pdf》由会员分享，可在线阅读，更多相关《最优化理论与算法(第一章).pdf（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选文档最优化理论与算法（数学专业研究生）最优化理论与算法（数学专业研究生）第一章第一章引论引论前言前言一、历史与现状一、历史与现状最优化理论最早可追忆到古老的极值问题，最优化理论最早可追忆到古老的极值问题，但成为一门独立的学科则是在但成为一门独立的学科则是在 20 20 世纪四十年月末至世纪四十年月末至五十年月初。其奠定性工作包含五十年月初。其奠定性工作包含FritzJohnFritzJohn 最优性条件（最优性条件（1948 1948），），Kuhn-TuckerKuhn-Tucker 最优性条件（最优性条件（19511951），），和和 KarushKarush 最优性条件最优性条件(1
2、939)(1939)。近几十年来最优化理论与算法发展十分快速，应用也愈来愈宽泛。现。近几十年来最优化理论与算法发展十分快速，应用也愈来愈宽泛。现在已形成一个相当宏大的研究领域。对于最优化理论与方法，狭义的主要指非线性规划的有关内容，而广义的在已形成一个相当宏大的研究领域。对于最优化理论与方法，狭义的主要指非线性规划的有关内容，而广义的则涵盖：线性规划、非线性规划、动向规划、整数规划、几何规划、多目标规划、随机规则涵盖：线性规划、非线性规划、动向规划、整数规划、几何规划、多目标规划、随机规划甚至还包含变分、最优控制等动向优化内容。本课程所波及的内容属于前者。二、最优化问题的一般形式划甚至还包含变
3、分、最优控制等动向优化内容。本课程所波及的内容属于前者。二、最优化问题的一般形式1 1、无拘束最优化问题、无拘束最优化问题minf(x)minf(x)xRxR2 2、拘束最优化问题、拘束最优化问题minf(x)minf(x)c ci i(x)0,(x)0,st.st.n n（）（）i iE E（）（）c ci i(x)0,(x)0,i iI I这里这里E和和I均为指标集。均为指标集。xx一、范数一、范数数学基础数学基础（）（）maxxi（l范数）范数）n向量范数向量范数xi（l1范数）范数）i1（）（）11nx2 2)（l2范数）范数）(xi2（）（）i11/301 1精选文档n1xp(i 1
4、xip)p（lp范数）范数）1（）（）xA(xTAx)2（A正定）（椭球范数）正定）（椭球范数）范数分别是范数分别是p范数当范数当（）（）事实上事实上 1范数、范数、2范数与范数与2矩阵范数矩阵范数p1、2 和和p时情况。时情况。定义方阵定义方阵A的范数是指与的范数是指与A有关系并记做有关系并记做对于对于A对于随意对于随意A的一个非负数，它拥有以下性质：的一个非负数，它拥有以下性质：0；0都有都有A0，而，而A0时时AkR，都有，都有kAkA；ABABAB；AA若还进一步知足：若还进一步知足：AxpxB；p则称之为与向量范数则称之为与向量范数p相协调（相容）的方阵范数。若令相协调（相容）的方阵
5、范数。若令Amaxx0（）（）Axx（这里（这里x是某一直量范数）是某一直量范数）可证这样定义的范数是与向量范数可证这样定义的范数是与向量范数对方阵对方阵A(aij)nn，有：，有：nA1maxjaij相协调的，往常称之为由向量范数相协调的，往常称之为由向量范数引诱的方阵范数。特别地，引诱的方阵范数。特别地，（列和的最大者）（列和的最大者）（）（）（行和的最大者）（行和的最大者）表示表示ATA的特点值的最大者）的特点值的最大者）（）（）i 1nT(1.11)AmaxiaAAijj11(称为谱范数（注：方阵称为谱范数（注：方阵A2ATA)2（A的特点值的模的最大者称为的特点值的模的最大者称为A的
6、谱半径，记为的谱半径，记为(A)）。）。对于由向量引诱的方阵范数，总有：对于由向量引诱的方阵范数，总有：2/302 2精选文档A1，I1minAxx0 x1（I为单位阵）为单位阵）对于方阵范数，除了上述由向量范数引诱的范数以外，还有常用的对于方阵范数，除了上述由向量范数引诱的范数以外，还有常用的Frobenius 范数，简称范数，简称 F-范数：范数：nn11AF(aij2)2tr(ATA)2(1.12)i1j1及加权及加权 Frobenius 范数和加权范数和加权l2范数范数:AMAM,F(1.13)AM,2MAM(1.14)此中此中M为对称正定矩阵。为对称正定矩阵。范数的等价性范数的等价性
7、定义定义设设与与是是Rn上的两个范数，若存在上的两个范数，若存在1,20，使得，使得1xx2x，xRn(1.15)则称范数则称范数是等价的。是等价的。简单证明：简单证明：与与x2x1nx2(1.16)xx2nx(1.17)xx1nx(1.18)xx2x1(1.19)nx2xA1x2(1.20)此中此中1是是A的最大特点值，而的最大特点值，而n是是A的最小特点值。因而可知的最小特点值。因而可知，Rn中的常用向量范数均等价，事中的常用向量范数均等价，事实上还可证明：实上还可证明：Rn中全部向量范数均等价中全部向量范数均等价。对于范数的几个重要不等式。对于范数的几个重要不等式。Cauchy-Schw
8、arz不等式不等式xTyxy（当且仅当（当且仅当x和和y线性有关时，等式建立）线性有关时，等式建立）(1.21)3/303 3精选文档设设A是正定矩阵，则是正定矩阵，则xTAyxAyA（当且仅当（当且仅当x与与y线性有关时，等式建立）线性有关时，等式建立）(1.22)由由xyxAyT(,)是一种内积，以及一般内积的是一种内积，以及一般内积的Cauchy-Schwarz不等式即得。不等式即得。设设A是是nn正定矩阵，则正定矩阵，则xTyxAyA1（仅当（仅当x与与A1y线性有关时，等式建立）线性有关时，等式建立）(1.23)xTyxTAA1yxAA1yAxAyA1(1.24)此中的不等号由可得。
9、此中的不等号由可得。Young 不等式：假定不等式：假定p与与q都是大于都是大于111 的实数，且知足的实数，且知足1，则，则x,yR，有，有pqxpyqxy，(1.25)pq当且仅当当且仅当xpyq时，等式建立。其证明由算术几何不等式直接给出，事实上时，等式建立。其证明由算术几何不等式直接给出，事实上11yqqxy(xp)p(y)qxp（算术几何不等式）（算术几何不等式）pqH?lder 不等式不等式1n1nxTyxy)p(yq)q(1.26)pq(ixpii1i1此中此中p与与q都是大于都是大于111 的实数，且知足的实数，且知足1，其证明利用，其证明利用Young不等式可得。不等式可得。
10、pqMinkowski不等式不等式xyp）(1.27)xpyp，（，（p1后边将利用凸函数理论予以证明。后边将利用凸函数理论予以证明。二、矩阵求逆与广义逆二、矩阵求逆与广义逆Von-Neumann引理引理定理定理(Von-Neumann引理引理)设设E Rnn，IRnn是单位阵，是单位阵，是知足是知足I1的相容矩阵范数。的相容矩阵范数。假如假如E1，则，则(IE)非奇怪，且非奇怪，且4/304 4精选文档(IE)1K0Ek，(IE)111E若若A非奇怪，非奇怪，A1(AB)B11,则则B非奇怪，且非奇怪，且k(IA B)k01A，B11A11A1(AB).证明：因为证明：因为E1，故，故SkI
11、EE21Ek定义了一个定义了一个 Cauchy序列，因此收敛。由序列，因此收敛。由Sk(IE)I Ek可得可得limSk(IE)lim(IkEk1)Ik故有故有k0EklimSkk(IE)1进一步有进一步有(IE)1Ek0k1。1E再令再令E知知EIA1B，IA1BA1(AB)1由上边结论可得，由上边结论可得，(IE)1(A1B)1k0(IA1B)k所以有所以有B1(IA1B)kA1k0进一步有进一步有B1k 0IA B1kA1A(Ak01B)kA1A1。1A1(AB)注：这个定理表示，若注：这个定理表示，若B充足靠近一个可逆矩阵充足靠近一个可逆矩阵上述定理还能够写成下边形式：上述定理还能够写
12、成下边形式：A，则，则B也可逆，且逆矩阵可由也可逆，且逆矩阵可由A的逆矩阵来表示。的逆矩阵来表示。定理定理 设设A,BRnn，A可逆，可逆，A1。若。若A。B，且，且1，则，则B可逆，且可逆，且B11证明：只要注意到证明：只要注意到A1(BA)A1BA1，再由上述，再由上述 Von-Neumann引理即得。引理即得。5/305 5精选文档广义逆广义逆设设A定义定义Cmn，若，若ACnm知足：知足：A,(AA)*AAAA,AAAAA,(AA)*AA(1.28)则称则称A是是A的广义逆。此中的广义逆。此中广义逆的求法广义逆的求法设设AA*是是A的共轭转置。的共轭转置。Cmn，秩，秩(A)r，若，若
13、A直交分解为直交分解为AQ*RP，此中，此中Q，P分别为分别为mm,nn酉矩阵，酉矩阵，RRCmn，R11000，此中，此中R11是是rr非奇怪的上三角矩阵。则非奇怪的上三角矩阵。则A的广义逆为：的广义逆为：AP*RQ此中此中RR1110UDV*00(1.29)若若A的奇怪值分解为的奇怪值分解为A，此中，此中U，V均为酉矩阵，均为酉矩阵，D0Cmn，而，而0(1.30)0diag(1,r),i0是是A的非零奇怪值，则的非零奇怪值，则1A的广义逆为：的广义逆为：AVDU*，此中，此中D000若若A的最大秩分解为的最大秩分解为ABC，则，则A的广义逆为：的广义逆为：AC*(CC*)1(B*B)1B
14、*.(1.31)三、矩阵的三、矩阵的 Rayleigh 商商定义定义A是是nnHermite 矩阵，矩阵，uCn，则称，则称0）u*AuR(u)（u(1.32)u*u为矩阵为矩阵A的的 Rayleigh 商商nHermit设设A是是ne定理定理矩阵，则矩阵，则 Rayleigh 商拥有以下性质：商拥有以下性质：1)齐次性：齐次性：R(u)R(u)（u00）2)极性：极性：*1maxuAumaxu21u*Au*uu6/306 6精选文档nminuAuminu21u0*u*Au*u u，这里这里nR(u)11n分别对应于矩阵分别对应于矩阵A的最大与最小特点值。这表示的最大与最小特点值。这表示Ray
15、leigh 商拥有有界商拥有有界性：性：(AR(u)I)uA13）极小残量性质）极小残量性质：对随意：对随意u(AI)u，证明：证明：1）由定义直接可得。）由定义直接可得。2）由）由nR。Cn，是是 Hermite 矩阵，故存在酉矩阵矩阵，故存在酉矩阵T，使，使T*AT又令又令u则则u*Au当取当取yTy，且，且u21，故，故y2y*T*ATyy*yy12112nny(1,0,0)时达到最大值时达到最大值3）令）令s(u)1，当取，当取y(0,0,0,1)时，达到最小值时，达到最小值n。AuR(u)u，(u0，0)，则，则Aus(u)R(u)u，可直接考证，可直接考证s(u),R(u)uR(u
16、)uR(u)uAu注意到注意到是是因为因为(s(u),u)(AuR(u)u,u)u*AuR(u)u*u0是与是与u共线的，故共线的，故s(u)与与R(u)u正交。即正交。即R(u)u与与s(u)是是Au的正交分解。因此的正交分解。因此在在Lu上的直交投影，因此拥有极小残量性质。上的直交投影，因此拥有极小残量性质。四、矩阵的秩一校订四、矩阵的秩一校订当矩阵当矩阵A变到变到AuvT时，即在时，即在A上加了一个秩为上加了一个秩为秩一校订的逆，队列式，特点值及矩阵分解。秩一校订的逆，队列式，特点值及矩阵分解。1 的矩阵，称为秩一校订。下边议论怎样求的矩阵，称为秩一校订。下边议论怎样求定理设定理设ARm
17、n是非奇怪的，是非奇怪的，u,v非奇怪，其逆矩阵能够表示为非奇怪，其逆矩阵能够表示为Rn是随意愿量。若是随意愿量。若1vTAu0，则，则A的秩一校订的秩一校订AuvT7/307 7精选文档(Auv)T 1A1A1uvTA11vTA1u(1.33)证明：可直接考证。证明：可直接考证。上述定理的可进一步推行为：上述定理的可进一步推行为：m矩阵，若矩阵，若IV*A1U可逆，则可逆，则AUV*可逆，且可逆，且V*A1U)1V*A1(1.34)定理设定理设A是非奇怪矩阵，是非奇怪矩阵，U,V是是n(AUV*)1A1A1U(I下边介绍对于秩一校订的队列式定理下边介绍对于秩一校订的队列式定理定理定理 1）d
18、et(T)1TIuvu1u2）det(I2vuu3u4TT)(1u1Tu2)(1u3Tu4)u0，设，设w是是(I(u1Tu4)(u2Tu3)uvT)的特点向量。则的特点向量。则证明：证明：1）若）若u0，则结论明显建立；若，则结论明显建立；若(IuvT)ww1易见易见w要么与要么与v垂直，要么与垂直，要么与u平行。若与平行。若与v垂直，则特点值为垂直，则特点值为1；若与；若与u平行，则对应特点值为平行，则对应特点值为vTu。进一步，平行于。进一步，平行于u的特点向量只有一个（线性没关），而垂直于的特点向量只有一个（线性没关），而垂直于v的线性没关的向量有的线性没关的向量有uvT属于特点值属于
19、特点值1 的特点向量，即特点值的特点向量，即特点值1 是是(nn个，它们均为个，它们均为I故有故有1)重根，重根，而而1vTu是单根。是单根。1det(I2）对）对Iu1u2TuvT)1n1TTn1(1v u)1v u。使用上边结果，故有：使用上边结果，故有：det(I u1u2Tu3u4T)(Iu3u4T(Iu1u2T)I(Iu1u2T)1u3u4Tu1Tu2)1 u4T(Iu1u2T)1u3T4(1 uTu)1u12(Iu1u2T)u3T1u1u2(1 u1Tu2)(1u3Tu4)(u1Tu4)(u2Tu3)。对于秩一校订矩阵的特点值定理。对于秩一校订矩阵的特点值定理。定理定理设设A是对称
20、矩阵，其特点值为是对称矩阵，其特点值为n，那么，那么12n，又设，又设AAuuT，其特点值为，其特点值为121）若）若0，则，则1122nn8/308 8精选文档2）若）若0，则，则1122nn五、函数与微分五、函数与微分1.多元函数的梯度与多元函数的梯度与Hessian 矩阵矩阵梯度梯度f(x)(1.35)(,f)Tx1fxn2f2fx122x1xn2Hessian 矩阵矩阵f(x)2(1.36)ffxnx1xn2方导游数：（设方导游数：（设d为一方向向量，即长度为为一方向向量，即长度为1 的单位向量，明显与范数的取法有关）的单位向量，明显与范数的取法有关）注：对欧氏范数（注：对欧氏范数（2
21、范数）而言，梯度方向是函数上涨最快的方向，而负梯度方向则是函数降落最范数）而言，梯度方向是函数上涨最快的方向，而负梯度方向则是函数降落最快的方向。正因为这个原由，使得梯度在最优化理论与算法中据有特别重要的地位。快的方向。正因为这个原由，使得梯度在最优化理论与算法中据有特别重要的地位。flim0 xf(xd)f(x)f(x)Td(1.37)T若若f:RnR在开凸集在开凸集D上连续可微，则有上连续可微，则有f(xd)f(x)10Ttd)ddtf(xf(x)f()d（）（）此中此中(x,xd)。上式也可改写为：。上式也可改写为：f(y)f(x)()fx()f(xt(yx)T(yx)t)(0,1)或或
22、()T()fyfxyxoyx若若f在在D上二阶连续可微，则对于任何上二阶连续可微，则对于任何x,x dD，存在，存在f(x)Td(x,x d)，使得，使得f(xd)f(x)f(x)1dT2!12f()d2f(x)dTdT2f(x)do(d)向量函数的微分向量函数的微分2!设设F:RnRm是一个向量函数，若其每个重量是一个向量函数，若其每个重量微。微。F(x)在在x处的导数记为：处的导数记为：fi(i 1,m)都连续可微，则称都连续可微，则称F(x)连续可连续可9/309 9精选文档f1x1f1xnF(x)J(x)（）（）fmx1fmxn称之为称之为F(x)在在x处的处的 Jacobi 矩阵，而
23、称矩阵，而称()()在在T为向量函数为向量函数FxFxF(x)x处的梯度。处的梯度。若若F:RnRm在开凸集在开凸集D上连续可微，则对任何上连续可微，则对任何x,xdD，有：，有：1F(xd)F(x)0F(xtd)ddt定义定义G:RnRmn在在xDRn处称为处称为 Lipschitz连续的，若连续的，若vD，都有，都有G(v)G(x)vx。若在若在D中每一点均中每一点均 Lipschitz连续，则称连续，则称G在在D上上 Lipschitz称为称为 Lipschitz 常数。常数。定理定理连续，记为连续，记为GLip(D)。此中，。此中，（向量函数线性化近似的偏差预计）（向量函数线性化近似的
24、偏差预计）设设F:RnRm在开凸集在开凸集D上连续可微，上连续可微，F(x)在在x的邻域的邻域D中中 Lipschitz连续，则对于任何连续，则对于任何xdD，有，有2F(xd)F(x)F(x)d2d.证明：证明：F(xd)F(x)F(x)d10F(x1010d)ddF(x)d从而从而1010F(xd)F(x)F(x)d10F(xF(xd)F(x)ddd)F(x)dd(F(xd)F(x)ddF(xd)F(x)dd2d.dddd210d12注：在上述证明过程中的第一个不等式其实不平庸，它实质上要求，对一般向量函数的积分，下述命注：在上述证明过程中的第一个不等式其实不平庸，它实质上要求，对一般向量
25、函数的积分，下述命题建立。题建立。bba命题：对可积向量函数命题：对可积向量函数f(t)(f1(t),f2(t),fn(t)T，有，有af(t)dtf(t)dt.证明：对于证明：对于l1范数上述命题是建立的，这是因为：范数上述命题是建立的，这是因为：1010精选文档10/301111精选文档bb1bbaf(t)dtaf1(t)dtaf2(t)dtafn(t)dtbaf1(t)dtf(t)dtbaf2(t)dtbafn(t)dtba(f1(t)f2(t)fn(t)dta对于对于2范数上述命题也建立。事实上，范数上述命题也建立。事实上，l1b2nba2nf(t)dt(fi(t)dt)i1abbbi
26、1aafi(t)fi(s)dtdsbbaan(fi(t)fi(s)dtdsbbaanfi(t)2nfi(s)dtds2bai 1nbani1bi1nfi(t)dt2i1fi(s)ds(2afi(t)dt)(f(t)dtdt)i122b2i1a对于一般范数，需借助于对于一般范数，需借助于Banach空间弱空间弱 Riemann积分理论进行证明。积分理论进行证明。定理给出了线性近似的偏差界，下边考虑二次近似的偏差界。定理给出了线性近似的偏差界，下边考虑二次近似的偏差界。定理设定理设f:Rn续。则对于任何续。则对于任何x2R在开凸集在开凸集DRn上二次连续可微，上二次连续可微，f(x)在在x的邻域的
27、邻域D上上 Lipschitz连连dD有：有：Tf(xd)f(x)f(x)d1dT2f(x)dd6232证明：证明：f(xd)t1f(x)f(x)Td1dT21tf(x)ddf(xT2001t001td)dddtdT200f(x)dddtdT22f(xd)ddT2f(x)dddtddddtd31tddt16d30000F(u)F(v)F(x)(u0t1定理设定理设F:RnnRm在开凸集在开凸集DR上连续可微，则对任何上连续可微，则对任何x,u,vD，有，有v)supF(vt(u v)F(x)uv，若进一步若进一步F在在D中中 Lipschitz连续，则有：连续，则有：u xv2xuv.F(u)
28、F(v)F(x)(uv)11/301212精选文档证明：证明：F(u)1F(v)F(x)(uv)10F(vt(uv)F(x)(uv)dtF(vt(u v)01F(x)uvdt10（由此式即可得第一部分结论）（由此式即可得第一部分结论）vt(u v)0 x uvdt10(1t)(v1x)t(ux)uvdtuvxv(1t)dtuxtdtuxvx21uv.0定理定理设设F,F知足上边定理条件，假定矩阵知足上边定理条件，假定矩阵F(x)存在（这包含着存在（这包含着F(x)是方阵，即是方阵，即xF(x):Rnuv证明：证明：Rn）。则存在）。则存在F(u)F(v)0,0，使得，使得u,vD，当，当max
29、u x,v时，有：时，有：u vv)F(u)F(v)F(x)(uF(u)F(v)F(x)(uv)F(x)2(uxvx)uvF(x)uvuv（令（令F(x)）从而右侧不等式得证。另一方面，注意到：从而右侧不等式得证。另一方面，注意到：1uvF(x)F(x)(uv)F(x)1F(x)(uv)）故有故有F(u)1F(v)(u2F(x)(uxv)vF(u)F(v)F(x)(uv)vx)uF(x)11F(x)1uvuv所以，若取所以，若取1F(x)1，且令，且令1F(x)1(0)，则得左侧不等式结论。，则得左侧不等式结论。由由1F(x)1F(x)F(x)1F(x)，可得，可得1F(x)1F(x)，从而有
30、，从而有0。六、差商（偏差商）六、差商（偏差商）设设F(x)(f1(x),fm(x)T是一个向量函数，其是一个向量函数，其Jacobi 矩阵的第矩阵的第i12/30行行j列元素可用差商（偏差列元素可用差商（偏差1313精选文档商）商）afi(xhej)fi(x)hij近似。由偏差商组成的矩阵近似。由偏差商组成的矩阵A(aij)mn称为称为F(x)的差商矩阵。明显差商矩阵的第的差商矩阵。明显差商矩阵的第j列为列为对于差商矩阵与对于差商矩阵与AF(xhej)F(x)hjJacobi 矩阵有以下偏差预计式矩阵有以下偏差预计式定理设定理设F:RnRm在开凸集在开凸集D上连续可微，上连续可微，F(x)在
31、在D中中 Lipschitz连续，则连续，则AjJ(x)jh2若采纳的范数是若采纳的范数是l1范数，则有：范数，则有：AJ(x)12h证明：将定理证明：将定理中的中的d取为取为hej，则有，则有F(xheF(xhe2j)F(x)J(x)hejj)F(x)J(x)jhhejh222两边同除两边同除h，则有，则有AjJ(x)jh.2近似地，也能够用中心差分来近似梯度和近似地，也能够用中心差分来近似梯度和Hessian 矩阵，并有以下偏差预计结果。矩阵，并有以下偏差预计结果。定理设定理设f:RnR在开凸集在开凸集D上二次连续可微，上二次连续可微，2f(x)在在D上上 Lipschitz 连续，又设所
32、采连续，又设所采用的范数知足用的范数知足ej1，(i1,n)，定义，定义f(x)在在x处的中心偏差商为：处的中心偏差商为：af(xhei)f(xhei)i2h则则aif(x)ih26如采纳如采纳l范数，则范数，则af(x)h2，此中，此中a(a1,an)T.6证明：由定理证明：由定理有：有：f(xd)f(x)T23f(x)Td1df(x)dd26令令dhei，则有，则有1414精选文档13/301515精选文档f(xhei)f(x)hf(x)i1h22f(x)ii2h36再令再令dhe，又有，又有if(xhei)f(x)hf(x)i,1h22，则有，则有2f(x)ii令上两式中左端绝对值内的部
33、分分别为令上两式中左端绝对值内的部分分别为h36f(xhei)f(xhei)2hf(x)i3aif(x)ih3由此即得：由此即得：由由l范数的定义，有范数的定义，有f(xhei)f(xhei)2hf(x)ih26af(x)h2.6定理设定理设f(x)在开凸集在开凸集D上二次连续可微，上二次连续可微，2f(x)在在D上上 Lipschitz连续，采纳的范数知足连续，采纳的范数知足ej1，(i 1,n)，假定，假定x,xhe,xihe,xjheheiD(i,j1,j,n)。定义：。定义：af(xheiijhej)f(xhei)h2f(xhej)f(x)则有：则有：aij2f(x)ij5h3若采纳矩
34、阵范数是若采纳矩阵范数是l1,l或或 F-范数，则范数，则A2f(x)5hn（这里（这里A3f(xheihej)(aij)是是 Hessian 矩阵的失散形式）。矩阵的失散形式）。证明：令证明：令f(x)(heihej)Tf(x)1(heihej)T2f(x)(heihej)f(xhei)f(x)(hei)Tf(x)1T2(hei)Tf(x)22(hej)f(x)(hei)f(xhej)f(x)2h1(hej)T2f(x)(hej)22经简单计算有：经简单计算有：(aijf(x)ij)又由定理又由定理有，有，hei6hej38h6314/301616精选文档h31363hei36hejh6从而
35、有从而有aij2f(x)1ij22()10h5 hhh63再由矩阵再由矩阵l1,l及及 F-范数的定义立刻可得：范数的定义立刻可得：hA2f(x)5 n3凸集与凸函数凸集与凸函数一、凸集（一、凸集（1凸集的观点凸集的观点ConvexSet）定义定义设设SRn，若，若x1,x2S，都有，都有x1(1)x2S0,1则称则称S是凸集。是凸集。定理定理Rnx1,x2,xmS的子集的子集S为凸集的充足必需条件是为凸集的充足必需条件是有有mixiSi1m1,)且且此中此中0(iimi1。i1凸集的例子：凸集的例子：n维球、半空间、超平面、维球、半空间、超平面、xAxb,x定理若定理若S1,S2是是Rn中的
36、凸集，则中的凸集，则0等均为凸集。等均为凸集。1）SS是凸集；（事实上，随意多个凸集的交仍为凸集）是凸集；（事实上，随意多个凸集的交仍为凸集）122x）S1S2x12x1S1,x2S2也是凸集也是凸集2凸包会合凸包会合S的凸包的定义以下：的凸包的定义以下：mmConv(S)xxixi,xiS,i1,i0,m1,2,i1i1由定义知，会合由定义知，会合S的凸包由的凸包由S中元素全部可能的凸组合组成。还可证明：它是全部包含会合中元素全部可能的凸组合组成。还可证明：它是全部包含会合15/301717S的的凸凸精选文档集的交，即它是包含会合集的交，即它是包含会合S的最小凸集。的最小凸集。3锥、凸锥锥、
37、凸锥定义设定义设KRn，若，若凸锥。凸锥。简单证明：简单证明：xK，则称，则称K为锥；若锥为锥；若锥K仍是凸集，则称之为仍是凸集，则称之为xK,0，有，有K是凸锥的充要条件是，是凸锥的充要条件是，K对正组合运算关闭。对正组合运算关闭。定理若定理若CRn是凸集，则是凸集，则C的闭包的闭包C也是凸集。也是凸集。证明：证明：x,y C，则存在序列，则存在序列 xk,yklimxkkC，使得，使得yx(1)y，x(1kk从而有从而有lim(xk(1x，limyk)yk)0,1注意到注意到xk(1)ykC及及C的闭性，可知的闭性，可知)yC这就证了然这就证了然C是凸集。是凸集。4极点与极方向极点与极方向
38、定义设定义设SRn是非空凸集，是非空凸集，xS，若，若x不在不在S中任何线段的内部，则称中任何线段的内部，则称x是凸集是凸集S的极点。的极点。明显，多边形极点、圆周上的点均为极点。明显，多边形极点、圆周上的点均为极点。则称则称d为为S的方向；若的方向；若为为S的极方向。的极方向。定义定义 设设S Rn是闭凸集，是闭凸集，d为非零向量，若对随意为非零向量，若对随意xS，当，当0时，总有时，总有xdS，S中的某方向中的某方向d不可以表示为该会合的两个不一样方向的正的线性组合，则称不可以表示为该会合的两个不一样方向的正的线性组合，则称d极点与极方向是凸多面体中特别重要的观点，在线性规划中有重要应用，
39、对于这些方面的详尽议论，可参阅有关线性规划极点与极方向是凸多面体中特别重要的观点，在线性规划中有重要应用，对于这些方面的详尽议论，可参阅有关线性规划教材。教材。二、凸函数二、凸函数定义设定义设SRn是非空凸集，是非空凸集，f是定义在是定义在S上的函数，若对随意的上的函数，若对随意的x1,x2(0,1)f(x1(1)x2)f(x1)(1)f(x2)S都有：都有：则称则称f是是S上的凸函数。凸函数的另一等价定义是：上的凸函数。凸函数的另一等价定义是：16/301818精选文档nnii1f(i1ix)niif(xi)i1此中，此中，1,i0。若。若x1x2时，不等式严格建立，则称时，不等式严格建立，
40、则称f在在S上是严格凸的。若上是严格凸的。若f在在S上上是凸（严格凸），则称是凸（严格凸），则称f在在S上是凹（严格凹）。上是凹（严格凹）。定理定理设设f(x)是定义在凸集是定义在凸集S上的凸函数，上的凸函数，1）若）若0，则，则f(x)是是S上的凸函数；上的凸函数；2）若）若f1,f2是是S上的凸函数，则上的凸函数，则f1f2也是凸函数。也是凸函数。m由此立刻可得：若由此立刻可得：若f1,fm是是S上的凸函数，上的凸函数，1,m0，则，则i1ifi也是也是S上的凸函数。上的凸函数。凸函数的一阶特点凸函数的一阶特点定理定理设设SRn是非空开凸集，是非空开凸集，f是定义在是定义在S上的可微函数，
41、则上的可微函数，则Tf(y)f(x)f(x)(yx)x,ySf为凸函数的充要条件是：为凸函数的充要条件是：证明：必需性，设证明：必需性，设f是凸函数，则对随意的是凸函数，则对随意的(0,1)，有，有f(y(1)x)所以有所以有f(y)(1)f(x)f(y)f(x(yx)f(x)f(x)令令0得得即即()f y()T()()()f yf xf xy x()()T()ffxxyx必需性得证。必需性得证。充足性：设充足性：设Sf(y)f(x)f(x)T(y x)，x,yS建立。建立。任取任取x1,x2及及(0,1)，令，令xx1(1)x2，于是有：，于是有：f(x1)f(x)f(x)T(x1f(x2
42、)f(x)f(x)T(x2f(x1)x)x)于是有于是有(1)f2x()fx()fTx()1x(12x)x17/301919精选文档f(x)f(x1(1)x2)x2)即即f(x1(1亦即亦即f(x)是凸函数，充足性得证。是凸函数，充足性得证。几何解说：凸函数图像位于割线之下，切线之上。几何解说：凸函数图像位于割线之下，切线之上。凸函数的二阶特点凸函数的二阶特点定理设定理设Sf(x1)(1)f(x2)f为凸函数的充要条件是为凸函数的充要条件是Rn是非空开凸集，是非空开凸集，f是定义在是定义在S上的二次可微函数，则上的二次可微函数，则S上的每一点的上的每一点的 Hessian 矩阵半正定。矩阵半正
43、定。证明：充足性，证明：充足性，设设2f(x)在每一点在每一点x21S均半正定。任取均半正定。任取x,yS，由中值定理有：，由中值定理有：f(y)f(x)f(x)T(yx)(yx)T2f()(yx)f(x)所以，所以，f(x)是凸函数。是凸函数。f(x)T(yx)，（此中，（此中在以在以x,y为端点的线段上）为端点的线段上）必需性，设必需性，设f(x)是凸函数，则任取是凸函数，则任取xS，对随意的，对随意的pRn，2充足小时有充足小时有f(xp)f(x)f(x)Tpp)f(x)f(x)pT另一方面另一方面f(x2T2pf(x)p0(p2T22)故故pf(x)p0(p)022两边除以两边除以2并
44、令并令0，则有，则有pT2f(x)p0即即2f(x)半正定。半正定。注：对严格凸函数有近似的一阶与二阶特点，但要注意一些细微的差异。注：对严格凸函数有近似的一阶与二阶特点，但要注意一些细微的差异。定理设定理设SRn是非空开凸集，是非空开凸集，f是定义在是定义在S上的可微函数，则上的可微函数，则f为严格凸的充要条件是为严格凸的充要条件是f(y)f(x)f(x)T(yx)，x,yS,xy证明：充足性证明与前述凸函数情况完整近似，故从略。必需性的证明以下：证明：充足性证明与前述凸函数情况完整近似，故从略。必需性的证明以下：18/302020精选文档设设f(x)在在S上严格凸，上严格凸，x,yS且且x
45、y，令，令z12xy，则明显，则明显12zS。因为。因为f(x)严格凸，严格凸，故有故有及及f(z)1f(x)1)f(y)()f zf x22()(T()由上两式有由上两式有1f xzx1f(y)1f(x)1 f(y)22f(x)Tf(x)f(x)(z()(x).22所以有所以有T1f(x)(yx)2()()Tf yf xf xyx定理设定理设SRn是非空开凸集，是非空开凸集，f是定义在是定义在S上的二次可微函数，若上的二次可微函数，若xS,2f(x)正定，则正定，则f(x)为严格凸函数。为严格凸函数。注：严格凸不可以推注：严格凸不可以推出出2f(x)正定，所以正定，所以2f(x)正定是严格凸
46、的充足条件，但不是必需条件。如正定是严格凸的充足条件，但不是必需条件。如f(x)定理定理x4，f(x)12x2，f(0)0不正定，但它是严格凸的。不正定，但它是严格凸的。设设SRn是非空开凸集，是非空开凸集，f是定义在是定义在S上的凸函数，上的凸函数，是一个实数，则水平集是一个实数，则水平集LxxS,f(x)是凸集。是凸集。证明：证明：略略进一步，若进一步，若f(x)是连续凸函数，则是连续凸函数，则L是闭凸集。事实上，设是闭凸集。事实上，设xkL，且，且limxkxk那么那么f(x)f(lim xk)limf(xk)kk所以所以xL，故，故L设设f(x)是是S2为闭集。为闭集。定理定理T2Rn
47、上二次连续可微的凸函数，且存在常数上二次连续可微的凸函数，且存在常数uf(x)umu则水平集则水平集L(x0)xL(x0)，uRnxxS,f(x)f(x0)是有界闭凸集。是有界闭凸集。0，使得，使得证明：由上边议论可知，证明：由上边议论可知，因此因此x,y从而有从而有(yL(x0)是闭凸集，因此仅需是闭凸集，因此仅需(yx)(yx)(y证明证明L(x0)是有界的。因为是有界的。因为L(x0)是凸的，是凸的，L(x0)，xx)T2f(xy(1)xL(x0)，2x)myx由由 Taylor 睁开式，睁开式，2121精选文档19/302222精选文档f(y)f(x)f(x)(yx)f(x)(yx)T
48、Tf(x)(y10Tx)yx10t0(yx)T2f(x(yx)(yx)ddtf(x)m0t2ddtf(x)1myx22可知，可知，yL(x0),yx0，有，有f(y)f(x0)f(x0)(yx0)T1212myx02f(x0)yx0myx02再由再由f(y)故有故有f(x0)0，f(x0)1myx002yx0即即2mf(x0)由由y是是L(x0)中任一直量，所以中任一直量，所以定理（定理（MinkowskiL(x0)有界，因此有界，因此L(x0)是有界闭凸集。是有界闭凸集。，有，有xp1p不等式）对不等式）对p1nypxpnp1pyp，即：，即：p1pn(i1xiyi)(xi)i1(i1yi)
49、.证明：当证明：当x或或y为零向量时，结论明显建立。当为零向量时，结论明显建立。当考虑函数考虑函数因为因为p1时，也易证明。以下设时，也易证明。以下设x,y(t)tp，2t 0(t)p(p1)tpxpxpyp0，故，故(t)严格凸。严格凸。注意到注意到ypxp1yp由函数由函数(t)的凸性，于是有，的凸性，于是有，ppxxpxpiypxpyiypypyixpxpypnxixpypxpypxp所以，所以，npnpxipxiyixixpypyyyyy0，且，且p1。pippi1pi1xpypi1xpypxpypi1xpxpyp2323精选文档20/302424精选文档ppxpxpypyppxpyp
50、xpxpyyp1ppnpp由此即得由此即得xiyixpyp，i1即即xypxpyp.三、一致凸函数三、一致凸函数定义定义 设设f是非空凸集是非空凸集D上的函数，若存在一个常数上的函数，若存在一个常数0，使得对随意的，使得对随意的x,yD，及随意，及随意(0,1)。均有。均有2f(x)(1)f(y)f(x(1)y)(1)xy，则称则称f(x)在凸集在凸集D上一致凸。上一致凸。由定义立刻可知：由定义立刻可知：一致凸一致凸严格凸严格凸凸。凸。一致凸函数的鉴别定理一致凸函数的鉴别定理定理定理 设设f(x)是非空开凸集是非空开凸集D上连续可微函数，则上连续可微函数，则f(x)在在D上一致凸的充要条件是存