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 x 2f x x 0forallx SecondOrderSufficientCondition GivenFONCsatisfied 2f x ispositivedefinite PD x 2f x x 0forallx f xi 0 xi f 3 GeometriesofKKT EqualityConstrained oneconstraint Problem Minimizef x wherexisavectorSubjectto h x bFirstOrderNecessaryConditionforminimum orformaximum f x h x forsome free isascalar Twosurfacesmustbetangenth x band h x barethesame thereisnosignrestrictionon h x b 4 GeometriesofKKT EqualityConstrained oneconstraint FirstOrderNecessaryCondition f x h x forsome Lagrangian L x f x h x b MinimizeL x overxandMaximizeL x over Useprinciplesofunconstrainedoptimization L x 0 xL x f x h x 0 L x h x b 0 5 GeometriesofKKT EqualityConstrained multipleconstraints Problem Minimizef x wherexisavectorSuchthat hi x bifori 1 2 mKKTConditions NecessaryConditions Exist i i 1 2 m suchthat f x i 1n i hi x hi x bifori 1 2 mSuchapoint x iscalledaKKTpoint and iscalledtheDualVectorortheLagrangeMultipliers Furthermore theseconditionsaresufficientiff x isconvexandhi x i 1 2 m arelinear 6 GeometriesofKKT Unconstrained ExceptNon NegativityCondition Problem Minimizef x wherexisavector x 0FirstOrderNecessaryCondition f xi 0ifxi 0 f xi 0ifxi 0Thus f xi xi 0forallxi or f x x 0 f x 0Ifinteriorpoint x 0 then f x 0Nothingchangesiftheconstraintisnotbinding f xi 0 xi f f xi 0 7 GeometryofKKT InequalityConstrained oneconstraint Problem Minimizef x wherexisavectorSubjectto g x b Assumefeasiblesetandsetofpointspreferredtoanypointareallconvexsets i e convexprogram FirstOrderNecessaryCondition f x g x forsome 0 isascalar Ifconstraintisbinding g x b then 0Ifconstraintisnone binding g x b then f x 0or 0 8 GeometriesofKKT InequalityConstrained oneconstraint Foranypointx onthefrontierofthefeasibleregionofg 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 c atx x1 x2 f x c constant f x 10 GeometriesofKKT InequalityConstrained oneconstraint FirstOrderNecessaryCondition f x g x forsome 0 isascalar Ifconstraintisbinding g x b then 0 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 0ifconstraintisnotbinding g x b X1 X2 f x decreasestowardsinkatthemiddle Atoptimalpoint f x 0Thiscanbeseesasanunconstrainedoptimum 14 GeometriesofKKT InequalityConstrained oneconstraint FirstOrderNecessaryCondition f x g x forsome 0Ifconstraintisnon binding g x 0 then 0Lagrangian L x f x g x b s t 0MinimizeL x overxandMaximizeL x over Useprinciplesofunconstrainedoptimization xL x f x g x 0g x b 0 then 0 15 GeometriesofKKT InequalityConstrained oneconstraint Problem Mimimizef x wherexisavectorSubjectto g x bEquivalently f x g x g x b 0 g x b 0 16 GeometriesofKKT InequalityConstrained twoconstraints Problem Minimizef x wherexisavectorSubjectto g1 x b1andg2 x b2FirstOrderNecessaryConditions f x 1 g1 x 2 g2 x 1 0 2 0 f x liesintheconebetween g1 x and g2 x g1 x b1 1 0g2 x b2 2 0 1 g1 x b1 0 2 g2 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 1 g1 x 1 0g2 x b2 2 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 b1 1 0g2 x b2 2 0Shadedareaisfeasiblesetwithtwoconstraints x1 x2 f x 0 Noneconstraintisbinding 19 GeometriesofKKT InequalityConstrained twoconstraints Lagrangian L x 1 2 f x 1 g1 x b1 2 g2 x b2 MinimizeL x 1 2 overx Useprinciplesofunconstrainedmaximization L x 1 2 0 gradientwithrespecttoxonly L x 1 2 f x 1 g1 x 2 g2 x 0Thus f x 1 g1 x 2 g2 x MaximizeL x 1 2 over 1 0 2 0 g1 x b1 0 then 1 0g2 x b2 0 then 2 0 20 KKT InequalityConstrained multipleconstraints 21 KKTConditions InequalityCase TheKarush Kuhn TuckerTheorem Ifthefunctionf x hasaminimumatx inthefeasiblesetandif f x and gi x i 1 2 m exist thenthereisanm dimensionalvector suchthat 0 f x i 1m i gi x 0 i gi x bi 0 fori 1 2 m Suchapoint x iscalledaKKTpoint and iscalledtheDualVectorortheLagrangeMultipliers 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 intotheconstraintwithequalitygivesus 1 8 Wecanthensolveforx1 61andx2 1 28 25 EconomicalInterpretationofLagrangeMultipliers AswithLPs thereisactuallyawholeareaofdualitytheorythatcorrespondstoNLPs Inthisvein wecanviewLagrangiansasshadowpricesfortheconstraintsinNLP correspondingtotheyvectorinLP 26 KKTConditions FinalNotes KKTconditionsmaynotleaddirectlytoaveryefficientalgorithmforsolvingNLPs However theydohaveanumberofbenefits TheygiveinsightintowhatoptimalsolutionstoNLPslooklikeTheyprovideawaytosetupandsolvesmallproblemsTheyprovideamethodtochecksolutionstolargeproblemsTheLagrangemultiplierscanbeseenasshadowpricesoftheconstraints