凸优化理论与应用_凸优化

信息与通信工程学院庄伯金[e-mail]1凸优化理论与应用第三章凸优化信息与通信工程学院庄伯金[e-mail]2优化问题的基本形式优化问题的基本描述：0minimize(),subjectto()0,1,...,()0,1,...,niifxxfximhxjpR优化变量nxR()0,1,...,ifxim不等式约束等式约束()0,1,...,ihxip.0mp无约束优化信息与通信工程学院庄伯金[e-mail]3优化问题的基本形式最优化值*0inf{()|()0,1,...,,()0,1,...,}iipfxfximhxip**0()pfx最优化解优化问题的域01domdompmiiiiDfh可行点(解)(feasible)且满足约束条件xD可行域(可解集)所有可行点的集合信息与通信工程学院庄伯金[e-mail]4局部最优解局部最优问题02minimize(),subjectto()0,1,...,()0,1,...,,0niifzxfzimhzjpxzRRR若为局部最优问题的最优解，则它为原最优问题的局部最优解。x信息与通信工程学院庄伯金[e-mail]5优化问题的等价形式(1)定理：若000minimize()(),subjectto()()0,1,...,()()0,1,...,niiiiifxfxxfxfximhxhxipR0,0,...,,0,1,...,iiimip则原优化问题与以下优化问题等价信息与通信工程学院庄伯金[e-mail]6优化问题的等价形式(2)定理：设为一一对应，且00minimize()(()),subjectto()(())0,1,...,()(())0,1,...,niiiifzfzzfzfzimhzhzipR:nnRR则原优化问题与以下优化问题等价(dom)D信息与通信工程学院庄伯金[e-mail]7优化问题的等价形式(3)定理：设为严格单调增函数；满足当且仅当；满足当且仅当。则原优化问题与以下优化问题等价000minimize()(()),subjectto()(())0,1,...,()(())0,i1,...,niiiiiifzfzzfzfzimhzhzpR0:RR1,...,m()0iu0u1,...,p()0iu0u信息与通信工程学院庄伯金[e-mail]8优化问题的等价形式(4)定理：原优化问题与以下优化问题等价0minimize(),subjectto()0,1,...,0()0,1,...,niiiifxxfxsimshxjpR称为松弛变量s信息与通信工程学院庄伯金[e-mail]9优化问题的等价形式(5)定理：设满足等式成立，当且仅当。则原优化问题与以下优化问题等价0minimize(()),subjectto(())0,1,...,nifzxfzimR:knRR()0,1,...,ihxjp()xz信息与通信工程学院庄伯金[e-mail]10可分离变量优化问题性质：,inf(,)inf()xyxfxyfx其中()inf(,)yfxfxy可以分离变量定理：优化问题0121122minimize(,),subjectto()0,1,...,()0,1,...,niifxxxfximfximR12,xx信息与通信工程学院庄伯金[e-mail]11优化问题的上半图形式0minimizesubjectto()0,()0,1,...,()0,1,...,iitfxtfximhxjp信息与通信工程学院庄伯金[e-mail]12凸优化问题的基本形式凸优化问题的基本描述：0minimize(),subjectto()0,1,...,()0,1,...,niifxxfximhxjpR为仿射函数()ihx为凸函数()ifx若为准凸函数，则优化问题称为准凸优化问题。0()fx性质：凸优化问题的可行域是凸集。信息与通信工程学院庄伯金[e-mail]13抽象凸优化问题例：2201221122112minimize()subjectto()/(1)0()()0fxxxfxxxhxxx等价于凸优化问题2201211112minimize()subjectto()0()0fxxxfxxhxxx信息与通信工程学院庄伯金[e-mail]14凸优化问题的局部最优解定理：凸优化问题的局部最优解均是全局最优解。信息与通信工程学院庄伯金[e-mail]15凸优化问题最优解定理：设为凸优化问题的可行域，可微。则为最优解当且仅当成立。0()fx0()()0,TfxyxyXXx信息与通信工程学院庄伯金[e-mail]16凸优化问题最优解定理：无约束凸优化问题中，若可微。则为最优解当且仅当成立。0()fxx0()0fx例：无约束二次优化问题01()2TTfxxPxqxr可知0()0fxPxq信息与通信工程学院庄伯金[e-mail]17凸优化问题的最优解则为最优解当且仅当，且存在向量满足定理：设凸优化问题仅有等式约束x0()0TfxAv0minimize(),subjecttonfxxAxbRxXv信息与通信工程学院庄伯金[e-mail]18凸优化问题的最优解则为最优解当且仅当，且定理：设凸优化问题仅有逐项非负不等式约束x00()0,(())0,1,...,iifxxfxin0minimize(),subjectto0nfxxxR0x信息与通信工程学院庄伯金[e-mail]19凸优化问题的等价形式0minimize(),subjectto()0,1,...,niTfxxfximAxbR等价于定理：设凸优化问题000minimize(),subjectto()0,1,...,nifFzxxfFzximR其中0TAxbxFzx信息与通信工程学院庄伯金[e-mail]20凸优化问题的等价形式0minimize(),subjectto,1,...,nTiifxxaxbimR等价于定理：设凸优化问题0minimize(),subjectto,1,...,0,1,...,nTiiiifxxaxsbimsimR信息与通信工程学院庄伯金[e-mail]21准凸优化问题为准凸函数，为凸函数。1(),...,()mfxfx准凸优化问题的基本描述0()fx0minimize(),subjectto()0,1,...,()0,1,...,niifxxfximhxjpR注：准凸优化问题的局部最优解不一定是全局最优解。准凸优化问题-最优解的充分条件信息与通信工程学院庄伯金[e-mail]22定理：设为准凸优化问题的可行域，可微。若有则为准凸优化问题的最优解。0()fx0()()0,\{}TfxyxyXxXxXx信息与通信工程学院庄伯金[e-mail]23准凸优化问题的上半图形式设为准凸函数的凸函数族表示，即0()fx()tx0()()0tfxtx则准凸优化问题的可行解问题为findsubjectto()0,()0,1,...,tixxfximAxb设为准凸优化问题的最优解，若上述问题可解，则。否则。*p*pt*pt信息与通信工程学院庄伯金[e-mail]24准凸优化问题二分法求解给定一个足够小的和足够大的，使得区间能包含最优解。给定ul*p,lu0LOOP：令求解可行解问题；若可解，则令，否则令若，则结束，否则gotoLOOP。()/2tluutltul信息与通信工程学院庄伯金[e-mail]25线性规划(linearprogram,LP)LP问题的一般描述minimizesubjecttoTcxdGxhAxb,mnpnGARR信息与通信工程学院庄伯金[e-mail]26LP问题的几种类型标准LP问题minimizesubjectto0TcxAxbx不等式形式LP问题minimizesubjecttoTcxdAxb信息与通信工程学院庄伯金[e-mail]27标准LP问题的转换minimizesubjectto0,0,0TTcxcxbGxGxshAxAxbxxs信息与通信工程学院庄伯金[e-mail]28LP问题的例ChebyshevcenterofapolyhedronPiecewise-linearminimizationLinear-fractionalprogramming信息与通信工程学院庄伯金[e-mail]29Chebyshevcenterofapolyhedron{|}nPxRAxb多面体Chebyshevcenter：到多面体边界距离最大的内点（最深的点）2(,){|}ccBxrxuur问题描述maximizesubjectto(,)crBxrPLP形式2minimizesubjectto,1,...,Ticiiraxrabim信息与通信工程学院庄伯金[e-mail]30Piecewise-linearminimization问题描述1,...,minimize()max()Tiiimfxaxb上半图形式1,...,minimizesubjecttomax()TiiimtaxbtLP形式minimizesubjectto,1,...,Tiitaxbtim信息与通信工程学院庄伯金[e-mail]31Linear-fractionalprogramming问题描述00minimize(),dom{|0}subjecttoTTTcxdfxfxexfexfGxhAxbLP形式minimizesubjectto0010TTcydzGyhzAybzeyfzz1TTxyexfzexf信息与通信工程学院庄伯金[e-mail]32二次规划(quadraticprogram,QP)minimize(1/2)subjectto,,TTnmnpnxPxqxrGxhAxbPSGRARQP问题的基本描述信息与通信工程学院庄伯金[e-mail]33二次约束二次规划000minimize(1/2)subjectto(1/2)0,TTTTiiinpnixPxqxrxPxqxrAxbPSARquadraticallyconstrainedquadraticprogram(QCQP)信息与通信工程学院庄伯金[e-mail]34QP问题的例Least-squaresandregressionDistancebetweenpolyhedraMarkow