凸优化理论与应用PPT课件.ppt

1、可编辑可编辑1 1凸优化理论与应用凸优化理论与应用庄 伯 金B可编辑可编辑2 2优化理论概述n什么是优化问题？什么是优化问题？0minimize ( )subject to ( ), 1,.,iinfxf xbimxR RObjective functionConstraint functions可编辑可编辑3 3几类经典的优化问题n线性规划问题线性规划问题( )if x 为线性函数n最小二乘问题最小二乘问题202( )-, 0.fxAx bm n凸优化问题凸优化问题( )if x 为凸函数凸优化问题理论上有凸优化问题理论上有有效的方法进行求解！有效的方法进行求解！可编辑可编辑4 4本课程的主

2、要内容n理论部分理论部分n凸集和凸函数凸集和凸函数n凸优化问题凸优化问题n对偶问题对偶问题n应用部分应用部分n逼近与拟合逼近与拟合n统计估计统计估计n几何问题几何问题n算法部分算法部分n非约束优化方法非约束优化方法n等式约束优化方法等式约束优化方法n内点法内点法可编辑可编辑5 5n熟悉了解凸优化理论的基本原理和基本方法；熟悉了解凸优化理论的基本原理和基本方法；n掌握实际问题转化为凸优化问题的基本方法；掌握实际问题转化为凸优化问题的基本方法；n掌握最优化问题的经典算法。掌握最优化问题的经典算法。课程要求可编辑可编辑6 6参考书目nStephen Boyd and Lieven Vandenber

3、ghe, “Convex Optimization”, Cambridge University Press.n袁亚湘、孙文瑜，袁亚湘、孙文瑜，“最优化理论与方法最优化理论与方法”，科学出版，科学出版社，社，1999。 可编辑可编辑7 7凸优化理论与应用凸优化理论与应用第一章第一章凸集凸集可编辑可编辑8 8仿射集(Affine sets)n直线的表示：直线的表示：12(1), .yxxR .n线段的表示：线段的表示：12(1), 0,1.yxx.可编辑可编辑9 9仿射集(Affine sets)n仿射集的定义：过集合仿射集的定义：过集合C内任意两点的直线均在集合内任意两点的直线均在集合C内，则

4、称集合内，则称集合C为仿射集。为仿射集。n仿射集的例：直线、平面、超平面仿射集的例：直线、平面、超平面Axb可编辑可编辑1010仿射集n仿射包：包含集合仿射包：包含集合C的最小的仿射集。的最小的仿射集。aff |,1iiiiCxxCn仿射维数：仿射包的维数。仿射维数：仿射包的维数。可编辑可编辑1111仿射集n内点（内点（interior）：）：int |( , ),0Cx B x rC rn相对内点（相对内点（relative interior）：）：relint |( , )aff,0Cx B x rCC r可编辑可编辑1212凸集(Convex Sets)n凸集的定义：集合凸集的定义：集合

5、C内任意两点间的线段均在集合内任意两点间的线段均在集合C内，则称集合内，则称集合C为凸集。为凸集。1212,0,1,(1)x xCxxC则111,.,0,11,kkiiikiiixxCxC且 则可编辑可编辑1313凸集n凸包的定义：包含集合凸包的定义：包含集合C的最小的凸集。的最小的凸集。11conv |,0,1kkiiiiiiiCxxC可编辑可编辑1414锥(Cones)n锥的定义：锥的定义：,0,.xCxC 则有n凸锥的定义：集合凸锥的定义：集合C既是凸集又是锥。既是凸集又是锥。12121 122,0,.x xCxxC 则有n锥包的定义：集合锥包的定义：集合C内点的所有锥组合。内点的所有锥

6、组合。1|,0kiiiiixxC可编辑可编辑1515超平面和半空间n超平面超平面(hyperplane) ： |Tx a xbn半空间半空间(Halfspace)： |Tx a xb |Tx a xb可编辑可编辑1616欧氏球和椭球n欧氏球欧氏球(euclidean ball):22(, ) | |() ()ccTccB x rxxxrxxxxxrn椭球椭球(ellipsoid):12 |()(), TccExxxPxxrP为对称正定矩阵2(, )|1ccB x rxruu1/22|1, cExAuuAP可编辑可编辑1717范数球和范数锥n范数范数(norm)：0,00;| |,xxxtxtx

