向量和子空间投影定理课件

1、向量和子空间投影定理向量和子空间投影定理基本概念基本概念和和基本理论基本理论 整理发布向量和子空间投影定理向量和子空间投影定理1 1、向量和子空间投影定理、向量和子空间投影定理(1) (1) n n维欧氏空间：维欧氏空间：R Rn n 点（向量）点（向量）：x R Rn n, , x = ( = (x1 , ,x2 , , ,xn) )T T 分量分量 xi R R ( (实数集实数集) ) 方向（自由向量）方向（自由向量）：d R Rn n, , d 0 d =(=(d1 , ,d2 , , ,dn) )T T 表示从表示从0 0指向指向d 的方向的方向 实用中，常用实用中，常用 x + d

2、 表示从表示从x 点出发沿点出发沿d 方向方向移动移动 d 长度得到的点长度得到的点d0 xx+(1/2)d向量和子空间投影定理向量和子空间投影定理1 1、向量和子空间投影定理、向量和子空间投影定理(2) (2) 向量运算：向量运算：x , y R Rn n n x , y 的内积：的内积：xTy = xiyi = x1y1+ x2y2+ + xnyn i =1 x , y 的距离：的距离： x-y = (x-y)T(x-y)(1/2) x 的长度：的长度： x= xTx (1/2) 三角不等式三角不等式： x + y xy 点列的收敛：点列的收敛：设点列设点列x(k) R Rn n , ,

3、x R Rn n 点列点列x(k)收敛到收敛到 x ，记记lim x(k) = x limx(k)- x = 0 lim xi(k) = xi , ik k kx+yyx向量和子空间投影定理向量和子空间投影定理1 1、向量和子空间投影定理、向量和子空间投影定理(3) (3) 子空间：子空间：设设 d (1) , d (2) , , d (m) R Rn n, , d (k) 0 m 记记 L L( ( d (1) , d (2) , , d (m) )=)= x = j d (j) j R j =1为由向量为由向量d (1) , d (2) , , d (m) 生成的子空间，简记为生成的子空间

4、，简记为L L。l正交子空间：设正交子空间：设 L 为为R Rn n的的子空间，其正交子空间为子空间，其正交子空间为 L x R Rn n xTy=0 , y L l子空间投影定理：子空间投影定理：设设 L 为为R Rn n的的子空间。那么子空间。那么 x R Rn n， 唯一唯一 x L , y L , 使使 z=x+y , 且且 x 为问题为问题 min z - u s.t. u L 的唯一解，最优值为的唯一解，最优值为y。l特别，特别， L R Rn n 时，正交子空间时，正交子空间 L 0 （零空间零空间）向量和子空间投影定理向量和子空间投影定理l规定：规定：x , y R Rn n，

5、x y xi yi ， i 类类似规定似规定 x y，x = y，x y .l一个有用的定理一个有用的定理 设设 x R Rn n， R R，L L为为R Rn n 的线性子空间，的线性子空间， (1) (1)若若 xTy , y R Rn n 且且 y 0， 则则 x 0， 0 . (2) (2)若若 xTy , y L L R Rn n ， 则则 x L L ， 0 .(特别特别, L LR Rn n时时, ,x =0=0)l定理的其他形式：定理的其他形式：“若若 xTy , y R Rn n 且且 y 0，则则 x 0， 0 .”“若若 xTy , y R Rn n 且且 y 0，则则

6、x 0， 0 .”“若若 xTy , y R Rn n 且且 y 0，则则 x 0， 0 .”“若若 xTy , y L L R Rn n ， 则则 x L L ， 0 .”向量和子空间投影定理向量和子空间投影定理2 2、多元函数及其导数、多元函数及其导数(1) (1) n n元函数：元函数：f ( (x): ): R Rn n R R 线性函数线性函数：f (x) = cTx + b = ci xi + b 二次函数二次函数：f (x) = (1/2) xTQx + cTx + b = (1/2) i j aij xi xj + ci xi + b 向量值线性函数：向量值线性函数：F(x)

