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

1、第 二 章,基本概念 和 基本理論, 整理發(fā)布,2.0、預(yù)備知識,1、向量和子空間投影定理 (1) n維歐氏空間：Rn 點（向量）：x Rn, x = (x1 ,x2 ,xn)T 分量 xi R (實數(shù)集) 方向（自由向量）：d Rn, d 0 d =(d1 ,d2 ,dn)T 表示從0指向d 的方向 實用中，常用 x + d 表示從x 點出發(fā)沿d 方向移動d 長度得到的點,d,0,x,x+(1/2)d,2.0、預(yù)備知識（續(xù)）,1、向量和子空間投影定理 (2) 向量運算：x , y Rn n x , y 的內(nèi)積：xTy = xiyi = x1y1+ x2y2+ + xnyn i =1 x ,

2、y 的距離： x-y = (x-y)T(x-y)(1/2) x 的長度： x= xTx (1/2) 三角不等式： x + y xy 點列的收斂：設(shè)點列x(k) Rn , x Rn 點列x(k)收斂到 x ，記 lim x(k) = x limx(k)- x = 0 lim xi(k) = xi ,i k k k,x+y,y,x,2.0、預(yù)備知識（續(xù)）,1、向量和子空間投影定理 (3) 子空間：設(shè) d (1) , d (2) , , d (m) Rn, d (k) 0 m 記 L( d (1) , d (2) , , d (m) )= x = j d (j) jR j =1 為由向量d (1)

3、, d (2) , , d (m) 生成的子空間，簡記為L。 正交子空間：設(shè) L 為Rn的子空間，其正交子空間為 L x Rn xTy=0 , y L 子空間投影定理：設(shè) L 為Rn的子空間。那么 x Rn， 唯一 x L , y L, 使 z=x+y , 且 x 為問題 min z - u s.t. u L 的唯一解，最優(yōu)值為y。 特別， L Rn 時，正交子空間 L 0 （零空間）,2.0、預(yù)備知識（續(xù)）,規(guī)定：x , y Rn，x y xi yi ，i 類似規(guī)定 x y，x = y，x y . 一個有用的定理 設(shè) xRn，R，L為Rn 的線性子空間， (1)若 xTy , yRn 且 y

4、 0， 則 x 0， 0 . (2)若 xTy , y L Rn ， 則 x L， 0 .(特別, LRn時,x =0) 定理的其他形式： “若 xTy , yRn 且 y 0，則 x 0， 0 .” “若 xTy , yRn 且 y 0，則 x 0， 0 .” “若 xTy , yRn 且 y 0，則 x 0， 0 .” “若 xTy , y L Rn ， 則 x L， 0 .”,2.0、預(yù)備知識（續(xù)）,2、多元函數(shù)及其導(dǎo)數(shù) (1) n元函數(shù)：f (x): Rn R 線性函數(shù)：f (x) = cTx + b = ci xi + b 二次函數(shù)：f (x) = (1/2) xTQx + cTx

5、+ b = (1/2)i j aij xi xj + ci xi + b 向量值線性函數(shù)：F(x) = Ax + d Rm 其中 A為 mn矩陣，d為m維向量 F(x)=( f1(x), f2(x), , fm(x) )T 記 aiT為A的第i行向量，fi (x) = aiTx,2.0、預(yù)備知識（續(xù)）,2、多元函數(shù)及其導(dǎo)數(shù) (2) 梯度（一階偏導(dǎo)數(shù)向量）： f (x)( f / x1 , f / x2 , , f / xn )TRn . 線性函數(shù)：f (x) = cTx + b , f (x) = c 二次函數(shù)：f (x) = (1/2) xTQx + cTx + b f (x) = Qx +

6、 c 向量值線性函數(shù)：F(x) = Ax + d Rm F / x = AT,2.0、預(yù)備知識（續(xù)）,2、多元函數(shù)及其導(dǎo)數(shù) (3) Hesse 陣（二階偏導(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ù)：f (x) = cTx + b , 2f (x) = 0 二次函數(shù)：f (x) = (1/2) xTQx + cTx + b, 2f (x)=Q,2.0、預(yù)備知識（續(xù)）,2、多元函數(shù)及其導(dǎo)數(shù) (4)n元函數(shù)的Taylor展開式及中值公式

7、： 設(shè) f (x): Rn R ，二階可導(dǎo)。在x* 的鄰域內(nèi) 一階Taylor展開式： f (x) = f (x*)+ f T(x*)(x-x*) + ox-x* 二階Taylor展開式： f (x) = f (x*)+ f T(x)(x-x*) + (1/2)(x-x*)T 2f (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*)+ f T(x)(x-x*) + (1/2)(x-x*)T 2f (x )(x-x*)

