Constrained Optimization - Columbia University

1 ConstrainedOptimizationJoshuaWilde,revis edbyIsab elTecu,TakeshiSuzukiandMar aJos Bo ccardiAugust13,20131 GeneralProblemConsiderthefollowinggenera lconstrainedoptimizationproblem:maxxi Rf(x1,..,xn)sub jectto:g1(x1,..,xn) b1,..,gk(x1,..,xn) bk,h1(x1,..,xn) =c1,..,hm(x1,..,xn) = (x)iscalledtheob jectivefunction,g(x)iscalledaninequality constraint,andh(x) ,gandhareC1functions, ersfromtheregularunconstrainedoptimizati onprobleminthatinsteadof ndingthemaximumoff(x),weare ndingthemaximumoff(x)onlyoverthep :Maximizef(x) =x2sub jectto0 x :Weknowthatf(x)isstrictlymonotonicallyin creasingoverthedomain,thereforethemaximu m(ifitexists)mustlieatthelargestnumb ,thep ointx= 1isthemaximalnumb erinthedomain, ecausewecouldvisualizethegraphoff(x) ,weseeametho dto ndconstrainedmaximaoffunctionsevenwhenwe can' :maxx Rf(x1,..,xn)sub jectto:h(x1,..,xn) = (x1,..,xn).Sincewemightnotb eabletoachievetheun-constrainedmaximaoft hefunctionduetoourconstraint,weseekto ndthevalueofxwhichgets12 ConstrainedOptimizationusontothehighestl evelcurveoff(x)whileremainingonthefuncti onh(x).

2 Noticealsothatthefunctionh(x)willb ejusttangenttothelevelcurveoff(x).Callth ep ointwhichmaximizestheoptimizationproblem x ,(alsoreferredtoasthemaximizer).Sinceatx thelevelcurveoff(x)istangenttothecurveg( x),itmustalsob ethecasethatthegradientoff(x )mustb einthesamedirectionasthegradientofh(x ),or f(x ) = h(x ),where netheLagrangianthefollowingway:L(x1,..,x n, ) =f(x1,..,xn) [h(x1,..,xn) c]Thensettingthepartialderivativesofthis functionwithresp ecttoxequaltozerowillyieldthe rstorderconditionsforaconstrainedmaximum : f(x ) h(x ) = ectto equaltozerogivesusouroriginalconstraintb ack:h(x ) c= rstorderconditionsforthisproblemaresimpl y L(x, ) = 0 ExampleMaximizef(x1,x2) =x1x2sub jecttoh(x1,x2) x1+ 4x2= :FormtheLagrangianL(x1,x2) =x1x2 (x1+ 4x2 16)The rstorderconditionsaredLdx1=x2 = 0dLdx2=x1 4 = 0dLd =x1+ 4x2 16 = 0 Fromthe rsttwoequationswehavex1= 2,whichinturnimpliesthatx1= 8,andthat = (x1,x2, ) = (8,2,2).

3 Rememb erthatp ointsobtainedusingthisformulamayormaynot b eamaximumorminimum,sincethe cessmayfail, h(x ) = 0,orinotherwords,thep ointwhichmaximizesf(x)isalsoacriticalp ointofh(x).Rememb erournecessaryconditionforamaximum f(x ) = h(x ),Since h(x ) = 0,thisimpliesthat f(x ) = ,thisthenecessaryconditionforanunconstra inedoptimizationproblem,notaconstrainedo ne!Ine ect,when h(x ) = 0,theconstraintisnolongertakenintoaccoun tintheproblem, Rf(x1,..,xn)sub jectto:h1(x1,..,xn) =c1,..,hm(x1,..,xn) = 's rsttalkab ,if h(x ) = 0, ,oravectorofthegradientsofthedi erenthi(x ).Dh(x ) = h1(x ).. hm(x ) = dh1(x ) (x ) (x ) (x )dxn Noticethatifanyofthe hi(x )'siszero,thenthatconstraintwillnotb ,therewillb earowofzerosintheJacobian,andthereforeth eJacobianwillnotb h(x )6= 0forthecasewhenm= 1isthattheJacobianmatrixmustb ,oneoftheconstraintsisnotb eingtakenintoaccount, cation(NDCQ).Notethatweonlyhavetocheckwh ethertheNDCQ holdsatp ointsintheconstraintset,sincep ndthattheconstraintisviolatedforsomep ointwithinourconstraintset,wehavetoaddth isp esnotgiveusanyinformationab outthisp (x1.)

