最优化理论与方法lec10-penalty课件

IntroductionThegeneralclassofpenalizationmethodsincludestwogroupsofmethods:Onegroupimposesapenaltyforviolatingaconstraint;Theotherimposesapenaltyforreachingtheboundaryofaninequalityconstraint.

(ii)BarrierMethods(i)PenaltyMethodsThispartdiscussesagroupofmethods,referredtoaspenalizationmethods,whichsolveaconstrainedoptimizationproblembysolvingasequenceofunconstrainedoptimizationproblems.Thehopeisthat,inthelimit,thesolutionsoftheunconstrainedproblemswillconvergetothesolutionoftheconstrainedproblem.IntroductionThegeneralclaIntroductionSupposethatourconstrainedproblemisgivenintheformDefineHencetheconstrainedproblemcanbetransformedintoequivalentunconstrainedproblemConceptually,ifwecouldsolvethisunconstrainedminimizationproblemwewouldbedone.IntroductionSupposethatourcIntroductionUnfortunatelythisisnotapracticalidea,sincetheobjectivefunctionoftheunconstrainedminimizationisnotdefinedoutsidethefeasibleregion.Barrierandpenaltymethodssolveasequenceofunconstrainedsubproblemsthataremore“manageable”.BarrierMethodsPenaltyMethodsbarriertermpenaltytermIntroductionUnfortunatelythisIntroductiongenerateasequenceofstrictlyfeasibleiteratesthatconvergetoasolutionoftheproblemfromtheinteriorofthefeasibleregionalsocalledinterior-pointmethodssincethemethodsrequiretheinteriorofthefeasibleregiontobenonempty,theyarenotappropriateforproblemswithequalityconstraintsBarriermethodsPenaltymethodsgenerateasequenceofpointsthatconvergestoasolutionoftheproblemfromtheexteriorofthefeasibleregionusuallymoreconvenientonproblemswithequalityconstraintsIntroductiongenerateasequencIntroductionDespitetheirapparentdifferences,barrierandpenaltymethodshavemuchincommon.Theirconvergencetheoriesaresimilar,andtheunderlyingstructureoftheirunconstrainedproblemsissimilarMuchofthetheoryforbarriermethodscanbereplicatedforpenaltymethodsandviceversaItiscommontousethegenericname“penaltymethods”todescribebothmethodsBarrierMethodsPenaltyMethodsinteriorpenaltymethodsexteriorpenaltymethodsIntroductionDespitetheirappaBarrierMethodsConsiderthenonlinearinequality-constrainedproblemThefunctionsareassumedtobetwicecontinuouslydifferentiable.BarrierMethodsConsiderthenoBarrierFunctionsTwoexamplesofsuchafunctionarethelogarithmicfunctionBarrierFunctionsTwoexamplesBarrierFunctionsEffectofBarrierTermaone-dimensionalproblemwithboundedconstraintsBarrierFunctionsEffectofBarBarrierFunctionsThebestknownbarrierfunctionisthelogarithmicbarrierfunction:buttheinversebarrierfunctionisalsowidelyused:BarrierFunctionsThebestknowBarrierFunctionsBarriermethodssolveasequenceofunconstrainedminimizationproblemsoftheformAsthebarrierparameterisdecreased,theeffectofthebarriertermisdiminished,sothattheiteratescangraduallyapproachtheboundaryofthefeasibleregion.BarrierFunctionsBarriermeBarrierMethods–Example1Considerthenonlinearprogram:ThenthelogarithmicbarrierfunctiongivestheunconstrainedproblemBarrierMethods–Example1CoBarrierMethods–Example1Iftheconstraintsarestrictlysatisfied,thedenominatorsarepositive.Theunconstrainedobjectiveisstrictlyconvex,hencethissolutionistheuniquelocalminimizerinthefeasibleregion.BarrierMethods–Example1IfBarrierMethods–SomeRemarksFromtheExample1,weseethatIndeed,itispossibletoproveconvergenceforbarriermethodsundermildconditions.barriertrajectoryAregularpointisapointthatsatisfiessomeconstraintqualification(LICQ).BarrierMethods–SomeRemarksBarrierMethods–SomeRemarksSettingthegradientofthebarrierfunctiontozeroweobtain.BarrierMethods–SomeRemarksBarrierMethods–SomeRemarksTheaboveresultsshowthatthepointsonthebarriertrajectory,togetherwiththeirassociatedLagrangemultiplierestimates,arethesolutionstoaperturbationofthefirst-orderoptimalityconditionsExample2Obviously,theoptimum:BarrierMethods–SomeRemarksBarrierMethods–Example2Thefirst-ordernecessaryconditionsforoptimalityare:Supposetheproblemissolvedviaalogarithmicbarriermethod.ThenthemethodsolvestheunconstrainedminimizationproblemTheLagrangemultiplierestimatesatthispointare:BarrierMethods–Example2TheBarrierMethods–SomeRemarksAnotherdesirablepropertysharedbyboththelogarithmicbarrierfunctionandtheinversebarrierfunctionisthatthebarrierfunctionisconvexiftheconstrainedproblemisaconvexprogram.Barriermethodsalsohavepotentialdifficulties.Thepropertyforwhichbarriermethodshavedrawnthemostseverecriticismisthattheunconstrainedproblemsbecomeincreasinglydifficulttosolveasthebarrierparameterdecreases.——Thereasonisthat(withtheexceptionofsomespecialcases)theconditionnumberoftheHessianmatrixofthebarrierfunctionatitsminimumpointbecomesincreasinglylarge,tendingtoinfinityasthebarrierparametertendstozero.BarrierMethods–SomeRemarksBarrierMethods–Example3ConsidertheproblemofExample2.ThenTheHessianmatrixisillconditioned.BarrierMethods–Example3ConBarrierMethodsBarriermethodsrequirethattheinitialguessofthesolutionbestrictlyfeasible.Inourexamples,suchaninitialguesshasbeenprovided,butforgeneralproblemsastrictlyfeasiblepointmaynotbeknown.Itissometimespossibletofindaninitialpointbysolvinganauxiliaryoptimizationproblem.Thisisanalougoustotheuseofatwo-phasemethodinlinearprogramming.BarrierMethodsBarriermethodsPenaltyMethodsIncontrasttobarriermethods,penaltymethodssolveasequenceofunconstrainedoptimizationproblemswhosesolutionisusuallyinfeasibletotheoriginalconstrainedproblem.Apenaltyforviolationoftheconstraintsisincurred.Asthispenaltyisincreased,theiteratesareforcedtowardsthefeasibleregion.Anadvantageofpenaltymethodsisthattheydonotrequiretheiteratestobestrictlyfeasible.Thus,unlikebarriermethods,theyaresuitableforproblemswithequalityconstraints.Considertheequality-constrainedproblemAssumethatallfunctionsaretwicecontinuouslydifferentiable.PenaltyMethodsIncontrastPenaltyMethodsThebest-knownsuchpenaltyisthequadratic-lossfunction:AlsopossibleisapenaltyoftheformPenaltyMethodsThebest-knownPenaltyMethodsThepenaltymethodconsistsofsolvingasequenceofunconstrainedminimizationproblemsoftheformPenaltymethodssharemanyofthepropertiesofbarriermethods:Undermildconditions,itispossibletoguaranteeconvergenceUnderappropriateconditions,thesequenceofpenaltyfunctionminimizersdefinesacontinuoustrajectoryItispossibletogetestimatesoftheLagrangemultipliersatthesolutionPenaltyMethodsThepenaltymetPenaltyMethodsForexample,considerthequadratic-losspenaltyfunctionPenaltyMethodsForexample,coPenaltyMethods–Example3Supposethatthisproblemissolvedviaapenaltymethodusingthequadratic-losspenaltyfunction.ConsidertheproblemThenecessaryconditionsforoptimalityfortheunconstrainedproblemarePenaltyMethods–Example3SupPenaltyMethods–Example3DefineaLagrangemultiplierestimate:PenaltyMethods–Example3DefPenaltyMethods–Example3Penaltyfunctionssufferfromthesameproblemsofillconditioningasdobarrierfunctions.PenaltyMethods–Example3PenPenaltyMethodsItisalsopossibletoapplypenaltymethodstoproblemswithinequalityconstraints.Thequadratic-losspenaltyinthiscaseisThisfunctionhascontinuousfirstderivativesPenaltyMethodsItisalsopossPenaltyMethodsThesameobservationholdsforothersimpleformsofthepenaltyfunction.Thus,onecannotsafelyuseNewton’smethodtominimizethefunction.Forthisreason,straightforwardpenaltymethodshavenotbeenwidelyusedforsolvinggeneralinequality-constrainedproblems.PenaltyMethodsThesameobservMultiplier-BasedMethodsTheillconditioningofpenaltymethodscanbeamelioratedbyincludingmultipliersexplicitlyinthepenaltyfunction.Ofcourse,multipliersappearinthecontextoftheclassicalpenaltymethod,butinthatcasetheyareaby-productofthemethod.Forexample,inclassicalpenaltymethod,themultiplierestimateiswheregisthevectorofconstraintfunctions.ThesemultiplierestimatesareusedinterminationtestsinsensitivityanalysisinamoreactivewaytoderiveanoptimizationalgorithmMultiplier-BasedMethodsThMultiplier-BasedMethodsExaminingproblemsoftheformaugmentedLagrangianmethodMultiplier-BasedMethodsExaminMultiplier-BasedMethods–AlgorithmAsimpleaugmented-Lagrangianmethodhasthefollowingform:Multiplier-BasedMethods–AlgMultiplier-BasedMethodsCommentsonthefinalsteprequires.ThealgorithmwillterminatewhenMultiplier-BasedMethodsCommenMultiplier-BasedMethods–ExampleTheaugmented-LagrangianfunctionisMultiplier-BasedMethods–ExaMultiplier-BasedMethods–ExampleAttheinitialpointMultiplier-BasedMethods–ExaMultiplier-BasedMethods–ExampleUseNewton’smethodtosolvetheunconstrainedsubproblem.Multiplier-BasedMethods–ExaMultiplier-BasedMethodsSomebasicpropertiesoftheaugmented-Lagrangianfunction:Thisshowsthattheobjectivefunctionandtheaugmented-Lagrangianfunctionhavethesamevalueatthesolution.Hencethegradientoftheaugmented-LagrangianisequaltothegradientoftheLagrangian,andvanishesatthesolution.Multiplier-BasedMethodsSomebMultiplier-BasedMethodsAmultiplier-basedmethodcanalsobederivedforproblemswithinequalityconstraintsThenthemultipliersareupdatedusingMultiplier-BasedMethodsAmultMultiplier-BasedMethodsInthebarriermethod,everyestimateofthesolutionhastobestrictlyfeasiblesothatthelogarithmicbarriertermcanbeevaluated.Themodifiedbarrierfunctionhasmanyofthesamepropertiesastheaugmented-Lagrangianfunction.Multiplier-BasedMethodsIntheIntroductionThegeneralclassofpenalizationmethodsincludestwogroupsofmethods:Onegroupimposesapenaltyforviolatingaconstraint;Theotherimposesapenaltyforreachingtheboundaryofaninequalityconstraint.

