Bertsimas &ampamp;amp; Tsitsiklis 1997 solutions_manual.pdf

《Bertsimas &ampamp;amp; Tsitsiklis 1997 solutions_manual.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、SolutionManualFor:IntroductiontoLinearOptimizationbyDimitrisBertsimas&JohnN.TsitsiklisJohnL.Weatherwax∗November22,2007IntroductionAcknowledgementsSpecialthankstoDaveMonetforhelpingfindandcorrectvarioustyposinthesesolutions.Chapter1(Introduction)Exercise1.1Sincef(·)is

2、convexwehavethatf(λx+(1−λ)y)≤λf(x)+(1−λ)f(y).(1)Sincef(·)isconcavewealsohavethatf(λx+(1−λ)y)≥λf(x)+(1−λ)f(y).(2)Combiningthesetwoexpressionswehavethatfmustsatisfyeachwithequalityorf(λx+(1−λ)y)=λf(x)+(1−λ)f(y).(3)Thisimpliesthatfmustbelinearandtheexpressiongiveninthe

3、bookholds.∗wax@alum.mit.edu1Exercise1.2Part(a):Wearetoldthatfiisconvexsowehavethatfi(λx+(1−λ)y)≤λfi(x)+(1−λ)fi(y),(4)foreveryi.Forourfunctionf(·)wehavethatXmf(λx+(1−λ)y)=fi(λx+(1−λ)y)(5)i=1Xm≤λfi(x)+(1−λ)fi(y)(6)i=1XmXm=λfi(x)+(1−λ)fi(y)(7)i=1i=1=λf(x)+(1−λ)f(y)(8)a

4、ndthusf(·)isconvex.Part(b):Thedefinitionofapiecewiselinearconvexfunctionfiisthatishasarepresen-tationgivenby′fi(x)=Maxj=1,2,...,m(cjx+dj).(9)Soourf(·)functionisXn′f(x)=Maxj=1,2,...,m(cjx+dj).(10)i=1Nowforeachofthefi(x)piecewiselinearconvexfunctionsi∈1,2,3,...,nwearea

5、ddingupinthedefinitionoff(·)wewillassumethatfunctionfi(x)hasmiaffine/linearfunctionstomaximizeover.Nowselectanewsetofaffinevalues(˜cj,d˜j)formedbysummingelementsfromeachofthe1,2,3,...,nsetsofcoefficientsfromtheindividualfi.Eachpairof(˜cj,d˜j)isobtainedbysummingoneofthe(cj,

6、dj)pairsfromeachofthensets.Thenumberofsuchcoefficientscanbedeterminedasfollows.Wehavem1choicestomakewhenselecting(cj,dj)fromthefirstpiecewiselinearconvexfunction,m2choicesforthesecondpiecewiselinearconvexfunction,andsoongivingatotalofm1m2m3···mntotalpossiblesumseachpro

7、ducingasinglepair(˜cj,d˜j).Thuswecanseethatf(·)canbewrittenasQ′f(x)=Maxj=1,2,3,...,nmc˜jx+d˜j,(11)l=1lsinceoneofthe(˜cj,d˜j)willproducetheglobalmaximum.Thisshowsthatf(·)canbewrittenasapiecewiselinearconvexfunction.Exercise1.3(minimizingalinearpluslinearconvexconstra

8、int)Wedesiretoconverttheproblemmin(c′x+f(x))subjecttothelinearconstraintAx≥b,withf(x)givenasinthepicturetothestandardformforlinearprogramm