凸集與凸函數(shù)

1、凸集與凸函數(shù)第一頁，共39頁。2. 凸集與凸函數(shù)則一個仿射集的平移也是仿射集Th2.1 (1)Rn的子空間是包含原點的仿射集;(2),對每一非空的仿射集M,存在唯一的子空間L和向量aRn,使得nMa M+ax+a|x n設(shè),M相對于a的平移為M約定 M-a=M+(-a)若aM,則M-a是子空間.|MLaxa xL第二頁，共39頁。2. 凸集與凸函數(shù)若非空仿射集M=L+a,則aM,于是唯一子空間L可表為Df2.2. 非空仿射集非空仿射集M的維數(shù)是指平行于仿射集的維數(shù)是指平行于仿射集M的子空間的維數(shù)的子空間的維數(shù).nTnTTHLLLLaM,MLaxa| x p0y|p yp a nT設(shè) 為一超平面

2、,子空間 平行于H,則 的正交補空間是一維的.不妨設(shè)p0是的一個基,則L=x|x p=0,有| ,LMMxy x yMRn中的n-1維仿射集稱為超平面超平面.第三頁，共39頁。2. 凸集與凸函數(shù)Th2.2 給定向量p(0)Rn,R,則是Rn中的一個超平面.反之,Rn任一超平面都可表成上式的形式,且在相差一個非零常數(shù)的意義下,(p,)是唯一的.m nnnnnTh2.3A,b,Mx|Axb(Axb)(2.2).,(2.2),. 給定矩陣向量則 簡記為 是中的一仿射集反之中的每一仿射集都可表成式的形式 即一組超平面的交集| (2.1)nTHxp x第四頁，共39頁。2. 凸集與凸函數(shù)可驗證,仿射集的

3、交集仍是仿射集仿射集的交集仍是仿射集Df2.3 給定Rn中集合S,包含S的所有仿射集的交集,即包含S的最小仿射集稱為S的仿射包,記為affS11,|1,1,., ,kkiiiiiiiSaffSxR xS ik k 可證的仿射包12121(,.,),( ,.,) |.1,2,., TTmmTiiimiiAa aabb bbHx a xbimMH 若記 則第五頁，共39頁。2. 凸集與凸函數(shù)Df2.1 Rn中任一集合S的維數(shù)定義為它的仿射包affS的維數(shù),即包含S的仿射集的最小維數(shù).0101012.51,.,.,.mmmDfmxxxxxxmaff xxxm 由個向量組成的向量組稱為是仿射無關(guān)的 是

4、指集合的維數(shù)為即仿射包維數(shù)是 .010010010010,.0,.,.,.mmmmaff xxxLxLaffxxxxxxxxLmxxxx一般,有限點集的仿射包,是包含的最小子空間的維數(shù)是線性無關(guān)第六頁，共39頁。2. 凸集與凸函數(shù)命題2.1 下述斷言相互等價.01001011(1),.,;(2),.,(,1),(,1),.(,1)nmnmnmxxxxxxxxxx 中的向量組仿射無關(guān)中的向量組線性無關(guān);(3)中的向量組線性無關(guān).0110001010101010101,.,().() =.(1),.,(,.,)(,.,).mmmmmmiimmmMaff xxxLMxM xxxxxxxxxxxxxM

5、xxx 設(shè)仿射集, 是平行于的子空間 則其中表示式唯一仿射無關(guān);此時,稱為相對于向量組的重心坐標第七頁，共39頁。2. 凸集與凸函數(shù)2.6 ,( )-( ),.,.,.nDfSxS NxxNxaffSSxSSriSriSSSclS riSSrbS設(shè)是非空集合表示 的鄰域。若則 稱為 的一個相對內(nèi)點 的相對內(nèi)點的全體稱為它的相對內(nèi)部 記為 若則 稱為一個相對開集集合稱為的相對邊界 記為01,.,.mxxxM仿射無關(guān)向量組稱為仿射集的一個重心坐標系第八頁，共39頁。2. 凸集與凸函數(shù)2.2 凸集與錐凸集與錐2.7 DfSn(1)(2)(1)(2)(1)(2)(1)(2)n設(shè) 為 維歐氏空間中的一個

