最优化 10 凸集分离定理.pdf

《最优化 10 凸集分离定理.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、集合00x的-邻域：N{

2、

3、

4、xxx

5、

6、,0}0n0内点：设xS，若存在0，使得Nx()S，0则称x为S的一个内点。Cn补集：集合S的补集定义为S{

7、xxSx,}开集：若对xSx,为内点，则称S为开集。C闭集：若集合S的补集S为开集，则称S为闭集。有界集：若存在正数M0,使得xS,

8、

9、

10、

11、xM成立，则称S为有界集。紧集：有界闭集称为紧集．性质：n（1）集合S是闭集，当且仅当对任意的无穷kk序列{}xS，若xx*，则x*S。n（2）集合S是紧集当且仅当对任意的无穷kk序列

12、{}xS，必存在收敛于S中点的子序列{xi}.定义：设S⊆En,若对∀x(1),x(2)∈S及∀λ∈[0,1],都有λx(1)+(1-λ)x(2)∈S则称S为凸集。凸集分离定理定义：nT设S和S是E中两个非空集合，H{x

13、px}为12T超平面，如果对xS，都有px，对xS，都有12Tpx（或情形恰好相反），则称超平面H分离集合S1和S。2n定理1：设S为E的闭凸集，yS，则存在唯一的xS，使得

14、

15、yx

16、

17、inf

18、

19、yx

20、

21、0。xSx是这一最小距离点对xS，有T(yx)(xx)0。证明

22、：令inf

23、

24、yx

25、

26、r0xS()k()k()k序列{x},xS,使得

27、

28、yx

29、

30、r。()k先证{x}为Cauchy序列。()k(m)2

31、

32、xx

33、

34、2()k(m)()k2(m)2xx2

35、

36、xy

37、

38、2

39、

40、xy

41、

42、4y2()k2(m)222

43、

44、xy

45、

46、2

47、

48、xy

49、

50、4r0(当m,k)()k()k{x}为Cauchy序列，{x}极限存在，设为x,S为闭集，xS.n定理1：设S为E的闭凸集，yS，则存在唯一的xS，使得

51、

52、yx

53、

54、inf

55、

56、yx

57、

58、0。xS证明：假

59、设存在xˆS，使得

60、

61、yx

62、

63、yxˆrxxˆS为凸集，x，xˆS,S.2xxˆ11ry

64、

65、yx

66、

67、yxˆr222xxˆ11y

68、

69、yx

70、

71、yxˆ222yx(yxˆ)

72、

73、yx

74、

75、yxˆ1xxˆ.定理1：x是这一最小距离点对xS，有T(yx)(xx)0。T证明：“”假设(xy)(xx)0，则对任意的xS，有22yxyxxx22Tyxxx2(yx)(xx)2yxx是最小距离点。定理1：x是这一最小距离点对

76、xS，有T(yx)(xx)0。证明“：”假设x是最小距离点,则对xS，有22yxyx.S是凸集，(0,1),有x(xx)S.22y(x(xx))yx,2222Ty(x(xx))yxxx2(yx)(xx)22Txx2(yx)(xx)02Txx2(yx)(xx)0T令0,得2(yx)(xx)0T(yx)(xx)0.n定理2:设S是E的非空闭凸集，yS，则存在非零向量TTp及数0，使得对xS，有py

77、px.证明：S为闭凸集，yS，由定理1，xS，使yxinfyx0xST2令pyx0,p(yx)yx0TTp(yx)p(yxxx)TTp(yx)p(xx)T(yx)(xx)TTpypx.n定理3:设S是E的非空凸集，yS，则存在非零向量p，使得对xclS(S的闭包，由S的内点和边界点组成)，TT有pypx.证明：S是凸集，clS是闭凸集。()k()kyS，则存在序列{y}clS，使得yy.()k()k对每个点y，由定理2，存在单位

78、向量p，TT()k()k()k使得对每个xclS，有pypx.()k(k)序列{p}有界单位向量，存在收敛的子序列{pj},其极限为单位向量p.TT(kj)()k(kj)pypx对每个xclS成立，TT令k，得到pypx,xclS.jn推论4:设S是E的非空凸集，yS，则存在非零向量p，使得对xclS(S的闭包，由S的内点和边界点组成)，T有p(xy)0.n定理5:设S1和S2是E的两个非空凸集，S1S2，则存在非零向量p，使得TTinf{px

79、xS}sup{px

80、x

81、S}.12TT(或pypx对yS,xS成立)12(2)(1)(1)(2)证明：设SSS{xx

82、xS,xS}2112S,S是非空凸集，12S是凸集且S.SS,0S12T存在p0,对xS