向量和子空間投影定理課件

1、向量和子空間投影定理向量和子空間投影定理基本概念基本概念和和基本理論基本理論 整理發(fā)布向量和子空間投影定理向量和子空間投影定理1 1、向量和子空間投影定理、向量和子空間投影定理(1) (1) n n維歐氏空間：維歐氏空間：R Rn n 點（向量）點（向量）：x R Rn n, , x = ( = (x1 , ,x2 , , ,xn) )T T 分量分量 xi R R ( (實數(shù)集實數(shù)集) ) 方向（自由向量）方向（自由向量）：d R Rn n, , d 0 d =(=(d1 , ,d2 , , ,dn) )T T 表示從表示從0 0指向指向d 的方向的方向 實用中，常用實用中，常用 x + d

2、 表示從表示從x 點出發(fā)沿點出發(fā)沿d 方向方向移動移動 d 長度得到的點長度得到的點d0 xx+(1/2)d向量和子空間投影定理向量和子空間投影定理1 1、向量和子空間投影定理、向量和子空間投影定理(2) (2) 向量運算：向量運算：x , y R Rn n n x , y 的內(nèi)積：的內(nèi)積：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ōu)值為的唯一解，最優(yōu)值為y。l特別，特別， L R Rn n 時，正交子空間時，正交子空間 L 0 （零空間零空間）向量和子空間投影定理向量和子空間投影定理l規(guī)定：規(guī)定：x , y R Rn n，

5、x y xi yi ， i 類類似規(guī)定似規(guī)定 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、多元函數(shù)及其導數(shù)、多元函數(shù)及其導數(shù)(1) (1) n n元函數(shù)：元函數(shù)：f ( (x): ): R Rn n R R 線性函數(shù)線性函數(shù)：f (x) = cTx + b = ci xi + b 二次函數(shù)二次函數(shù)：f (x) = (1/2) xTQx + cTx + b = (1/2) i j aij xi xj + ci xi + b 向量值線性函數(shù)：向量值線性函數(shù)：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、多元函數(shù)及其導數(shù)、多元函數(shù)及其導數(shù)(2) (2) 梯度（一階偏導數(shù)向量）：梯度（一階偏導數(shù)向量）： f ( (x) )( ( f / x1 , f / x2 , , f / xn ) )T T R Rn n . . 線性函數(shù)線性函數(shù)：f (x) = cTx + b , f (x) = c 二次函數(shù)二次函數(shù)：f (x) = (1/

8、2) xTQx + cTx + b f (x) = Qx + c 向量值線性函數(shù)：向量值線性函數(shù)：F(x) = Ax + d R Rm m F / x = AT向量和子空間投影定理向量和子空間投影定理2 2、多元函數(shù)及其導數(shù)、多元函數(shù)及其導數(shù)(3) Hesse (3) Hesse 陣（二階偏導數(shù)矩陣）：陣（二階偏導數(shù)矩陣）： 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 線性函數(shù)線性函數(shù)：f (x) = cTx + b , 2f

9、 (x) = 0 二次函數(shù)二次函數(shù)：f (x) = (1/2) xTQx + cTx + b, 2f (x)=Q向量和子空間投影定理向量和子空間投影定理2 2、多元函數(shù)及其導數(shù)、多元函數(shù)及其導數(shù)(4)(4)n n元函數(shù)的元函數(shù)的TaylorTaylor展開式及中值公式：展開式及中值公式： 設設 f ( (x): ): R Rn n R R ，二階可導。在二階可導。在x* 的鄰域內(nèi)的鄰域內(nèi)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 數(shù)學規(guī)劃模型的一般形式數(shù)學規(guī)劃模型的一般形式 min min f(x) -目標函數(shù)目標函數(shù) s.t. s.t. x S -約

11、束集合，可行集約束集合，可行集其中，其中，S R Rn n，f : :S R R，x S稱（稱（f S ) )的可行解的可行解l最優(yōu)解最優(yōu)解: : x* S，滿足滿足f (x*) f (x), x S。則稱則稱 x*為為( (f S) )的全局最優(yōu)解的全局最優(yōu)解( (最優(yōu)解最優(yōu)解),), 記記 g.opt.( (global optimum),),簡記簡記 opt.l最優(yōu)值最優(yōu)值: : x*為為( (f S) )的最優(yōu)解的最優(yōu)解, , 則稱則稱 f * = f (x*) 為為 ( (f S) )的最優(yōu)值的最優(yōu)值( (最優(yōu)目標函數(shù)值最優(yōu)目標函數(shù)值) )( f S )向量和子空間投影定理向量和子空

12、間投影定理l局部最優(yōu)解局部最優(yōu)解: : x* S， x* 的鄰域的鄰域 N(x*) ，使?jié)M足，使?jié)M足 f (x*) f (x), x S N(x*) 。則稱則稱 x*為為( (f S) )的局的局部最優(yōu)解部最優(yōu)解, ,記記 l .opt.( (local optimum) )l在上述定義中，當在上述定義中，當x x* 時有嚴格不等式成立，時有嚴格不等式成立，則則分別稱分別稱 x* 為為( (f S) )的嚴格全局最優(yōu)解和嚴格局部最的嚴格全局最優(yōu)解和嚴格局部最優(yōu)解。優(yōu)解。嚴格嚴格l .opt .嚴格嚴格g .opt .l .opt .向量和子空間投影定理向量和子空間投影定理l函數(shù)形式函數(shù)形式:

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)均為線性函數(shù)時，稱線性均為線性函數(shù)時，稱線性規(guī)劃；若其中有非線性函數(shù)時，稱非線性規(guī)劃。規(guī)劃；若其中有非線性函數(shù)時，稱非線性規(guī)劃。向量和子空間投影定理向量和子空間投影定理一、凸集一、凸集1、凸集的概念：、凸集的

