向量和子空间投影定理(

第二章基本概念和基本理论、预备知识1、向量和子空间投影定理(1)n维欧氏空间：Rn点（向量）：xRn,x=(x1,x2,…,xn)T分量xiR(实数集)方向（自由向量）：dRn,d0d=(d1,d2,…,dn)T表示从0指向d的方向实用中，常用x+d表示从x点出发沿d方向移动d长度得到的点d0xx+(1/2)d2.0、预备知识（续）1、向量和子空间投影定理(2)向量运算：x,yRnnx,y的内积：xTy=xiyi=x1y1+x2y2+…+xnyni=1x,y的距离：‖x-y‖=[(x-y)T(x-y)](1/2)x的长度：‖x‖=[xTx](1/2)三角不等式：‖x+y‖≤‖x‖＋‖y‖点列的收敛：设点列｛x(k)｝Rn,xRn点列｛x(k)｝收敛到x，记limx(k)=xlim‖x(k)-x‖=0limxi(k)=xi,ikkkx+yyx2.0、预备知识（续）1、向量和子空间投影定理(3)子空间：设d(1),d(2),…,d(m)Rn,d(k)0m记L(d(1),d(2),…,d(m))={x=jd(j)jR}j=1为由向量d(1),d(2),…,d(m)生成的子空间，简记为L。正交子空间：设L为Rn的子空间，其正交子空间为L＝{xRnxTy=0,yL}子空间投影定理：设L为Rn的子空间。那么xRn，唯一xL,yL,使z=x+y,且x为问题min‖z-u‖s.t.uL的唯一解，最优值为‖y‖。特别，L＝Rn时，正交子空间L＝{0}（零空间）2.0、预备知识（续）规定：x,yRn，x≤yxi≤yi，i类似规定x≥y，x=y，xy,xy.一个有用的定理设xRn，R，L为Rn的线性子空间，(1)若xTy≤,yRn且y≥0，则x≤0，≥0.(2)若xTy≤,yLRn，则xL，≥0.(特别,L＝Rn时,x=0)定理的其他形式：“若xTy≤,yRn且y≤0，则x≥0，≥0.”“若xTy≥,yRn且y≥0，则x≥0，≤0.”“若xTy≥,yRn且y≤0，则x≤0，≤0.”“若xTy≥,yLRn，则xL，≤0.”2.0、预备知识（续）2、多元函数及其导数(1)n元函数：f(x):RnR线性函数：f(x)=cTx+b=cixi+b二次函数：f(x)=(1/2)xTQx+cTx+b=(1/2)ijaijxixj+cixi+b向量值线性函数：F(x)=Ax+dRm其中A为mn矩阵，d为m维向量F(x)=(f1(x),f2(x),…,fm(x))T记aiT为A的第i行向量，fi(x)=aiTx2.0、预备知识（续）2、多元函数及其导数(2)梯度（一阶偏导数向量）：f(x)＝(f/x1,f/x2,…,f/xn)TRn.线性函数：f(x)=cTx+b,f(x)=c二次函数：f(x)=(1/2)xTQx+cTx+bf(x)=Qx+c向量值线性函数：F(x)=Ax+dRmF/x=AT2.0、预备知识（续）2、多元函数及其导数(3)Hesse阵（二阶偏导数矩阵）：2f/x122f/x2x1…2f/xnx12f(x)=2f/x1x22f/x22…2f/xnx2…………2f/x1xn2f/x2xn…2f/xn2线性函数：f(x)=cTx+b,2f(x)=0二次函数：f(x)=(1/2)xTQx+cTx+b,2f(x)=Q2.0、预备知识（续）2、多元函数及其导数(4)n元函数的Taylor展开式及中值公式：设f(x):RnR，二阶可导。在x*的邻域内一阶Taylor展开式：f(x)=f(x*)+fT(x*)(x-x*)+o‖x-x*‖二阶Taylor展开式：f(x)=f(x*)+fT(x)(x-x*)+(1/2)(x-x*)T2f(x*)(x-x*)+o‖x-x*‖2一阶中值公式：对x,,使f(x)=f(x*)+［f(x*+(x-x*))]T(x-x*)Lagrange余项：对x,,记xx*+(x-x*)f(x)=f(x*)+fT(x)(x-x*)+(1/2)(x-x*)T2f(x)(x-x*)2.1数学规划模型的一般形式minf(x)--------目标函数s.t.xS--------约束集合，可行集其中，SRn，f:SR，xS称（fS)的可行解最优解:x*S，满足f(x*)≤f(x),xS。则称x*为(fS)的全局最优解(最优解),记g.opt.(globaloptimum),简记opt.最优值:x*为(fS)的最优解,则称f*=f(x*)为(fS)的最优值(最优目标函数值)(fS)2.1数学规划模型的一般形式（续）局部最优解:x*S，x*的邻域N(x*)，使满足f(x*)≤f(x),xSN(x*)。则称x*为(fS)的局部最优解,记l.opt.(localoptimum)在上述定义中，当xx*时有严格不等式成立，则分别称x*为(fS)的严格全局最优解和严格局部最优解。严格l.opt.严格g.opt.l.opt.2.1数学规划模型的一般形式（续）函数形式:f(x),gi(x),hj(x):RnRminf(x)(fgh)s.t.gi(x)≤0,i=1,2,…,mhj(x)=0,j=1,2,…,l矩阵形式:minf(x)，f(x):RnR(fgh)s.t.g(x)≤0,g(x):RnRmh(x)=0,h(x):RnRl当f(x),gi(x),hj(x)均为线性函数时，称线性规划；若其中有非线性函数时，称非线性规划。2.2凸集、凸函数和凸规划一、凸集1、凸集的概念：定义：设集合SRn，若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={x∣Ax=b}是凸集。其中，A为mn矩阵，b为m维向量。凸组合：设x(1),x(2),…,x(m)Rn,j≥0mmj=1,那么称jx(j)为x(1),x(2),…,x(m)的j=1j=1凸组合。m•比较:z=jx(j)j=1jR—构成线性组合——线性子空间j≥0,j0—构成半正组合——凸锥j≥0,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、凸集的性质：1)凸集的交集是凸集；（并？）2)凸集的内点集是凸集；（逆命题是否成立？）3)凸集的闭包是凸集。（逆命题是否成立？）4)分离与支撑：凸集边界上任意点存在支撑超平面两个互相不交的凸集之间存在分离超平面支撑强分离分离非正常分离2.2凸集、凸函数和凸规划(续)一、凸集3、凸锥：定义：CRn,若xC,0有xC,则称C是以0为顶点的锥。如果C还是凸集，则称为凸锥。集合{0}、Rn是凸锥。命题：C是凸锥C中任意有限点的半正组合属于S02.2凸集、凸函数和凸规划(续)二、凸函数1、凸函数及水平集定义:设集合SRn为凸集，函数f:SR若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)设1,20,1f1+2f2,1f1-2f2是否凸函数？2)f(x)=max{f1(x),f2(x)},g(x)=min{f1(x),f2(x)}是否凸函数？2.2凸集、凸函数和凸规划(续)二、凸函数1、凸函数及水平集：定义：设集合SRn，函数f:SR，R，称S={xS∣f(x)≤}为f(x)在S上的水平集。定理：设集合SRn是凸集，函数f:SR是凸函数，则对R，S是凸集。注：1)水平集的概念相当于在地形图中，海拔高度不高于某一数值的区域。2)上述定理的逆不真。考虑分段函数f(x)=1(x≥0)或0(x0)，函数非凸，但任意水平集是凸集。2.2凸集、凸函数和凸规划(续)二、凸函数2、凸函数的性质：1)方向导数：设SRn为非空凸集，函数f:SR，再设x*S,d为方向，使当0充分小时有x*+dS,如果lim[f(x*+d)-f(x*)]/存在（包括）则称f(x)为在点沿方向的方向导数存在，记f`(x*;d)=lim[f(x*+d)-f(x*)]/•若f(x)在x*可导，则f`(x*;d)=[f(x*)]Td.2.2凸集、凸函数和凸规划(续)二、凸函数2、凸函数的性质：以下设SRn为非空凸集，函数f:SR2）若f凸，则f在S的内点集上连续；注：f在S上不一定连续。例:f(x)＝2(当x=1)；f(x)＝x2(当x1).3）设f凸，则对任意方向方向导数存在。4）设S是开集，f在S上可微，则f凸x*S，有f(x)≥f(x*)+fT(x*)(x-x*),xS.5)设S是开集，f在S上二次可微，则a)f凸xS，2f(x)半正定；b)若xS，2f(x)正定，则f严格凸。2.2凸集、凸函数和凸规划(续)二、凸函数2、凸函数的性质：例：1)f(x)＝x12+2x1x2+2x22+10x1-4；2)f(x)＝-3x12+x1x2-x22-2x32-2x2x3+26;3)f(x)＝3x12+ax1x2+2x22-4x1+6(a=5,4.5)；2.2凸集、凸函数和凸规划(续)三、凸规划：当（fS）中，S为凸集，f是S上的凸函数（求min），称（fS）为凸规划；对于（fgh）,f,gi为凸函数，hj为线性函数时，（fgh）为凸规划。定理：设集合SRn为凸集，函数f:SRf(x)为凸集S上的凸函数。X*为问题（fs）的l.opt，则X*为g.opt；又如果f是严格凸函数，那么X*是（fs）的唯一g.opt。2.3多面体、极点、极方向1）多面体：有限个半闭空间的交例：S={xRnAx=b,x≥0}2.3多面体、极点、极方向2)多面体的极点（顶点）：xS，不存在S中的另外两个点x(1)和x(2)，及λ(0,1)，使x=λx(1)+(1-λ)x(2).3)方向：xS,dRn,d0及λ0,总有x+λdS.d(1)=λd(2)(λ0)时，称d(1)和d(2)同方向。4)极方向：方向d不能表示为两个不同方向的组合(d=d(1)+d(2)).2.3多面体、极点、极方向多面体S={xRnAx=b,x≥0}的极点和极方向定理1（极点特征）设A满秩，x是S极点的充分必要条件是:存在分解A=[B,N]，其中B为m阶非奇异矩阵，使xT=[xBT,xNT],这里xB=B-1b≥0,xN=0.S中必存在有限多个极点。(≤C