4 ,xn, ) =f(x1,..,xn) m i=1 i[hi(x1,..,xn) ci]Andthereforethenecessaryconditionsfor amaximumaredLdx1= 0,..,dLdxn= 0dLd 1= 0,..,dLd n= (x,y,z) =xyzsub jecttoh1(x,y,z) x2+y2= 1andh2(x,y,z) x+z= (x,y,z) =(2x2y01 0 1)Noticethattherankis1ifandonlyifb othx=y= ,ifthisisthecase,thenour ,therankis2forallp ointsintheconstraintset,andsowedon't4 ConstrainedOptimizationneedtoworryab (x,y,z) =xyz 1(x2+y2 1) 2(x+z 1).The rstorderconditionsare L x=yz 2 1x 2= 0 L y=xz 2 1y= 0 L z=xy 2= 0 L 1=x2+y2 1 = 0 L 2=x+z 1 = 0 Inordertosolvefor 1and 2wedividebyy,sowehavetoassumey6= 0, 1=xz2y, 2= rstequationtogetyz 2x2z2y xy= 0 Multiplyb othsidesbyy6= 0y2z x2z xy2= 0 Nowwewanttosolvethetwoconstraintsforyand zintermsofx,plugthemintothisequation,and getoneequationintermsofx(1 x2)(1 x) x2(1 x) x(1 x2) = 0(1 x)[(1 x2) x2 x(1 +x)]= 0(1 x)[1 3x2 x]= 0 Thisyieldsx={1, 1+ 136, 1 136}.Let'sanalyzex= 1 0,andfromthe rstconstraintwehavethaty= 0,sothiscannotb ,wegetfourcandidatesolutionsx=.

5 4343, y= , z= .7676, y= , z= ,let'slo okatthecasey= 1andz= 0orx= 1andz= 2, rstcase,alltheother rstorderconditionsholdaswell,so(1,0,0) ,weget2 = 0inthesecondFOCandthereforethisp ointcannotb Rf(x1,..,xn)sub jectto:g(x1,..,xn) (x), ,imaginethegraphofthelevelsetswhichwetal kedab outb eingconstrainedtothefunctiong(x),thedoma inisnowb ,theboundaryofthefunctionisstillthesamea sb ointwheretheb oundaryistangenttosomelevelsetofg(x).The questionnowiswhethertheb oundaryisbindingornot erthatwearetryingto ndcandidatep ointswhereg(x) bgivesustwotyp esofcandidatep oints:Pointsontheb oundaryg(x) =bwhereg(x) =bistangenttothelevelcurvesoff(x),andlo calmaximaoff(x)forwhichg(x) rsttyp ewecan ndbytheconstrainedFOC f(x) = g(x),andthesecondtyp ewecan ndbytheunconstrainedFOC f(x) = 'slo :Candidatesalongtheb oundary(constraintbinding) , ,thegradientoff(x)isgoingtop ointinthesteep (x)p ointstothesetg(x) b(sinceitp ointsinthedirectionofincreasingg(x)).

6 Therefore g(x)isp ointinginthesamedirectionas f(x),whichimpliesthat oundaryare f(x) g(x) = 0and :Candidatesnotontheb oundary(constraintnotbinding) ,theinequalitydo rstorderconditionissimply f(x) = 0,whichwecanrewrite(totakethesameshap easab ove)as f(x) g(x) = 0and = ,eithertheconstraintisbinding(tight),tha tisg(x) b= 0and 0,ortheconstraintisnot-binding(slack),an dthen = [g(x) b] = ecauseiftheconstraintisbinding,theng(x) b= 0,andiftheconstraintisnotbinding,thenwew anttoignoreitbyhaving = ,itdo esnotmatterwhethertheconstraintbindsordo esnotbind,theLagrangianmultipliermustalw aysb ,anothernewsetofconditionsare i 0 ,wehaveincludeouroriginalinequalityconst raintg(x) ,whichwede neasb eforetob eL(x, ) =f(x) (g(x) b): L(x, ) xi= f(x) xi g(x) xi= 0foralli= 1,..,n L(x, ) = [g(x) b] = 0complementaryslackness L(x, ) = [g(x) b] 0originalconstraint :maxxi Rf(x1.)