7、 txyxy当且仅当；R ;n范数球范数球(norm ball)：(, ) |ccB x rxxxrn范数锥范数锥(norm cone)：( , )|x txt可编辑可编辑1818多面体(Polyhedra)n多面体：多面体： |,TTjjiiPx a xb c xdn单纯形单纯形(simplex)：10000|0,1,.,kki iiikiivvvvv线性无关可编辑可编辑1919半正定锥(Positive semidefinite cone)nn阶对称矩阵集：阶对称矩阵集：|nn nTSXXXnRnn阶半正定矩阵集：阶半正定矩阵集：|0nnSXSXnn阶正定矩阵集：阶正定矩阵集：|0nnSX

8、SXn阶半正定矩阵集阶半正定矩阵集为凸锥！为凸锥！可编辑可编辑2020保持凸性的运算n集合交运算集合交运算n仿射变换仿射变换n透视透视/投射函数投射函数(perspective function)( , )/ ,nP z tz t ztRR( ),m nmf xAxb ARbR可编辑可编辑2121保持凸性的运算n线性分式函数线性分式函数(linear-fractional function)( )()/(),0Tm nmnTf xAxbc xdAbcdc xdRRRR可编辑可编辑2222真锥(proper cone)n真锥的定义：锥真锥的定义：锥 满足如下条件满足如下条件nKR1.4.KKKK

9、为凸集；2. 为闭集；3. 非中空；有端点。K具有内点具有内点K内不含直线内不含直线可编辑可编辑2323广义不等式n真锥真锥 下的下的偏序关系偏序关系：KKxyyxK intKxyyxK n例：例：n逐项不等式逐项不等式n矩阵不等式矩阵不等式广义不等式广义不等式严格广义不等式严格广义不等式可编辑可编辑2424广义不等式的性质1.;2.,;3.,;4.,;5.,0;6.,lim,lim.KKKKKKKKKKKiKiiiKxxxy yxxyxy yzxzxy uvxuyvxyxyxyxxyyxy可编辑可编辑2525严格广义不等式的性质1.;2.;3.,;4.,05.,.KKKKKKKKKKxyxy

10、xxxy uvxuyvxyxyxy uxuy足够小可编辑可编辑2626最值和极值n最小元的定义：设最小元的定义：设 ，对，对 ，都有，都有 成立，则称成立，则称 为为 的最小元。的最小元。xSyS KxyxSn极小元的定义：设极小元的定义：设 ，对于，对于 ，若，若 ，则，则 成立，则称成立，则称 为为 的极小元。的极小元。xSySKyxxSyx可编辑可编辑2727分割超平面(separating hyperplane)n定理：设定理：设 和和 为两不相交凸集，则存在超平面将为两不相交凸集，则存在超平面将 和和 分离。即：分离。即：,.TTxC a xbxD a xb 且CDCD可编辑可编辑2

11、828支撑超平面(supporting hyperplane)n定义：设集合定义：设集合 ， 为为 边界上的点。若存在边界上的点。若存在 ，满足对任意满足对任意 ，都有，都有 成立，则称超平成立，则称超平面面 为集合为集合 在点在点 处的支撑超平面。处的支撑超平面。C0 xC0a xC0TTa xa x0 |TTx a xa xC0 xn定理：凸集边界上任意一点均存在支撑超平面。定理：凸集边界上任意一点均存在支撑超平面。n定理：若一个闭的非中空集合，在边界上的任意一点定理：若一个闭的非中空集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。存在支撑超平面，则该集合为凸集。可编辑可编辑292

12、9对偶锥(dual cone)n对偶锥的定义：设对偶锥的定义：设 为锥，则集合为锥，则集合 称为对偶锥。称为对偶锥。K* |0,TKy x yxK n对偶锥的性质：对偶锥的性质：*1.3.KKKKKKK是闭凸集；2若 非中空，则有端点；若 的闭包有端点，则非中空；4.是 的闭凸包；真锥的对偶锥仍真锥的对偶锥仍然是真锥！然是真锥！可编辑可编辑3030对偶广义不等式n广义不等式与对偶等价性质广义不等式与对偶等价性质*,for all 0;,for all 0,0.TTKKTTKKxyxyxyxyn最小元的对偶特性：最小元的对偶特性：*0, ,.TKxSKxz zS为集合 中关于 偏序的最小元对所有