7、= Ax + d R Rm m其中其中 A为为 m n矩阵，矩阵，d为为m维向量维向量 F(x)=( f1(x), f2(x), , fm(x) )T 记记 aiT为为A的第的第i行向量，行向量，fi (x) = aiTx向量和子空间投影定理向量和子空间投影定理2 2、多元函数及其导数、多元函数及其导数(2) (2) 梯度（一阶偏导数向量）：梯度（一阶偏导数向量）： f ( (x) )( ( f / x1 , f / x2 , , f / xn ) )T T R Rn n . . 线性函数线性函数：f (x) = cTx + b , f (x) = c 二次函数二次函数：f (x) = (1/

8、2) xTQx + cTx + b f (x) = Qx + c 向量值线性函数：向量值线性函数：F(x) = Ax + d R Rm m F / x = AT向量和子空间投影定理向量和子空间投影定理2 2、多元函数及其导数、多元函数及其导数(3) Hesse (3) Hesse 阵（二阶偏导数矩阵）：阵（二阶偏导数矩阵）： 2f / x1 2 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

9、 (x) = 0 二次函数二次函数：f (x) = (1/2) xTQx + cTx + b, 2f (x)=Q向量和子空间投影定理向量和子空间投影定理2 2、多元函数及其导数、多元函数及其导数(4)(4)n n元函数的元函数的TaylorTaylor展开式及中值公式：展开式及中值公式： 设设 f ( (x): ): R Rn n R R ，二阶可导。在二阶可导。在x* 的邻域内的邻域内l一阶一阶TaylorTaylor展开式：展开式： f (x) = f (x*)+ f T(x*)(x-x*) + ox-x*l二阶二阶TaylorTaylor展开式：展开式： f (x) = f (x*)+

10、f T(x)(x-x*) + (1/2)(x-x*)T 2f (x*)(x-x*) + ox-x*2l一阶中值公式：对一阶中值公式：对x, , , 使使 f (x) = f (x*)+ f (x*+ (x-x*)T(x-x*)lLagrange余项：余项：对对x, , , 记记x x*+ (x-x*) f (x) = f (x*)+ f T(x)(x-x*) + (1/2)(x-x*)T 2f (x )(x-x*) 向量和子空间投影定理向量和子空间投影定理2.1 2.1 数学规划模型的一般形式数学规划模型的一般形式 min min f(x) -目标函数目标函数 s.t. s.t. x S -约

11、束集合，可行集约束集合，可行集其中，其中，S R Rn n，f : :S R R，x S称（称（f S ) )的可行解的可行解l最优解最优解: : x* S，满足满足f (x*) f (x), x S。则称则称 x*为为( (f S) )的全局最优解的全局最优解( (最优解最优解),), 记记 g.opt.( (global optimum),),简记简记 opt.l最优值最优值: : x*为为( (f S) )的最优解的最优解, , 则称则称 f * = f (x*) 为为 ( (f S) )的最优值的最优值( (最优目标函数值最优目标函数值) )( f S )向量和子空间投影定理向量和子空

12、间投影定理l局部最优解局部最优解: : x* S， x* 的邻域的邻域 N(x*) ，使满足，使满足 f (x*) f (x), x S N(x*) 。则称则称 x*为为( (f S) )的局的局部最优解部最优解, ,记记 l .opt.( (local optimum) )l在上述定义中，当在上述定义中，当x x* 时有严格不等式成立，时有严格不等式成立，则则分别称分别称 x* 为为( (f S) )的严格全局最优解和严格局部最的严格全局最优解和严格局部最优解。优解。严格严格l .opt .严格严格g .opt .l .opt .向量和子空间投影定理向量和子空间投影定理l函数形式函数形式:

13、f(x), gi(x) , hj(x) : RnR min f(x)(fgh) s.t. gi(x) 0 , i = 1,2,m hj(x) = 0 , j = 1,2,ll矩阵形式矩阵形式: : min f(x) ，f(x) : RnR(fgh) s.t. g(x) 0 , g(x) : RnRm h(x) = 0 , h(x) : RnRl 当当 f(x), gi(x) , hj(x)均为线性函数时，称线性均为线性函数时，称线性规划；若其中有非线性函数时，称非线性规划。规划；若其中有非线性函数时，称非线性规划。向量和子空间投影定理向量和子空间投影定理一、凸集一、凸集1、凸集的概念：、凸集的

14、概念：定义：设集合定义：设集合 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)的线段的线段 。凸集凸集非凸集非凸集非凸集非凸集向量和子空间投影定理向量和子空间投影定理一、凸集一、凸集 1、凸集的概念：、凸集的概念：l例例: :证明集合证明集合 S = = x Ax = b 是凸集。其是凸集。其中，中，A为为 m n矩阵，矩阵，b为为m

