Optimization第二讲.ppt

OptimizationLecture2,MarcoHaanFebruary21,2005,2,Lastweek,Optimizingafunctionofmorethan1variable.Determininglocalminimaandlocalmaxima.Firstandsecond-orderconditions.Determiningglobalextremawithdirectrestrictionsonvariables.,Thisweek,Constrainedproblems.TheLagrangeMethod.InterpretationoftheLagrangemultiplier.Second-orderconditions.Existence,uniqueness,andcharacterizationofsolutions.,3,Supposethatwewanttomaximizesomefunctionf(x1,x2)subjecttosomeconstraintg(x1,x2)=0.Example:AconsumerwantstomaximizeutilityU(x1,x2)=x1x2subjecttobudgetconstraint2x1+3x2=10.Inthiscase:f(x1,x2)=x1x2andg(x1,x2)=102x13x2.,4,Supposethat,fromg(x1,x2)=0wecanwritex2=(x1).Takethetotaldifferential:dx2=(x1)dx1Also:g1(x1,x2)dx1+g2(x1,x2)dx2=0,Wewanttomaximizef(x1,x2)subjecttog(x1,x2)=0.,Hence:,Wecannowwritetheobjectivefunctionas:,WeveseenthisinMicro1!,5,Theorem13.1,If(x1*,x2*)isatangencysolutiontotheconstrainedmaximizationproblem,thenwehavethatx1*andx2*satisfy,6,Backtotheexample,f(x1,x2)=x1x2andg(x1,x2)=102x13x2.Weneed,So,With,Hence,Thisyields,Note:thisonlysaysthatthisisalocaloptimum.,7,LagrangeMethod,Again,wewantto,Considerthefunction,Thefirsttwoequalitiesimply,Letsmaximizethis:,Hence,wegetexactlytheconditionsweneed!,8,Definition13.2,TheLagrangemethodoffindingasolution(x1*,x2*)totheproblem,consistsofderivingthefollowingfirst-orderconditionstofindthecriticalpoint(s)oftheLagrangefunction,whichare,9,Backtotheexample,f(x1,x2)=x1x2andg(x1,x2)=102x13x2.,Again,thisonlysaysthatthisisalocaloptimum.,10,Themethodalsoworksforfindingminima.(Definition13.2),TheLagrangemethodoffindingasolution(x1*,x2*)totheproblem,consistsofderivingthefollowingfirst-orderconditionstofindthecriticalpoint(s)oftheLagrangefunction,whichare,11,Theinterpretationof*,*istheshadowpriceoftheconstraint.Ittellsyoubyhowmuchyourobjectivefunctionwillincreaseatthemarginasthetheconstraintisrelaxedby1unit.Later,wegointomoredetailsastowhythisisthecase.Intheconsumptionexample,wehadincome10and*=0.204.Thistellsusthatasincomeincreasesby1unit,utilityincreasesby0.204units.Inthisexample,thisisnotveryinformative,asthe“amountofutility”isnotaveryinformativenumber.Yet,inthecaseofe.g.afirmmaximizingitsprofits,thisyieldsinformationthatismuchmoreuseful.,12,TheLagrangemethodoffindingasolution(x1*,.,xm*)totheproblem,consistsofderivingthefollowingfirst-orderconditionstofindthecriticalpoint(s)oftheLagrangefunction,whichare,Italsoworkswithmorevariablesandmoreconstraints.(Definition13.3),13,Second-OrderConditions,Withregularoptimizationinmoredimensions,weneededsomeconditionsontheHessian.,WenowneedthesameconditionsbutontheHessianoftheLagrangefunction.,ThisistheBorderedHessian.,14,Theorem13.3,AstationaryvalueoftheLagrangefunctionyieldsamaximumifthedeterminantoftheborderedHessianispositive,minimumifthedeterminantoftheborderedHessianisnegative.,15,Againbacktotheearlierexample,f(x1,x2)=x1x2andg(x1,x2)=102x13x2.,Evaluatein,Thus,wenowknowthatthisisalocalmaximum.,16,Withmorethantwodimensions.(Theorem13.4),IfaLagrangefunctionhasastationaryvalue,thenthatstationaryvalueisamaximumifthesuccessiveprincipalminorof|H*|alternateinsigninthefollowingway:,Itisamaximumifalltheprincipalminorsof|H*|arestrictlynegative.,Note:Boththeoremsonlygivesufficientconditions.,17,Theorem13.6,TheLagrangemethodworks(infindingalocalextremum)ifandonlyifitispossibletosolvethefirst-orderconditionsfortheLagrangemultipliers.,18,WeierstrasssTheorem:Iffisacontinuousfunction,andXisanonempty,closed,andboundedset,thenfhasbothaminimumandamaximumonX.,Butwhencanwebesurethataminimumandamaximumreallyexist!?,19,WeierstrasssTheorem:Iffisacontinuousfunction,andXisanonempty,closed,andboundedset,thenfhasbothaminimumandamaximumonX.,Butwhencanwebesurethataminimumandamaximumreallyexist!?,fiscontinuousifitdoesnotcontainanyholes,jumps,etc.Youcannotmaximizethefunctionf(x)=1/xontheinterval-1,1.Butyoucanmaximizethefunctionf(x)=1/xontheinterval1,2.,20,WeierstrasssTheorem:Iffisacontinuousfunction,andXisanonempty,closed,andboundedset,thenfhasbothaminimumandamaximumonX.,Butwhencanwebesurethataminimumandamaximumreallyexist!?,Xisnonemptyifitcontainsatleastoneelement.Otherwisetheproblemdoesnotmakesense.Ifthereisnovalue,thereisalsonomaximumvalue.,21,WeierstrasssTheorem:Iffisacontinuousfunction,andXisanonempty,closed,andboundedset,thenfhasbothaminimumandamaximumonX.,Butwhencanwebesurethataminimumandamaximumreallyexist!?,XisclosediftheendpointsoftheintervalarealsoincludedinX.0x1isanopenset.Itisnotaclosedset.0x1isaclosedset.Youcannotmaximizethefunctionf(x)=xontheinterval0x0.,23,Butwhencanwebesurethatalocalextremumisalsoaglobalone!?,Notalways.,g(x),fincreases,notaglobalmaximum,globalmaximum,24,Togiveaformalderivation,weneedsomemoremathematics.,ConvexsetConsidersomesetX.TakeanytwopointsinX.Drawalinebetweenthesepoints.IftheentirelineiswithinX,andthisistrueforanytwopointsintheset,thenthesetisconvex.,Convexset,Notaconvexset,25,Note,A“convexset”issomethingentirelydifferentthana“convexfunction”.Thereisnosuchthingisa“concaveset”.,26,Togiveaformalderivation,weneedsomemoremathematics.,Quasi-concavityConsidersomefunctionf(x).Takesomepointx1.ConsiderthesetX0consistingofallpointsx0thathavef(x0)f(x1).Ifthissetisconvex,andthisistrueforallpossiblex1,thenthefunctionisquasi-concave.,x1,Thisfunctionisquasi-concave,butnotconcave!,27,Togiveaformalderivation,weneedsomemoremathematics.,x1,Thisfunctionisnotquasi-concave.,Quasi-concavityConsidersomefunctionf(x).Takesomepointx1.ConsiderthesetX0consistingofallpointsx0thathavef(x0)f(x1).Ifthissetisconvex,andthisistrueforallpossiblex1,thenthefunctionisquasi-concave.,28,Togiveaformalderivation,weneedsomemoremathematics.,Quasi-convexityConsidersomefunctionf(x).Takesomepointx1.ConsiderthesetX0consistingofallpointsx0thathavef(x0)f(x1).Ifthissetisconvex,andthisistrueforallpossiblex1,thenthefunctionisquasi-convex.,x1,Thisfunctionisquasi-convex,butnotconvex!,29,Quasi-convexityConsidersomefunctionf(x).Takesomepointx1.ConsiderthesetX0consistingofallpointsx0thathavef(x0)f(x1).Ifthissetisconvex,andthisistrueforallpossiblex1,thenthefunctionisquasi-convex.,x1,Thisfunctionisnotquasi-convex.,Togiveaformalderivation,weneedsomemoremathematics.,30,Importanttonote.,Afunctionthatisconcave,isalsoquasi-concave.Afunctionthatisconvex,isalsoquasi-convex.Inalmostallofthecasesweruninto,wellhaveconvexandconcavefunctions.Notealsothatautilityfunctionthatisstrictquasi-concaveifandonlyifityieldsindifferencecurvesthatarestrictlyconvex.,31,Theorem13.7,Inaconstrainedmaximizationproblem,Iffisquasiconcave,allgsarequasiconvex,thenanylocallyoptimalsolutiontotheproblemisalsogloballyoptimal.Thus,iftheseconditionsaresatisfied,solvingtheLagrangeyieldstheglobaloptimum!,32,Theorem13.8:Uniqueness,Inaconstrainedmaximizationproblem,wherefandallthegsareincreasing,theniffisstrictlyquasiconcaveandthegsareconvex,orfisquasiconcaveandthegsarestrictconvex,thenalocallyoptimalsolutionisuniqueandalsogloballyoptimal.Example:theconsumerproblem!Utilityfunctionisincreasingandstrictlyquasi-concave,Budgetconstraintisincreasingandconvex.ThetheoremsaysthatsolvingtheFOCsyieldsauniquean