13、为使最小的值可编辑可编辑3131对偶广义不等式n极小元的对偶特性极小元的对偶特性*0, ,.TKxz zSx为使最小的值为极小元反过来不一定成反过来不一定成立！立！可编辑可编辑3232作业nP60 2.8nP60 2.10nP60 2.14nP62 2.16nP62 2.18nP64 2.30nP64 2.31nP64 2.33可编辑可编辑3333凸优化理论与应用凸优化理论与应用第二章第二章 凸函数凸函数可编辑可编辑3434凸函数的定义1.定义域定义域 为凸集；为凸集；dom f.(1) )( )(1) ( ).fxyf xf y2. ，有，有,dom ,01x yf.n凸函数的定义：函数凸函

14、数的定义：函数 ，满足，满足:nfnRR .n凸函数的扩展定义：若凸函数的扩展定义：若 为凸函数，则可定义其扩为凸函数，则可定义其扩展函数展函数 为为f.: nfnRR .( )dom( )domf xxff xxf凸函数的凸函数的扩展函数扩展函数也是凸函也是凸函数！数！可编辑可编辑3535凸函数的一阶微分条件n若函数若函数 的定义域的定义域 为开集，且函数为开集，且函数 一阶可微，一阶可微，则函数则函数 为凸函数当且仅当为凸函数当且仅当 为凸集，且对为凸集，且对( )( )( ) ()Tf yf xf xyxfffdomfdomf,domx yf可编辑可编辑3636凸函数的二阶微分条件fn若

15、函数若函数 的定义域的定义域 为开集，且函数为开集，且函数 二阶可二阶可微，则函数微，则函数 为凸函数当且仅当为凸函数当且仅当 为凸集，且为凸集，且对对 ，其，其Hessian矩阵矩阵2( )0.f xffdomfdomfdomxf 可编辑可编辑3737凸函数的例n幂函数幂函数,1 or 0.axxaaRn负对数函数负对数函数log xn负熵函数负熵函数logxxn范数函数范数函数pxaxen指数函数指数函数可编辑可编辑3838凸函数的例1( )max( ,.,)nf xxx2( )/ ,0f xxy y1( )log(.)nxxf xee1/1( )(),domnnniif xxfR()lo

16、g(det),domnf XXfS可编辑可编辑3939下水平集(sublevel set)n定理：凸函数的任一下水平集均为凸集。定理：凸函数的任一下水平集均为凸集。n任一下水平集均为凸集的函数任一下水平集均为凸集的函数不一定不一定为凸函数。为凸函数。dom |( )Cxff x称为称为 的的 下水平集。下水平集。fn定义：集合定义：集合可编辑可编辑4040函数上半图(epigraph)n定理：函数定理：函数 为凸函数为凸函数当且仅当当且仅当 的上半图为凸集。的上半图为凸集。ffepi( , )|dom ,( )fx txf f xt称为函数称为函数 的上半图。的上半图。fn定义：集合定义：集合

17、可编辑可编辑4141Jensen不等式n 为凸函数，则有：为凸函数，则有：1 111(.)().()nnnnfxxf xf xf101,.1.in其中nJensen不等式的另外形式：不等式的另外形式：( )( ) ( ).SSfp x xdxp x f x dx可编辑可编辑4242保持函数凸性的算子n凸函数的逐点最大值凸函数的逐点最大值1( )max( ),.,( )nf xf xfxn凸函数与仿射变换的复合凸函数与仿射变换的复合( )()g xf Axb( )sup ( , )yf xg x yA1 1( )( ).( )nnf xf xfxn凸函数的非负加权和凸函数的非负加权和可编辑可编辑

