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

《KKTgeometry(从几何图形的角度来阐释KTT条件的意义)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ThePrinciplesandGeometriesofKKTandOptimization1GeometriesofKKT:UnconstrainedProblem:Minimizef(x),wherexisavectorthatcouldhaveanyvalues,positiveornegativeFirstOrderNecessaryCondition(minormax):f(x)=0(∂f/∂xi=0foralli)isthefirstordernecessaryconditionforoptimizationSe

2、condOrderNecessaryCondition:2f(x)ispositivesemidefinite(PSD)[x•2f(x)•x≥0forallx]SecondOrderSufficientCondition(GivenFONCsatisfied)2f(x)ispositivedefinite(PD)[x•2f(x)•x>0forallx]∂f/∂xi=0xif∂2f/∂xi2>02GeometriesofKKT:EqualityConstrained(oneconstraint)Problem:Minim

3、izef(x),wherexisavectorSubjectto:h(x)=bFirstOrderNecessaryConditionforminimum(orformaximum):f(x)=h(x)forsomefree(isascalar)Twosurfacesmustbetangenth(x)=band-h(x)=-barethesame;thereisnosignrestrictiononh(x)=b3GeometriesofKKT:EqualityConstrained(oneconstraint)Fi

4、rstOrderNecessaryCondition: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=04GeometriesofKKT:EqualityConstrained(multipleconstrain

5、ts)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,the

6、seconditionsaresufficientiff(x)isconvexandhi(x),i=1,2,…,m,arelinear.5GeometriesofKKT:Unconstrained,ExceptNon-NegativityConditionProblem:Minimizef(x),wherexisavector,x>0FirstOrderNecessaryCondition:∂f/∂xi=0ifxi>0∂f/∂xi≥0ifxi=0Thus:[∂f/∂xi]xi=0forallxi,orf(x)•x=0,f(

7、x)≥0Ifinteriorpoint(x>0),thenf(x)=0Nothingchangesiftheconstraintisnotbinding∂f/∂xi=0xif∂f/∂xi>06GeometryofKKT:InequalityConstrained(oneconstraint)Problem:Minimizef(x),wherexisavectorSubjectto:g(x)≥b.Assumefeasiblesetandsetofpointspreferredtoanypointareallconvexsets

8、.(i.e.convexprogram)FirstOrderNecessaryCondition:f(x)=g(x)forsome>0(isascalar)Ifconstraintisbinding[g(x)=b],then≥0Ifconstraintisnone