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

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

2、 表示從表示從x 點(diǎn)出發(fā)沿點(diǎn)出發(fā)沿d 方向方向移動(dòng)移動(dòng) d 長(zhǎng)度得到的點(diǎn)長(zhǎng)度得到的點(diǎn)d0 xx+(1/2)d向量和子空間投影定理向量和子空間投影定理1 1、向量和子空間投影定理、向量和子空間投影定理(2) (2) 向量運(yùn)算：向量運(yùn)算：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 的長(zhǎng)度：的長(zhǎng)度： x= xTx (1/2) 三角不等式三角不等式： x + y xy 點(diǎn)列的收斂：點(diǎn)列的收斂：設(shè)點(diǎn)列設(shè)點(diǎn)列x(k) R Rn n , ,

3、x R Rn n 點(diǎn)列點(diǎn)列x(k)收斂到收斂到 x ，記記lim x(k) = x limx(k)- x = 0 lim xi(k) = xi , ik k kx+yyx向量和子空間投影定理向量和子空間投影定理1 1、向量和子空間投影定理、向量和子空間投影定理(3) (3) 子空間：子空間：設(shè)設(shè) 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) 生成的子空間，簡(jiǎn)記為生成的子空間

4、，簡(jiǎn)記為L(zhǎng) L。l正交子空間：設(shè)正交子空間：設(shè) L 為為R Rn n的的子空間，其正交子空間為子空間，其正交子空間為 L x R Rn n xTy=0 , y L l子空間投影定理：子空間投影定理：設(shè)設(shè) L 為為R Rn n的的子空間。那么子空間。那么 x R Rn n， 唯一唯一 x L , y L , 使使 z=x+y , 且且 x 為問(wèn)題為問(wèn)題 min z - u s.t. u L 的唯一解，最優(yōu)值為的唯一解，最優(yōu)值為y。l特別，特別， L R Rn n 時(shí)，正交子空間時(shí)，正交子空間 L 0 （零空間零空間）向量和子空間投影定理向量和子空間投影定理l規(guī)定：規(guī)定：x , y R Rn n，

5、x y xi yi ， i 類(lèi)類(lèi)似規(guī)定似規(guī)定 x y，x = y，x y .l一個(gè)有用的定理一個(gè)有用的定理 設(shè)設(shè) 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時(shí)時(shí), ,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ù)及其導(dǎo)數(shù)、多元函數(shù)及其導(dǎo)數(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ù)及其導(dǎo)數(shù)、多元函數(shù)及其導(dǎo)數(shù)(2) (2) 梯度（一階偏導(dǎo)數(shù)向量）：梯度（一階偏導(dǎo)數(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ù)及其導(dǎo)數(shù)、多元函數(shù)及其導(dǎo)數(shù)(3) Hesse (3) Hesse 陣（二階偏導(dǎo)數(shù)矩陣）：陣（二階偏導(dǎo)數(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ù)及其導(dǎo)數(shù)、多元函數(shù)及其導(dǎo)數(shù)(4)(4)n n元函數(shù)的元函數(shù)的TaylorTaylor展開(kāi)式及中值公式：展開(kāi)式及中值公式： 設(shè)設(shè) f ( (x): ): R Rn n R R ，二階可導(dǎo)。在二階可導(dǎo)。在x* 的鄰域內(nèi)的鄰域內(nèi)l一階一階TaylorTaylor展開(kāi)式：展開(kāi)式： f (x) = f (x*)+ f T(x*)(x-x*) + ox-x*l二階二階TaylorTaylor展開(kāi)式：展開(kāi)式： f (x) = f (x*)+

10、f T(x)(x-x*) + (1/2)(x-x*)T 2f (x*)(x-x*) + ox-x*2l一階中值公式：對(duì)一階中值公式：對(duì)x, , , 使使 f (x) = f (x*)+ f (x*+ (x-x*)T(x-x*)lLagrange余項(xiàng)：余項(xiàng)：對(duì)對(duì)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ù)學(xué)規(guī)劃模型的一般形式數(shù)學(xué)規(guī)劃模型的一般形式 min min f(x) -目標(biāo)函數(shù)目標(biāo)函數(shù) s.t. s.t. x S -約

