《凸集分离定理》由会员分享，可在线阅读，更多相关《凸集分离定理（33页珍藏版）》请在金锄头文库上搜索。
1、集合集合内点内点：0000()nxSNxSxS 设，若存在，使得，则称 为 的一个内点。 补集补集： |,CnSSx xS x集合 的补集定义为开集开集：,xS xS 若对为内点，则称 为开集。闭集闭集：CSSS若集合 的补集为开集，则称 为闭集。有界集有界集 ：0,|MxSxM S 若存在正数使得成立，则称 为有界集。 紧集紧集：有界闭集称为紧集有界闭集称为紧集0x的00 |,0Nxxxx -邻域邻域：性质性质：1*2.inkknkkSxSxxxSSxSSx （ ）集合是闭集，当且仅当对任意的无穷序列，若，则。（ ）集合是紧集当且仅当对任意的无穷序列，必存在收敛于 中点的子序列定义定义：设设
2、S En,若对若对 x(1),x(2)S及及 0,1,都有都有 x(1)+(1-)x(2)S 则称则称S为凸集为凸集。凸集分离定理凸集分离定理定义定义：。和分离集合则称超平面（或情形恰好相反），都有，对，都有超平面，如果对为中两个非空集合，是和设212121|SSHxpSxxpSxxpxHESSTTTn定理定理1： | inf | 0() ()0nx STSEySxS yxyxxxSyxxx 设 为的集，则存在唯一的，使得 。是这一最小距离点对，有闭凸。 证明证明：()()()()()()22()() ()2()2()2()22()()inf |0,|Cauchy|2 |2 |422 |2 |
3、40(,)Cauchy,xSkkkkkmkm kmkmkkyxrxxSyxrxxxxxxyxyyxyxyrmkxxx 令序列使得。先证为序列。当为序 列，极限存 在，设 为.SxS为 闭集，定理定理1： 。，使得，则存在唯一的的闭凸集，为设 0|inf|xyxySxSyESSxn证明证明：|,.2 11|222 11|222 ()0|1.xSyxyxrxxSx xSSxxryyxyxrxxyyxyxyxyxyxyxxx假 设存 在， 使 得为 凸 集 ， ，定理定理1：() ()0TxxSyxxx 是这一最小距离点对，有。证明证明：22222() ()02() ()TTyxxxxSyxyxxx
4、yxxxyxxxyxx“”假设，则对任意的，有是最小距离点。定理定理1：() ()0TxxSyxxx 是这一最小距离点对，有。证明证明：22222222222,.(0,1),().(),()2 () ()2 () ()02() ()00,2() ()0() ()0.TTTTTxxSyxyxSxxxSyxxxyxyxxxyxxxyxxxxxyxxxxxyxxxyxxxyxxx “”假设 是最小距离点 则对，有是凸集，有令得定理定理2:0.nTTSEySpxSp yp x 设 是的非空凸集，则存在非零向量及数，使得对，有闭.)()()()()()(0)(, 00inf12xpypxxxyxxpxy
5、pxxxypxypxyxypxypxyxySxSySTTTTTTTTSx令，使，由定理为闭凸集，证明证明：定理定理3:.)(xpypSSclSxpSyESTTn有，的内点和边界点组成的闭包，由，使得对，则存在非零向量的非空凸集，是设证明证明：( )( )( )( )( )( )( )()( )()()( ).2.,.,.jjjkkkkTTkkkkkTTkkkTT jSclSySyclSyyypxclSpypxppppypxxclSkp yp xxclS 是凸集，是闭凸集。，则存在序列，使得对每个点，由定理 ，存在单位向量，使得对每个，有序列有界 单位向量 ， 存在收敛的子序列其极限为单位向量对
6、每个成立，令，得到推论推论4:. 0)()(yxpSSclSxpSyESTn有，的内点和边界点组成的闭包，由，使得对，则存在非零向量的非空凸集，是设定理定理5:),(.|sup|inf21212121成立对或，使得非零向量，则存在的两个非空凸集，是和设SxSyxpypSxxpSxxppSSESSTTTTn)1()2(21212)2( 1)1()1 ()2( 120)0(, 00,.,|xpxpxpSxpSSSSSSSSxSxxxSSSTTT有对存在是凸集且是非空凸集，设证明证明：1211212120inf |sup|.(,)nTTTTSSESSSpp x xSp x xSp yp xySxS
7、设 和是的两个非空闭凸集， 有界，且，则存在非零向量 和，使得或对成立定理定理6:(2)(1)(1)(2) 2112( )( )( )( )( )( ) 21( ) 1( )( )( )( ) 12221|,0.,=,1,2,=()kkkkkkkkkkkSSSxxxS xSSSxSxySzSxyzkSzzzSyxzxzSxzSxxzzSSSS 证明设则 是非空凸集且假设存在序列则存在序列和使得是有界闭集，存在收敛的子列，不妨设,则有是闭集，是.2闭集由定理 ，结论成立.Farkas定理定理：000TTAmncnAxc xA ycy设 为矩阵， 为 维列向量，则，有解的充要条件是，无解。证明证明
8、：）矛盾。与（但则有的一个解，为设得，使得设存在”“100, 0) 1 (00, 00, 00xAyxAyxcxAyxcxAxcAxxcAycyAyTTTTTTTT,0 |,0,20,0,0,010010.00TTTTTTTTTTTTTTA yc ySz zA y ycSSxzSx cx zx cx zc xz xy Axyc xy Axyc xc xyAxxAxc x “” 设无解，令则可以证明 为闭凸集，由定理 ，使得对有即对任意的，有（ ）令，得为一定数， 的分量可取任意大，由（ ），必有既非零向量 是，的解。Farkas定理定理：000TTAmncnAxc xA ycy设 为矩阵， 为
9、 维列向量，则，有解的充要条件是，无解。Gordan定理定理：。，使得向量充要条件是不存在非零有解的矩阵，那么为设000yAyAxnmAT证明证明：.0,00, 00, 00矛盾与数的各分量不可能为非负则有使得若存在非零向量，使得设存在”“yyxAxAyAyyAyxAxTTT1212200,0.0 |, |00,1000010,02TnnTTTnTAxyA yAxSz zAx xESz zAxSSyxEzSy Axy zxy zzyzxEy Ax “”（证等价命题）即若无解，则存在非零向量使得设无解，令无解由凸集分离定理知，存在非零向量 ，使得对，有（ ）特别地，当时，有。，它的分量可取任意负
10、数，在（ ）中令，则对有（ ）令200,0.0,0.TTTTTTxA yy AA yA yA yyA y ，代入（ ），得即因此，存在非零向量使得Gordan定理定理：。，使得向量充要条件是不存在非零有解的矩阵，那么为设000yAyAxnmAT证明证明：“0,0(0)|,00.0,0,00,0,0,0 0,0.TTTTTTTA yyySz zA y ySSxzSxx zzSx zzA yyy Ax AxxAx 设无解，令，则可以证明 是闭凸集，则由点与凸集的分离定理，使得对都有， 对都有对有成立， ，即存在使有解证法正证法正 确吗确吗？凸函数凸函数凸函数凸函数：设设S是是En中的非空凸集中的非
11、空凸集， f(x)是定义在是定义在S上的上的 实函数实函数，如果如果对于每一对对于每一对x1，x2 S及每一个及每一个a，0a1,都都 有有 f(ax1+(1a)x2)a f(x1)+(1a)f(x2) 则称函数则称函数f(x)为为S上的上的凸函数凸函数上式中上式中，若若变为变为，则则 称为严格凸函数称为严格凸函数。 若若-f(x)为为S的凸函数的凸函数，则称则称f(x)为为S上的上的凹函数凹函数(a)严格凸x凸x非凸x(b)(c)凸函数性质凸函数性质(1) 设设 f1(x) ， f2(x) 是 凸 集是 凸 集 S 上 的 凸 函 数上 的 凸 函 数 ， 则 函 数则 函 数 f1(x)+
12、f2(x)在在S上也是凸函数上也是凸函数。(2) 设设f(x)是凸集是凸集S上的凸函数上的凸函数，则对任意的则对任意的a0，函数函数 af(x)是凸的是凸的。推广推广：设设f1(x)，f2(x), , fk(x)是凸集是凸集S上的凸函数上的凸函数， ai0,则则a1f1(x)+a2f2(x)+ + akfk(x)也是凸集也是凸集S S上的凸函上的凸函 数数. .(3) 设设f(x)是凸集是凸集S上的凸函数上的凸函数，对每一个实数对每一个实数c，则集则集 合合Scx | x S，f(x) c是凸集是凸集。(4)设设S是是En中的非空凸集中的非空凸集，f是定义在是定义在S上的凸函数上的凸函数，则则
13、f在在 S上的局部极小点是整体极小点上的局部极小点是整体极小点，且极小点的集合是凸集且极小点的集合是凸集 证明证明：(0)(0)(0)(0)(0)(0)0( )( )( )( )( )()(0,1)(1)(1) )()(1) ( ) ( )(1) ( )( )xfSxNxxSNxf xf xxxSf xf xSxxSfSfxxf xf x f xf xf xx 设 是 在 中的局部极小点，既存在 的邻域使得对，有。若 不是整体极小点，则使，是凸集，对有，是 上的凸函数，当 取得充分小时，可使(1)( ) |,( )xSNxxxfSfSSx xS f x，这与 为局部极小点矛盾，是 在 上的整体极小点。在 上的极小值也是它在 上的最小值。极小点集合为，则由性质（3），为凸集。凸函数的判别凸函数的判别梯度梯度：Tnxxf xxfxf )(,)()(1Hesse矩阵矩阵： 221222122122 122)()()()()()()(nnnnxxf xxxfxxxf xxxfxxxf xxfxfAxfbA