18、4343保持函数凸性的算子n复合运算复合运算:, :( )( ( )nghf xh g xRRRRfn最小值算子最小值算子( )inf( , )y Cg xf x yn凸函数的透视算子凸函数的透视算子( , )(/ )g x ttf x t可编辑可编辑4444共轭函数(conjugate function)n定义：设函数定义：设函数 ，其共轭函数，其共轭函数 ，定义为定义为:nfRR*dom( )sup ( ).Txffyy xf x*:nfRRn共轭函数的例共轭函数的例共轭函数共轭函数具有凸性！具有凸性！( )Tf xa xb( )xf xe( )logf xxx可编辑可编辑4545共轭函数

19、的性质nFenchels inequality*( )( ).Tf xfyy xn性质：若性质：若 为凸函数，且为凸函数，且 的上半图是闭集，则有的上半图是闭集，则有( )f x( )f x*.ffn性质：设性质：设 为凸函数，且可微，对于为凸函数，且可微，对于 ，若，若( )f xnzR( )yf z 则则*( )( )( )Tfyzf zf z可编辑可编辑4646准凸函数(quasiconvex function)n准凸函数的例准凸函数的例n定义：设函数定义：设函数 ，若函数的定义域和任意下，若函数的定义域和任意下水平集水平集 |( ),dom Sx f xxf:nfnRR则称函数则称函数

20、 为准凸函数。为准凸函数。( )f x可编辑可编辑4747准凸函数的判定定理n定理：函数定理：函数 为准凸函数，当且仅当为准凸函数，当且仅当 为凸集，为凸集，且对且对 ，有，有( )f x(1) )max ( ),( )fxyf xf ydomf,dom ,01x yfn定理：若函数定理：若函数 一阶可微，则一阶可微，则 为准凸函数，当且仅为准凸函数，当且仅当当 为凸集，且对为凸集，且对 ，有，有 ( )f x( )f xdomf,domx yf( )( )( )()0Tf yf xf xyx ，有，有n定理：若函数定理：若函数 二阶可微，且满足对二阶可微，且满足对( )f xdom ,0nx

21、f yy R2( )0( )0TTyf xyf x y则函数则函数 准凸函数。准凸函数。( )f x可编辑可编辑4848n最小值函数最小值函数n非负权值函数的最大值函数非负权值函数的最大值函数保持准凸性的算子n复合函数复合函数可编辑可编辑4949准凸函数的凸函数族表示n若若 为准凸函数，根据为准凸函数，根据 的任意的任意 下水平集，我们下水平集，我们可以构造一个凸函数族可以构造一个凸函数族 ，使得，使得( )f x( )f xt( )tx( )( )0tf xtx n性质：若性质：若 为准凸函数为准凸函数 的凸函数族表示，对每一的凸函数族表示，对每一个个 ，若，若 ，则有，则有( )( ).s

22、txx( )f x( )txdomxfst可编辑可编辑5050对数凸函数 为凸集为凸集为凸函数。为凸函数。n定义：函数定义：函数 称为对数凸函数，若函数称为对数凸函数，若函数 满足：满足：2. ( )0f x ( )f x( )f x3.log( )f x1.domfn定理：函数定理：函数 的定义域为凸集，且的定义域为凸集，且 ，则，则 为为对数凸函数，当且仅当对对数凸函数，当且仅当对( )f x( )0f x ( )f x,dom ,01x yf 有有1(1) )( )( )fxyf xf yn对数凸函数的例对数凸函数的例可编辑可编辑5151对数凸函数和凹函数的性质n性质：对数凸性与凹性对函

23、数乘积和正数数乘运算均保持封性质：对数凸性与凹性对函数乘积和正数数乘运算均保持封闭。闭。n定理：函数定理：函数 二阶可微，则二阶可微，则 为对数凸函数当且仅为对数凸函数当且仅当当2( )( )( )( )Tf xf xf xf x( )f x( )f xn性质：对数凸性对函数加运算保持封闭。但对数凹性对函数性质：对数凸性对函数加运算保持封闭。但对数凹性对函数加运算不封闭。加运算不封闭。n推论：函数推论：函数 对每一个对每一个 在在 上对数凸，则函上对数凸，则函数数 也是对数凸函数。也是对数凸函数。( , )f x yyCx( )( , )Cg xf x y dy可编辑可编辑5252对数凸函数和

