凸优化理论笔记－金锄头文库

资源描述

《凸优化理论笔记》由会员分享，可在线阅读，更多相关《凸优化理论笔记（78页珍藏版）》请在金锄头文库上搜索。

1、Chapter 2 Convex Set 对于12nR?xx 连接两点的直线可表示为?12(1),R?x | xxx 连接两点的线段可表示为?12(1),0,1?x | xxx 仿射集（仿射集（Affine Set）定义：C是仿射集12,?x xC，则连接两点的直线直线也在C内例：线性方程组的解集是仿射集证：线性方程组的解集可表示为,m nn?RRCx| Ax = b Ab 设12,?x xC，则1Ax = b，1Ax = b ?1212(1)(1)(1)?AxxAx +Axbbb，得证仿射组合（仿射组合（Affine Combination）设k个点12,k?x xx，1212,

2、1kkR? ? ? ? ?则称1122kk?xxx为12,k?x xx的仿射组合仿射包（仿射包（Affine Hull）任意集合n?RC，C中任意元素的仿射组合构成的集合称仿射包 1211221212,aff, 1kkkkkR? ? ? ? ? ?x xxCCxxx 如果一个集合的仿射包就是它自己，那么它就是一个仿射集 ?一条直线是仿射集，一条线段则不是平面是仿射集，一块矩形区域则不是凸集（凸集（Convex Set）定义：C是仿射集12,?x xC，则连接两点的线段线段也在C内凸组合（凸组合（Convex Combination）设k个点12,k?x xx，12120,1, 1k

3、k? ? ? ? ?则称1122kk?xxx为12,k?x xx的凸组合凸包（凸包（Convex Hull）任意集合n?RC，C中任意元素的凸组合构成的集合称凸包 1211221212,conv,0,1 1kkkkk? ? ? ? ? ?x xxCCxxx 一个凸集，它的凸包就是它本身 ?一条直线是凸集，一条线段也是凸集平面是凸集，一块矩形区域也是凸集凸集非凸集非凸集凸集的凸包（本身）非凸集的凸包凸锥（凸锥（Convex Cone）定义：C是仿射集12,?x xC，对12,0? ?，有1122?xxC 凸锥组合（凸锥组合（Convex Cone Combination）设k个点1

4、2,k?x xx，12,0k? ? 则称1122kk?xxx为12,k?x xx的凸锥组合凸锥包（凸锥包（Convex Cone Hull）任意集合n?RC，C中任意元素的凸锥组合构成的集合称凸锥包 12 1122 12,0k kk k? ?x xxCxxx?一个凸锥集，它的凸锥包就是它本身过原点的射线是凸锥过原点的两条射线之间的区域是凸锥集合名称凸集仿射集凸锥 1. 空集 2. 1 个点 3. nR空间 4. nR空间的子空间：0x| Ax = 5. 任一直线 6. 任一线段 7. 任一射线：?00?xv | 8. 超平面：,TnbbR?Rx|a x =x 9. 半空间：,Tn

5、TnbbRbbR?RRx |a xxx |a xx 10. 欧几里得空间中的球： ?2(, )|,n cccrrrR?RB xxxxx 11. 欧几里得空间中的椭球： ?1(, ,)()(),Tn ccccrrrR?RE xPx xxPxxxP正定 12. 多面体（Polyhedron）： ,1,1,T iiT jjimjn?a xbPxc x = d（很多超平面和半空间的交集） 13. 对称矩阵：?|nn nT?RSAA= A 14. 对称半正定矩阵：?|,nn nT? ?R0?SAA= AA 15. 对称正定矩阵：?|,nn nT? ?R0?SAA= AA 10）证明：设12,?x xB

6、，则1222|ccrr?xxxx? ? ? ?1221221221222|(1)|(1)(1)|(1)|(1)|(1)ccccccc rrr?xxxxxxxxxxxxxxx(1)xxx?1 12 2( ,)xa abx? ?13）对称阵是仿射集，因而是凸集证明：设12,n?A AS，则11T?AA，22T?AA 对R? ?，?1212(1)(1)T?AAAA，得证 14）对称半正定阵是凸锥，因而是凸集证明：设12,n ?A AS，则11T?AA，22T?AA，且对?x，有10T?x A x，20T?x A x 对称已证明，现证明半正定，对?x和12,0? ?，11221122()0TTT?