8、,2.1 數(shù)學(xué)規(guī)劃模型的一般形式 min f(x) -目標函數(shù) s.t. xS -約束集合，可行集 其中，S Rn，f :S R，xS稱（f S )的可行解 最優(yōu)解: x*S，滿足f (x*) f (x), xS。則稱 x*為(f S)的全局最優(yōu)解(最優(yōu)解), 記 g.opt.(global optimum),簡記 opt. 最優(yōu)值: x*為(f S)的最優(yōu)解, 則稱 f * = f (x*) 為 (f S)的最優(yōu)值(最優(yōu)目標函數(shù)值),( f S ),2.1 數(shù)學(xué)規(guī)劃模型的一般形式（續(xù)）,局部最優(yōu)解: x*S， x* 的鄰域 N(x*) ，使?jié)M足 f (x*) f (x), x S N(x*)

9、 。則稱 x*為(f S)的局部最優(yōu)解,記 l .opt.(local optimum) 在上述定義中，當x x* 時有嚴格不等式成立，則分別稱 x* 為(f S)的嚴格全局最優(yōu)解和嚴格局部最優(yōu)解。,嚴格l .opt .,嚴格g .opt .,l .opt .,2.1 數(shù)學(xué)規(guī)劃模型的一般形式（續(xù)）,函數(shù)形式: 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,l 矩陣形式: min f(x) ，f(x) : RnR (fgh) s.t. g(x) 0 , g(x) : Rn

10、Rm h(x) = 0 , h(x) : RnRl 當 f(x), gi(x) , hj(x)均為線性函數(shù)時，稱線性規(guī)劃；若其中有非線性函數(shù)時，稱非線性規(guī)劃。,2.2 凸集、凸函數(shù)和凸規(guī)劃,一、凸集 1、凸集的概念： 定義：設(shè)集合 S Rn，若x(1), x(2)S, 0,1，必有 x(1)(1- ) x(2) S ，則稱 S 為凸集。 規(guī)定：單點集 x 為凸集，空集為凸集。 注: x(1)(1- ) x(2) = x(2)(x(1)- x(2) 是連接 x(1)與x(2)的線段 。,凸集,非凸集,非凸集,2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),一、凸集 1、凸集的概念： 例:證明集合 S = x

11、Ax = b 是凸集。其中，A為 mn矩陣，b為m維向量。 凸組合：設(shè) x(1) , x(2) , , x(m) Rn, 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 jR 構(gòu)成線性組合 線性子空間 j0 , j 0 構(gòu)成半正組合 凸錐 j0 , j =0 構(gòu)成凸組合 凸集,2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),一、凸集 1、凸集的概念： 定理：S是凸集S中任意有限點的凸組合屬于S 多胞形 H(x(1) , x(2) , , x(m) )： 由 x(1) , x(2) , ,

12、 x(m) 的所有凸組合構(gòu)成。 單純形：若多胞形 H(x(1) , x(2) , , x(m) )滿足， x(2)-x(1) , x(3) -x(1) , , x(m)- x(1) 線性無關(guān)。,多胞形,單純形,單純形,2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),一、凸集 2、凸集的性質(zhì)： 凸集的交集是凸集；（并？） 凸集的內(nèi)點集是凸集；（逆命題是否成立？） 凸集的閉包是凸集。 （逆命題是否成立？） 分離與支撐： 凸集邊界上任意點存在支撐超平面 兩個互相不交的凸集之間存在分離超平面,支撐,強分離,分離,非正常分離,2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),一、凸集 3、凸錐： 定義：C Rn, 若 x C,

13、0 有 x C, 則稱 C 是以 0 為頂點的錐。如果 C 還是凸集，則稱為凸錐。 集合 0 、Rn 是凸錐。 命題：C是凸錐C中任意有限點的半正組合屬于S,0,2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),二、凸函數(shù) 1、凸函數(shù)及水平集 定義: 設(shè)集合 S Rn 為凸集，函數(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ù)。 若進一步有上面不等式以嚴格不等式成立，則稱 f(x) 為凸集 S 上的嚴格凸函數(shù)。 當- f(x) 為凸函數(shù)（嚴格凸函數(shù)）時，則稱 f(

14、x) 為凹函數(shù)（嚴格凹函數(shù)）。,嚴格凸函數(shù),凸函數(shù),嚴格凹函數(shù),2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),二、凸函數(shù) 1、凸函數(shù)及水平集： 定理： f(x) 為凸集 S 上的凸函數(shù) S 上任意有限點的凸組合的函數(shù)值不大于各點函數(shù)值的凸組合。 思考：設(shè)f1, f2是凸函數(shù)， 設(shè)1, 2 0, 1f1+2f2 , 1f1 - 2f2是否凸函數(shù)？ f(x)= max f1(x) , f2 (x) , g(x)= min f1(x) , f2 (x) 是否凸函數(shù)？,2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),二、凸函數(shù) 1、凸函數(shù)及水平集： 定義：設(shè)集合 S Rn ，函數(shù) f :SR， R ， 稱 S = x Sf