15、维向量。维向量。l凸组合：凸组合：设设 x(1) , x(2) , , x(m) R Rn n, , j j 0 m m j =1, 那么称那么称 j x(j) 为为x(1), x(2), , x(m)的的 j =1 j = 1凸组合。凸组合。 m比较比较: z = j x(j) j =1 j R 构成线性组合构成线性组合 线性子空间线性子空间 j0 , j 0 构成半正组合构成半正组合 凸锥凸锥 j0 , j =0 构成凸组合构成凸组合 凸集凸集向量和子空间投影定理向量和子空间投影定理一、凸集一、凸集 1、凸集的概念：、凸集的概念：定理：定理：S是凸集是凸集S中任意有限点的凸组合属于中任意有

16、限点的凸组合属于Sl多胞形多胞形 H( (x(1) , x(2) , , x(m) ) )： 由由 x(1) , x(2) , , x(m) 的所有凸组合构成。的所有凸组合构成。l单纯形：若单纯形：若多胞形多胞形 H( (x(1) , x(2) , , x(m) ) )满足，满足， x(2)-x(1) , x(3) -x(1) , , x(m)- x(1) 线性无关。线性无关。多胞形多胞形单纯形单纯形单纯形单纯形向量和子空间投影定理向量和子空间投影定理一、凸集一、凸集 2、凸集的性质：、凸集的性质：l凸集的交集是凸集；凸集的交集是凸集；（并？）（并？）l凸集的内点集是凸集；凸集的内点集是凸集；

17、（逆命题是否成立？）（逆命题是否成立？）l凸集的闭包是凸集。凸集的闭包是凸集。 （逆命题是否成立？）（逆命题是否成立？）l分离与支撑：分离与支撑： 凸集边界上任意点存在支撑超平面凸集边界上任意点存在支撑超平面 两个互相不交的凸集之间存在分离超平面两个互相不交的凸集之间存在分离超平面支撑支撑强分离强分离分离分离非正常非正常分离分离向量和子空间投影定理向量和子空间投影定理一、凸集一、凸集 3、凸锥：、凸锥：l定义：定义：C Rn, 若若 x C, 0 有有 x C, 则称则称 C 是以是以 0 为顶点的锥。如果为顶点的锥。如果 C 还是凸集，则还是凸集，则称为凸锥。称为凸锥。l集合集合 0 、Rn

18、 是凸锥。是凸锥。l命题：命题：C是凸锥是凸锥C中任意有限点的半正组合属于中任意有限点的半正组合属于S0向量和子空间投影定理向量和子空间投影定理二、凸函数二、凸函数 1、凸函数及水平集、凸函数及水平集定义定义: 设集合设集合 S Rn 为凸集，函数为凸集，函数 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

19、上的严格凸函数。上的严格凸函数。l当当- f(x) 为凸函数（严格凸函数）时，则称为凸函数（严格凸函数）时，则称 f(x) 为为凹函数（严格凹函数）。凹函数（严格凹函数）。严格凸函数严格凸函数凸函数凸函数严格凹函数严格凹函数向量和子空间投影定理向量和子空间投影定理二、凸函数二、凸函数 1、凸函数及水平集：、凸函数及水平集：l定理：定理： f(x) 为凸集为凸集 S 上的凸函数上的凸函数 S 上任上任意有限点的凸组合的函数值不大于各点函意有限点的凸组合的函数值不大于各点函数值的凸组合。数值的凸组合。l思考：设思考：设f1, f2是凸函数，是凸函数，l设设 1, 2 0, 1f1+ 2f2 , 1

20、f1 - 2f2是否凸函是否凸函数？数？1)f(x)= max f1(x) , f2 (x) , g(x)= min f1(x) , f2 (x) 是否凸函数？是否凸函数？ 向量和子空间投影定理向量和子空间投影定理二、凸函数二、凸函数 1、凸函数及水平集：、凸函数及水平集：l定义：定义：设集合设集合 S Rn ，函数，函数 f :SR， R ， 称称 S = x S f(x) 为为 f(x) 在在 S 上上 的的 水平集水平集。l定理：定理：设集合设集合 S Rn 是凸集，函数是凸集，函数 f :SR是是凸函数，则对凸函数，则对 R ，S 是凸集是凸集。l注：注：l水平集的概念相当于在地形图中

