搜索
Chapter2ConvexSet对于12nRxx连接两点的直线可表示为12(1),Rx|xxx连接两点的线段可表示为12(1),[0,1]x|xxx仿射集（AffineSet）定义：C是仿射集↔12,xxC，则连接两点的直线也在C内例：线性方程组的解集是仿射集证：线性方程组的解集可表示为{,,}mnnRRCx|Ax=bAb设12,xxC，则1Ax=b，1Ax=b1212(1)(1)(1)AxxAx+Axbbb，得证仿射组合（AffineCombination）设k个点12,,,kxxx，1212,,,1kkR则称1122kkxxx为12,,,kxxx的仿射组合仿射包（AffineHull）任意集合nRC，C中任意元素的仿射组合构成的集合称仿射包1211221212,,,aff,,,1kkkkkRxxxCCxxx如果一个集合的仿射包就是它自己，那么它就是一个仿射集一条直线是仿射集，一条线段则不是平面是仿射集，一块矩形区域则不是凸集（ConvexSet）定义：C是仿射集↔12,xxC，则连接两点的线段也在C内凸组合（ConvexCombination）设k个点12,,,kxxx，1212[0,1],,,1kk则称1122kkxxx为12,,,kxxx的凸组合凸包（ConvexHull）任意集合nRC，C中任意元素的凸组合构成的集合称凸包1211221212,,,conv,,,[0,1]1kkkkkxxxCCxxx一个凸集，它的凸包就是它本身一条直线是凸集，一条线段也是凸集平面是凸集，一块矩形区域也是凸集凸集非凸集非凸集凸集的凸包（本身）非凸集的凸包凸锥（ConvexCone）定义：C是仿射集↔12,xxC，对12,0，有1122xxC凸锥组合（ConvexConeCombination）设k个点12,,,kxxx，12,,,0k则称1122kkxxx为12,,,kxxx的凸锥组合凸锥包（ConvexConeHull）任意集合nRC，C中任意元素的凸锥组合构成的集合称凸锥包12112212,,,,,,0kkkkxxxCxxx一个凸锥集，它的凸锥包就是它本身过原点的射线是凸锥过原点的两条射线之间的区域是凸锥集合名称凸集仿射集凸锥1.空集√√2.1个点√√3.nR空间√√√4.nR空间的子空间：{}0x|Ax=√√√5.任一直线√√×6.任一线段√××7.任一射线：00xv|√××8.超平面：{,,}TnbbRRx|ax=x√√×9.半空间：{,,}{,,}TnTnbbRbbRRRx|axxx|axx√××10.欧几里得空间中的球：2(,)||||,,ncccrrrRRBxxxxx√11.欧几里得空间中的椭球：1(,,)()(),,,TnccccrrrRRExPxxxPxxxP正定√12.多面体（Polyhedron）：,1,,,1,,TiiTjjimjnaxbPxcx=d（很多超平面和半空间的交集）√13.对称矩阵：|nnnTRSAA=A√√√14.对称半正定矩阵：|,nnnTR0SAA=AA√×√15.对称正定矩阵：|,nnnTR0SAA=AA√××10）证明：设12,xxB，则1222||||||||ccrrxxxx1221221221222||(1)||||(1)(1)||||(1)||||||(1)||||(1)cccccccrrrxxxxxxxxxxxxxxx(1)xxx1122(,)xaabx13）对称阵是仿射集，因而是凸集证明：设12,nAAS，则11TAA，22TAA对R，1212(1)(1)TAAAA，得证14）对称半正定阵是凸锥，因而是凸集证明：设12,nAAS，则11TAA，22TAA，且对x，有10TxAx，20TxAx对称已证明，现证明半正定，对x和12,0，11221122()0TTTxAAx=xAxxAx，得证14）对称正定阵是凸集证明：设12,nAAS，则11TAA，22TAA，且对0x，有10TxAx，20TxAx对称已证明，现证明正定，对0x和[0,1]，1212(1)(1)0TTTxAAx=xAxxAx，得证保持凸集凸性的操作交集（Intersection）若1S，2S为凸集，则12SS为凸集。若S为凸集，对A，则AS为凸集。注：并集不能保持凸集的凸性仿射函数（AffineFunction）定义：对domnRx，(),,mnmRRfxAx+bAb，在称:nmRRf是仿射的定理：若nSR是凸的，:nmRRf是仿射的，则S在f下的映射(){()|}fSfxxS是凸的同样，若nSR是凸的，:nmRRg是仿射的，则S在g下的反映射1(){|()}gSxgxS是凸的例：缩放{|}SxxS和位移{|}Sax+axS是保持凸性的例：两个凸集的和1212{|,}SSx+yxSyS是保持凸性的解释如下，集合1S与集合2S的笛卡尔乘积1212{(,)|,}SSxyxSyS是保持凸性的集合12SS在仿射变换(,)fxyxy下1212()fSSSS依然是保持凸性的例：线性矩阵不等式（LMI:LinearMatrixInequality）：11()nnxxAxAAB，,niBAS（对称阵）类比一般的线性不等式（LinearInequality）：11Tnnxaxabax，,ibxR）求证：线性矩阵不等式()AXB的解集{|()}XAXB是凸集证明：()()nfXBAXS是凸集1(){|()}nfXXBAXS也是凸集例：椭球是球的仿射映射，因此是凸的球2||||1,nRuuu是凸的，它在仿射变换12()cxuPu+x下2()||||1,nRxuuu也是凸的而1211()222222()||||1,()||()||1,()||()||1,cnnnccRRRu=PxxxuuuxuPxxuxuPxxu2||1()()()1,TTnccRa||aaxuxxPxxu就是椭圆仿射变换S()fS透视函数（PerspectiveFunction）定义：1:nnRRP，domRnRP=（R{R|0}tt）(,),,RntttRzPzz定理：若domCP是凸集，则(){()|}PCPxxC也是凸集例：考虑1nR内的一个线段设1111(,),0(,),0nnnnxxyyxxyy，则1nR内的一个线段可表示为(1),[0,1]xy该线段经透视变换后仍为线段1111111111111[0,1](1)(1)(1)(1)(1)(1)(1)(1)nnnnnnnnnnnnnxxyxyxyxyxxyyxyxyPxy+PxPy线性分数函数（Linear-fractionalFunction）设仿射函数1:nmRRg满足()TdAbgxx+c，,,RmnmndRRRAbc设透视函数1:mmRRP满足(,),,RmtttRzPzz定义线性分数函数:nmRRf满足fPg，即()()dom{|0}TTTdddAx+bAx+bfxPgxPfxcxcxcx例：两个随机变量的联合概率与条件概率设两个离散型随机变量（RandomVariable）:{1,,}Un，:{1,,}Vm联合概率：{,}ijpPUiVj；条件概率：1{,}{|}{}ijijnkjkpPUiVjqPUiVjPVjp设11111nmmnmppppppp，11111nmmnmqqqqqqq，thblock1thblock,n1s()(00110)jnnnmnjjnmj000IIe，于是()jjjIpqfpep{}jq是凸集，{}q是凸集Chapter3ConvexFunction凸函数：一个函数:RnfR为凸函数若domf为凸集，且对,domfxy，[0,1]，有((1))()(1)()fffxyxy即凸组合的函数值≤函数值的凸组合严格凸函数：一个函数:RnfR为凸函数若domf为凸集，且对domfxy，(0,1)，有((1))()(1)()fffxyxy凹函数：若f是凸函数，则f是凹函数严格凹函数：若f是严格凸函数，则f是严格凹函数凸函数的另一种定义：一个函数:RnfR为凸函数若domf为凸集，且对domfx，nRv，有()()gtftxv在dom{|dom}gttfxv上是凸的扩展的凸函数：设函数:RnfR为凸函数，domnfR，则定义()dom()domffffxxxx例：已知凸集nRC0()nodefinedfxCxxC0()IxCxxC0()1JCxCxxC是凸函数是凸函数不是凸函数domf为凸集是为了保证(1)xy在定义域内,()fxx,()fyy((1))fxy()(1)()ffxy,()fxxtxv()gt降维凸函数的一阶条件（可微情况下的等价定义）：设函数:RnfR可微，即梯度f在domf均存在，则f为凸函数若domf为凸集，且对,domfxy，有()()()()Tfffyxxyx性质：若f为凸函数，0domfx，使0()f0x，则对domfy，0000()()()()()Tffffyxxyxx即0()fx是f的昀小值同理可定义严格凸函数的一阶条件设函数:RnfR可微，即梯度f在domf均存在，则f为凸函数若domf为凸集，且对domfxy，有()()()()Tfffyxxyx()fx()()Tfxyx,()fxx,()fyy附录：求证凸函数的一阶条件Step1：考虑一维情况，即f为凸函数若domf为凸集，且对,domxyf，有()()'()()fyfxfxyx充分性（）若f为凸函数，则对,domxyf（domf为凸集），有()(1)()(),[0,1]()()()()()()()()fxyxfxfyfyfxfxyxfxfxyxfxfyfx当0时，()()'()()fyfxfxyx必要性（）对,domxyf（domf为凸集），构造(1)zxy()()'()()(1)()()'()()(2)fxfzfzxzfyfzfzyz把(1)(1)(2)，得()(1)()()'()(1)()fxfyfzfzxyzfz，得证Step2：考虑多维情况，即f为凸函数若domf为凸集，且对,domfxy，有()()()()Tfffyxxyx充分性（）若f为凸函数，则对,domfxy（domf为凸集），有12212()(),[0,1]'()()()()()'()()(1)(0)()()()()TTTgfgfgggggffffxyxxyxyxxyxyxxyx必要性（）对,domfxy（domf为凸集），构造(1)zxy111222221221212212()(),,[0,1]()()'()()()()()()()()()'()TTgfgfgffffgggxyxxyxxyxyxxyxxyxxyxyx构造一个低维凸函数Step1的结论(1)(),(0)()gfgfyx凸函数的二阶条件（二阶可微情况下的等价定义）：定义：设向量x的数量值函数()fx二阶可微，则有12nxxxx，12()nfxfxffxx，22221121222222122222212()nnnnnfffxxxxxffffxxxxxfffxxxxxx（Hessian矩阵）定义：设函数:RnfR二阶可微，即梯度2f在domf均存在，则f为凸函数若domf为凸集，且对domfx，有2()fx半正定Note：对于一维情况，则要求该函数的二阶偏导≥0定义：f为严格凸函数若domf为凸集，且对domfx，有2()fx正定例如：函数4()fxx它是一个严格凸函数，但()fx在0x这一点不满足正定条件，故22()fxx正定是严格凸函数的充分而不必要条件例：函数21()fxx虽然242()60fxxx，但domf不是凸集，故不能通过凸函数的二阶条件来判定凸函数事实上，该函数确实不是凸函数例：二次函数:RnfR，domnfR，1()2TTfrxxPx+qx+（nPS，nRq，Rr）2()fxP，if0,convexfunctionif0,strictlyconvexfunctionif0,concavefunctionPPP例：仿射函数:nmRRf，domnRf，()fxAx+b（,mnmRRAb）2()f0x，故()fx即是凸函数又是凹函数例：指数