《第3讲凸集凸函数凸规划》由会员分享，可在线阅读，更多相关《第3讲凸集凸函数凸规划（51页珍藏版）》请在金锄头文库上搜索。
1、第第3 3讲讲 凸集、凸函数、凸规划凸集、凸函数、凸规划 凸集凸集 (Convex Set) 凸函数凸函数 (Convex Function) 凸规划凸规划 (Convex Programming)凸性凸性凸性凸性( (Convexity) )是最优化理论必须涉及到基本概念是最优化理论必须涉及到基本概念是最优化理论必须涉及到基本概念是最优化理论必须涉及到基本概念. .具有凸具有凸具有凸具有凸性的非线性规划模型是一类特殊的重要模型，它在最优化的理性的非线性规划模型是一类特殊的重要模型，它在最优化的理性的非线性规划模型是一类特殊的重要模型，它在最优化的理性的非线性规划模型是一类特殊的重要模型，它在
2、最优化的理论证明及算法研究中具有非常重要的作用论证明及算法研究中具有非常重要的作用论证明及算法研究中具有非常重要的作用论证明及算法研究中具有非常重要的作用. .襟映呕盘虐井隋刻手羌消霓于掳泵胜侧庚踪抨每妙邮涛验量烈材糠槛信敛第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划凸集凸集-定义定义线性组合线性组合 (linear Combination)仿射组合仿射组合 ( (Affine Combination)凸组合凸组合 (Convex Combination)凸锥组合凸锥组合 (Convex Cone Combination)每尝钠拢膘兴锣嗡札焦樟怯阮辱节肢泳贾踞稚计惠疼遭埋帮卑汞陀楞镶倘第3讲凸
3、集凸函数凸规划第3讲凸集凸函数凸规划凸集凸集-定义定义例例 二维情况下，两点二维情况下，两点x1 1, , x2 2 的的 (a) (a)线性组合为全平面；线性组合为全平面； (b) (b)仿射组合为过这两点的直线；仿射组合为过这两点的直线； (c) (c)凸组合为连接这两点的线段；凸组合为连接这两点的线段； (b) (b)凸锥组合为以原点为锥顶并通过这两点的锥凸锥组合为以原点为锥顶并通过这两点的锥. .砚飘静车蚌钟缠旋增煌黔插脖扬汗哨笋校查交坞协搞踌躺萧蓝雁深巢靖昼第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划凸集凸集-定义定义哼盔愿汽荔廖这乞缨瞪逐教吭全醋榜搂渐祸搽肇船蛆墩锥墟淑廊进琶商茵第
4、3讲凸集凸函数凸规划第3讲凸集凸函数凸规划凸集凸集-定义定义定义定义1 1设集合设集合若对于任意两点若对于任意两点及实数及实数都有：都有：则称集合则称集合为为凸集凸集常见的凸集常见的凸集：单点集单点集 x ，空集空集 ，整个欧氏空间，整个欧氏空间 Rn，超平面超平面：半空间半空间：涣汛措原啤天鉴拿长达骆吠鲍扛睡昭学因殷锁倪记泞裤笺晨惮挥得发窟燎第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划例：例： 证明超球证明超球为凸集为凸集证明证明： 设设为超球中的任意两点，为超球中的任意两点，则有：则有：即点即点属于超球属于超球, ,所以超球为凸集所以超球为凸集凸集凸集-举举例例巢址草拇颈检离闸提正操句暇拖
5、踢篷个剂帛赊隔蛀形戳涟讳烫就懈妈寓尼第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划 (1) (1) 任意多个凸集的交集任意多个凸集的交集为凸集为凸集 (2)(2)设设是凸集，是凸集， 是一实数，是一实数，则下面的则下面的集合是凸集：集合是凸集：凸集凸集-性性质质(3)(3)商切沦种被习善约纺灿宽佃起澎梭筒炕剂在语镐适瞬亚桨朴贮碱巾舟帛影第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划推论推论： 设设是凸集，是凸集， 则则也是凸集，也是凸集， 其中其中是实数是实数 (4)(4) S 是凸集当且仅当是凸集当且仅当S中任意有限个点的凸中任意有限个点的凸 组合仍然在组合仍然在S中中. .凸集凸集-性性质质潞
6、熊稀淄镶吐缎尉心鲸身疚手停寸刮标耗靴义谦洱任娥颧伟振绒永值胡郡第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划注：注：和集和集和和并集并集有很大的区别，凸集的并集有很大的区别，凸集的并集未必是凸集，而凸集的和集是凸集未必是凸集，而凸集的和集是凸集例例：表示表示轴上的点轴上的点表示表示轴上的点轴上的点则则表示两个轴的所有点，表示两个轴的所有点， 它不是凸集；它不是凸集；而而凸集凸集凸集凸集-性性质质咆狭痴控亩睫滇衬艾乱即骨窒癌矢桅研冤肯介消卞赊溯妥鳃寺牙灸孔偶崭第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划定义定义 设设 S S 中任意有限个点的所有凸中任意有限个点的所有凸组合所构成的集合称为组合所构
7、成的集合称为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讲凸集凸函数凸规划第3讲凸集凸函数凸规划定义定义 锥、凸锥锥、凸锥凸集凸集-凸锥凸锥 (Convex Cone)佛弦已臂怀曼梁笑塞簿效称箔省汽驾借匆嘉戍筒戳药秩蒋柄悦搏团落遥部第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划凸函
8、数凸函数凸函数凸函数(Convex Function)(Convex Function) -定义定义定义定义2.42.4设设是非空凸集，是非空凸集，若对任意的若对任意的及任意的及任意的都有：都有：则称函数则称函数为为上的凸函数上的凸函数注：注：将上述定义中的不等式反向，可以得到将上述定义中的不等式反向，可以得到凹函数凹函数的定义的定义邑斌狙渠袄拿痛宜兢打喂枫述搪踞短毯骸约诽暑屠攻谁波字浸迟谰固械染第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划凸函数凸函数严格凸函数严格凸函数设设是非空凸集，是非空凸集，若对任意的若对任意的及任意的及任意的都有：都有：则称函数则称函数为为上的上的严格凸函数严格凸函数
9、注：注：将上述定义中的不等式反向，可以将上述定义中的不等式反向，可以得到得到严格凹函数严格凹函数的定义的定义伊蜘窥为痒利挡撑翰五嗜深巾混降择售围既引蜜甫诉提谭及凳帐水巫竖乌第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划凸函数凸函数l 对一元函数对一元函数在几何上在几何上表示连接表示连接的线段的线段所以所以一元凸函数表示连接函数图形上任意两点一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方的线段总是位于曲线弧的上方几何性质几何性质表示在点表示在点处的处的函数值函数值l 筏商竹浓肄根鸟沦怪换嗽靛忿荣插适溉荡慷反器梧袭吃役狗岳容憎航锅艾第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划f(X)
10、f(X)X Xf(Xf(X1 1) )f(Xf(X2 2) ) X X1 1X X2 2吾连俞峙氰客抗彬倡示奴掘涪螺贷韧极裤姑芬逸讨类瘦练乔柱拜秸泽菇慧第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划f(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讲凸集凸函数凸规划第3讲凸集凸函数凸规划f(X)f(X)X Xf f(X(X1 1) )f f(X(X2 2) ) X X1
11、 1X X2 2 x x1 1+(1-+(1- )x)x2 2f f( ( x x1 1+(1-+(1- )x)x2 2 ) )罢家粒诧缄工缸缔促唱隅檀司颈驶家邑伯静贯肺崖肤公蔼莽疫谈血熏属筏第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划f(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 ) )氧目魁饼暴河踢欲捻仟像龙沂插奋缔丘自肾藩揭浚垛鸿佣券警妖抡蛮站衅第
12、3讲凸集凸函数凸规划第3讲凸集凸函数凸规划f(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讲凸集凸函
13、数凸规划第3讲凸集凸函数凸规划(a) 凸函数凸函数 (b)凹函数凹函数该定义的一个应用该定义的一个应用证明不等式证明不等式例：证明例：证明Young不等式不等式推广：推广：Hlder不等式不等式P41 2.37证法：在证法：在YoungYoung不等式中令不等式中令唇暂恒门串京命报鹊酉饱可咆夫抵酷拭陈档涩粗虱窟莽疙被诫郸晕催能河第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划例：例：设设试证明试证明在在上是严格凸函数上是严格凸函数证明证明: :设设且且都有：都有：因此因此, ,在在上是严格凸函数上是严格凸函数凸函数凸函数拌酮谈浮卡完纤咋痞褪萌尿行晃拄舟攒耍例奄婪扬蕊烟壮筒分勺柜淮皱毙第3讲凸集凸函
14、数凸规划第3讲凸集凸函数凸规划例：例：试证线性函数是试证线性函数是上的凸函数上的凸函数证明证明: :设设则则故故, ,是凸函数是凸函数类似可以证明类似可以证明也是凹函数也是凹函数.凸函数凸函数传影析韶府肮漆蝴署溺蛾量癌显僳舍妨滔轴帅飘证泼罢强偏菇玖试多椽迂第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划凸函数凸函数定理定理1 1 设设是凸集是凸集上的凸函数上的凸函数充要条件充要条件性质性质詹生詹生(Jensen)不等不等式式不等式应用不等式应用: 设设，证明，证明:P41 2.36美捕珠包渡发衅宪扯置灿卖茁星摹仗鼓诺缄琼甲蛛戳殴嫌酋狄柠冶关仲庐第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划凸函数凸函
15、数定理定理2 2性质性质正线性组合正线性组合勉紊艺技僧蔽沁屋颜升昆戒易浆拧忆淀记仟赖附骸盲砍镭团滞蜕骏腔赋蛙第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划凸函数凸函数定理定理3 3设设是凸集是凸集上的凸函数，上的凸函数，则对任意则对任意，水平集水平集是凸集是凸集水平集水平集(Level Set)称为函数称为函数f f在集合在集合S S上关于数上关于数 的水平集的水平集. .注：注：定理定理3 3 的逆命题不成立的逆命题不成立. .豪鹃久茬肚为峡诡矾铁和娃搀耙默阿欺童粟靴宁拐誊搔需肠秒倦氢送皆工第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划下面的图形给出了凸函数下面的图形给出了凸函数的等值线的图形，
16、可以看出水平集是凸集的等值线的图形，可以看出水平集是凸集. .凸函数凸函数犁疟迁底监梁共质果惕柄砰葫泣悦厅尾耳程洛刃挽精牌透鼓淹笆搁赞陌竖第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划凸函数凸函数痔摩薄娟谬涤告喇勘惯悼导枫涂彭杆央阳任炬运玉酵刮介毫政休即泳海灌第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划定理定理1:1:设设是定义在凸集上，上，令令则则: :(1(1) )是定义在凸集是定义在凸集是凸集是凸集上的上的凸函数凸函数的充要条件是对的充要条件是对任意的任意的一元函数一元函数为为上的凸函数上的凸函数. .(2(2) )设设若若在在上为上为严格严格凸函数凸函数， 则则在在上为严格凸函数上为严格
17、凸函数凸函数凸函数凸函数的判别定理凸函数的判别定理吾巳杂捧形梧良肘酶族朋娘植破去麦傅耻享琼姑攀巩福贡眩碧吊厄龄汁昏第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划该定理的该定理的几何意义几何意义是：凸函数上任意两点之是：凸函数上任意两点之间的部分是一段向下凸的弧间的部分是一段向下凸的弧凸函数凸函数棒麓咐赃拾挪涧秋钟渡甘谚巢瞒抉血查懒恕仰罕襟争篇黑紊烛谱测储摇豁第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划定理定理4 4设在凸集设在凸集上上可微可微， 则：则：在上为凸函数的充要条件是对任意的上为凸函数的充要条件是对任意的都有：都有：严格凸函数严格凸函数( (充要条件充要条件)?)?凸函数凸函数凸函数的
18、判别定理凸函数的判别定理-一阶条件一阶条件注：注：定理定理4 4提供了一个判别可微函数是否为凸提供了一个判别可微函数是否为凸 函数的依据函数的依据. .缴粗矢碟坦钉锄旬擅疏城党葛箕禹备右菩妖立蚂蹄搜毛尹肯疽迢祸眷职蝉第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划凸函数凸函数定理定理4-几何几何解释解释一个可微函数一个可微函数是凸函数当且是凸函数当且仅当函数图形仅当函数图形上任一点处的上任一点处的切线位于曲切线位于曲线的下方线的下方.各墩靠嫁暂技巳拟颈傣劣勇休各奢苯晚瞄诀逃叔倾谷阁擂岭卑锣膘午磁盎第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划凸函数凸函数定理定理4-几何几何解释解释一个可微函数一个可
19、微函数是凸函数当且是凸函数当且仅当函数图形仅当函数图形上任一点处的上任一点处的切平面位于曲切平面位于曲面的下方面的下方.恰企斟忌仑广植磁揽狞犯褐卷椭尔篮碳炊伊粥舰剿澡甜嗣诫鹰沉汀墨足何第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划定理定理5:5:设在开凸集设在开凸集内内二阶可微二阶可微, ,则则是内的凸函数的充要条件为内的凸函数的充要条件为: :对任意对任意的的HesseHesse矩阵矩阵半正定半正定, ,其中：其中：凸函数凸函数凸函数的判别定理凸函数的判别定理-二阶条件二阶条件饵斑掺脓匡杀皂韶出屿绍哭搁民酗俗宛机庭坞压昆丽流绝皑宜矣坡陆苦河第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划定理定理2
20、.3.6:2.3.6: 设在开凸集设在开凸集内内二阶可微二阶可微, ,若在若在内内正定正定, ,则则在在内内是严格凸函数是严格凸函数注注: : 反之不成立反之不成立例例：f(x)是严格凸的，是严格凸的，但在点但在点处不是正定的不是正定的凸函数凸函数凸函数的判别定理凸函数的判别定理-二阶条件二阶条件郸力赔靴但琢噶辜阶聂眼碳足颗峭刊绑粤妹哭雏甄孟蕉窗诸访绦疆搽妓逻第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划例：例：凸函数凸函数凸函数的判别定理凸函数的判别定理-二阶条件二阶条件填纠丽宣佛序它邢喇磺闹州肚傲毁桔没鞭叠谐尽衫起忻阶颈鼎懂毅盯蕴守第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划凸规划凸规划凸规
21、划凸规划(Convex Programming)(Convex Programming)设设为凸集为凸集，为为上的凸函数上的凸函数，则称规划问题则称规划问题为凸规划问题为凸规划问题例：例：为为上的凸函数，上的凸函数，为无约束凸规划问题为无约束凸规划问题例：例：凸凸规规划划牟厩寨旧僵蚕蛰晨擒颁汞率歹猩须霍渐忻氯帘根学总复瑞阑满韭贴护绝仍第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划凸规划凸规划例：例：邪鄂彦冶佛幕寂潦素悬劲僚怂捎雌谢郊猴慕眶追迟璃崩灭介窜峨完改尘膘第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划凸规划凸规划定理定理2.42.4(1)(1)凸规划问题的任一局部极小点是全局凸规划问题的任一
22、局部极小点是全局极小点，且全体极小点的集合为凸集极小点，且全体极小点的集合为凸集(2(2) )若若是凸集是凸集上的严格凸函数，上的严格凸函数，且凸规划问题且凸规划问题局部极小点局部极小点x x* *存在，存在，则则x x* *是唯一的全局极小点是唯一的全局极小点凸规划的基本性质凸规划的基本性质钡症促张各撰诊遮谰被饱垛低村尝朽富贫矗隔喳瞥圣音奄骤婚锡备虞玫怀第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划定理定理 凸规划的任一局部最优解都是它的整体最优解。凸规划的任一局部最优解都是它的整体最优解。证明：设证明：设x*是凸规划的一个局部解，则存在是凸规划的一个局部解，则存在0,使使如果如果x*不是整体
23、最优解，则不是整体最优解，则又因为又因为f是凸函数，所以是凸函数，所以取取0充分小，有充分小，有艰盼焦漓阜薄们睬猫棘迷膨犬父蒙儡耀欺玻滔扎婪心瞒镣丢榨蚤惯硬悲奸第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划例 如下非线性规划是否为凸规划：正定，正定，凸函数凸函数舅犹亦鬃戈栽钦朱邓衔颁柯钓鼠樱之框文貌谗属闹钧园九载讹衍灿键矮筒第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划所以，该问题为凸规划。半正定，半正定，凸函数凸函数半正定，半正定，凸函数凸函数嘘朵县贱矿协奉安孜南茨终碑晋药栽独巫谐娟锄芳般炼女淄确彩胸溯郝辰第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划 如图所示，该问题最优解（最小点）在如图所示，
24、该问题最优解（最小点）在如图所示，该问题最优解（最小点）在如图所示，该问题最优解（最小点）在x x* *点取得。点取得。点取得。点取得。止烛橙娟靛腊粪爬酞厘辞狰航蔚腻腻音借椭但纬倔氧寒绷瞻彰刚激乳石呵第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划例例 验证下列（验证下列（MP）是凸规划）是凸规划亚赌咽咎卷赣醇驳思希壕遂冯颗笛妈赊琅龚尝翠汰雅束沁逆净难塘伐秉捡第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划作业作业nP38 2.1, 2.2, 2.4, 2.9-14,2.19, 2.20(后),2.32, 2.36膏冀疥黔志瞩宝绰槽钒下邢碎菱帜纶怔石鳃瞎雾岗澜墓辗踏知神异茸锦蹲第3讲凸集凸函数凸规划第3讲凸集凸函数凸规划
