向量和子空间投影定理.ppt

第二章,基本概念和基本理论,整理发布,2.0、预备知识,1、向量和子空间投影定理(1)n维欧氏空间：Rn点（向量）：xRn,x=(x1,x2,xn)T分量xiR(实数集)方向（自由向量）：dRn,d0d=(d1,d2,dn)T表示从0指向d的方向实用中，常用x+d表示从x点出发沿d方向移动d长度得到的点,d,0,x,x+(1/2)d,2.0、预备知识（续）,1、向量和子空间投影定理(2)向量运算：x,yRnnx,y的内积：xTy=xiyi=x1y1+x2y2+xnyni=1x,y的距离：x-y=(x-y)T(x-y)(1/2)x的长度：x=xTx(1/2)三角不等式：x+yxy点列的收敛：设点列x(k)Rn,xRn点列x(k)收敛到x，记limx(k)=xlimx(k)-x=0limxi(k)=xi,ikkk,x+y,y,x,2.0、预备知识（续）,1、向量和子空间投影定理(3)子空间：设d(1),d(2),d(m)Rn,d(k)0m记L(d(1),d(2),d(m)=x=jd(j)jRj=1为由向量d(1),d(2),d(m)生成的子空间，简记为L。正交子空间：设L为Rn的子空间，其正交子空间为LxRnxTy=0,yL子空间投影定理：设L为Rn的子空间。那么xRn，唯一xL,yL,使z=x+y,且x为问题minz-us.t.uL的唯一解，最优值为y。特别，LRn时，正交子空间L0（零空间）,2.0、预备知识（续）,规定：x,yRn，xyxiyi，i类似规定xy，x=y，xy.一个有用的定理设xRn，R，L为Rn的线性子空间，(1)若xTy,yRn且y0，则x0，0.(2)若xTy,yLRn，则xL，0.(特别,LRn时,x=0)定理的其他形式：“若xTy,yRn且y0，则x0，0.”“若xTy,yRn且y0，则x0，0.”“若xTy,yRn且y0，则x0，0.”“若xTy,yLRn，则xL，0.”,2.0、预备知识（续）,2、多元函数及其导数(1)n元函数：f(x):RnR线性函数：f(x)=cTx+b=cixi+b二次函数：f(x)=(1/2)xTQx+cTx+b=(1/2)ijaijxixj+cixi+b向量值线性函数：F(x)=Ax+dRm其中A为mn矩阵，d为m维向量F(x)=(f1(x),f2(x),fm(x)T记aiT为A的第i行向量，fi(x)=aiTx,2.0、预备知识（续）,2、多元函数及其导数(2)梯度（一阶偏导数向量）：f(x)(f/x1,f/x2,f/xn)TRn.线性函数：f(x)=cTx+b,f(x)=c二次函数：f(x)=(1/2)xTQx+cTx+bf(x)=Qx+c向量值线性函数：F(x)=Ax+dRmF/x=AT,2.0、预备知识（续）,2、多元函数及其导数(3)Hesse阵（二阶偏导数矩阵）：2f/x122f/x2x12f/xnx12f(x)=2f/x1x22f/x222f/xnx22f/x1xn2f/x2xn2f/xn2线性函数：f(x)=cTx+b,2f(x)=0二次函数：f(x)=(1/2)xTQx+cTx+b,2f(x)=Q,2.0、预备知识（续）,2、多元函数及其导数(4)n元函数的Taylor展开式及中值公式：设f(x):RnR，二阶可导。在x*的邻域内一阶Taylor展开式：f(x)=f(x*)+fT(x*)(x-x*)+ox-x*二阶Taylor展开式：f(x)=f(x*)+fT(x)(x-x*)+(1/2)(x-x*)T2f(x*)(x-x*)+ox-x*2一阶中值公式：对x,使f(x)=f(x*)+f(x*+(x-x*)T(x-x*)Lagrange余项：对x,记xx*+(x-x*)f(x)=f(x*)+fT(x)(x-x*)+(1/2)(x-x*)T2f(x)(x-x*),2.1数学规划模型的一般形式minf(x)-目标函数s.t.xS-约束集合，可行集其中，SRn，f:SR，xS称（fS)的可行解最优解:x*S，满足f(x*)f(x),xS。则称x*为(fS)的全局最优解(最优解),记g.opt.(globaloptimum),简记opt.最优值:x*为(fS)的最优解,则称f*=f(x*)为(fS)的最优值(最优目标函数值),(fS),2.1数学规划模型的一般形式（续）,局部最优解:x*S，x*的邻域N(x*)，使满足f(x*)f(x),xSN(x*)。则称x*为(fS)的局部最优解,记l.opt.(localoptimum)在上述定义中，当xx*时有严格不等式成立，则分别称x*为(fS)的严格全局最优解和严格局部最优解。,严格l.opt.,严格g.opt.,l.opt.,2.1数学规划模型的一般形式（续）,函数形式:f(x),gi(x),hj(x):RnRminf(x)(fgh)s.t.gi(x)0,i=1,2,mhj(x)=0,j=1,2,l矩阵形式:minf(x)，f(x):RnR(fgh)s.t.g(x)0,g(x):RnRmh(x)=0,h(x):RnRl当f(x),gi(x),hj(x)均为线性函数时，称线性规划；若其中有非线性函数时，称非线性规划。,2.2凸集、凸函数和凸规划,一、凸集1、凸集的概念：定义：设集合SRn，若x(1),x(2)S,0,1，必有x(1)(1-)x(2)S，则称S为凸集。规定：单点集x为凸集，空集为凸集。注:x(1)(1-)x(2)=x(2)(x(1)-x(2)是连接x(1)与x(2)的线段。,凸集,非凸集,非凸集,2.2凸集、凸函数和凸规划(续),一、凸集1、凸集的概念：例:证明集合S=xAx=b是凸集。其中，A为mn矩阵，b为m维向量。凸组合：设x(1),x(2),x(m)Rn,j0mmj=1,那么称jx(j)为x(1),x(2),x(m)的j=1j=1凸组合。m比较:z=jx(j)j=1jR构成线性组合线性子空间j0,j0构成半正组合凸锥j0,j=0构成凸组合凸集,2.2凸集、凸函数和凸规划(续),一、凸集1、凸集的概念：定理：S是凸集S中任意有限点的凸组合属于S多胞形H(x(1),x(2),x(m)：由x(1),x(2),x(m)的所有凸组合构成。单纯形：若多胞形H(x(1),x(2),x(m)满足，x(2)-x(1),x(3)-x(1),x(m)-x(1)线性无关。,多胞形,单纯形,单纯形,2.2凸集、凸函数和凸规划(续),一、凸集2、凸集的性质：凸集的交集是凸集；（并？）凸集的内点集是凸集；（逆命题是否成立？）凸集的闭包是凸集。（逆命题是否成立？）分离与支撑：凸集边界上任意点存在支撑超平面两个互相不交的凸集之间存在分离超平面,支撑,强分离,分离,非正常分离,2.2凸集、凸函数和凸规划(续),一、凸集3、凸锥：定义：CRn,若xC,0有xC,则称C是以0为顶点的锥。如果C还是凸集，则称为凸锥。集合0、Rn是凸锥。命题：C是凸锥C中任意有限点的半正组合属于S,0,2.2凸集、凸函数和凸规划(续),二、凸函数1、凸函数及水平集定义:设集合SRn为凸集，函数f:SR若x(1),x(2)S,(0,1)，均有f(x(1)(1-)x(2)f(x(1)+(1-)f(x(2)，则称f(x)为凸集S上的凸函数。若进一步有上面不等式以严格不等式成立，则称f(x)为凸集S上的严格凸函数。当-f(x)为凸函数（严格凸函数）时，则称f(x)为凹函数（严格凹函数）。,严格凸函数,凸函数,严格凹函数,2.2凸集、凸函数和凸规划(续),二、凸函数1、凸函数及水平集：定理：f(x)为凸集S上的凸函数S上任意有限点的凸组合的函数值不大于各点函数值的凸组合。思考：设f1,f2是凸函数，设1,20,1f1+2f2,1f1-2f2是否凸函数？f(x)=maxf1(x),f2(x),g(x)=minf1(x),f2(x)是否凸函数？,2.2凸集、凸函数和凸规划(续),二、凸函数1、凸函数及水平集：定义：设集合SRn，函数f:SR，R，称S=xSf(x)为f(x)在S上的水平集。定理：设集合SRn是凸集，函数f:SR是凸函数，则对R，S是凸集。注：水平集的概念相当于在地形图中，海拔高度不高于某一数值的区域。上述定理的逆不真。考虑分段函数f(x)=1(x0)或0(x0充分小时有x*+dS,如果limf(x*+d)-f(x*)/存在（包括）则称f(x)为在点沿方向的方向导数存在，记f(x*;d)=limf(x*+d)-f(x*)/若f(x)在x*可导，则f(x*;d)=f(x*)Td.,2.2凸集、凸函数和凸规划(续),二、凸函数2、凸函数的性质：以下设SRn为非空凸集，函数f:SR2）若f凸，则f在S的内点集上连续；注：f在S上不一定连续。例:f(x)2(当x=1)；f(x)x2(当x0,总有x+dS.d(1)=d(2)(0)时，称d(1)和d(2)同方向。4)极方向：方向d不能表示为两个不同方向的组合(d=d(1)+d(2).,2.3多面体、极点、极方向,多面体S=xRnAx=b,x0的极点和极方向定理1（极点特征）设A满秩，x是S极点的充分必要条件是:存在分解A=B,N，其中B为m阶非奇异矩阵，使xT=xBT,xNT,这里xB=B-1b0,xN=0.S中必存在有限多个极点。(Cnm),2.3多面体、极点、极方向,多面体S=xRnAx=b,x0的极点和极方向定理2（极方向特征）设A=p1,p2,pn满秩，d是S极方向的充分必要条件是:存在分解A=B,N，其中B为m阶非奇异矩阵，对于N中的列向量pj使B-1pj0,dT=dBT,dNT,这里jdB=-B-1pj,dN=(0,.,1,0)TS中必存在有限多个极方向。(n-m)Cnm),考虑多面体S=xRnAx=b,x0，其中3210065A=21010b=400300175即3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x50,例题,32100A=P1,P2,P3,P4,P5=2101003001A矩阵包含以下10个33的子矩阵：B1=p1，p2，p3B2=p1，p2，p4B3=p1，p2，p5B4=p1，p3，p4B5=p1，p3，p5B6=p1，p4，p5B7=p2，p3，p4B8=p2，p3，p5B9=p2，p4，p5B10=p3，p4，p5,例题,其中B4=0，因而B4不能构成极点和极方向。其余均为非奇异方阵，因此该问题共有9个可构成极点、极方向的子矩阵，我们称之为基。对于基B3=p1，p2，p5，令x3=0，x4=0，在等式约束中令x3=0，x4=0，解线性方程组：3x1+2x2+0 x5=652x1+x2+0 x5=400 x1+3x2+x5=75得到x1=15，x2=10，x5=45，对应的极点：x=(x1，x2，x3，x4，x5)T=(15，10，0，0，45)T,例题,类似可得到极点x(2)=(5,25,0,5,0)T（对应B2）x(7)=(20,0,5,0,75)T（对应B5）x(8)=(0,25,15,15,0)T（对应B7）x(9)=(0,0,65,40,75)T（对应B10）而x(3)=(0,32.5,0,7.5,-22.5)T（对应B9）x(4)=(65/3,0,0,-10/3,75)T（对应B6）x(5)=(7.5,25,-7.5,0,0)T（对应B1）x(6)=(0,40,-15,0,-45)T（对应B8）不是极点,例题,2.3多面体、极点、极方向,多面体S=xRnAx=b,x0的极点和极方向定理3（表示定理）考虑上述多面体S，设A满秩，x(1),x(2),x(k)为所有极点，d(1),d(2),d(l)为所有极方向。那么，对于xS，i0，且1+2+k=1,j0,j=1,2,l,使x=1x(1)+2x(2)+kx(k)+1d(1)+2d(2)+ld(l).,