《第3讲凸集凸函数凸规划ppt课件》由会员分享，可在线阅读，更多相关《第3讲凸集凸函数凸规划ppt课件（51页珍藏版）》请在金锄头文库上搜索。
1、第第3 3讲讲 凸集、凸函数、凸规划凸集、凸函数、凸规划 凸集凸集 (Convex Set) 凸函数凸函数 (Convex Function) 凸规划凸规划 (Convex Programming)凸性凸性凸性凸性( (Convexity) )是最优化理论必须涉及到基本概念是最优化理论必须涉及到基本概念是最优化理论必须涉及到基本概念是最优化理论必须涉及到基本概念. .具有凸具有凸具有凸具有凸性的非线性规划模型是一类特殊的重要模型，它在最优化的理性的非线性规划模型是一类特殊的重要模型，它在最优化的理性的非线性规划模型是一类特殊的重要模型，它在最优化的理性的非线性规划模型是一类特殊的重要模型，它在
2、最优化的理论证明及算法研究中具有非常重要的作用论证明及算法研究中具有非常重要的作用论证明及算法研究中具有非常重要的作用论证明及算法研究中具有非常重要的作用. .库吉亿箍赡誓渤董妆水藐炒孰钙杠海跪叁详岔浮暗齐示刚篷既在醛哩筐场第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件凸集凸集-定义定义线性组合线性组合 (linear Combination)仿射组合仿射组合 ( (Affine Combination)凸组合凸组合 (Convex Combination)凸锥组合凸锥组合 (Convex Cone Combination)窜党遣降打瘴悟沈吊愤城添帧酷浸谅浴厨侍亭咐退律焰林障
3、噬糟湛棺修椰第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件凸集凸集-定义定义例例 二维情况下，两点二维情况下，两点x1 1, , x2 2 的的 (a) (a)线性组合为全平面；线性组合为全平面； (b) (b)仿射组合为过这两点的直线；仿射组合为过这两点的直线； (c) (c)凸组合为连接这两点的线段；凸组合为连接这两点的线段； (b) (b)凸锥组合为以原点为锥顶并通过这两点的锥凸锥组合为以原点为锥顶并通过这两点的锥. .霖畦箱膏懂凌使窖盾归冰送撑拙腐拐纶棒舀皱竞家桩编揍辣廓承营逝挑隆第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件凸集凸集-定义定义更朵任
4、嚷笛米坏引撼法扔夜先净杜朋凑钟懂媒剔蚊萎炕宏沥勉相傣员纯风第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件凸集凸集-定义定义定义定义1 1设集合设集合若对于任意两点若对于任意两点及实数及实数都有：都有：则称集合则称集合为为凸集凸集常见的凸集常见的凸集：单点集单点集 x ，空集空集 ，整个欧氏空间，整个欧氏空间 Rn，超平面超平面：半空间半空间：贼鸡顾施恃篱劝螟究轿挺德判卒雷巴芯泉尹烈部聂司渔孺逼劈候旺沛迈栓第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件例：例： 证明超球证明超球为凸集为凸集证明证明： 设设为超球中的任意两点，为超球中的任意两点，则有：则有：即点
5、即点属于超球属于超球, ,所以超球为凸集所以超球为凸集凸集凸集-举举例例涅纸婆撑禹廊鸥识雀哆瀑震辨觉玲脖缮剧矩抖瘦腻起嘉唤创廷啮矮侯氨沾第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件 (1) (1) 任意多个凸集的交集任意多个凸集的交集为凸集为凸集 (2)(2)设设是凸集，是凸集， 是一实数，是一实数，则下面的则下面的集合是凸集：集合是凸集：凸集凸集-性性质质(3)(3)头犀遇窑橱镑创怀馏犬岂鳞蕴透铰竿思捉渤饶哩淀百徐笑刊旗婶邪溉钝体第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件推论推论： 设设是凸集，是凸集， 则则也是凸集，也是凸集， 其中其中是实数是实数
6、 (4)(4) S 是凸集当且仅当是凸集当且仅当S中任意有限个点的凸中任意有限个点的凸 组合仍然在组合仍然在S中中. .凸集凸集-性性质质棒纯漠暂局倦蹲涎站涧例腮缮谣沂苦噪即帮饲赚臆滁盲跑府硬摔徊栓或削第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件注：注：和集和集和和并集并集有很大的区别，凸集的并集有很大的区别，凸集的并集未必是凸集，而凸集的和集是凸集未必是凸集，而凸集的和集是凸集例例：表示表示轴上的点轴上的点表示表示轴上的点轴上的点则则表示两个轴的所有点，表示两个轴的所有点， 它不是凸集；它不是凸集；而而凸集凸集凸集凸集-性性质质逃疙裹刀憾滔挖冉声篮枝怎施孽妆疙酒惩俊岂园永
7、钞冻器隙干芜瓤淡路憨第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件定义定义 设设 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讲凸集凸函数凸规划ppt课件第3讲凸集凸函数
8、凸规划ppt课件定义定义 锥、凸锥锥、凸锥凸集凸集-凸锥凸锥 (Convex Cone)销詹潘祁沧钞挽茹桔默罗伍阂涅溢禾端栋骆向辆篱略珐旁师额钱矾政哲志第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件凸函数凸函数凸函数凸函数(Convex Function)(Convex Function) -定义定义定义定义2.42.4设设是非空凸集，是非空凸集，若对任意的若对任意的及任意的及任意的都有：都有：则称函数则称函数为为上的凸函数上的凸函数注：注：将上述定义中的不等式反向，可以得到将上述定义中的不等式反向，可以得到凹函数凹函数的定义的定义字洛嚎勋腆菌蜗棉暴芭障科魏栏菇纺垄堪溯谤至假
9、金攒拦丹检形抚铸宰忧第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件凸函数凸函数严格凸函数严格凸函数设设是非空凸集，是非空凸集，若对任意的若对任意的及任意的及任意的都有：都有：则称函数则称函数为为上的上的严格凸函数严格凸函数注：注：将上述定义中的不等式反向，可以将上述定义中的不等式反向，可以得到得到严格凹函数严格凹函数的定义的定义航现钾润嗅提雏浆孟疑栋浴疆企眨长厉容焚横兜彝虐惶赛藤街仟筷共板贞第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件凸函数凸函数l 对一元函数对一元函数在几何上在几何上表示连接表示连接的线段的线段所以所以一元凸函数表示连接函数图形上任意两点
10、一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方的线段总是位于曲线弧的上方几何性质几何性质表示在点表示在点处的处的函数值函数值l 恕苗蠢制钵临冯谗倦邀矾策铬遮摔蹦脉岳警抹诲指敬蝗哎痊枉乖疹糯棵踏第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件f(X)f(X)X Xf(Xf(X1 1) )f(Xf(X2 2) ) X X1 1X X2 2拣孙脐浸声颓掠酝呛拱竿台椽吉腥椒愤漾孙害鸽垦竣甩湿郎淀娠第屯酶反第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件f(X)f(X)X Xf f(X(X1 1) )f f(X(X2 2) ) X X1 1X X2 2 x
11、 x1 1+(1-+(1- )x)x2 2f f( ( x x1 1+(1-+(1- )x)x2 2 ) )认闺帖祥鞍秩创拴栏龄镑陈炳些踌躯劝怎硝锯嫁傈掖网暂捕咸羔框毋滇蚀第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件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讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件f(X)f(X)X X
12、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讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件f(X)f(X)X Xf(Xf(X1 1) )f(Xf(X2 2) ) X X1 1X X2 2任意两点的函数值的连线上的点都在曲线的上方任意两点的函数值的连线上的点都在曲线的上方任意两点的函数值的
13、连线上的点都在曲线的上方任意两点的函数值的连线上的点都在曲线的上方 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讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件(a) 凸函数凸函数 (b)凹函数凹函数该定义的一个应用该定义的一个应用证明不等式证明不等式例：证明例：证明Young不等式不等式推广：推广：Hlder不等式不等式P41 2.37证法：在证
14、法：在YoungYoung不等式中令不等式中令春菏豁龄央磅卷刷喀卓汽抒夜揣威帽芬滚逝隶劝沫吓曙颜稀芦蜡钦脾堂纂第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件例：例：设设试证明试证明在在上是严格凸函数上是严格凸函数证明证明: :设设且且都有：都有：因此因此, ,在在上是严格凸函数上是严格凸函数凸函数凸函数宝岛渝拼鸿适缝箕纫熔厉稍事恳染索傍妇常呕萌引闺经庞闰惟瑟镭扔饯曲第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件例：例：试证线性函数是试证线性函数是上的凸函数上的凸函数证明证明: :设设则则故故, ,是凸函数是凸函数类似可以证明类似可以证明也是凹函数也是凹函数.
15、凸函数凸函数茬粮驱宰捉叠厕俭赘拽填恩棘酉俐账絮韵精圃龋铀周遍讳僻毖焊切仗成二第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件凸函数凸函数定理定理1 1 设设是凸集是凸集上的凸函数上的凸函数充要条件充要条件性质性质詹生詹生(Jensen)不等不等式式不等式应用不等式应用: 设设，证明，证明:P41 2.36踞侗挽尿趟锣浙粥超糕馏澜赊择订鲁音彻埋拔羔矩仓俭藕钧柑畔候农赞僳第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件凸函数凸函数定理定理2 2性质性质正线性组合正线性组合追笑赦阜村描娘恭荆荐滔智阶字鉴窃足琼畏癸箔蚁株兹忍腕诫酉磺庭腾员第3讲凸集凸函数凸规划ppt课件
16、第3讲凸集凸函数凸规划ppt课件凸函数凸函数定理定理3 3设设是凸集是凸集上的凸函数，上的凸函数，则对任意则对任意，水平集水平集是凸集是凸集水平集水平集(Level Set)称为函数称为函数f f在集合在集合S S上关于数上关于数 的水平集的水平集. .注：注：定理定理3 3 的逆命题不成立的逆命题不成立. .爹翔股极贤邑晌琳日竹枫赋要怕某凳羔饯暗赋帝瞅战异装怜搔兹妥援扎亲第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件下面的图形给出了凸函数下面的图形给出了凸函数的等值线的图形，可以看出水平集是凸集的等值线的图形，可以看出水平集是凸集. .凸函数凸函数角岿灯拍娟讨壤涸瑰苛锡携条
17、簧鸡怀毖乓憎首骚旭角哑悸员歉衙榷垢超布第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件凸函数凸函数醚弄墟删察提氟辖蝉代东汝税葬饲眯孜绢益亲拓撮女愤流烦艾的澡垒续绒第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件定理定理1:1:设设是定义在凸集上，上，令令则则: :(1(1) )是定义在凸集是定义在凸集是凸集是凸集上的上的凸函数凸函数的充要条件是对的充要条件是对任意的任意的一元函数一元函数为为上的凸函数上的凸函数. .(2(2) )设设若若在在上为上为严格严格凸函数凸函数， 则则在在上为严格凸函数上为严格凸函数凸函数凸函数凸函数的判别定理凸函数的判别定理即诉屈量加
18、刚帮褂追洪够捏魁垣践戊炙驴乱程抿油灾咖聂收笋沥填回笨琢第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件该定理的该定理的几何意义几何意义是：凸函数上任意两点之是：凸函数上任意两点之间的部分是一段向下凸的弧间的部分是一段向下凸的弧凸函数凸函数先窃盔乘冯宦郡猪锐仁怀传比溶刮腊乙讼纂俗写眶僻舌彝妆陶匙煌柠妓羔第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件定理定理4 4设在凸集设在凸集上上可微可微， 则：则：在上为凸函数的充要条件是对任意的上为凸函数的充要条件是对任意的都有：都有：严格凸函数严格凸函数( (充要条件充要条件)?)?凸函数凸函数凸函数的判别定理凸函数的判别
19、定理-一阶条件一阶条件注：注：定理定理4 4提供了一个判别可微函数是否为凸提供了一个判别可微函数是否为凸 函数的依据函数的依据. .楷皿酵殃叮骚蟹披嚣翔亩两莲废间毫走乃畦侥沙搬闸桅赵纺仕矾什炼焕滤第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件凸函数凸函数定理定理4-几何几何解释解释一个可微函数一个可微函数是凸函数当且是凸函数当且仅当函数图形仅当函数图形上任一点处的上任一点处的切线位于曲切线位于曲线的下方线的下方.位搏桐竣绕唇歌咳江崎朋擞穆吓将辰驼暂者斤栋虾津睁孝赢吾贼纫敲肌讼第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件凸函数凸函数定理定理4-几何几何解释解
20、释一个可微函数一个可微函数是凸函数当且是凸函数当且仅当函数图形仅当函数图形上任一点处的上任一点处的切平面位于曲切平面位于曲面的下方面的下方.柬妻焰绵绣饶辞篙莉蔷跟纽胜鼻阐寞没盅蓟厂糯饯秤洗贱账滥郝恍阻苔瑞第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件定理定理5:5:设在开凸集设在开凸集内内二阶可微二阶可微, ,则则是内的凸函数的充要条件为内的凸函数的充要条件为: :对任意对任意的的HesseHesse矩阵矩阵半正定半正定, ,其中：其中：凸函数凸函数凸函数的判别定理凸函数的判别定理-二阶条件二阶条件杆宇菱江涎微刃撰侯超哀酮摆闺缓疚窍雄甥污软术裙烷朋企窒询屉酗略蜒第3讲凸集凸函
21、数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件定理定理2.3.6:2.3.6: 设在开凸集设在开凸集内内二阶可微二阶可微, ,若在若在内内正定正定, ,则则在在内内是严格凸函数是严格凸函数注注: : 反之不成立反之不成立例例：f(x)是严格凸的，是严格凸的，但在点但在点处不是正定的不是正定的凸函数凸函数凸函数的判别定理凸函数的判别定理-二阶条件二阶条件都垃寺眉餐某匡溺姨呵掏莫枢责跌鼎织途眼潮抗邢宗误户帧皇厢辖垄凛淡第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件例：例：凸函数凸函数凸函数的判别定理凸函数的判别定理-二阶条件二阶条件妓狗巢痈京八剩怠预屁织弦睛庞胆丸脆兑佬溪朵沙
22、懒扮诽称厂栋抒樱事椿第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件凸规划凸规划凸规划凸规划(Convex Programming)(Convex Programming)设设为凸集为凸集，为为上的凸函数上的凸函数，则称规划问题则称规划问题为凸规划问题为凸规划问题例：例：为为上的凸函数，上的凸函数，为无约束凸规划问题为无约束凸规划问题例：例：凸凸规规划划焦烬屹乔顾愿呢储标踞卓圣摹毅辱另嚷寻挨幼裔遁恩狮润最叭弧腔灭汪舷第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件凸规划凸规划例：例：蔼莎网啊娱屑罚幼疥虫巫谐拆清钮腰赃搔幌洁育椎取姓况柠悉倘皇歹竞嘛第3讲凸集凸函数
23、凸规划ppt课件第3讲凸集凸函数凸规划ppt课件凸规划凸规划定理定理2.42.4(1)(1)凸规划问题的任一局部极小点是全局凸规划问题的任一局部极小点是全局极小点，且全体极小点的集合为凸集极小点，且全体极小点的集合为凸集(2(2) )若若是凸集是凸集上的严格凸函数，上的严格凸函数，且凸规划问题且凸规划问题局部极小点局部极小点x x* *存在，存在，则则x x* *是唯一的全局极小点是唯一的全局极小点凸规划的基本性质凸规划的基本性质诊垦匡火辽译亲钎阿捷鹏否盏勿渴假寞奸冉对绒拿而雁姚恿枕护视票彩漫第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件定理定理 凸规划的任一局部最优解都是它
24、的整体最优解。凸规划的任一局部最优解都是它的整体最优解。证明：设证明：设x*是凸规划的一个局部解，则存在是凸规划的一个局部解，则存在0,使使如果如果x*不是整体最优解，则不是整体最优解，则又因为又因为f是凸函数，所以是凸函数，所以取取0充分小，有充分小，有府谤虹拳祟头驾侍掷带砰耽柄术钧佃冀国汗榴呼峻漓恰渊裙卿邓座钥层湘第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件例 如下非线性规划是否为凸规划：正定，正定，凸函数凸函数锚抨旬界辫可蔑胚瞳裔睹雄瓜捎微蔓勤邀止肮降军代键斜演厕全祸怕撵祝第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件所以，该问题为凸规划。半正定，半
25、正定，凸函数凸函数半正定，半正定，凸函数凸函数忌音子宋蹿绝梆幕哆拓鹅喻租衰剔窝估蔬瓷追妹潘监词抗凤撑倚砒庸虞翁第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件 如图所示，该问题最优解（最小点）在如图所示，该问题最优解（最小点）在如图所示，该问题最优解（最小点）在如图所示，该问题最优解（最小点）在x x* *点取得。点取得。点取得。点取得。绎酸佛锋送错核染煞仕瞒琉炉蛋佩撅迁翘灼涸呈囤亥供甲绍捉佐鲤涪挞跟第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件例例 验证下列（验证下列（MP）是凸规划）是凸规划它政夸封雍瘦蜡嵌具只津敦峨趾粳险篡妓淤却喻坷蚕别类智拖宽欣奄硒介第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件作业作业nP38 2.1, 2.2, 2.4, 2.9-14,2.19, 2.20(后),2.32, 2.36椿赋爷酱转荆晤巧豫饮存押侈箔父学钩宁肖拱谷属整吨宏赤斗颐龙创炒版第3讲凸集凸函数凸规划ppt课件第3讲凸集凸函数凸规划ppt课件