14、概念：定義：設集合定義：設集合 S Rn，若若 x(1), x(2) S, 0,1，必有必有 x(1)(1- ) x(2) S ，則稱，則稱 S 為凸集。為凸集。規(guī)定：單點集規(guī)定：單點集 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凸集的內(nèi)點集是凸集；凸集的內(nèi)點集是凸集；

17、（逆命題是否成立？）（逆命題是否成立？）l凸集的閉包是凸集。凸集的閉包是凸集。 （逆命題是否成立？）（逆命題是否成立？）l分離與支撐：分離與支撐： 凸集邊界上任意點存在支撐超平面凸集邊界上任意點存在支撐超平面 兩個互相不交的凸集之間存在分離超平面兩個互相不交的凸集之間存在分離超平面支撐支撐強分離強分離分離分離非正常非正常分離分離向量和子空間投影定理向量和子空間投影定理一、凸集一、凸集 3、凸錐：、凸錐：l定義：定義：C Rn, 若若 x C, 0 有有 x C, 則稱則稱 C 是以是以 0 為頂點的錐。如果為頂點的錐。如果 C 還是凸集，則還是凸集，則稱為凸錐。稱為凸錐。l集合集合 0 、Rn

18、 是凸錐。是凸錐。l命題：命題：C是凸錐是凸錐C中任意有限點的半正組合屬于中任意有限點的半正組合屬于S0向量和子空間投影定理向量和子空間投影定理二、凸函數(shù)二、凸函數(shù) 1、凸函數(shù)及水平集、凸函數(shù)及水平集定義定義: 設集合設集合 S Rn 為凸集，函數(shù)為凸集，函數(shù) 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 上的凸函數(shù)。上的凸函數(shù)。 若進一步有上面不等式以嚴格不等式成立，則若進一步有上面不等式以嚴格不等式成立，則稱稱 f(x) 為凸集為凸集 S

19、上的嚴格凸函數(shù)。上的嚴格凸函數(shù)。l當當- f(x) 為凸函數(shù)（嚴格凸函數(shù)）時，則稱為凸函數(shù)（嚴格凸函數(shù)）時，則稱 f(x) 為為凹函數(shù)（嚴格凹函數(shù)）。凹函數(shù)（嚴格凹函數(shù)）。嚴格凸函數(shù)嚴格凸函數(shù)凸函數(shù)凸函數(shù)嚴格凹函數(shù)嚴格凹函數(shù)向量和子空間投影定理向量和子空間投影定理二、凸函數(shù)二、凸函數(shù) 1、凸函數(shù)及水平集：、凸函數(shù)及水平集：l定理：定理： f(x) 為凸集為凸集 S 上的凸函數(shù)上的凸函數(shù) S 上任上任意有限點的凸組合的函數(shù)值不大于各點函意有限點的凸組合的函數(shù)值不大于各點函數(shù)值的凸組合。數(shù)值的凸組合。l思考：設思考：設f1, f2是凸函數(shù)，是凸函數(shù)，l設設 1, 2 0, 1f1+ 2f2 , 1

20、f1 - 2f2是否凸函是否凸函數(shù)？數(shù)？1)f(x)= max f1(x) , f2 (x) , g(x)= min f1(x) , f2 (x) 是否凸函數(shù)？是否凸函數(shù)？ 向量和子空間投影定理向量和子空間投影定理二、凸函數(shù)二、凸函數(shù) 1、凸函數(shù)及水平集：、凸函數(shù)及水平集：l定義：定義：設集合設集合 S Rn ，函數(shù)，函數(shù) f :SR， R ， 稱稱 S = x S f(x) 為為 f(x) 在在 S 上上 的的 水平集水平集。l定理：定理：設集合設集合 S Rn 是凸集，函數(shù)是凸集，函數(shù) f :SR是是凸函數(shù)，則對凸函數(shù)，則對 R ，S 是凸集是凸集。l注：注：l水平集的概念相當于在地形圖中

21、，海拔高度不高于某一水平集的概念相當于在地形圖中，海拔高度不高于某一數(shù)值的區(qū)域。數(shù)值的區(qū)域。l上述定理的逆不真。上述定理的逆不真。 考慮分段函數(shù)考慮分段函數(shù)f(x)=1(x0)或或0(x 0 充分小時有充分小時有 x*+ d S, 如果如果 lim f(x*+ d )-f(x*) / 存在（包括存在（包括 ） 則稱則稱 f(x) 為在點沿方向的方向導數(shù)存在，記為在點沿方向的方向導數(shù)存在，記 f (x*;d) = lim f(x*+ d )-f(x*) / 1)若若 f(x) 在在 x* 可導，則可導，則 f (x*;d) = f (x*) Td .向量和子空間投影定理向量和子空間投影定理二、凸

22、函數(shù)二、凸函數(shù) 2、凸函數(shù)的性質：、凸函數(shù)的性質：以下設以下設 S Rn 為非空凸集，函數(shù)為非空凸集，函數(shù) f :SR2）若）若f 凸，則凸，則 f 在在 S 的內(nèi)點集上連續(xù)；的內(nèi)點集上連續(xù)； 注：注： f 在在 S 上不一定連續(xù)。上不一定連續(xù)。 例例: 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