15、(x) 為 f(x) 在 S 上 的 水平集。 定理：設(shè)集合 S Rn 是凸集，函數(shù) f :SR是凸函數(shù)，則對 R ，S 是凸集。 注： 水平集的概念相當于在地形圖中，海拔高度不高于某一數(shù)值的區(qū)域。 上述定理的逆不真。 考慮分段函數(shù)f(x)=1(x0)或0(x0)，函數(shù)非凸，但任意水平集是凸集。,2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),二、凸函數(shù) 2、凸函數(shù)的性質(zhì)： 方向?qū)?shù)：設(shè) S Rn 為非空凸集，函數(shù) f :SR ，再設(shè) x* S, d 為方向，使當 0 充分小時有 x*+d S, 如果 lim f(x*+ d )-f(x*) / 存在（包括 ） 則稱 f(x) 為在點沿方向的方向?qū)?shù)存在，

16、記 f (x*;d) = lim f(x*+ d )-f(x*) / 若 f(x) 在 x* 可導(dǎo)，則 f (x*;d) = f (x*) Td .,2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),二、凸函數(shù) 2、凸函數(shù)的性質(zhì)： 以下設(shè) S Rn 為非空凸集，函數(shù) f :SR 2）若f 凸，則 f 在 S 的內(nèi)點集上連續(xù)； 注： f 在 S 上不一定連續(xù)。 例: f(x)2(當x=1)； f(x)x2 (當x1) . 3）設(shè)f 凸，則對任意方向方向?qū)?shù)存在。 4）設(shè) S 是開集，f 在 S 上可微，則 f凸 x*S，有f (x) f (x*)+ f T(x*)(x-x*) , x S . 5) 設(shè) S 是

17、開集，f 在 S 上二次可微，則 a) f 凸 xS，2f (x) 半正定； b) 若 xS，2f (x) 正定，則f嚴格凸。,2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),二、凸函數(shù) 2、凸函數(shù)的性質(zhì)： 例： f(x)x12+2x1x2+2x22+10 x1 - 4 ； f(x)-3x12+x1x2-x22-2x32-2x2x3+26 ; f(x)3x12+ax1x2+2x22-4x1+6 ( a=5, 4.5 )；,2.2 凸集、凸函數(shù)和凸規(guī)劃(續(xù)),三、凸規(guī)劃： 當（f S）中，S為凸集，f是S上的凸函數(shù)（求min），稱（f S）為凸規(guī)劃； 對于（fgh）, f,gi為凸函數(shù)，hj為線性函數(shù)時，（

18、fgh）為凸規(guī)劃。 定理：設(shè)集合 S Rn 為凸集，函數(shù) f :SR f(x) 為凸集 S 上的凸函數(shù)。X*為問題（fs）的l.opt，則X*為g.opt；又如果f是嚴格凸函數(shù)，那么X*是（fs）的唯一g.opt。,2.3 多面體、極點、極方向,1）多面體：有限個半閉空間的交 例：S = xRnAx = b , x0 ,2.3 多面體、極點、極方向,2) 多面體的極點（頂點）： xS，不存在 S 中的另外兩個點x(1)和x(2)，及 (0,1)，使 x = x(1)+(1-)x(2). 3) 方向：xS , dRn , d 0 及 0 , 總有 x + d S. d(1) = d(2) ( 0

19、) 時，稱 d(1)和d(2)同方向。 4) 極方向：方向 d 不能表示為兩個不同方向的組合 ( d = d(1)+d(2) ) .,2.3 多面體、極點、極方向,多面體 S = xRnAx = b , x0 的極點和極方向 定理1（極點特征）設(shè) 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（極方向特征） 設(shè) A = p1

20、, p2, ,pn滿秩，d 是 S 極方向的充分必要條件是: 存在分解 A = B , N ，其中B為m階非奇異矩陣，對于N中的列向量 pj 使 B-1pj0, dT = dBT, dNT , 這里 j dB = -B-1pj , dN = (0, . , 1, ,0)T S中必存在有限多個極方向。( (n-m)Cnm ),考慮多面體 S = xRnAx = b , x0 ，其中 3 2 1 0 0 65 A = 2 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

21、 , x2 , x3 , x4 , x5 0,例題,3 2 1 0 0 A = P1 , P2 , P3 , P4 , P5 = 2 1 0 1 0 0 3 0 0 1 A矩陣包含以下10個33的子矩陣： B1=p1 ，p2 ，p3 B2=p1 ，p2 ，p4 B3=p1 ，p2 ，p5 B4=p1 ，p3 ，p4 B5=p1 ，p3 ，p5 B6=p1 ，p4 ，p5 B7=p2 ，p3 ，p4 B8=p2 ，p3 ，p5 B9=p2 ，p4 ，p5 B10=p3 ，p4 ，p5,例題,其中B4= 0，因而B4不能構(gòu)成極點和極方向。其余均為非奇異方陣，因此該問題共有9個可構(gòu)成極點、極方向的子矩陣，我們稱之為基。 對于基B3=p1 ，p2 ，p5，令x3 = 0， x4 = 0，在