KKT条件

Karush-Kuhn-TuckerconditionsGeoGordon&RyanTibshiraniOptimization10-725/36-7251RememberdualityGivenaminimizationproblemminx2Rnf(x)subjecttohi(x)0;i=1;:::m`j(x)=0;j=1;:::rwedenedtheLagrangian:L(x;u;v)=f(x)+mXi=1uihi(x)+rXj=1vj`j(x)andLagrangedualfunction:g(u;v)=minx2RnL(x;u;v)2Thesubsequentdualproblemis:maxu2Rm;v2Rrg(u;v)subjecttou0Importantproperties:Dualproblemisalwaysconvex,i.e.,gisalwaysconcave(evenifprimalproblemisnotconvex)Theprimalanddualoptimalvalues,f?andg?,alwayssatisfyweakduality:f?g?Slater'scondition:forconvexprimal,ifthereisanxsuchthath1(x)0;:::hm(x)0and`1(x)=0;:::`r(x)=0thenstrongdualityholds:f?=g?.(Canbefurtherrenedtostrictinequalitiesovernonanehi,i=1;:::m)3DualitygapGivenprimalfeasiblexanddualfeasibleu;v,thequantityf(x)g(u;v)iscalledthedualitygapbetweenxandu;v.Notethatf(x)f?f(x)g(u;v)soifthedualitygapiszero,thenxisprimaloptimal(andsimilarly,u;varedualoptimal)Fromanalgorithmicviewpoint,providesastoppingcriterion:iff(x)g(u;v),thenweareguaranteedthatf(x)f?Veryuseful,especiallyinconjunctionwithiterativemethods...moredualusesincominglectures4DualnormsLetkxkbeanorm,e.g.,`pnorm:kxkp=(Pni=1jxijp)1=p,forp1Nuclearnorm:kXknuc=Pri=1i(X)Wedeneitsdualnormkxkaskxk=maxkzk1zTxGivesustheinequalityjzTxjkzkkxk,likeCauchy-Schwartz.Backtoourexamples,`pnormdual:(kxkp)=kxkq,where1=p+1=q=1Nuclearnormdual:(kXknuc)=kXkspec=max(X)Dualnormofdualnorm:itturnsoutthatkxk=kxk...connectionstoduality(includingthisone)incominglectures5OutlineToday:KKTconditionsExamplesConstrainedandLagrangeformsUniquenesswith1-normpenalties6Karush-Kuhn-TuckerconditionsGivengeneralproblemminx2Rnf(x)subjecttohi(x)0;i=1;:::m`j(x)=0;j=1;:::rTheKarush-Kuhn-TuckerconditionsorKKTconditionsare:02@f(x)+mXi=1ui@hi(x)+rXj=1vj@`j(x)(stationarity)ui
hi(x)=0foralli(complementaryslackness)hi(x)0;`j(x)=0foralli;j(primalfeasibility)ui0foralli(dualfeasibility)7NecessityLetx?andu?;v?beprimalanddualsolutionswithzerodualitygap(strongdualityholds,e.g.,underSlater'scondition).Thenf(x?)=g(u?;v?)=minx2Rnf(x)+mXi=1u?ihi(x)+rXj=1v?j`j(x)f(x?)+mXi=1u?ihi(x?)+rXj=1v?j`j(x?)f(x?)Inotherwords,alltheseinequalitiesareactuallyequalities8Twothingstolearnfromthis:Thepointx?minimizesL(x;u?;v?)overx2Rn.HencethesubdierentialofL(x;u?;v?)mustcontain0atx=x?|thisisexactlythestationarityconditionWemusthavePmi=1u?ihi(x?)=0,andsinceeachtermhereis0,thisimpliesu?ihi(x?)=0foreveryi|thisisexactlycomplementaryslacknessPrimalanddualfeasibilityobviouslyhold.Hence,we'veshown:Ifx?andu?;v?areprimalanddualsolutions,withzerodualitygap,thenx?;u?;v?satisfytheKKTconditions(Notethatthisstatementassumesnothingaprioriaboutconvexityofourproblem,i.e.off;hi;`j)9SuciencyIfthereexistsx?;u?;v?thatsatisfytheKKTconditions,theng(u?;v?)=f(x?)+mXi=1u?ihi(x?)+rXj=1v?j`j(x?)=f(x?)wheretherstequalityholdsfromstationarity,andthesecondholdsfromcomplementaryslacknessThereforedualitygapiszero(andx?andu?;v?areprimalanddualfeasible)sox?andu?;v?areprimalanddualoptimal.I.e.,we'veshown:Ifx?andu?;v?satisfytheKKTconditions,thenx?andu?;v?areprimalanddualsolutions10PuttingittogetherInsummary,KKTconditions:alwayssucientnecessaryunderstrongdualityPuttingittogether:Foraproblemwithstrongduality(e.g.,assumeSlater'scondi-tion:convexproblemandthereexistsxstrictlysatisfyingnon-aneinequalitycontraints),x?andu?;v?areprimalanddualsolutions,x?andu?;v?satisfytheKKTconditions(Warning,concerningthestationaritycondition:foradierentiablefunctionf,wecannotuse@f(x)=frf(x)gunlessfisconvex)11What'sinaname?OlderfolkswillknowtheseastheKT(Kuhn-Tucker)conditions:FirstappearedinpublicationbyKuhnandTuckerin1951LaterpeoplefoundoutthatKarushhadtheconditionsinhisunpublishedmaster'sthesisof1939Manypeople(includinginstructor!)usethetermKKTconditionsforunconstrainedproblems,i.e.,torefertostationarityconditionNotethatwecouldhavealternativelyderivedtheKKTconditionsfromstudyingoptimalityentirelyviasubgradients02@f(x?)+mXi=1Nfhi0g(x?)+rXj=1Nf`j=0g(x?)whererecallNC(x)isthenormalconeofCatx12QuadraticwithequalityconstraintsConsiderforQ0,minx2Rn12xTQx+cTxsubjecttoAx=0E.g.,asinNewtonstepforminx2Rnf(x)subjecttoAx=bConvexproblem,noinequalityconstraints,sobyKKTconditions:xisasolutionifandonlyifQATA0xu=c0forsomeu.Linearsystemcombinesstationarity,primalfeasibility(complementaryslacknessanddualfeasibilityarevacuous)13Water-llingExamplefromB&Vpage245:considerproblemminx2RnnXi=1log(i+xi)subjecttox0;1Tx=1Informationtheory:thinkoflog(i+xi)ascommunicationrateofithchannel.KKTconditions:1=(i+xi)ui+v=0;i=1;:::nui
xi=0;i=1;:::n;x0;1Tx=1;u0Eliminateu:1=(i+xi)v;i=1;:::nxi(v1=(i+xi))=0;i=1;:::n;x0;1Tx=114Canarguedirectlystationarityandcomplementaryslacknessimplyxi=(1=vifv1=0ifv1==maxf0;1=vg;i=1;:::nStillneedxtobefeasible,i.e.,1Tx=1,andthisgivesnXi=1maxf0;1=vig=1Univariateequation,piecewiselinearin1=vandnothardtosolveThisreducedproblemiscalledwater-lling(FromB&Vpage246)15LassoLet'sreturnthelassoproblem:givenresponsey2Rn,predictorsA2Rnp(columnsA1;:::Ap),solveminx2Rp12kyAxk2+kxk1KKTconditions:AT(