KKTgeometry(从几何图形的角度来阐释KTT条件的意义).ppt

1,ThePrinciplesandGeometriesofKKTandOptimization,2,GeometriesofKKT:Unconstrained,Problem:Minimizef(x),wherexisavectorthatcouldhaveanyvalues,positiveornegativeFirstOrderNecessaryCondition(minormax):f(x)=0(f/xi=0foralli)isthefirstordernecessaryconditionforoptimizationSecondOrderNecessaryCondition:2f(x)ispositivesemidefinite(PSD)x2f(x)x0forallxSecondOrderSufficientCondition(GivenFONCsatisfied)2f(x)ispositivedefinite(PD)x2f(x)x0forallx,f/xi=0,xi,f,3,GeometriesofKKT:EqualityConstrained(oneconstraint),Problem:Minimizef(x),wherexisavectorSubjectto:h(x)=bFirstOrderNecessaryConditionforminimum(orformaximum):f(x)=h(x)forsomefree(isascalar)Twosurfacesmustbetangenth(x)=band-h(x)=-barethesame;thereisnosignrestrictionon,h(x)=b,4,GeometriesofKKT:EqualityConstrained(oneconstraint),FirstOrderNecessaryCondition:f(x)=h(x)forsomeLagrangian:L(x,)=f(x)-h(x)-b,MinimizeL(x,)overxandMaximizeL(x,)over.UseprinciplesofunconstrainedoptimizationL(x,)=0:xL(x,)=f(x)-h(x)=0L(x,)=h(x)-b=0,5,GeometriesofKKT:EqualityConstrained(multipleconstraints),Problem:Minimizef(x),wherexisavectorSuchthat:hi(x)=bifori=1,2,mKKTConditions(NecessaryConditions):Existi,i=1,2,m,suchthatf(x)=i=1nihi(x)hi(x)=bifori=1,2,mSuchapoint(x,)iscalledaKKTpoint,andiscalledtheDualVectorortheLagrangeMultipliers.Furthermore,theseconditionsaresufficientiff(x)isconvexandhi(x),i=1,2,m,arelinear.,6,GeometriesofKKT:Unconstrained,ExceptNon-NegativityCondition,Problem:Minimizef(x),wherexisavector,x0FirstOrderNecessaryCondition:f/xi=0ifxi0f/xi0ifxi=0Thus:f/xixi=0forallxi,orf(x)x=0,f(x)0Ifinteriorpoint(x0),thenf(x)=0Nothingchangesiftheconstraintisnotbinding,f/xi=0,xi,f,f/xi0,7,GeometryofKKT:InequalityConstrained(oneconstraint),Problem:Minimizef(x),wherexisavectorSubjectto:g(x)b.Assumefeasiblesetandsetofpointspreferredtoanypointareallconvexsets.(i.e.convexprogram)FirstOrderNecessaryCondition:f(x)=g(x)forsome0(isascalar)Ifconstraintisbindingg(x)=b,then0Ifconstraintisnone-bindingg(x)b,thenf(x)=0or=0,8,GeometriesofKKT:InequalityConstrained(oneconstraint),Foranypointxonthefrontierofthefeasibleregionofg(x)b,recallthat-g(x)isthedirectionofsteepestdescentofg(x)atx.Itisalsoperpendiculartothefrontierofg(x)=b,pointinginthedirectionofdecreasingg(x).Thus-g(x)isperpendiculartothetangenthyperplaneofg(x)=batx.,9,GeometriesofKKT:InequalityConstrained(oneconstraint),f(x)issimilarlyavectorperpendiculartothelevelsetoff(x)evaluatedatx:Sayf(x)=c.-f(x)isavectorpointedindirectionofdecreasingvalueoff(x).Also,-f(x)isperpendiculartothetangenthyperplaneoff(x)=catx.,x1,x2,f(x)=c(constant),-f(x),10,GeometriesofKKT:InequalityConstrained(oneconstraint),FirstOrderNecessaryCondition:f(x)=g(x)forsome0(isascalar)Ifconstraintisbindingg(x)=bthen0,x1,x2,g(x)b,f(x)constant,-f(x)isperpendiculartof(x)constant,-g(x)isperpendiculartofrontier:g(x)=b,-g(x),Atoptimum-g(x)and-f(x)mustbeparallel:twosurfacesmustbetangent,11,GeometriesofKKT:InequalityConstrained(oneconstraint),If-g(x)and-f(x)arenotparallel,therearefeasiblepointswithlessf(x).,12,GeometriesofKKT:InequalityConstrained(oneconstraint),If-g(x)and-f(x)areparallelbutinoppositedirection,therearefeasiblepointswithlessf(x).,x1,x2,g(x)b,f(x)constant,-g(x),-f(x),13,GeometriesofKKT:InequalityConstrained(oneconstraint),FirstOrderNecessaryCondition:f(x)=0ifconstraintisnotbindingg(x)b,X1,X2,f(x)decreasestowardsinkatthemiddle.Atoptimalpoint,f(x)=0Thiscanbeseesasanunconstrainedoptimum.,14,GeometriesofKKT:InequalityConstrained(oneconstraint),FirstOrderNecessaryCondition:f(x)=g(x)forsome0Ifconstraintisnon-bindingg(x)0then=0Lagrangian:L(x,)=f(x)-g(x)-b,s.t.0MinimizeL(x,)overxandMaximizeL(x,)over.UseprinciplesofunconstrainedoptimizationxL(x,)=f(x)-g(x)=0g(x)-b0,then=0.,15,GeometriesofKKT:InequalityConstrained(oneconstraint),Problem:Mimimizef(x),wherexisavectorSubjectto:g(x)bEquivalently:f(x)=g(x)g(x)b0g(x)b=0,16,GeometriesofKKT:InequalityConstrained(twoconstraints),Problem:Minimizef(x),wherexisavectorSubjectto:g1(x)b1andg2(x)b2FirstOrderNecessaryConditions:f(x)=1g1(x)+2g2(x),10,20f(x)liesintheconebetweeng1(x)andg2(x)g1(x)b11=0g2(x)b22=01g1(x)-b1=02g2(x)-b2=0Shadedareaisfeasiblesetwithtwoconstraints,x1,x2,-g1(x),-g2(x),-f(x),Bothconstraintsarebinding,17,GeometriesofKKT:InequalityConstrained(twoconstraints),Problem:Minimizef(x),wherexisavectorSubjectto:g1(x)b1andg2(x)b2FirstOrderNecessaryConditions:f(x)=1g1(x),10g2(x)b22=0g1(x)-b1=0Shadedareaisfeasiblesetwithtwoconstraints,x1,x2,-g1(x),-f(x),Firstconstraintisbinding,18,GeometriesofKKT:InequalityConstrained(twoconstraints),Problem:Minimizef(x),wherexisavectorSubjectto:g1(x)b1andg2(x)b2FirstOrderNecessaryConditions:f(x)=0g1(x)b11=0g2(x)b22=0Shadedareaisfeasiblesetwithtwoconstraints,x1,x2,f(x)=0,Noneconstraintisbinding,19,GeometriesofKKT:InequalityConstrained(twoconstraints),Lagrangian:L(x,1,2)=f(x)-1g1(x)-b1-2g2(x)-b2MinimizeL(x,1,2)overx.UseprinciplesofunconstrainedmaximizationL(x,1,2)=0(gradientwithrespecttoxonly)L(x,1,2)=f(x)-1g1(x)-2g2(x)=0Thusf(x)=1g1(x)+2g2(x)MaximizeL(x,1,2)over10,20.g1(x)-b10,then1=0g2(x)-b20,then2=0,20,KKT:InequalityConstrained(multipleconstraints),21,KKTConditions:InequalityCase,TheKarush-Kuhn-TuckerTheorem:Ifthefunctionf(x)hasaminimumatx*inthefeasiblesetandiff(x*)andgi(x*),i=1,2,m,exist,thenthereisanm-dimensionalvectorsuchthat0f(x*)-i=1migi(x*)=0igi(x*)-bi=0,fori=1,2,m.Suchapoint(x*,)iscalledaKKTpoint,andiscalledtheDualVectorortheLagrangeMultipliers.Furthermore,theseconditionsaresufficientif(aswehaveassumedhere)wearedealingwithaconvexprogrammingproblem,22,Example:KKTConditions,23,Example:KKTConditions,-f(x),g(x),Thecurve(surface)oftheobjectivefunctionistangentialtotheconstraintcurve(surface)attheoptimalpoint.,24,Example:ComputationoftheKKTCondition,If=0,thenx1=0andx2=0,andthustheconstraintwouldnotholdwithequality.Therefore,mustbepositive.Pluggingthetwovaluesofx1()andx2