凸集与凸函数

2.凸集与凸函数•2.1仿射集Df2.1Mx,yn若集合包含所有的通过其内任意两点的直线,即M,,有(1-)x+yM则称M为一个仿射集(仿射流形,仿射子空间)。对n维欧氏空间中任意两点x≠y,则通过x和y的直线可表为l(x,y)={(1-λ)x+λy|λ∈R},,{},(,).nxlxy空集单点集直线都是仿射集2.凸集与凸函数则一个仿射集的平移也是仿射集Th2.1(1)Rn的子空间是包含原点的仿射集;(2),对每一非空的仿射集M,存在唯一的子空间L和向量a∈Rn,使得nMaM+a{x+a|xn设,,M相对于a的平移为M}约定M-a=M+(-a)若a∈M,则M-a是子空间.{|}MLaxaxL2.凸集与凸函数•若非空仿射集M=L+a,则a∈M,于是唯一子空间L可表为Df2.2.非空仿射集M的维数是指平行于仿射集M的子空间的维数.nTnTTHLLLLaM,MLa{xa|xp0}{y|pypa}nT设为一超平面,子空间平行于H,则的正交补空间是一维的.不妨设p0是的一个基,则L={x|xp=0},有{|,}LMMxyxyMRn中的n-1维仿射集称为超平面.2.凸集与凸函数Th2.2给定向量p(≠0)∈Rn,∈R,则是Rn中的一个超平面.反之,Rn任一超平面都可表成上式的形式,且在相差一个非零常数的意义下,(p,)是唯一的.mnnnnnTh2.3A,b,M{x|Axb}(Axb)(2.2).,(2.2),.给定矩阵向量则简记为是中的一仿射集反之中的每一仿射集都可表成式的形式即一组超平面的交集{|}(2.1)nTHxpx2.凸集与凸函数•可验证,仿射集的交集仍是仿射集Df2.3给定Rn中集合S,包含S的所有仿射集的交集,即包含S的最小仿射集称为S的仿射包,记为affS11,{|1,,,1,..,,}kkiiiiiiiSaffSxRxSikk可证的仿射包¥12121(,,...,),(,,...,){|}.1,2,...,,TTmmTiiimiiAaaabbbbHxaxbimMH若记则2.凸集与凸函数Df2.1Rn中任一集合S的维数定义为它的仿射包affS的维数,即包含S的仿射集的最小维数.0101012.51,,...,{,,...},{,,...}mmmDfmxxxxxxmaffxxxm由个向量组成的向量组称为是仿射无关的是指集合的维数为即仿射包维数是.010010010010{,,...}{0,,...}{,...}.,....mmmmaffxxxLxLaffxxxxxxxxLmxxxx一般,有限点集的仿射包,是包含的最小子空间的维数是线性无关2.凸集与凸函数命题2.1下述断言相互等价.01001011(1){,,...,};(2){,...,}{(,1),(,1),...(,1)}nmnmnmxxxxxxxxxx中的向量组仿射无关中的向量组线性无关;(3)中的向量组线性无关.0110001010101010101{,,...},,()...()=...(1),,...,(,,...,)(,,...,).mmmmmmiimmmMaffxxxLMxMxxxxxxxxxxxxxMxxx设仿射集,是平行于的子空间则其中表示式唯一仿射无关;此时,称为相对于向量组的重心坐标2.凸集与凸函数2.6,,()-(),.,,.\,.nDfSxSNxxNxaffSSxSSriSriSSSclSriSSrbS设是非空集合表示的邻域。若则称为的一个相对内点的相对内点的全体称为它的相对内部记为若则称为一个相对开集集合称为的相对边界记为01{,,...,}.mxxxM仿射无关向量组称为仿射集的一个重心坐标系2.凸集与凸函数•2.2凸集与锥2.7DfSn(1)(2)(1)(2)(1)(2)(1)(2)n设为维欧氏空间中的一个集合。若对任意两点x,xS及每个实数[0,1],有x+(1-)xS则称S为凸集。x+(1-)x称为x和x的凸组合。2.凸集与凸函数T+T-T+T-T2.3H={xpx=}pnpH={xpx}H={xpx}H={xpx}H={xpx}例超平面为凸集，其中为维列向量，为实数。此外,下面相对于法向量的半空间都是凸集:正的闭半空间负的闭半空间正的开半空间负的开半空间2.凸集与凸函数x0xx-x0px0xx-x0p(0)(0)2.4L={xx=xd0}dx例集合，为凸集，其中为给定的非零向量，为定点。(0)(0)L={xx=xd0}x集合,称为射线,为射线的顶点2.凸集与凸函数111112.8,,...,,1,1,..,,...{,...,}mmniiimmmDfmxxRimxxxx给定个向量以及满足的非负实数称向量为的凸组合.11112.4{1,2,...},,...,,...,1,0,1,..,.nmnmmmiiiThSSmxxxxSRim+集合是凸集,当且仅当包含其中任意有限个元素的凸组合,即对任意的有其中运用定义不难验证如下命题：2.凸集与凸函数n12SSE,命题2.2设和为中两个凸集,是实数则11S{xxS}1,为凸集。122SS，为凸集12123SSSS(1)(2)(1)(2)，={x+xx,x}为凸集12124SSSS(1)(2)(1)(2)，={x-xx,x}为凸集2.9,,.nCTDfTTconvTCC集合的凸包是指所有包含的凸集的交集记为为凸集2.凸集与凸函数0101{,,...,}{,...,}mnmixxxxxxmx有限点集的凸包称为多胞形。若,仿射无关时，对应的凸包称为维单纯形。向量称为该单纯形的顶点。多面体(polyhedralset)是有限闭半空间的交.(可表为Axb).x4x3x2x1x5xy2.凸集与凸函数2.10,,,,.nDfCxCxCCCC设有集合若对每一点当取任何非负数时，都有称为锥又若为凸集，则称为凸锥ii,,...,{0,i1,2,...,k}(1)(2)(k)k(i)i=1例，向量集的所有非负线性组合构成的集合为凸锥。2.3Sn命题若集合S为凸集，则它的闭包也是凸集。•多面集{x|Ax0}也是凸锥，称为多面锥。2.凸集与凸函数由定义可知,锥关于正的数乘运算封闭,凸锥关于加法和正的数乘封闭,一般的,对于凸集S,集合K(S)={λx|λ0,xS}是包含S的最小凸锥.锥C称为尖锥,若0S.尖锥称为突出的,若它不包含一维子空间约定:非空集合S生成的凸锥,是指可以表示成S中有限个元素的非负线性组合(称为凸锥组合)的所有点所构成的集合,记为coneS.若S凸,则coneS=K(S)∪{0}•2.3凸集分离定理2.凸集与凸函数n1212TDf2.11SSxS,xS,H,H,H,H{x|px},0,H,HTTT+1212121212+1212，设和是中两个非空集合，H={xpx=}为超平面。若对有px，对于有px（或情况恰好相反），则称超平面H分离集合S和S.若SS则称正常分离S和S。若SHS则称严格分离S和S。若SH()S则称强分离S和S。2.凸集与凸函数2.12(),0,{()0}{()0}{()0},nnTTTDfSppxSSHxpxxSHxpxxHxpxxSxSHHSx－，设，若或者则称＝是在处的支撑超平面，若则称为在处的正常支撑超平面。nxSTh2.5SES,infx设为中的闭凸集，yS,则存在唯一的点x使得y-xy-2.13dist,)inf(2.4)nxSDfSySxn设非空，y,则点y与集合S之间的距离dist(y,S)定义为（y-证明：令2.凸集与凸函数(k)(k)(k){x},xS,yxr.于是,由下确界定义知,存在序列使得xSinfxr0y-22(k)(m)(k)(m)222(k)(m)(k)(m)xx(xy)(xy)2xy2xy(xy)(xy)(k)(k){x}xS.{x}先证存在极限只须证为柯西数列。所以为柯西列，必有极限,且由S为闭集知。此极限点必在S中。2.凸集与凸函数2(k)(m)22(k)(m)22(k)(m)222(k)2(m)2(xx)2xy2xy4y22xy2xy4r2(xyr)2(xyr)0(k,m)下证明唯一性2.凸集与凸函数ˆˆxS,xyxyr.1ˆS2111ˆˆxyxyr,222111ˆˆrxyxyr222ˆˆyx(yx)||yx||||||yx||||11,yS,设有由为凸集，有（x+x）S,由Schwartz不等式y-（x+x）再由的定义y-（x+x）因否则导出矛盾。2.凸集与凸函数TTTTTTSyS,H{x|px}Hypy,pxxS.pyySpypx,xS.设为闭凸集，为超平面。分离点若则，令，则与分离可表为2.7(),00,nTTThSySpxSpypx设为中的闭凸集，则存在及实数，使得对点有。2.6.,(2.4)(-)()0nTThSySxSyxxx设的非空闭凸集，则点为极小化问题的最优解当且仅当2.凸集与凸函数xpX(i)(x-)(y-)0对任意xX.(ii)令p=y-，=pp.Txxxyx证明提纲xSxS,||y-x||=inf||y-x||由此可得2.凸集与凸函数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，则即2.凸集与凸函数•Th2.7表明，S为闭凸集，yS，则y与S可分离。若令clS表示非空集合S的闭包，则当yclS时，定理结论也真。实际上我们有下述定理TTTT2p(yx)p(yxxx)p(yx)p(xx)=(yx)(xx)（）nTT2.1CS,py0px推论设为中的非空闭凸锥集，yC,则存在p(0)使得证明2.凸集与凸函数nTTTh2.8S()clS,pypx设为中的凸集，yS,则存在p0，使得对点x有。jjjjj(k)(k)(k)(k)(k)(k)T(k)(k)T(k)(k)(k)(k)(k)TT(k)TTjyS{y},yclSyy.y2.7,p,xclS,pypx.{p}{p},p.pypx,xclS.xclSk,pypx,xclS使得对每一，由定理存在单位向量使得成立因为序列有界，存在收敛子列其极限为单位向量显然固定，令得。推论：设S为Rn中的非空集合，yS,则存在非零向量p，使对xclS,pT(x-y)02.凸集与凸函数n1212TT1212Th2.9.S,S()SSinf{pxxS}Sup{pxxSSS+-设为中的凸集,=,则存在p0使}(换言之，存在超平面H,使得H,H)。21(2)(1)(1)(2)12SSSzzxx,xS,xS证明：令2.凸集与凸函数12T(1)T(2)(1)(2)12SSS8pxpx,xS,xS12T由于和是非空凸集，因此是非空凸集。由于SS=,则零元素0S。根据定理2.的推论，存在非零向量p，使得对每一个zS，成立pz0，即2.凸集与凸函数1211212122.10.,(),,00inf{}{}nT