11、束集合，可行集約束集合，可行集其中，其中，S R Rn n，f : :S R R，x S稱(chēng)（稱(chēng)（f S ) )的可行解的可行解l最優(yōu)解最優(yōu)解: : x* S，滿足滿足f (x*) f (x), x S。則稱(chēng)則稱(chēng) x*為為( (f S) )的全局最優(yōu)解的全局最優(yōu)解( (最優(yōu)解最優(yōu)解),), 記記 g.opt.( (global optimum),),簡(jiǎn)記簡(jiǎn)記 opt.l最優(yōu)值最優(yōu)值: : x*為為( (f S) )的最優(yōu)解的最優(yōu)解, , 則稱(chēng)則稱(chēng) f * = f (x*) 為為 ( (f S) )的最優(yōu)值的最優(yōu)值( (最優(yōu)目標(biāo)函數(shù)值最優(yōu)目標(biāo)函數(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*) 。則稱(chēng)則稱(chēng) x*為為( (f S) )的局的局部最優(yōu)解部最優(yōu)解, ,記記 l .opt.( (local optimum) )l在上述定義中，當(dāng)在上述定義中，當(dāng)x x* 時(shí)有嚴(yán)格不等式成立，時(shí)有嚴(yán)格不等式成立，則則分別稱(chēng)分別稱(chēng) x* 為為( (f S) )的嚴(yán)格全局最優(yōu)解和嚴(yán)格局部最的嚴(yán)格全局最優(yōu)解和嚴(yán)格局部最優(yōu)解。優(yōu)解。嚴(yán)格嚴(yán)格l .opt .嚴(yán)格嚴(yán)格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 當(dāng)當(dāng) f(x), gi(x) , hj(x)均為線性函數(shù)時(shí)，稱(chēng)線性均為線性函數(shù)時(shí)，稱(chēng)線性規(guī)劃；若其中有非線性函數(shù)時(shí)，稱(chēng)非線性規(guī)劃。規(guī)劃；若其中有非線性函數(shù)時(shí)，稱(chēng)非線性規(guī)劃。向量和子空間投影定理向量和子空間投影定理一、凸集一、凸集1、凸集的概念：、凸集的

14、概念：定義：設(shè)集合定義：設(shè)集合 S Rn，若若 x(1), x(2) S, 0,1，必有必有 x(1)(1- ) x(2) S ，則稱(chēng)，則稱(chēng) S 為凸集。為凸集。規(guī)定：?jiǎn)吸c(diǎn)集規(guī)定：?jiǎn)吸c(diǎn)集 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凸組合：凸組合：設(shè)設(shè) x(1) , x(2) , , x(m) R Rn n, , j j 0 m m j =1, 那么稱(chēng)那么稱(chēng) j x(j) 為為x(1), x(2), , x(m)的的 j =1 j = 1凸組合。凸組合。 m比較比較: z = j x(j) j =1 j R 構(gòu)成線性組合構(gòu)成線性組合 線性子空間線性子空間 j0 , j 0 構(gòu)成半正組合構(gòu)成半正組合 凸錐凸錐 j0 , j =0 構(gòu)成凸組合構(gòu)成凸組合 凸集凸集向量和子空間投影定理向量和子空間投影定理一、凸集一、凸集 1、凸集的概念：、凸集的概念：定理：定理：S是凸集是凸集S中任意有限點(diǎn)的凸組合屬于中任意有

16、限點(diǎn)的凸組合屬于Sl多胞形多胞形 H( (x(1) , x(2) , , x(m) ) )： 由由 x(1) , x(2) , , x(m) 的所有凸組合構(gòu)成。的所有凸組合構(gòu)成。l單純形：若單純形：若多胞形多胞形 H( (x(1) , x(2) , , x(m) ) )滿足，滿足， x(2)-x(1) , x(3) -x(1) , , x(m)- x(1) 線性無(wú)關(guān)。線性無(wú)關(guān)。多胞形多胞形單純形單純形單純形單純形向量和子空間投影定理向量和子空間投影定理一、凸集一、凸集 2、凸集的性質(zhì)：、凸集的性質(zhì)：l凸集的交集是凸集；凸集的交集是凸集；（并？）（并？）l凸集的內(nèi)點(diǎn)集是凸集；凸集的內(nèi)點(diǎn)集是凸集；

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

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