21、，海拔高度不高于某一水平集的概念相当于在地形图中，海拔高度不高于某一数值的区域。数值的区域。l上述定理的逆不真。上述定理的逆不真。 考虑分段函数考虑分段函数f(x)=1(x0)或或0(x 0 充分小时有充分小时有 x*+ d S, 如果如果 lim f(x*+ d )-f(x*) / 存在（包括存在（包括 ） 则称则称 f(x) 为在点沿方向的方向导数存在，记为在点沿方向的方向导数存在，记 f (x*;d) = lim f(x*+ d )-f(x*) / 1)若若 f(x) 在在 x* 可导，则可导，则 f (x*;d) = f (x*) Td .向量和子空间投影定理向量和子空间投影定理二、凸

22、函数二、凸函数 2、凸函数的性质：、凸函数的性质：以下设以下设 S Rn 为非空凸集，函数为非空凸集，函数 f :SR2）若）若f 凸，则凸，则 f 在在 S 的内点集上连续；的内点集上连续； 注：注： f 在在 S 上不一定连续。上不一定连续。 例例: f(x)2(当当 x =1)； f(x)x2 (当当 x 0 , 总有总有 x + d S. d(1) = d(2) ( 0) 时，称时，称 d(1)和和d(2)同方向。同方向。4) 极方向：方向极方向：方向 d 不能表示为两个不同不能表示为两个不同方向的组合方向的组合 ( d = d(1)+d(2) ) .向量和子空间投影定理向量和子空间投

23、影定理多面体多面体 S = x Rn Ax = b , x0 的极点和极方向的极点和极方向定理定理1（极点特征）设（极点特征）设 A 满秩，满秩，x 是是 S 极极点的充分必要条件是点的充分必要条件是: 存在分解存在分解 A = B , N ，其中，其中B为为m阶非奇异矩阵，使阶非奇异矩阵，使 xT = xBT, xNT , 这里这里 xB = B-1b0, xN =0.lS中必存在有限多个极点。中必存在有限多个极点。( Cnm )向量和子空间投影定理向量和子空间投影定理多面体多面体 S = x Rn Ax = b , x0 的极点和极方向的极点和极方向定理定理2（极方向特征）（极方向特征）设

24、设 A = p1, p2, ,pn满秩，满秩，d 是是 S 极方向极方向的充分必要条件是的充分必要条件是: 存在分解存在分解 A = B , N ，其中，其中B为为m阶非奇异矩阵，对阶非奇异矩阵，对于于N中的列向量中的列向量 pj 使使 B-1pj0, dT = dBT, dNT , 这里这里 j dB = -B-1pj , dN = (0, . , 1, ,0)TlS中必存在有限多个极方向。中必存在有限多个极方向。( (n-m)Cnm )向量和子空间投影定理向量和子空间投影定理考虑多面体考虑多面体 S = x Rn Ax = b , x0 ，其中，其中 3 2 1 0 0 65 A = 2

25、1 0 1 0 b = 40 0 3 0 0 1 75 即即 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 0 例题例题向量和子空间投影定理向量和子空间投影定理 3 2 1 0 0A = = P1 , P2 , P3 , P4 , P5 = = 2 1 0 1 0 0 3 0 0 1 A A矩阵包含以下10个33的子矩阵： B B1 1=p p1 1 ，p p2 2 ，p p3 3 B B2 2=p p1 1 ，p p2 2 ，p p4 4 B B3 3=p p1 1 ，p p2

26、2 ，p p5 5 B B4 4=p p1 1 ，p p3 3 ，p p4 4 B B5 5=p p1 1 ，p p3 3 ，p p5 5 B B6 6=p p1 1 ，p p4 4 ，p p5 5 B B7 7=p p2 2 ，p p3 3 ，p p4 4 B B8 8=p p2 2 ，p p3 3 ，p p5 5 B B9 9=p p2 2 ，p p4 4 ，p p5 5 B B1010=p p3 3 ，p p4 4 ，p p5 5 例题例题 向量和子空间投影定理向量和子空间投影定理 其中其中 B B4 4 = 0= 0，因而，因而B B4 4不能构成极点和极方向。其余不能构成极点和极方向。其余均为非奇异方阵，因此该问题共有均为非奇异方阵，因此该问题共有9 9个可构成极点、个可构成极点、极方向的子矩阵，我们称之为基。极方向的子矩阵，我们称之为基。 对于基对于基B B3 3=p p1 1 ，p p2 2 ，p p5 5 ，令，令x x3 3 = 0= 0， x x4 4 = 0= 0，在等，在等式约束中令式约束中令x x3 3 = 0= 0，x x4 4 = 0= 0，解线性方程组：，解线性方程组： 3 3 x x1 1 + 2 + 2 x x2 2 + 0 + 0 x x5 5 = 65= 65