《运筹学2凸分析》由会员分享，可在线阅读，更多相关《运筹学2凸分析（53页珍藏版）》请在金锄头文库上搜索。
1、TP SHUAI 1 最优化理论与算法 帅天平 北京邮电大学数学系 Email:, Tel:62281308,Rm:主楼814 2，凸分析与凸函数 TP SHUAI 2 2. 凸集与凸函数 2.1 凸集与锥凸集与锥 (1)(2)(1)(2)(1)(2)(1)(2),0,1,(1- )(2- )11. nSnRxxSxxSSxDxfxx设 为 维欧氏空间中的一个集合。若对任意两点及每个实数有则称 为。称为和的凸集凸组合。TP SHUAI 3 2. 凸集与凸函数 -,:2.1TTTTTHx p xpnpHx p xHx p xHx p xHx p x 为凸集，其中 为 维列向量， 为实数。此外 下
2、面相对于法向量 的半空间都是凸集正的闭半空间负的闭半空间正的开半空间负的开半空平面间例超TP SHUAI 4 2. 凸集与凸函数 x0 x x-x0 p x0 x x-x0 p (0)(0) 02.2 Lx xxddx 集合，为凸集，其中 为给定的例非零向量，为定点。(0)(0) ,0Lx xxdx 集合称为,为射线射线的顶点TP SHUAI 5 2. 凸集与凸函数 111 11,.,1,1,.,. ,2.,2m mn i im immmxxRR imxxxDfx 给定 个向量以及满足的非负实数称向量 为的凸组合.11 1 11,2,.,.,.,12.1,0,1,., .nmnm m mii
3、iSRSmRxxRxxSmTR ih 集合是凸集,当且仅当 包含其中任意有限个元素的凸组合,即对任意的有其中TP SHUAI 6 运用定义不难验证如下命题： 2. 凸集与凸函数 n 12SSR2,1,. 设 和为中两个凸集是题实数命则11S x xS 1,为凸集。122SS，为凸集12123SSSS(1)(2)(1)(2)，=x +xx,x为凸集12124SSSS(1)(2)(1)(2)，=x -xx,x为凸集,2.3.nC TDfconCCv TTRT集合的是指所有包含 的凸集的交集 记为 凸包为凸集 TP SHUAI 7 2. 凸集与凸函数 0101,.,.,mnmixxxRxxxxm有限
4、点集的凸包称为。若,仿射无关时，对应的凸包称为。向量 称为该单多胞形维单纯形纯形的顶点。多面体多面体(polyhedral set)是有限闭半空间的交. (可表为 Axb ). x4 x3 x2 x1 x5 x y TP SHUAI 8 2. 凸集与凸函数 ,.2.4nCRxCxCCDCCf 设有集合若对每一点当 取任何非负数时，都有称 为又若 为凸集，则称 为锥凸锥ii,.,0,i1,2,. ,23. k (1)(2)(k)k (i)i=1，向量集的所有非负线性组合构成的集合例 .为凸锥。2.2RSn若集合S为凸集，则它的闭包命题也是凸集。TP SHUAI 9 多面集 x|Ax0也是凸锥，称
5、为多面锥多面锥。 2. 凸集与凸函数 由定义可知,锥关于正的数乘运算封闭,凸锥关于加法 和正的数乘封闭,一般的,对于凸集S,集合 K(S)=x|0,xS 是包含S的最小凸锥. 锥C称为尖锥,若0S.尖锥称为突出突出的,若它不包含 一维子空间. 约定约定: 非空集合非空集合S生成的凸锥生成的凸锥,是指可以表示成是指可以表示成S中有限中有限 个元素的非负线性组合个元素的非负线性组合(称为凸锥组合称为凸锥组合)的所有点所构成的所有点所构成 的集合的集合,记为记为coneS. 若若S凸凸,则则 coneS=K(S) 0 TP SHUAI 10 2. 凸集与凸函数 Df 2.5 非空凸集中的点 x 称为
6、极点极点,若 x=x1+(1-)x2 , (0,1) , x1 ,x2 S, 则 x=x1=x2.换言之,x不能表示成S中两个不 同点的凸组合. x4 x3 x 2 x1 x5 x y S x 由上可知,任何有界凸集中任一点都可表成极点的凸组合. TP SHUAI 11 2. 凸集与凸函数 Def 2.6. 设非空凸集SRn, Rn中向量d0 称为S的一个一个回收方回收方 向向(方向方向), 若对每一 xS, R(x.d)=x+d| 0 S.S的所有方向 构成的尖锥称为S的回收锥,记为0+S 方向d1和d2 称为S的两个不同的方向不同的方向,若对任意0, 都有 d1d2；方向d称为S的极方向e
7、xtreme direction ,若 d=d1+(1-)d2, (0,1),d1 ,d2 是S的两个方向,则有 d=d1=d2. 换言之d不能表成它的两个不同方向的凸锥组合 x0 x0 d d d TP SHUAI 12 2. 凸集与凸函数 1221TTTS(x ,x ) x| x |(0,1)45(1,1) ( 1,1)2 4集合凡是与向量夹角的向量都是它的方向。，是其仅有的例 .两个极方向Sx Axb,x0,d,dS2d0A0.5d 设是非零向量。证明 是 的方向且例 .(Th23P 若多面体 的极点 极方向)存在的话,则极点(极方向)的数目一.定有限.TP SHUAI 13 2. 凸集
8、与凸函数 表示定理表示定理 Th2.4 若多面体若多面体P=xRn|Axb, r(A)=n则则: (1)P的极点集是非空的有限集合的极点集是非空的有限集合,记为记为x k kK 则则 j (2)记记P的极方向集为的极方向集为d jJ (约定约定P不存在极方向时不存在极方向时J=) |1,0,0,kjkj kj k Kj Jnkkj k KPconv xkKcone djJxxd xRkKjJ (3)指标集指标集J是空集当且仅当是空集当且仅当P是有界集合是有界集合,即多胞形即多胞形. TP SHUAI 14 2. 凸集与凸函数 表示定理直观描述表示定理直观描述:设 X 为非空多面体. 则存在有限
9、个极点 x1, , xk , k0. 进一步,存在有限个极方向 d1, , dl, l0 当且 仅当 X 无界. 进而, xX 的充要条件是 x 可以表为 x1, , xk 的凸组合和d1, , dl的非负线性组合(凸锥组合). x y x1 x2 x3 d1 d2 0 推论推论2.1 若多面体若多面体S=x|Ax=b,x0非空非空,则则S必有极点必有极点. TP SHUAI 15 2. 2 凸集分离定理凸集分离定理 2. 凸集与凸函数 1212121212121212122.7,.,( ) |,0,nTTTTSSRHx p xxSp xxSp xHSSSSHHSSSHSHHSSSHx p x
10、SHHDfSS ，设 和是中两个非空集合，为超平面。若对有，对于有（或情形恰好相反），则称超平面集合和若则称 正常分离 和 。若分离强则称严格分离 和 。若则称分离和 。TP SHUAI 16 2. 凸集与凸函数 (),0,()0()0()08,2.nnTTTSRpRpxSSHx pxxSHx pxxHx pxxSxSHHSxDf ，设，若或者则称 是 在 处的，若则称 为 在支撑超平面正常支撑处的超平面。nx SSRS,Th2.5infx 设 为中的闭凸集，yS,则存在唯一的点x使得 y-xy-,( , ), )inf- .)22.9( 4nnx SSRyRySdist y Sdist y
11、Sy xDf设非空，则点 与集合 之间的距离定义为（TP SHUAI 17 证明：令 2. 凸集与凸函数 (k)(k)(k)x,xS,yxr.于是,由下确界定义知,存在序列使得x Sinfxr0 y-22(k)(m)(k)(m)222(k)(m)(k)(m)xx(xy)(xy)2 xy2 xy(xy)(xy)(k)(k)xxS.x先证存在极限只须证为柯西数列。TP SHUAI 18 所以为柯西列，必有极限,且由S为闭集知。 此极限点必在S中。 2. 凸集与凸函数 2(k)(m)22(k)(m)22(k)(m)222(k)2(m)2(xx)2 xy2 xy4y22 xy2 xy4r2( xyr
12、)2( xyr )0(k,m) 下证明唯一性 TP SHUAI 19 2. 凸集与凸函数 xS, xyxyr.1S2 111xyxyr,222111rxyxyr222 yx(yx)| yx | | yx | 11,yS, 设有由 为凸集，有 （x+x） S, 由 Schwartz 不等式y- （x+x）再由 的定义y- （x+x）因否则导出矛盾。TP SHUAI 20 2. 凸集与凸函数 TTTTTTSyS,Hx | p xHyp y,p xxS.p yySp yp x, xS. 设 为闭凸集，为超平面。分离点若则，令，则 与 分离可表为2.7 (),00, nTTThSRySpxSp yp
13、x 设为中的闭凸集，则存在及实数，使得对点有。2.6,(2.4)( - ) ( - )0nTThSRySxSy xxx设的非空闭凸集，则点为极小化问题的最优解当且仅且当TP SHUAI 21 2. 凸集与凸函数 x p X (i) (x- )(y- )0 对任意 xX. (ii) 令 p=y- ， =p p. T x x x y x 证明提纲 x SxS, |y-x|=inf|y-x| TP SHUAI 22 由此可得 2. 凸集与凸函数 222222(1)xx()x(1)x,yxy( x(1)x)yx(xx)yxxx2 (yx)(xx) 在连线如图 上取一点则2xx2(yx)(xx)002(
14、yx)(xx)0(yx)(xx)0 ，则 即 TP SHUAI 23 2. 凸集与凸函数 Th2.7表明，S为闭凸集， yS，则y与S可分离。 若令clS表示非空集合S的闭包，则当yclS时， 定理结论也真。实际上我们有下述定理 TTTT2p (yx)p (yxxx)p (yx)p (xx)=(yx)(xx) （ ）nTT2.1CRS,p y0p x推论设 为中的非空闭凸锥集，yC,则存在p(0)使得TP SHUAI 24 证明 2. 凸集与凸函数 nTTTh2.8 S()RclS, p yp x 设为中的凸集，yS,则存在p0，使得对点x有。jjjjj(k)(k)(k)(k)(k)(k)T(k)(k)T(k )(k)(k )(k )(k )TT(k )TT jySy,yclSyy.y2.7,p,xclS,pypx.pp,p.pypx, xclS.xclSk,p yp x, xclS