6、集合。若對任意兩點x ,xS及每個實數(shù)0,1,有x +(1- )xS則稱S為凸集。 x +(1- )x 稱為x 和x 的凸組合。第九頁，共39頁。2. 凸集與凸函數(shù)T+T-T+T-T2.3 H=x p x= pnpH =x p xH =x p x H =x p xH =x p x 例超平面為凸集，其中 為 維列向量， 為實數(shù)。此外,下面相對于法向量 的半空間都是凸集: 正的閉半空間 負的閉半空間正的開半空間 負的開半空間第十頁，共39頁。2. 凸集與凸函數(shù)x0 xx-x0px0 xx-x0p(0)(0)2.4 L=x x=xd0dx 例集合，為凸集，其中 為給定的非零向量，為定點。(0)(0)

7、L=x x=xd0 x 集合,稱為射線,為射線的頂點第十一頁，共39頁。2. 凸集與凸函數(shù)111112.8,.,1,1,.,. ,.,mmniiimmmDfmxxR imxxxx 給定 個向量以及滿足的非負實數(shù)稱向量為的凸組合.11112.41,2,.,.,.,1,0,1,., .nmnmmmiiiThSSmxxxxSR im + 集合是凸集,當且僅當 包含其中任意有限個元素的凸組合,即對任意的有其中第十二頁，共39頁。運用定義不難驗證如下命題：2. 凸集與凸函數(shù)n12SSE,命題2.2 設(shè) 和為中兩個凸集, 是實數(shù) 則11S x xS 1,為凸集。122SS，為凸集12123SSSS(1)(

8、2)(1)(2)，=x +xx,x為凸集12124SSSS(1)(2)(1)(2)，=x-xx,x為凸集2.9, ,.nC TDfTTconv TC C 集合的凸包是指所有包含 的凸集的交集 記為 為凸集第十三頁，共39頁。2. 凸集與凸函數(shù)0101,.,.,mnmixxxxxxmx有限點集的凸包稱為多胞形。若,仿射無關(guān)時，對應(yīng)的凸包稱為 維單純形。向量 稱為該單純形的頂點。多面體多面體(polyhedral set)是有限閉半空間的交. (可表為 Axb ).x4x3x2x1x5xy第十四頁，共39頁。2. 凸集與凸函數(shù)2.10,.nDfCxCxCCCC 設(shè)有集合若對每一點當 取任何非負數(shù)時

9、，都有稱 為錐 又若 為凸集，則稱 為凸錐ii,., 0,i1,2,.,k (1)(2)(k)k(i)i=1例，向量集的所有非負線性組合構(gòu)成的集合為凸錐。2.3Sn命題若集合S為凸集，則它的閉包 也是凸集。第十五頁，共39頁。 多面集 x|Ax0也是凸錐，稱為多面錐多面錐。2. 凸集與凸函數(shù)由定義可知,錐關(guān)于正的數(shù)乘運算封閉,凸錐關(guān)于加法和正的數(shù)乘封閉,一般的,對于凸集S,集合K(S)=x|0,xS是包含S的最小凸錐.錐C稱為尖錐,若0S.尖錐稱為突出的,若它不包含一維子空間約定約定: 非空集合非空集合S生成的凸錐生成的凸錐,是指可以表示成是指可以表示成S中有限個元中有限個元素的非負線性組合素

