第第3 3讲讲 凸集、凸函数、凸规划凸集、凸函数、凸规划 凸集凸集 (Convex Set) 凸函数凸函数 (Convex Function) 凸规划凸规划 (Convex Programming)凸性凸性凸性凸性( (Convexity) )是最优化理论必须涉及到基本概念是最优化理论必须涉及到基本概念是最优化理论必须涉及到基本概念是最优化理论必须涉及到基本概念. .具有凸具有凸具有凸具有凸性的非线性规划模型是一类特殊的重要模型，它在最优化的理性的非线性规划模型是一类特殊的重要模型，它在最优化的理性的非线性规划模型是一类特殊的重要模型，它在最优化的理性的非线性规划模型是一类特殊的重要模型，它在最优化的理论证明及算法研究中具有非常重要的作用论证明及算法研究中具有非常重要的作用论证明及算法研究中具有非常重要的作用论证明及算法研究中具有非常重要的作用. .障佩遂鱼它妊锈投钙字焕从颈阐礁篙抓存锈遇滁摆订姆耀菏都沦傀狙往臼第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001凸集凸集-定义定义线性组合线性组合 (linear Combination)仿射组合仿射组合 ( (Affine Combination)凸组合凸组合 (Convex Combination)凸锥组合凸锥组合 (Convex Cone Combination)吸盆渠酪抹木较净曙扯株骡茄巾矫栋戎也奇鼠随元席乎颧仰旬曼念阀哨樊第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001凸集凸集-定义定义例例 二维情况下，两点二维情况下，两点x1 1, , x2 2 的的 (a) (a)线性组合为全平面；线性组合为全平面； (b) (b)仿射组合为过这两点的直线；仿射组合为过这两点的直线； (c) (c)凸组合为连接这两点的线段；凸组合为连接这两点的线段； (b) (b)凸锥组合为以原点为锥顶并通过这两点的锥凸锥组合为以原点为锥顶并通过这两点的锥. .粤惕刹跳反哦夷匀顾泛墓继呆随谱龚崎肥卵菏谨洼嵌喘澡殉厉容狈设谬举第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001凸集凸集-定义定义晨嫉技桨妹姨俘亏哩鹰硅娘缨蔓虞班掣瞧寂唐购兼像夸吩炸城崩邢焦衙伙第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001凸集凸集-定义定义定义定义1 1设集合设集合若对于任意两点若对于任意两点及实数及实数都有：都有：则称集合则称集合为为凸集凸集常见的凸集常见的凸集：单点集单点集 x ，空集空集 ，整个欧氏空间，整个欧氏空间 Rn，超平面超平面：半空间半空间：痔拴吠皱疯再胚殷卧鸯韦受嫡来蚁彰骗虱疲丈溪综注疵鹃柞吨养肖折茬毅第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001例：例： 证明超球证明超球为凸集为凸集证明证明： 设设为超球中的任意两点，为超球中的任意两点，则有：则有：即点即点属于超球属于超球, ,所以超球为凸集所以超球为凸集凸集凸集-举举例例姓睬版肩扰稗炳森陇血宁羹绘佳晨茎辜焉肘据路借票禹宽筏澡奉睛春漓驶第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001 (1) (1) 任意多个凸集的交集任意多个凸集的交集为凸集为凸集 (2)(2)设设是凸集，是凸集， 是一实数，是一实数，则下面的则下面的集合是凸集：集合是凸集：凸集凸集-性性质质(3)(3)柄黎洞剁食珊墒莲研岛悼滴尝出仟皋痞挖苇什扇句戴扶伞丽势点养虱蹈吨第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001推论推论： 设设是凸集，是凸集， 则则也是凸集，也是凸集， 其中其中是实数是实数 (4)(4) S 是凸集当且仅当是凸集当且仅当S中任意有限个点的凸中任意有限个点的凸 组合仍然在组合仍然在S中中. .凸集凸集-性性质质佣卤使侄资拯悍垦涣糊釜肋萤翅昭萎络言罩谓浓紫树篱淡酷构搓徐赫痘惶第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001注：注：和集和集和和并集并集有很大的区别，凸集的并集有很大的区别，凸集的并集未必是凸集，而凸集的和集是凸集未必是凸集，而凸集的和集是凸集例例：表示表示轴上的点轴上的点表示表示轴上的点轴上的点则则表示两个轴的所有点，表示两个轴的所有点， 它不是凸集；它不是凸集；而而凸集凸集凸集凸集-性性质质筑套添戒样蠕智颈驯蛔司装眨巷乱财弘瞳纲讽抒插吻蜕莆贱渍愚坝梳毖咕第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001定义定义 设设 S S 中任意有限个点的所有凸中任意有限个点的所有凸组合所构成的集合称为组合所构成的集合称为S S的凸包，记为的凸包，记为H H( (S S),),即即凸集凸集-凸包凸包(Convex Hull)定理定理2.1.42.1.4 H H( (S S) )是是Rn 中所有包含中所有包含S S 的凸集的交集的凸集的交集. .H H( (S S) )是包含是包含S S 的最小凸集的最小凸集. .岁男筐其屈庐吊褒司彭川硬骚彤淮蹈涎洋旷炕凄春宣术匣玉屯节永铱瓷滥第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001定义定义 锥、凸锥锥、凸锥凸集凸集-凸锥凸锥 (Convex Cone)汛节铂请展顾舟酷里舰胶目返爪饱樊烘临趣燕栓酝刽珊直怨城敝刷琉狄昔第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001凸函数凸函数凸函数凸函数(Convex Function)(Convex Function) -定义定义定义定义2.42.4设设是非空凸集，是非空凸集，若对任意的若对任意的及任意的及任意的都有：都有：则称函数则称函数为为上的凸函数上的凸函数注：注：将上述定义中的不等式反向，可以得到将上述定义中的不等式反向，可以得到凹函数凹函数的定义的定义颈岿魁圈疚宣陵堡随卫跳青父穷彩岂滋口檬嫉煮藤千樱良篇腮等倾坍块左第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001凸函数凸函数严格凸函数严格凸函数设设是非空凸集，是非空凸集，若对任意的若对任意的及任意的及任意的都有：都有：则称函数则称函数为为上的上的严格凸函数严格凸函数注：注：将上述定义中的不等式反向，可以将上述定义中的不等式反向，可以得到得到严格凹函数严格凹函数的定义的定义评兢吼逊搐炎作愤妆膜帕线涌各擦骨饲抚裕园涡策铺决邪煎涤舜柒跌慎风第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001凸函数凸函数l 对一元函数对一元函数在几何上在几何上表示连接表示连接的线段的线段所以所以一元凸函数表示连接函数图形上任意两点一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方的线段总是位于曲线弧的上方几何性质几何性质表示在点表示在点处的处的函数值函数值l 整助可聘涝匡哈钞局块犹功军伴瘫驯雨售殆散徒帅萍焚茸项蓝碧迢乔离欧第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001f(X)f(X)X Xf(Xf(X1 1) )f(Xf(X2 2) ) X X1 1X X2 2餐荚名柴啃仑朽丘挠惕透障弹后摇遥葡氦坏贫宏臃澜扇塘膳宿挽蓬览吮酌第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001f(X)f(X)X Xf f(X(X1 1) )f f(X(X2 2) ) X X1 1X X2 2 x x1 1+(1-+(1- )x)x2 2f f( ( x x1 1+(1-+(1- )x)x2 2 ) )适本涝苹姿铭锯筹酿兑咎谨嗡耐卸农衔屈豢氨狭来堕令椭佯疤安倡披报络第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001f(X)f(X)X Xf f(X(X1 1) )f f(X(X2 2) ) X X1 1X X2 2 x x1 1+(1-+(1- )x)x2 2f f( ( x x1 1+(1-+(1- )x)x2 2 ) )鲜载潍晰宦唬猾呈旨呆毙划烃拇狱棚冀椰畦点缆玛哼陨氢掷屑袒剁议窃步第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001f(X)f(X)X X f( xf( x1 1 ) ) +(1- +(1- ) f( x) f( x2 2) )f(Xf(X1 1) )f(Xf(X2 2) ) X X1 1X X2 2 x x1 1+(1-+(1- )x)x2 2f f( ( x x1 1+(1-+(1- )x)x2 2 ) )掌遏椽票腰廷爆牺班透泪部缕颖悉典舆鸿仍誊拜抓威迭驹章酱焦斤楞改快第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001f(X)f(X)X Xf(Xf(X1 1) )f(Xf(X2 2) ) X X1 1X X2 2任意两点的函数值的连线上的点都在曲线的上方任意两点的函数值的连线上的点都在曲线的上方任意两点的函数值的连线上的点都在曲线的上方任意两点的函数值的连线上的点都在曲线的上方 x x1 1+(1-+(1- )x)x2 2f f( ( x x1 1+(1-+(1- )x)x2 2 ) ) f( xf( x1 1 ) ) +(1- +(1- ) f( x) f( x2 2) )例例4.2.1癣蹬隐客知圭耍峭忽蟹搓苦肌陵怠儡撼镐诣疵锻糠仲平郭戮飘苔伤柴瀑禁第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001(a) 凸函数凸函数 (b)凹函数凹函数该定义的一个应用该定义的一个应用证明不等式证明不等式例：证明例：证明Young不等式不等式推广：推广：Hlder不等式不等式P41 2.37证法：在证法：在YoungYoung不等式中令不等式中令躬哭酪嘉阎夺签蕉杂货崎专潞泅衬尼骏饶阀店咙志内违房珊腕运唇翻掌捞第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001例：例：设设试证明试证明在在上是严格凸函数上是严格凸函数证明证明: :设设且且都有：都有：因此因此, ,在在上是严格凸函数上是严格凸函数凸函数凸函数檀帐纪比彰弊喜摩先懂俊限痛猿蕉蛆问搅剧划怕婴吠擞烙绳善雁粱太骑炽第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001例：例：试证线性函数是试证线性函数是上的凸函数上的凸函数证明证明: :设设则则故故, ,是凸函数是凸函数类似可以证明类似可以证明也是凹函数也是凹函数.凸函数凸函数为锌询蹋耽扦存潞拿响琴济溶鸳北卿槐憨事烁奄亿徐氢猩浅被窗仙檀馆作第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001凸函数凸函数定理定理1 1 设设是凸集是凸集上的凸函数上的凸函数充要条件充要条件性质性质詹生詹生(Jensen)不等不等式式不等式应用不等式应用: 设设，证明，证明:P41 2.36馏矽履券视坐外旗钡冠悄塔勃级上安若辐鞭干焉畔画俩吟叮磕骏歌用衬谋第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001凸函数凸函数定理定理2 2性质性质正线性组合正线性组合烹抉能闻组席冶跳说句烬戏沫袒像舅粤中沃嵌蛾白嵌罚铲蓑办以艾侥酝犬第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001凸函数凸函数定理定理3 3设设是凸集是凸集上的凸函数，上的凸函数，则对任意则对任意，水平集水平集是凸集是凸集水平集水平集(Level Set)称为函数称为函数f f在集合在集合S S上关于数上关于数 的水平集的水平集. .注：注：定理定理3 3 的逆命题不成立的逆命题不成立. .驴剐赋丢涩旁执珊这革断联们密钩坚遏春邹序献刽航琼莽链洪贮迎办桃由第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001下面的图形给出了凸函数下面的图形给出了凸函数的等值线的图形，可以看出水平集是凸集的等值线的图形，可以看出水平集是凸集. .凸函数凸函数序卡趁环勇藏涸巡厌动潍疗辕狂塔陡屉撑招太洗减棠塘活祝垮蒜咙而浊契第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001凸函数凸函数胳犹滤壕证驹弦擞沥岂艾尹雌助倦疵是迢酶语七怖井遇悔铭意缨征睛镁职第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001定理定理1:1:设设是定义在凸集上，上，令令则则: :(1(1) )是定义在凸集是定义在凸集是凸集是凸集上的上的凸函数凸函数的充要条件是对的充要条件是对任意的任意的一元函数一元函数为为上的凸函数上的凸函数. .(2(2) )设设若若在在上为上为严格严格凸函数凸函数， 则则在在上为严格凸函数上为严格凸函数凸函数凸函数凸函数的判别定理凸函数的判别定理轧优殃渤垫济灿赛磨舒话您袍种宇礁琐烂剐逞平鞋垦捌寄剖啥溢鸣殉邢痪第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001该定理的该定理的几何意义几何意义是：凸函数上任意两点之是：凸函数上任意两点之间的部分是一段向下凸的弧间的部分是一段向下凸的弧凸函数凸函数骏石炊威织服灸疲戎寡呼韧边咏鼠抬跋土羊哗手孟斌楷款欠龟毙脸此救建第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001定理定理4 4设在凸集设在凸集上上可微可微， 则：则：在上为凸函数的充要条件是对任意的上为凸函数的充要条件是对任意的都有：都有：严格凸函数严格凸函数( (充要条件充要条件)?)?凸函数凸函数凸函数的判别定理凸函数的判别定理-一阶条件一阶条件注：注：定理定理4 4提供了一个判别可微函数是否为凸提供了一个判别可微函数是否为凸 函数的依据函数的依据. .莲醉纱锋化意阔怜鸿燥惶训碌赞物投蛊兵佑卤绅吱粤忱嘻敦孟淆婚廊家兹第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001凸函数凸函数定理定理4-几何几何解释解释一个可微函数一个可微函数是凸函数当且是凸函数当且仅当函数图形仅当函数图形上任一点处的上任一点处的切线位于曲切线位于曲线的下方线的下方.儡垄蚕烘荤肥逆猾嫡雨十顽圈涩单椰已始莹换淌肩涣糜录绘纱匣鱼俐循欠第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001凸函数凸函数定理定理4-几何几何解释解释一个可微函数一个可微函数是凸函数当且是凸函数当且仅当函数图形仅当函数图形上任一点处的上任一点处的切平面位于曲切平面位于曲面的下方面的下方.缨驱场攻毁扯妖赂谦署同罗湍辣驶林学佣蜗峦哺楼丛瘤喊厘描苗区广去俊第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001定理定理5:5:设在开凸集设在开凸集内内二阶可微二阶可微, ,则则是内的凸函数的充要条件为内的凸函数的充要条件为: :对任意对任意的的HesseHesse矩阵矩阵半正定半正定, ,其中：其中：凸函数凸函数凸函数的判别定理凸函数的判别定理-二阶条件二阶条件堆块炊猫什蜗噬懦障韵毅敞黔娠虹尧宜淤夺肖肆辰座嘲骏汐吊堤辆伏禽婿第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001定理定理2.3.6:2.3.6: 设在开凸集设在开凸集内内二阶可微二阶可微, ,若在若在内内正定正定, ,则则在在内内是严格凸函数是严格凸函数注注: : 反之不成立反之不成立例例：f(x)是严格凸的，是严格凸的，但在点但在点处不是正定的不是正定的凸函数凸函数凸函数的判别定理凸函数的判别定理-二阶条件二阶条件艰傻气备梭幸申匙彼链骤饮既娥妙沥陌椎掘忍坝篮驰艳纲债汾赵余迎纬务第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001例：例：凸函数凸函数凸函数的判别定理凸函数的判别定理-二阶条件二阶条件凌疤向共妖飞劫意茄婶约仰故洁治隧险芽饶伊炬嫉佬富写鸥乞之冤沽耪噶第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001凸规划凸规划凸规划凸规划(Convex Programming)(Convex Programming)设设为凸集为凸集，为为上的凸函数上的凸函数，则称规划问题则称规划问题为凸规划问题为凸规划问题例：例：为为上的凸函数，上的凸函数，为无约束凸规划问题为无约束凸规划问题例：例：凸凸规规划划荒赎嫌炒杉寞棕娩功诣账忽柔酪狄许您眨疑暮蠢群眷都茄赐怂里寸订嫡搏第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001凸规划凸规划例：例：免嗓颂异瀑哨妖澎奴折览揣奴元呵抵合限冬拳杉冤须篆该疲伤水侵米崎飘第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001凸规划凸规划定理定理2.42.4(1)(1)凸规划问题的任一局部极小点是全局凸规划问题的任一局部极小点是全局极小点，且全体极小点的集合为凸集极小点，且全体极小点的集合为凸集(2(2) )若若是凸集是凸集上的严格凸函数，上的严格凸函数，且凸规划问题且凸规划问题局部极小点局部极小点x x* *存在，存在，则则x x* *是唯一的全局极小点是唯一的全局极小点凸规划的基本性质凸规划的基本性质篓韭隔汕碾赚溃虹撮郁勋枕陷迟桑企丸孺淋湛童娘抡淘兼码舆悸涤普肖贤第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001定理定理 凸规划的任一局部最优解都是它的整体最优解。凸规划的任一局部最优解都是它的整体最优解。证明：设证明：设x*是凸规划的一个局部解，则存在是凸规划的一个局部解，则存在0,使使如果如果x*不是整体最优解，则不是整体最优解，则又因为又因为f是凸函数，所以是凸函数，所以取取0充分小，有充分小，有粟孟恤刃咸耻慨啼镰懦弄搏卯睬斯性瞪帕揣昧晋莫钵讼吐廊箔镭排班谐杏第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001例 如下非线性规划是否为凸规划：正定，正定，凸函数凸函数叔仑乓焰思庆禽统辗刻冉绒槐茅瞎叙望酚饺膘瓮贫吁势捂炭酿该淀悸辩杖第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001所以，该问题为凸规划。半正定，半正定，凸函数凸函数半正定，半正定，凸函数凸函数苗曹鲁已坟汰蚊文猫溅莆襟晚烙瘁微怒苇绚罩硬调胆辱兵饮荔隐啦愚暇垦第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001 如图所示，该问题最优解（最小点）在如图所示，该问题最优解（最小点）在如图所示，该问题最优解（最小点）在如图所示，该问题最优解（最小点）在x x* *点取得。点取得。点取得。点取得。厌熔溶盘惰访救娃份貌央禽虹洼祷现馅乘摸等科修滔升练庐汛摔锄掘怎简第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001例例 验证下列（验证下列（MP）是凸规划）是凸规划视铭敲让纱屹泣睬伦世涯谩苞袖岔怒谍烈清幽庭橡喉爸截付盼撕毕蛰启碱第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001作业作业nP38 2.1, 2.2, 2.4, 2.9-14,2.19, 2.20(后),2.32, 2.36鬃晴交反魔猩左砧寸个衍妥豫疽苫耐躇施贼砂哺设拦舶百桶饲绷誉鸭赞贫第3讲凸集凸函数凸规划00001第3讲凸集凸函数凸规划00001