Optimization第四讲VIP免费

FacultyofEconomicsOptimizationLecture4MarcoHaanMarch7,2005第一页，共二十九页。Week1Optimizationwithdirectrestrictionsonvariables.Week2minmax12max(,)s.t.,iiiifxxxxxxOptimizationwithequalityconstraintsonvariables.1212max(,)s.t.(,)0fxxgxxThisweek:ConcaveProgrammingOptimizationwithinequalityconstraintsonvariables.1212max(,)s.t.(,)0fxxgxx2第二页，共二十九页。Fromweek1:aglobaloptimummayalsoinvolveacornersolution...maxxx3第三页，共二十九页。minxxmaxx4第四页，共二十九页。Thus(againfromlecture1)Theglobalmaximumx*ofafunctionf(x)onsomeinterval[xmin,xmax]haseitheroneofthefollowingproperties:•f’(x*)=0•x*=xmin•x*=xmaxThisimpliesthatoneorbothofthefollowingmusthold:•f’(x*)≤0and(x*–xmin)f’(x*)=0•f’(x*)≥0and(xmax–x*)f’(x*)=05第五页，共二十九页。Nowsupposeweonlyhavetheconstraintx≥0.Theglobalmaximumx*ofafunctionf(x)withx≥0haseitheroneofthefollowingproperties:•f’(x*)=0•x*=0Thisimpliesthatthefollowingmusthold:•f’(x*)≤0andx*f’(x*)=0Suchconstraintshavetobesatisfiedinalmostalleconomicproblems.6第六页，共二十九页。Recall:maximizationwithanequalityconstraint.1212max(,)s.t.(,)0fxxgxx121212(,,)(,)+(,)xxfxxgxxL7第七页，共二十九页。1212max(,)s.t.(,)0fxxgxxNow:maximizationwithaninequalityconstraint.Someroughintuitionforthemethodwearegoingtouse:AgainwritedowntheLagrangean:121212(,,)(,)+(,)xxfxxgxxLUltimately,wewanttomaximizethis.ThuswewanttohaveitasclosetotheLagrangeanaspossible.8第八页，共二十九页。1212max(,)s.t.(,)0fxxgxxNow:maximizationwithaninequalityconstraint.Someroughintuitionforthemethodwearegoingtouse:AgainwritedowntheLagrangean:121212(,,)(,)+(,)xxfxxgxxLThus,wewantthisaslargeaspossibleAndthisassmallaspossible9第九页，共二十九页。1212max(,)s.t.(,)0fxxgxxNow:maximizationwithaninequalityconstraint.Someroughintuitionforthemethodwearegoingtouse:AgainwritedowntheLagrangean:121212(,,)(,)+(,)xxfxxgxxLHence,wewanttomaximizetheLagrangeanwithrespecttothex’s,andwewanttominimizeitwithrespecttolambda.WearelookingforasaddlepointoftheLagrangean.10第十页，共二十九页。Howtominimizeafunctionwitharestriction?Theglobalmaximumx*ofafunctionf(x)withx≥0haseitheroneofthefollowingproperties:•f’(x*)=0•x*=0Thisimpliesthatthefollowingmusthold:•f’(x*)≤0andx*f’(x*)=011第十一页，共二十九页。ThusTheglobalminimumx*ofafunctionf(x)withx≥0haseitheroneofthefollowingproperties:•f’(x*)=0•x*=0Thisimpliesthatthefollowingmusthold:•f’(x*)≥0andx*f’(x*)=0Thus:•Foramaximum:f’(x*)≤0andx*f’(x*)=0•Foraminimum:f’(x*)≥0andx*f’(x*)=012第十二页，共二十九页。Combiningresults...Whenwewantto121212max(,)s.t.(,)0,,0fxxgxxxxwetake121212(,,)(,)+(,)xxfxxgxxLandderivethefollowingKuhn-Tuckerconditions:****0,0,0,1,2.0,0,0.iiiixxixxLLLL13第十三页，共二十九页。Theorem15.1Iffandgareconcaveanddifferentiable,andifSlater’scondition(thereexistsapointwhereg>0)issatisfied,thenbeingabletosolvethisisnecessaryandsufficientforasolutiontotheproblem!Thus:justfindvaluesoflambdaandthex’ssuchthatalltheconditionsaresatisfiedandyou’redone!Thebookgivesaformalproofforthisresult.14第十四页，共二十九页。Backtotheconsumerproblem•Againconsidertheconsumerproblem.•Thusfar,wehaveassumedthattheconsumeralwayschoosestoconsumehisentireincome.•Butthisisnotnecessary!•Actually,theproblemshouldreadlikethis:121122max(,)s.t.uxxpxpxm•TheLagrangeanfort...