24、凹函数的性质n定理：函数定理：函数 为对数凹函数，则函为对数凹函数，则函数数 是对数凹函数。是对数凹函数。( , ):nmf x yRRR( )( , )g xf x y dy可编辑可编辑5353广义不等式下的凸性n广义单调性的定义：设广义单调性的定义：设 为真锥，函数为真锥，函数 称为称为 单调增，若函数单调增，若函数 满足：满足：nK R:nfRRK ( )f x( )( )Kxyf xf yn广义凸函数的定义：设广义凸函数的定义：设 为真锥，函数为真锥，函数 称为称为 凸，若函数凸，若函数 满足对满足对mK R:nmfRRK ( )f x,dom ,01x yf(1) )( )(1) (

25、 ).Kfxyf xf y 均有均有n定理定理(对偶等价对偶等价)：函数函数 为为 凸函数，当且仅当对所凸函数，当且仅当对所有有 ， 为凸函数。为凸函数。( )f xK *0Kw( )Tw f x可编辑可编辑5454作业(1)nP116 3.16nP116 3.21可编辑可编辑5555作业(2)nP121 3.41nP122 3.49 (1)(2)可编辑可编辑5656凸优化理论与应用凸优化理论与应用第三章第三章 凸优化凸优化可编辑可编辑5757优化问题的基本形式n优化问题的基本描述：优化问题的基本描述：0minimize ( ), subject to ( )0, 1,., ( )0, 1,.

26、,niifxxf ximh xjpR R优化变量优化变量nxR( )0if x 不等式约束不等式约束等式约束等式约束( )0ih x .0mp无约束优化无约束优化可编辑可编辑5858优化问题的基本形式最优化值最优化值*0inf( )|( )0,1,.,( )0,1,., iipfxf xim h xip*0()pfx最优化解最优化解 优化问题的域优化问题的域01domdompmiiiiDfh 可行点可行点(解解) (feasible) 满足约束条件满足约束条件xD 可行域可行域(可解集可解集) 所有可行点的集合所有可行点的集合可编辑可编辑5959局部最优问题n局部最优问题局部最优问题02min

