《现代优化方法现代优化方法 (2).pdf》由会员分享，可在线阅读，更多相关《现代优化方法现代优化方法 (2).pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、8.3 Dual ProblemQingna Li(BIT)8.3 Dual Problem1/13Dual ProblemConsidering problemminxXf(x)s.t.G(x)K.(1.1)its dual problem issupKinfxXL(x,):=supK(),(1.2)where()=infxXL(x,),L(x,)=f(x)G(x),.Qingna Li(BIT)8.3 Dual Problem2/13ExampleThe dual problem of quadratic programming.Consideringthe quadratic progr
2、ammingminxIRn12xTQx+c,xs.t.Ax=b,Bx d 0.(1.3)where Q is symmetric positive semi-definite,A IRpn,b IRp,B IRqn,d IRqare given.Qingna Li(BIT)8.3 Dual Problem3/13G(x)=Ax bBx d,K=0p IRq+.Notice thatK=IRp IRq+.Let=v IRp+q,IRp,v IRq.So we have K IRp,v IRq+.G(x)K Ax b=0,Bx d 0.Qingna Li(BIT)8.3 Dual Problem4
3、/13The Lagrange function isL(x,)=12xTQx+c,x G(x),=12xTQx+c,x Ax bBx d,v=12xTQx+c,x Ax b,Bx d,v=12xTQx+x,c AT BTv+b,+d,v.Qingna Li(BIT)8.3 Dual Problem5/13Notice that Q is symmetric positive semi-definite,theprobleminfxIRnL(x,)(1.4)admits a unique minimum point,andxL(x,)=0(1.5)is the sufficient and n
4、ecessary optimality condition to findthe minimizer.Qingna Li(BIT)8.3 Dual Problem6/13(1.5)is equivalent toQx+c AT BTv=0.Equivalently,x=Q1(c+AT+BTv)is the minimizer of(1.4).infxIRnL(x,)=L(x,)=12(c+AT+BTv)TQ1(c+AT+BTv)+Q1(c+AT+BTv),c AT v+,b+v,d=12(c+AT+BTv)Q1(c+AT+BTv)+,b+v,dQingna Li(BIT)8.3 Dual Pr
5、oblem7/13The dual problem issupKinfxXL(x,)=supK()=supIRp,vIRq+(,v).i.e.maxIRp,vIRq(,v)s.t.v 0.where(,v)=12(c+AT+BTv)Q1(c+AT+BTv)+,b+v,d.Qingna Li(BIT)8.3 Dual Problem8/13A QuestionIf Q 0 but Q is not positive definite,how to derivethe dual problem?How to solve it efficiently?Restricted Wolfe dual Te
6、chnique and SymmetricGaussian-Siedel Decompositionby Prof.Defeng Suns research groupXudong Li,Defeng Sun,and Kim Chuan Toh,QSDPNAL:A two-phase augmented Lagrangianmethod for convex quadratic semidefiniteprogramming,Mathematical ProgrammingComputation,10(2018)703-743.Qingna Li(BIT)8.3 Dual Problem9/1
7、3Indicator function and Support FunctionIndicator function of set C:(x|C)=0,x C,+,otherwise.(1.6)min f(x)s.t.x C min f(x)+(x|C)(1.7)Qingna Li(BIT)8.3 Dual Problem10/13Conjugate function of f at x:f(x)=supxx,x f(x).(1.8)The conjugate function of(|C)at xis referred asthe support function of C at x,den
8、oted as(x|C).The conjugate function is an important tool to derive dualproblems for more complicated problems.Qingna Li(BIT)8.3 Dual Problem11/13SummaryAbstract form of dual problemMore tools in duality theoryQingna Li(BIT)8.3 Dual Problem12/13Summary of Chapter 8KKT conditionDual problemMore questions and toolsQingna Li(BIT)8.3 Dual Problem13/13