7 ,xn)sub jectto:g1(x1,..,xn) b1,..,gk(x1,..,xn) ,wemustrealizethatifaconstraintdo esnotbind,wedon' ,theNDCQ withinequalityconstraintsisthesameasthee qualityconstraints,exceptforthefactthatw eonlycareab outtheJacobianmatrixofthebindingconstrai nts,ortheJacobianfortheconstraintswith i>0.(Noticethatwecannottellinadvancewhic hconstraintswillb ebinding,soweneedtocheckallofthemwhenwec hecktheNDCQb eforecomputingthesolutioncandidates.)The following rstorderconditionswilltellusthecandidate p ointsforamaximum L x1= 0,.., L xn= 0[g1(x1,..,xn) b1] 1= 0,..,[gk(x1,..,xn) bk] k= 0g1(x1,..,xn) b1,..,gk(x1,..,xn) bk 1 0,.., k 04 MixedconstraintsNowconsiderthegeneralpro blem,inwhichwehaveequalityandinequalityc onstraints:maxxi Rf(x1,..,xn)sub jectto:g1(x1,..,xn) b1,..,gk(x1,..,xn) bk,h1(x1,..,xn) =c1,..,hm(x1,..,xn) = ovewecanfor-mulatethefollowingtheorem:Ma thCamp7 Theorem:Supp osethatx isalo calmaximizeroffontheconstraintsetgivenby thekinequalityandmequalitiesab ,assumethatthe rstk0inequalityconstraintsarebindingandt hattheotherk osethattheJacobianoftheequalityconstrain tsandthebindinginequalityconstraintsatx (x, 1.

8 , k, 1,.., m) =f(x) k i=1 i[gi(x) bi] m i=1 i[hi(x) ci]Thenthereexistmultipliers 1,.., kand 1,.., msuchthat1. L xi(x , , ) = 0foralli {1,..,n}2. i[gi(x) bi] = 0foralli {1,..,k} (x ) =ciforalli {1,..,m} (x ) biforalli {1,..,k}5. i 0foralli {1,..,k}Noteagainthatthistheoremgivesusm erely rstorder,necessaryconditions:Ifx isamaximumandiftheNDCQ holdsatx , (x, , ) (Conditionsthatcanb eusedtodosowillb etaughtinyour rstsemestermathclass,oryoucanreadSimon&B lume,chapter19).Noticealsothatwemaynot ndallcandidatesolutionsusingtheLagrangia nmetho diftheNDCQ isviolatedatsomep :SeeSimon&Blume, ensifweareinsteadlo okingtominimizeafunctiongivencertaincons traints?Therearedi erentwaysinwhichwecanchangetheab :Supp osewearegivenaminimizationproblemminxi Rf(x1,..,xn)sub jectto:g1(x1,..,xn) b1,..,gk(x1,..,xn) bk,h1(x1,..,xn) =c1,..,hk(x1,..,xn) = ndingthemaximumof oveproblemintothemaximizationproblemmaxx i R f(x1.

9 ,xn)sub jectto:g1(x1,..,xn) b1,..,gk(x1,..,xn) bk,h1(x1,..,xn) =c1,..,hk(x1,..,xn) = ndcandidatesolutionsforthisproblemasdisc ussedab ,suchasrequiringconsumptiontob eweaklyp :maxx Rnf(x1,..,xn)sub jecttog1(x1 b1,..,xn),..,gm(x1,..,xn) bmandx1 0,..,xn 0 TheLagrangianfunctionwewouldwritewouldta ketheformL(x, ,v) =f(x) m i=1 i(gi(x) bi) +n i=1vixi,whichwouldleadtothefollowing rstorderconditions: L x1= f x1 m i=1 i gi x1+v1= 0,.., L xn= f xn m i=1 i gi xn+vn= 0 1[g1(x) b1] = 0,.., m[gm(x) bm] = 0g1(x1,..,xn) b1,..,gm(x1,..,xn) bmv1x1= 0,..,vnxn= 0,and i,xj 0 i= 1,..,mand j= 1,..,nThat'salotofconditions!(3m+ 3n)NowconsidertheLagrangianwithoutthenon negativityconstraints,andcallittheKuhn-T uckerLagrangian:L(x, ,v) = L(x, ) +n i=1vixiThe rstn rstorderconditionscanb erewrittenas L xj= L xj+vj= 0 j= 1,..,n,whichimplies L xj= vj j= 1,.., L xj= 0and L xj L j= L j=bj gj(x) 0 j= 1.

10 ,m,whichimplies L j 0and j L j= 0 j= 1,.., ,thefollowingarethe rstorderconditionsfortheKuhn-TuckerLagra ngian: L xj 0andxj L xj= 0 j= 1,..,n L j 0and j L j= 0 j= 1,..,m j 0 j= 1,..mThisis2n+ 3mconstraints,nlessthanb 'sconsumptionsetb eR2+andhispreferencerelationonhisconsump tionsetb erepresentedbyu(x,y) = (x 4)2 ,solvehisutilitymaximizationproblemifiti swellde :R+ Randf(x) = (x+ 1)2+ :R2+ Randf(x,y) = 2y (x,y)mustb eontheunitdisc, ,x2+y2 1,solvetheminimizationproblemifitiswelld e ,numb ers3,6,7,10,11, (1994).