10、的非負線性組合(稱為凸錐組合稱為凸錐組合)的所有點所構(gòu)成的集合的所有點所構(gòu)成的集合,記為記為coneS. 若若S凸凸,則則coneS=K(S) 0第十六頁，共39頁。 2. 3 凸集分離定理凸集分離定理2. 凸集與凸函數(shù)n1212TDf2.11SSxS ,xS ,H,H,H ,Hx |p x,0,H ,H TTT+1212121212+1212，設(shè) 和是中兩個非空集合，H=x p x= 為超平面。若對有p x，對于有p x（或情況恰好相反），則稱超平面H分離集合S 和S .若SS則稱 正常分離S 和S。若SHS則稱 嚴格分離S 和S。若SH( )S則稱 強分離S 和S。第十七頁，共39頁。2.

11、 凸集與凸函數(shù)2.12(),0,()0()0()0,nnTTTDfSppxSSHx pxxSHx pxxHx pxxSxSHHSx ，設(shè)，若或者則稱 是 在 處的支撐超平面，若則稱 為 在 處的正常支撐超平面。nx STh2.5SES,infx設(shè) 為中的閉凸集，yS,則存在唯一的點x使得 y-xy-2.13dist, )inf (2.4)nx SDfSy Sxn設(shè)非空，y,則點y與集合S之間的距離dist(y,S)定義為（y-第十八頁，共39頁。證明：令2. 凸集與凸函數(shù)(k)(k)(k)x,xS,yxr.于是,由下確界定義知,存在序列使得x Sinfxr0y-22(k)(m)(k)(m)22

12、2(k)(m)(k)(m)xx(xy)(xy)2 xy2 xy(xy)(xy)(k)(k)xxS.x先證存在極限只須證為柯西數(shù)列。第十九頁，共39頁。所以為柯西列，必有極限,且由S為閉集知。此極限點必在S中。2. 凸集與凸函數(shù)2(k)(m)22(k)(m)22(k)(m)222(k)2(m)2(xx)2 xy2 xy4y22 xy2 xy4r2( xyr )2( xyr )0(k,m) 下證明唯一性第二十頁，共39頁。2. 凸集與凸函數(shù)xS, xyxyr.1S2111xyxyr,222111rxyxyr222yx(yx)| yx | | yx | 11,yS, 設(shè)有由 為凸集，有 （x+x）

13、S, 由 Schwartz 不等式y(tǒng)- （x+x）再由 的定義y- （x+x）因否則導出矛盾。第二十一頁，共39頁。2. 凸集與凸函數(shù)TTTTTTSyS,Hx | p xHyp y,p xxS.p yyS p yp x, xS. 設(shè) 為閉凸集，為超平面。分離點若則，令，則 與 分離可表為2.7 (),00, nTTThSySpxSp yp x 設(shè)為中的閉凸集，則存在及實數(shù)，使得對點有。2.6.,(2.4)( - ) ()0nTThSySxSy xxx設(shè)的非空閉凸集，則點為極小化問題的最優(yōu)解當且僅當?shù)诙摚?9頁。2. 凸集與凸函數(shù)xpX(i) (x- )(y- )0 對任意 xX.(ii

14、) 令 p=y- ， =p p. Txxxyx 證明提綱x SxS, |y-x|=inf|y-x| 第二十三頁，共39頁。由此可得2. 凸集與凸函數(shù)222222(1)xx()x(1)x,yxy( x(1)x)yx(xx)yxxx2 (yx)(xx) 在連線如圖 上取一點則2xx2(yx)(xx)002(yx)(xx)0(yx)(xx)0 ，則 即 第二十四頁，共39頁。2. 凸集與凸函數(shù) Th2.7表明，S為閉凸集， yS，則y與S可分離。若令clS表示非空集合S的閉包，則當yclS時，定理結(jié)論也真。實際上我們有下述定理TTTT2p (yx)p (yxxx) p (yx)p (xx) =(yx

15、)(xx) （ ）nTT2.1CS,p y0p x推論設(shè) 為中的非空閉凸錐集，yC,則存在p(0)使得第二十五頁，共39頁。證明2. 凸集與凸函數(shù)nTTTh2.8 S()clS, p yp x 設(shè)為中的凸集，yS,則存在p0，使得對點x有。jjjjj(k)(k)(k)(k)(k)(k)T(k)(k)T(k )(k)(k )(k )(k )TT(k )TTjySy,yclSyy.y2.7,p,xclS,pypx.pp,p.pypx, xclS.xclSk,p yp x, xclS 使得對每一，由定理存在單位向量使得成立因為序列有界，存在收斂子列其極限為單位向量 顯然固定，令得 。第二十六頁，共3