7、xAA x =x A xx A x，得证 14）对称正定阵是凸集证明：设12,n ?A AS，则11T?AA，22T?AA，且对0? ?x，有10Tx A x ，20Tx A x 对称已证明，现证明正定，对0? ?x和0,1? ?，?1212(1)(1)0TTT?xAAx =x A xx A x ，得证保持凸集凸性的操作保持凸集凸性的操作 ? 交集（交集（Intersection）若1S，2S为凸集，则12?SS为凸集。若?S为凸集，对A?，则 A? S为凸集。注：并集不能保持凸集的凸性 ? 仿射函数（仿射函数（Affine Function）定义定义：对 dom n?Rx，( )

8、,m nm?RRf xAx+b Ab，在称:nm?RRf是仿射的定理定理：若n?SR是凸的，:nm?RRf是仿射的，则S在f下的映射( ) ( )|?f Sf xxS是凸的同样，若n?SR是凸的，:nm?RRg是仿射的，则S在g下的反映射1( ) | ( )?gSx g xS是凸的例例：缩放|?Sx xS和位移|?Sax+a xS是保持凸性的例例：两个凸集的和和1212|,?SSx+ y xSyS是保持凸性的解释如下，集合1S与集合2S的笛卡尔乘积笛卡尔乘积1212( , )|,?SSx yxSyS?是保持凸性的集合12?SS在仿射变换( , )f x yxy?下1212()?f

9、SSSS依然是保持凸性的例例：线性矩阵不等式（LMI: Linear Matrix Inequality）：11( )nnxx?A xAAB?，,n i?B AS（对称阵）类比一般的线性不等式（Linear Inequality）：1 1T nnx ax ab?a x?，,ib xR?）求证：线性矩阵不等式()A XB?的解集|()X A XB?是凸集证明：()()n ?f XBA XS?是凸集 1()|()n? ?fXX BA XS也是凸集例例：椭球是球的仿射映射，因此是凸的球?2|1,n?Ruuu是凸的，它在仿射变换1 2( )cx uP u+ x?下?2( ) |1,n?

11、,),0( ,),0nnnnxxyy?xxyy?，则1n?R内的一个线段可表示为(1) ,0,1?xy 该线段经透视变换后仍为线段 ? ? ?11111111111110,1(1)(1)(1)(1)(1)(1)(1)(1)nnnnnnnnnnnnnx xyxy xyxyxxyy?xyxyPxy+P xP y? 线性分数函数（线性分数函数（Linear-fractional Function）设仿射函数1:nm?RRg满足( )Td?Abg xx+c，,Rm nmnd?RRRAbc设透视函数1:mm?RRP满足( , ),Rmttt?RzP zz 定义线性分数函数:nm?RRf满足?fPg?，

12、即 ?( )( )dom |0T TTddd?Ax+bAx+bf xP g xPfx c xc xc x例：两个随机变量的联合概率与条件概率设两个离散型随机变量（Random Variable）:1, Un?，:1, Vm? 联合概率：,ijpP Ui Vj?；条件概率：1,|ij ijnkj kpP Ui VjqP Ui VjP Vjp?设11111nmmnmpppp? ? ? ? ? ?ppp?，11111nmmnmqqqq? ? ? ? ? ?qqq?，?th block1 th block, n1s()(00110)jn nnm njjnm j?000IIe?，于是( )j j j?

13、I pqf pe pjq是凸集， q是凸集 Chapter 3 Convex Function 凸函数凸函数：一个函数:Rnf?R为凸函数? 若domf为凸集，且对,domf?x y，0,1? ?，有 (1) )( )(1) ( )fff?xyxy 即凸组合的函数值函数值的凸组合严格凸函数严格凸函数：一个函数:Rnf?R为凸函数? 若domf为凸集，且对domf? ?xy，(0,1)? ?，有 (1) )( )(1) ( )fff?xyxy 凹函数凹函数：若f?是凸函数，则f是凹函数严格凹函数严格凹函数：若f?是严格凸函数，则f是严格凹函数凸函数凸函数的另一种定义：一个函数:Rnf?R为凸函数? 若domf为凸集，且对domf? ?x，n? ?Rv，有 ( )()g tft?xv在dom |dom gttf?xv上是凸的扩展的凸函数：扩展的凸函数：设函数:Rnf?R为凸函数，domnf?R，则定义 ( )dom( )domffff?xxxx?例：已知凸集n?RC 0( )no definedf?xCxxC0( )I?xCxxC0( )1JC?xCxxC是凸函数是凸函数不是凸函数 domf为凸集是为了保证(

展开阅读全文