19、上的嚴(yán)格凸函數(shù)。上的嚴(yán)格凸函數(shù)。l當(dāng)當(dāng)- f(x) 為凸函數(shù)（嚴(yán)格凸函數(shù)）時(shí)，則稱(chēng)為凸函數(shù)（嚴(yán)格凸函數(shù)）時(shí)，則稱(chēng) f(x) 為為凹函數(shù)（嚴(yán)格凹函數(shù)）。凹函數(shù)（嚴(yán)格凹函數(shù)）。嚴(yán)格凸函數(shù)嚴(yán)格凸函數(shù)凸函數(shù)凸函數(shù)嚴(yán)格凹函數(shù)嚴(yán)格凹函數(shù)向量和子空間投影定理向量和子空間投影定理二、凸函數(shù)二、凸函數(shù) 1、凸函數(shù)及水平集：、凸函數(shù)及水平集：l定理：定理： f(x) 為凸集為凸集 S 上的凸函數(shù)上的凸函數(shù) S 上任上任意有限點(diǎn)的凸組合的函數(shù)值不大于各點(diǎn)函意有限點(diǎn)的凸組合的函數(shù)值不大于各點(diǎn)函數(shù)值的凸組合。數(shù)值的凸組合。l思考：設(shè)思考：設(shè)f1, f2是凸函數(shù)，是凸函數(shù)，l設(shè)設(shè) 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定義：定義：設(shè)集合設(shè)集合 S Rn ，函數(shù)，函數(shù) f :SR， R ， 稱(chēng)稱(chēng) S = x S f(x) 為為 f(x) 在在 S 上上 的的 水平集水平集。l定理：定理：設(shè)集合設(shè)集合 S Rn 是凸集，函數(shù)是凸集，函數(shù) f :SR是是凸函數(shù)，則對(duì)凸函數(shù)，則對(duì) R ，S 是凸集是凸集。l注：注：l水平集的概念相當(dāng)于在地形圖中

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

22、函數(shù)二、凸函數(shù) 2、凸函數(shù)的性質(zhì)：、凸函數(shù)的性質(zhì)：以下設(shè)以下設(shè) S Rn 為非空凸集，函數(shù)為非空凸集，函數(shù) f :SR2）若）若f 凸，則凸，則 f 在在 S 的內(nèi)點(diǎn)集上連續(xù)；的內(nèi)點(diǎn)集上連續(xù)； 注：注： f 在在 S 上不一定連續(xù)。上不一定連續(xù)。 例例: f(x)2(當(dāng)當(dāng) x =1)； f(x)x2 (當(dāng)當(dāng) x 0 , 總有總有 x + d S. d(1) = d(2) ( 0) 時(shí)，稱(chēng)時(shí)，稱(chēng) d(1)和和d(2)同方向。同方向。4) 極方向：方向極方向：方向 d 不能表示為兩個(gè)不同不能表示為兩個(gè)不同方向的組合方向的組合 ( d = d(1)+d(2) ) .向量和子空間投影定理向量和子空間投

23、影定理多面體多面體 S = x Rn Ax = b , x0 的極點(diǎn)和極方向的極點(diǎn)和極方向定理定理1（極點(diǎn)特征）設(shè)（極點(diǎn)特征）設(shè) A 滿秩，滿秩，x 是是 S 極極點(diǎn)的充分必要條件是點(diǎn)的充分必要條件是: 存在分解存在分解 A = B , N ，其中，其中B為為m階非奇異矩陣，使階非奇異矩陣，使 xT = xBT, xNT , 這里這里 xB = B-1b0, xN =0.lS中必存在有限多個(gè)極點(diǎn)。中必存在有限多個(gè)極點(diǎn)。( Cnm )向量和子空間投影定理向量和子空間投影定理多面體多面體 S = x Rn Ax = b , x0 的極點(diǎn)和極方向的極點(diǎn)和極方向定理定理2（極方向特征）（極方向特征）設(shè)

24、設(shè) A = p1, p2, ,pn滿秩，滿秩，d 是是 S 極方向極方向的充分必要條件是的充分必要條件是: 存在分解存在分解 A = B , N ，其中，其中B為為m階非奇異矩陣，對(duì)階非奇異矩陣，對(duì)于于N中的列向量中的列向量 pj 使使 B-1pj0, dT = dBT, dNT , 這里這里 j dB = -B-1pj , dN = (0, . , 1, ,0)TlS中必存在有限多個(gè)極方向。中必存在有限多個(gè)極方向。( (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個(gè)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(niǎo) B4 4不能構(gòu)成極點(diǎn)和極方向。其余不能構(gòu)成極點(diǎn)和極方向。其余均為非奇異方陣，因此該問(wèn)題共有均為非奇異方陣，因此該問(wèn)題共有9 9個(gè)可構(gòu)成極點(diǎn)、個(gè)可構(gòu)成極點(diǎn)、極方向的子矩陣，我們稱(chēng)之為基。極方向的子矩陣，我們稱(chēng)之為基。 對(duì)于基對(duì)于基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