27、imize ( ), subject to ( )0, 1,., ( )0, 1,., , 0niifxxf ximh xjpxzR RR R可编辑可编辑6060优化问题的等价形式(1)n定理：若定理：若000minimize ( )( ), subject to ( )( )0, 1,., ( )( )0, 1,.,niiiiifxfxxf xf ximh xh xipR R0,0,.,0,1,.,iiimip 则原优化问题与以下优化问题等价则原优化问题与以下优化问题等价可编辑可编辑6161优化问题的等价形式(2)n定理：设定理：设 为一一对应，且为一一对应，且00minimize ( )(

28、 ( ), subject to ( )( ( )0, 1,., ( )( ( )0, 1,.,niiiifzfzzf zfzimh zhzipR R:nnRR 则原优化问题与以下优化问题等价则原优化问题与以下优化问题等价(dom )D可编辑可编辑6262优化问题的等价形式(3)n定理：设定理：设 为严格单调增函数；为严格单调增函数； 满满足足 当且仅当当且仅当 ； 满足满足 当当且仅当且仅当 。则原优化问题与以下优化问题等价。则原优化问题与以下优化问题等价000minimize ( )( ), subject to ( )( )0, 1,., ( )( ( )0, i1,.,niiiiiif

29、zfzzf zf zimh zh zpR R0:RR1,.,m( )0iu0u 1,.,p( )0iu0u 可编辑可编辑6363优化问题的等价形式(4)n定理：原优化问题与以下优化问题等价定理：原优化问题与以下优化问题等价0minimize ( ), subject to ( )0, 1,., 0 ( )0, 1,.,niiiifxxf xsimsh xjpR Rn 称为松弛变量称为松弛变量s可编辑可编辑6464优化问题的等价形式(5)n定理：设定理：设 满足等式满足等式 成立，当且仅当成立，当且仅当 。则原优化问题与以下优化。则原优化问题与以下优化问题等价问题等价0minimize ( (

30、), subject to ( ( )0, 1,.,nifzxfzimR R:knRR( )0, 1,.,ih xjp( )xz可编辑可编辑6565可分离变量优化问题n性质：性质：,inf( , )inf( )x yxf x yf x其中其中( )inf( , )yf xf x y可以分离变量可以分离变量n定理：优化问题定理：优化问题0121122minimize ( ,), subject to ()0, 1,., ()0, 1,.,niifx xxf ximf ximR R12,x x可编辑可编辑6666优化问题的上半图形式0minimize subject to ( )0, ( )0,

31、1,., ( )0, 1,.,iitfxtf ximh xjp 可编辑可编辑6767凸优化问题的基本形式n凸优化问题的基本描述：凸优化问题的基本描述：0minimize ( ), subject to ( )0, 1,., ( )0, 1,.,niifxxf ximh xjpR R 为仿射函数为仿射函数( )ih x 为凸函数为凸函数( )if x 若若 为准凸函数，则优化问题称为准凸优化问题。为准凸函数，则优化问题称为准凸优化问题。0( )fx 性质：凸优化问题的可行域是凸集。性质：凸优化问题的可行域是凸集。可编辑可编辑6868凸优化问题的例n例：例：2201221122112minimiz

32、e ( )subject to ( )/(1)0 ( )()0fxxxf xxxh xxx等价于凸优化问题等价于凸优化问题2201211112minimize ( )subject to ( )0 ( )0fxxxf xxh xxx可编辑可编辑6969凸优化问题的局部最优解n定理：凸优化问题的局部最优解均是全局最优解。定理：凸优化问题的局部最优解均是全局最优解。可编辑可编辑7070凸优化问题最优解的微分条件n定理：设定理：设 为凸优化问题的可行域，为凸优化问题的可行域， 可微。则可微。则 为最优解当且仅当为最优解当且仅当 成立。成立。0( )fx0( ) ()0,TfxyxyXXxn定理：非约

33、束凸优化问题中，若定理：非约束凸优化问题中，若 可微。则可微。则 为最为最优解当且仅当优解当且仅当 成立。成立。0( )fxx0( )0fx可编辑可编辑7171凸优化问题的等价形式则则 为最优解当且仅当为最优解当且仅当 ，且存在向量，且存在向量 满足满足 n定理：设凸优化问题仅有等式约束定理：设凸优化问题仅有等式约束x0( )0TfxA v0minimize ( ), subject to nfxxAxbR RxXv可编辑可编辑7272凸优化问题的等价形式则则 为最优解当且仅当为最优解当且仅当 ，且，且 n定理：设凸优化问题定理：设凸优化问题x0( )0Tfxx0minimize ( ), s

34、ubject to 0nfxxxR RxX可编辑可编辑7373凸优化问题的等价形式0minimize ( ), subject to ( )0, 1,., niTfxxf ximA xbR R等价于等价于 n定理：设凸优化问题定理：设凸优化问题000minimize (), subject to ()0, 1,.,nifFzxxf FzximR R其中其中 0 TA xbxFzx可编辑可编辑7474凸优化问题的等价形式0minimize ( ), subject to , 1,.,nTiifxxa xbimR R等价于等价于 n定理：设凸优化问题定理：设凸优化问题0minimize ( ),

35、subject to , 1,., 0, 1,.,nTiiiifxxa xsbimsimR R可编辑可编辑7575准凸优化问题 为准凸函数，为准凸函数， 为凸函数。为凸函数。1( ),.,( )mf xfxn准凸优化问题的基本描述准凸优化问题的基本描述0( )fx0minimize ( ), subject to ( )0, 1,., ( )0, 1,.,niifxxf ximh xjpR Rn注：准凸优化问题的局部最优解不一定是全局最优解。注：准凸优化问题的局部最优解不一定是全局最优解。可编辑可编辑7676准凸优化问题的上半图形式n设设 为准凸函数为准凸函数 的凸函数族表示，即的凸函数族表示

36、，即0( )fx( )tx0( )( )0tfxtx 则准凸优化问题的可行解问题为则准凸优化问题的可行解问题为find subject to ( )0, ( )0, 1,., tixxf ximAxbn设设 为准凸优化问题的最优解，若上述问题可解，为准凸优化问题的最优解，若上述问题可解，则则 。否则。否则 。*p*pt*pt可编辑可编辑7777准凸优化问题二分法求解n给定一个足够小的给定一个足够小的 和足够大的和足够大的 ，使得区间，使得区间 能包含最优解能包含最优解 。给定。给定ul*p, l u0nLOOP：n令令n求解可行解问题；求解可行解问题；n若可解，则令若可解，则令 ，否则令，否则

37、令n若若 ，则结束，否则，则结束，否则goto LOOP。 ()/2tluutltul可编辑可编辑7878线性规划(linear program,LP)nLP问题的一般描述问题的一般描述minimize subject to Tc xdGxhAxb,m np nGARR可编辑可编辑7979LP问题的几种类型n标准标准LP问题问题minimize subject to 0Tc xAxbxn不等式形式不等式形式LP问题问题minimize subject to Tc xdAxb可编辑可编辑8080标准LP问题的转换minimize subject to 0,0,0TTc xc xbGxGxshAx

38、Axbxxs可编辑可编辑8181LP问题的例nChebyshev center of a polyhedronnPiecewise-linear minimizationnLinear-fractional programming可编辑可编辑8282Chebyshev center of a polyhedron|nPxRAxbn多面体nChebyshev center：到多面体边界距离最大的内点（最深的点）2(, )|ccB x rxuurn问题描述maximize subject to (, )crB x rPnLP形式2minimize 1/subject to ,1,.,Ticiira

39、 xr ab im可编辑可编辑8383Piecewise-linear minimizationn问题描述1,.,minimize ( )max()Tiiimf xa xbn上半图形式1,.,minimize subject to max()Tiiimta xbtnLP形式minimize subject to ,1,.,Tiita xbt im可编辑可编辑8484Linear-fractional programmingn问题描述00minimize ( ),dom |0subject to TTTc xdfxfx e xfe xfGxhAxbnLP形式minimize subject to

40、 0 0 1 0TTc ydzGyhzAybze yfzz1TTxye xfze xf可编辑可编辑8585二次规划(quadratic program,QP)minimize (1/2)subject to ,TTnm np nx Pxq xrGxhAxbPSGRARnQP问题的基本描述问题的基本描述可编辑可编辑8686二次约束二次规划000minimize (1/2)subject to (1/2)0 ,TTTTiiinp nix P xq xrx Pxq xrAxbPSARnquadratically constrained quadratic program (QCQP)可编辑可编辑87

41、87QP问题的例nLeast-squares and regressionnDistance between polyhedra可编辑可编辑8888Least-squares and regressionn问题描述22minimize Axb222TTTTAxbx A Axb Axb b可编辑可编辑8989Distance between polyhedran问题描述12121122dist( ,)inf|,P PxxxP xP111 |Px A xb222 |Px A xbnQP形式21221122minimize subject to ,xxAxb A xb可编辑可编辑9090Second

42、-order cone program, SOCPnSOCP问题的基本描述2minimize subject to TTiiif xAxbc xdFxgn二次锥约束条件2TAxbc xd可编辑可编辑9191SOCP问题的例Robust linear programmingn问题描述minimize subject to TTiic xa xb其中 不是完全确定的常数。,iic a bn例： 为确定的常数， 为变量，其范围满足,ic bia2|1iiiiaaPuuSOCP形式2minimize subject to TTTiiic xa xP xb可编辑可编辑9292几何规划(Geometric

43、 programming)n单项式与多项式11( )naanf xcxx111( )knkKaaknkf xc xxn几何规划的基本描述0minimize ( )subject to ( )1,1,., ( )1,1,., iiniifxf ximh xipfhDR为多项式， 为单项式,可编辑可编辑9393几何规划的凸形式转换n令logiiyxn几何规划的凸形式000011minimize ( )log()subject to ( )log()0,1,., ( )0,1,.,TkkTiikikKay bkKa y bikTiiifyef yeimh yg yhip可编辑可编辑9494广义不等式

44、约束n广义不等式约束的优化问题0minimize ( )subject to ( )0,1,., iiKfxf ximAxbnSOCP的描述12minimize subject to (,)0,1,., ( , )|iiTTiiiiKkic xAxb c xdimFxgKy tRyt可编辑可编辑9595凸优化理论与应用凸优化理论与应用第四章第四章 对偶问题对偶问题可编辑可编辑9696优化问题的拉格朗日函数n设优化问题：设优化问题：0minimize ( ), subject to ( )0, 1,., ( )0, 1,.,niifxxf ximh xjpR Rn拉格朗日拉格朗日(Lagrang

45、ian)函数：函数：011( , , )( )( )( )pmiiiiiiL xfxf xh x n对固定的对固定的 ，拉格朗日函数，拉格朗日函数 为关于为关于 和和 的的仿仿射函数射函数。( , , )L x x可编辑可编辑9797拉格朗日对偶函数n拉格朗日对偶函数拉格朗日对偶函数(lagrange dual function) ：011( , )inf( , , )inf( )( )( )pmiiiix Dx DiigL xfxf xh x 若拉格朗日函数没有下界，则令若拉格朗日函数没有下界，则令( , )g n拉格朗日对偶函数为拉格朗日对偶函数为凹函数凹函数。n对对 和和 ，若原最优化问

46、题有最优值，若原最优化问题有最优值 ，则，则0*p( , )*gp 可编辑可编辑9898对偶函数的例nLeast-squares solution of linear equationsnStandard form LPnTwo-way partitioning problem可编辑可编辑9999Least-squares solution of linear equationsn原问题：原问题：minimize , subject to Tnx xxAxbR Rn拉格朗日函数：拉格朗日函数：( , )()TTL xx xAxbn拉格朗日对偶函数：拉格朗日对偶函数：1( )4TTTgAAb 可

47、编辑可编辑100100Standard form LPn原问题：原问题：minimize subject to 0Tc xAxbxn拉格朗日函数：拉格朗日函数：( , , )() ()TTTTTTL xc xxAxbbcAx n拉格朗日对偶函数：拉格朗日对偶函数：0( , )TTbAcgotherwise 可编辑可编辑101101Two-way partitioning problemn原问题：原问题：2minimize ,subject to 1,1,.,Tnix Wx WSxinn拉格朗日函数：拉格朗日函数：21( , )(1) (diag( )1nTiiiTTL xx Wxxx Wxn拉

48、格朗日对偶函数：拉格朗日对偶函数：1diag( )0( )TWgotherwise可编辑可编辑102102对偶函数与共轭函数n共轭函数共轭函数dom*( )sup ( )Txffyy xf xn共轭函数与对偶函数存在密切联系共轭函数与对偶函数存在密切联系n具有线性不等式约束和线性等式约束的优化问题：具有线性不等式约束和线性等式约束的优化问题：0minimize ( )subject to fxAxbCxd 对偶函数：对偶函数：*0( , )()TTTTgbdfAC 可编辑可编辑103103Equality constrained norm minimizationn问题描述：问题描述：mini

49、mize subject to xAxb*001( )yfyotherwisen共轭函数：共轭函数：n对偶函数：对偶函数：*01( )()TTTTbAgbfAotherwise 可编辑可编辑104104Entropy maximizationn原始问题：原始问题：n1minimize log, subject to 11niiiTxxDRAxbxn共轭函数：共轭函数：1*01( )imyifyen对偶函数对偶函数：*01111( , )(1 ) TiTiTTmaTimaTigbfAbebee 可编辑可编辑105105Minimum volume covering ellipsoidn原始问题：

50、原始问题：1minimize logdet, subject to 1,1,.,nTiiXDSa Xaim11logdet() 10( )mmTTTiiiiiiiia ana agotherwisen对偶函数：对偶函数：n共轭函数：共轭函数：*10( )logdet()fYYn可编辑可编辑106106拉格朗日对偶问题n拉格朗日对偶问题的描述：拉格朗日对偶问题的描述：maximize ( , )subject to 0g 0( , )g n对偶可行域对偶可行域*dn最优值最优值n最优解最优解( *, *) 可编辑可编辑107107LP问题的对偶问题n标准标准LP问题问题minimize subj