16、9頁。推論：設(shè)S為Rn 中的非空集合，yS,則存在非零向量p，使對xclS, pT (x-y)02. 凸集與凸函數(shù)n1212TT1212Th2.9. S ,S ()SSinf p x xS Supp x xSSS +-設(shè)為中的凸集,= ,則存在p0使 (換言之，存在超平面H,使得H ,H )。21(2)(1)(1)(2)12SSS z zxx,xS ,xS證明：令第二十七頁，共39頁。2. 凸集與凸函數(shù)12T(1)T(2)(1)(2)12SSS8 p xp x, xS ,xS12T由于 和是非空凸集，因此 是非空凸集。由于SS =,則零元素0S。根據(jù)定理2.的推論，存在非零向量p，使得對每一個

17、zS，成立p z0，即第二十八頁，共39頁。2. 凸集與凸函數(shù)1211212122.10. ,(),00inf nTTThS SSSSHSSpp x xSSup p x xS 設(shè)中的閉凸集有界，則存在超平面強分離 和 ，即存在，使 21SSS 12證明提綱：令，則S是非空的凸集，SS =0S。先證S是閉集，再根據(jù)Th2.7立明第二十九頁，共39頁。 作為凸集分離定理的應(yīng)用，下面介紹兩個擇一定理：Farkas定理和Gordan定理，它們在最優(yōu)化理論中是很有用的。2. 凸集與凸函數(shù)2.4 擇一定理擇一定理2.1100,0.TTFarkasAmncnAxc xA yc y定理（定理） 設(shè) 為矩陣，

18、為 維向量，則，有解的充要條件是，無解第三十頁，共39頁。2. 凸集與凸函數(shù) 0000,00 1 1 (2) 0 00200TTTTTTTTTAxc xxAxc xA yc yyA ycxy Axc xyAxy Axc xc x證明：先證必要性。設(shè)，有解，即存在 ，使且?，F(xiàn)在證明無解。用反證法。設(shè)存在，使（）將（）式兩端轉(zhuǎn)置，并右乘 ，得到由于，因此，從而由（）得到與的假設(shè)矛盾。第三十一頁，共39頁。2. 凸集與凸函數(shù),000,0(3)2.70,(4)045TTTTTTTA yc yAxc xSz zA y yScSxzSx cx zsx cx z 再證充分性。設(shè)無解，證明，有解。令 則 為閉

19、凸集。由假設(shè)，根據(jù)定理，存在非零向量 及數(shù)，使得對每一點成立 由于，根據(jù)（ ），必有 （ ）第三十二頁，共39頁。TTTTS c xy Ax(6)6c x0(7)c x6(7)(8)T上式兩端轉(zhuǎn)置，并考慮到集合 的定義，有在式（ ）中，令y=0，得到 由于為某個確定的數(shù)，y0，y的分量可取得任意大，因此由（ ）又可得出 Ax0(8)由和知非零向量x是Ax0，c x0的解。2. 凸集與凸函數(shù)第三十三頁，共39頁。2. 凸集與凸函數(shù)2.11A00m nnnTAcAxxc x 定理（Farkas置換定理）設(shè)，則c為 的行向量的凸錐組合，即cconeA對任意滿足的向量，都有。T 設(shè)A為m n矩陣，那么，Ax0有解的充要條件是不存在非零向量y0，使A y=0.2.12 定理（Gordan定理）0,0,0.TmTGaleAm nbmAxbA wwwb w推論（置換定理）設(shè) 為矩陣， 為 維向量，則線性系統(tǒng)有解對任意滿足，的向量都有第三