最新Optimization第四讲(共28张PPT)精品课件

Optimization第四讲第一页，共二十八页。Week1Optimizationwithdirectrestrictionsonvariables.Week2Optimizationwithequalityconstraintsonvariables.Thisweek:ConcaveProgrammingOptimizationwithinequalityconstraintsonvariables.2第二页，共二十八页。Fromweek1:aglobaloptimummayalsoinvolveacornersolution...3第三页，共二十八页。4第四页，共二十八页。Thus(againfromlecture1)Theglobalmaximumx*ofafunctionf(x)onsomeinterval[xmin,xmax]haseitheroneofthefollowingproperties:f’(x*)=0x*=xminx*=xmaxThisimpliesthatoneorbothofthefollowingmusthold:f’(x*)≤0and(x*–xmin)f’(x*)=0f’(x*)≥0and(xmax–x*)f’(x*)=05第五页，共二十八页。Nowsupposeweonlyhavetheconstraintx≥0.Theglobalmaximumx*ofafunctionf(x)withx≥0haseitheroneofthefollowingproperties:f’(x*)=0x*=0Thisimpliesthatthefollowingmusthold:f’(x*)≤0andx*f’(x*)=0Suchconstraintshavetobesatisfiedinalmostalleconomicproblems.6第六页，共二十八页。Recall:maximizationwithanequalityconstraint.7第七页，共二十八页。Now:maximizationwithaninequalityconstraint.Someroughintuitionforthemethodwearegoingtouse:AgainwritedowntheLagrangean:Ultimately,wewanttomaximizethis.ThuswewanttohaveitasclosetotheLagrangeanaspossible.8第八页，共二十八页。Now:maximizationwithaninequalityconstraint.Someroughintuitionforthemethodwearegoingtouse:AgainwritedowntheLagrangean:Thus,wewantthisaslargeaspossibleAndthisassmallaspossible9第九页，共二十八页。Now:maximizationwithaninequalityconstraint.Someroughintuitionforthemethodwearegoingtouse:AgainwritedowntheLagrangean:Hence,wewanttomaximizetheLagrangeanwithrespecttothex’s,andwewanttominimizeitwithrespecttolambda.WearelookingforasaddlepointoftheLagrangean.10第十页，共二十八页。Howtominimizeafunctionwitharestriction?Theglobalmaximumx*ofafunctionf(x)withx≥0haseitheroneofthefollowingproperties:f’(x*)=0x*=0Thisimpliesthatthefollowingmusthold:f’(x*)≤0andx*f’(x*)=011第十一页，共二十八页。ThusTheglobalminimumx*ofafunctionf(x)withx≥0haseitheroneofthefollowingproperties:f’(x*)=0x*=0Thisimpliesthatthefollowingmusthold:f’(x*)≥0andx*f’(x*)=0Thus:Foramaximum:f’(x*)≤0andx*f’(x*)=0Foraminimum:f’(x*)≥0andx*f’(x*)=012第十二页，共二十八页。Combiningresults...WhenwewanttowetakeandderivethefollowingKuhn-Tuckerconditions:13第十三页，共二十八页。Theorem15.1Iffandgareconcaveanddifferentiable,andifSlater’scondition(thereexistsapointwhereg>0)issatisfied,thenbeingabletosolvethisisnecessaryandsufficientforasolutiontotheproblem!Thus:justfindvaluesoflambdaandthex’ssuchthatalltheconditionsaresatisfiedandyou’redone!Thebookgivesaformalproofforthisresult.14第十四页，共二十八页。BacktotheconsumerproblemAgainconsidertheconsumerproblem.Thusfar,wehaveassumedthattheconsumeralwayschoosestoconsumehisentireincome.Butthisisnotnecessary!Actually,theproblemshouldreadlikethis:TheLagrangeanforthisproblemis:Makesuretowritetheconstraintinthecorrectmanner!!!15第十五页，共二十八页。ExampleAconsumerwantstomaximizeutilityU(x1,x2)=x1½x2½subjecttobudgetconstraint2x1+3x2≤10.Inthiscase:f(x1,x2)=x1½x2½andg(x1,x2)=10–2x1–3x2.16第十六页，共二十八页。Kuhn-Tuckerconditionssatisfiestheseconditions.Hencethisisthesolutiontotheproblem!!!Noneedtochecksecond-orderconditions.17第十七页，共二十八页。Anotherexample(fromlastyear’sexam!)AconsumermaximizesutilitygivenbyIncomeis60,bothpricesare6.Yet,theconsumercannotcarrymorethan8units.Thus,theproblemis:18第十八页，共二十八页。19第十九页，共二十八页。20第二十页，共二十八页。Thissatisfiesallconditions.Henceitisthesolutiontotheproblem.21第二十一页，共二十八页。Agraphshowswhat’sgoingonCarryingconstraintBudgetconstraintThebudgetconstraintisnotbinding.Notethatitalsohasashadowpriceofzero!Indeed,relaxingtheconstrainthasnoeffectontheoptimalvalue.22第二十二页，共二十八页。ItalsoworksforfindingminimaWhenwewanttowecanthentakeandderivethesameKuhn-Tuckerconditions:23第二十三页，共二十八页。AnotherexampleInlecture2,wemetarepresentativestudentwhospent60hoursperweekstudying.Shetakestwosubjects.Herobjective:allocatetimebetweenthetwosubjectssuchthattheaveragegradeismaximized.Subjectsdifferwithrespecttotheirproductionfunction.Nowconsideralazystudentswhowantstominimizethetimespentstudyingwhilestillpassingbothsubjects.24第二十四页，共二十八页。Try:bothconstraintsarebinding.Allconditionsaresatisfied!25第二十五页，共二十八页。Italsoworkswithmoreconstraintsandvariables.WhenwewanttoKuhn-Tuckerconditions:26第二十六页，共二十八页。LinearprogrammingNowsupposethatboththeobjectivefunctionandtheconstraintsarelinear.Theoptimumisalwaysacornerpoint.27第二十七页，共二十八页。(nèiróng)总结Optimization第四讲。x*=xmax。x*=0。U(x1,x2)=x1½x2½。satisfiestheseconditions.。27第二十八页，共二十八页。