(ii)BarrierMethods(i)PenaltyMethodsThispartdiscussesagroupofmethods,referredtoaspenalizationmethods,whichsolveaconstrainedoptimizationproblembysolvingasequenceofunconstrainedoptimizationproblems.Thehopeisthat,inthelimit,thesolutionsoftheunconstrainedproblemswillconvergetothesolutionoftheconstrainedproblem.IntroductionThegeneralclaIntroductionSupposethatourconstrainedproblemisgivenintheformDefineHencetheconstrainedproblemcanbetransformedintoequivalentunconstrainedproblemConceptually,ifwecouldsolvethisunconstrainedminimizationproblemwewouldbedone.IntroductionSupposethatourcIntroductionUnfortunatelythisisnotapracticalidea,sincetheobjectivefunctionoftheunconstrainedminimizationisnotdefinedoutsidethefeasibleregion.Barrierandpenaltymethodssolveasequenceofunconstrainedsubproblemsthataremore“manageable”.BarrierMethodsPenaltyMethodsbarriertermpenaltytermIntroductionUnfortunatelythisIntroductiongenerateasequenceofstrictlyfeasibleiteratesthatconvergetoasolutionoftheproblemfromtheinteriorofthefeasibleregionalsocalledinterior-pointmethodssincethemethodsrequiretheinteriorofthefeasibleregiontobenonempty,theyarenotappropriateforproblemswithequalityconstraintsBarriermethodsPenaltymethodsgenerateasequenceofpointsthatconvergestoasolutionoftheproblemfromtheexteriorofthefeasibleregionusuallymoreconvenientonproblemswithequalityconstraintsIntroductiongenerateasequencIntroductionDespitetheirapparentdifferences,barrierandpenaltymethodshavemuchincommon.Theirconvergencetheoriesaresimilar,andtheunderlyingstructureoftheirunconstrainedproblemsissimilarMuchofthetheoryforbarriermethodscanbereplicatedforpenaltymethodsandviceversaItiscommontousethegenericname“penaltymethods”todescribebothmethodsBarrierMethodsPenaltyMethodsinteriorpenaltymethodsexteriorpenaltymethodsIntroductionDespitetheirappaBarrierMethodsConsiderthenonlinearinequality-constrainedproblemThefunctionsareassumedtobetwicecontinuouslydifferentiable.BarrierMethodsConsiderthenoBarrierFunctionsTwoexamplesofsuchafunctionarethelogarithmicfunctionBarrierFunctionsTwoexamplesBarrierFunctionsEffectofBarrierTermaone-dimensionalproblemwithboundedconstraintsBarrierFunctionsEffectofBarBarrierFunctionsThebestknownbarrierfunctionisthelogarithmicbarrierfunction:buttheinversebarrierfunctionisalsowidelyused:BarrierFunctionsThebestknowBarrierFunctionsBarriermethodssolveasequenceofunconstrainedminimizationproblemsoftheformAsthebarrierparameterisdecreased,theeffectofthebarriertermisdiminished,sothattheiteratescangraduallyapproachtheboundaryofthefeasibleregion.BarrierFunctionsBarriermeBarrierMethods–Example1Considerthenonlinearprogram:ThenthelogarithmicbarrierfunctiongivestheunconstrainedproblemBarrierMethods–Example1CoBarrierMethods–Example1Iftheconstraintsarestrictlysatisfied,thedenominatorsarepositive.Theunconstrainedobjectiveisstrictlyconvex,hencethissolutionistheuniquelocalminimizerinthefeasibleregion.BarrierMethods–Example1IfBarrierMethods–SomeRemarksFromtheExample1,weseethatIndeed,itispossibletoproveconvergenceforbarriermethodsundermildconditions.barriertrajectoryAregularpointisapointthatsatisfiessomeconstraintqualification(LICQ).BarrierMethods–SomeRemarksBarrierMethods–SomeRemarksSettingthegradientofthebarrierfunctiontozeroweobtain.BarrierMethods–SomeRemarksBarrierMethods–SomeRemarksTheaboveresultsshowthatthepointsonthebarriertrajectory,togetherwiththeirassociatedLagrangemultiplierestimates,arethesolutionstoaperturbationofthefirst-orderoptimalityconditionsExample2Obviously,theoptimum:BarrierMethods–SomeRemarksBarrierMethods–Example2Thefirst-ordernecessaryconditionsforoptimalityare:Supposetheproblemissolvedviaalogarithmicbarriermethod.ThenthemethodsolvestheunconstrainedminimizationproblemTheLagrangemultiplierestimatesatthispointare:BarrierMethods–Example2TheBarrierMethods–SomeRemarksAnotherdesirablepropertysharedbyboththelogarithmicbarrierfunctionandtheinversebarrierfunctionisthatthebarrierfunctionisconvexiftheconstrainedproblemisaconvexprogram.Barriermethodsalsohavepotentialdifficulties.Thepropertyforwhichbarriermethodshavedrawnthemostseverecriticismisthattheunconstrainedproblemsbecomeincreasinglydifficulttosolveasthebarrierparameterdecreases.——Thereasonisthat(withtheexceptionofsomespecialcases)theconditionnumberoftheHessianmatrixofthebarrierfunctionatitsminimumpointbecomesincreasinglylarge,tendingtoinfinityasthebarrierparametertendstozero.BarrierMethods–SomeRemarksBarrierMethods–Example3ConsidertheproblemofExample2.ThenTheHessianmatrixisillconditioned.BarrierMethods–Example3ConBarrierMethodsBarriermethodsrequirethattheinitialguessofthesolutionbestrictlyfeasible.Inourexamples,suchaninitialguesshasbeenprovided,butforgeneralproblemsastrictlyfeasiblepointmaynotbeknown.Itissometimespossibletofindaninitialpointbysolvinganauxiliaryoptimizationproblem.Thisisanalougoustotheuseofatwo-phasemethodinlinearprogramming.BarrierMethodsBarriermethodsPenaltyMethodsIncontrasttobarriermethods,penaltymethodssolveasequenceofunconstrainedoptimizationproblemswhosesolutionisusuallyinfeasibletotheoriginalconstrainedproblem.Apenaltyforviolationoftheconstraintsisincurred.Asthispenaltyisincreased,theiteratesareforcedtowardsthefeasibleregion.Anadvantageofpenaltymethodsisthattheydonotrequiretheiteratestobestrictlyfeasible.Thus,unlikebarriermethods,theyaresuitableforproblemswithequalityconstraints.Considertheequality-constrainedproblemAssumethatallfunctionsaretwicecontinuouslydifferentiable.PenaltyMethodsIncontrastPenaltyMethodsThebest-knownsuchpenaltyisthequadratic-lossfunction:AlsopossibleisapenaltyoftheformPenaltyMethodsThebest-knownPenaltyMethodsThepenaltymethodconsistsofsolvingasequenceofunconstrainedminimizationproblemsoftheformPenaltymethodssharemanyofthepropertiesofbarriermethods:Undermildconditions,itispossibletoguaranteeconvergenceUnderappropriateconditions,thesequenceofpenaltyfunctionminimizersdefinesacontinuoustrajectoryItispossibletogetestimatesoftheLagrangemultipliersatthesolutionPenaltyMethodsThepenaltymetPenaltyMethodsForexample,considerthequadratic-losspenaltyfunctionPenaltyMethodsForexample,coPenaltyMethods–Example3Supposethatthisproblemissolvedviaapenaltymethodusingthequadratic-losspenaltyfunction.ConsidertheproblemThenecessaryconditionsforoptimalityfortheunconstrainedproblemarePenaltyMethods–Example3SupPenaltyMethods–Example3DefineaLagrangemultiplierestimate:PenaltyMethods–Example3DefPenaltyMethods–Example3Penaltyfunctionssufferfromthesameproblemsofillconditioningasdobarrierfunctions.PenaltyMethods–Example3PenPenaltyMethodsItisalsopossibletoapplypenaltymethodstoproblemswithinequalityconstraints.Thequadratic-losspenaltyinthiscaseisThisfunctionhascontinuousfirstderivativesPenaltyMethodsItisalsopossPenaltyMethodsThesameobservationholdsforothersimpleformsofthepenaltyfunction.Thus,onecannotsafelyuseNewton’smethodtominimizethefunction.Forthisreason,straightforwardpenaltymethodshavenotbeenwidelyusedforsolvinggeneralinequality-constrainedproblems.PenaltyMethodsThesameo