section33333333333

PartVMathematicalAppendixANotationandMathematicalPreliminariesA.
1LogicalStatementsThenotation:=isshorthandforbydenition.
Thismeanstheobjecttotheleftof:=isbydenitionequaltowhateveriswrittentotherightof:=.
LetAandBdenotetwosetsoflogicalconditions.
ThestatementAifandonlyifBandsymbolizedbyABrepresentstwologicalstatements:–theifpartwhichmeansthatifBholds,thenAmusthold.
Alsoexpressedas"BimpliesA"andsymbolizedbyA=B.
–theonlyifpart,whichmeansthatAholdsonlyifBholdsor,equiv-alently,ifBholds,thenAmusthold.
Alsoexpressedas"AimpliesB"andsymbolizedbyA=B.
A.
2SetsAsetistakenasaprimitiveconcept.
Theobjectsthatconstituteasetarecalledtheelementsoftheset.
Membershipx∈SmeansxisanelementofSorxbelongstoS.
x/∈SmeansxisnotanelementofSorxdoesnotbelongtoS.
{a,b,c,z}denotesthesetwhoseelementsarethoselistedinsidethebraces,i.
e.
,a,b,cuptoz—themeaningof"upto"mustbeclearinthecontext.
Forexample,giventhatthesymbolnisapositiveinteger,theset{1,2,n}isthesetofintegersfrom1upton.
{x:P(x)}meansthesetofallxforwhichthepropositionP(x)istrue.
Thesymbol{x∈S:P(x)}meansthesetofallx∈SforwhichthepropositionP(x)istrue.
436ANotationandMathematicalPreliminariesSTmeanseveryelementofSisalsoanelementofT.
ThesetSissaidtobeasubsetofTorcontainedinT.
S=TmeansthesetsSandTareequal,namely,STandTS.
Union,intersection,complementsS∪TisthesetofallelementsxthatbelongtoSorT,otherwiseknownastheunionofthesetsSandT.
Itcanalsobeexpressedas{x:x∈Sorx∈T}.
S∩TisthesetofallelementsxthatbelongtobothSandT,otherwiseknownastheintersectionofthesetsSandT.
Itcanalsobeexpressedas{x:x∈Sandx∈T}.
AsetSissaidtomeetthesetTiftheirintersectionS∩Tisnotempty.
S\TisthesetofelementsxthatbelongtoSbutdonotbelongtoT,knownasthecomplementofTwithrespecttoS.
Itcanalsobeexpressedas{x:x∈Sandx/∈T}.
SumandproductS+Tistheset{s+t:s∈S,t∈T},knownasthesumorset-theoreticadditionofthesetsSandT.
ThesetsSandTmustbesuchthatthesummakessense.
(x,y)isanorderedpairtakentobeaprimitiveconcept.
Twoorderedpairs(x1,y1),(x2,y2)areequalifx1=x2andy1=y2.
S*Tistheset{(x,y):x∈Sandy∈T},knownasthecarte-sianproductofthesetsSandT.
Moregenerally,Ni=1Siistheset{(x1,x2,xN):xi∈Siforeveryi=1,2,N},thecartesianprod-uctofthesetsS1,S2,SN.
IftheSiareidenticaltoasetS,thenNi=1SiisdenotedbySNandiscalledtheN-foldcartesianproductofS.
FamiliesAsetF={Si}i∈IwhoseelementsSiaresetsforeachi∈Iiscalledafamilyofsets.
ThesetIisknownastheindexset,whichcanbeuncountable.
Afamilyissaidtobeanitefamilyofsetswhentheindexsetisnite.
Theindexsetwilloftenbesuppressedfromthenotation.
LetFbeafamilyofsets.
IfFF,i.
e.
,everysetinthefamilyFisalsoamemberofF,thenFissaidtobeasubfamilyofF.
Givenafamily{Si}i∈Iofsets,itsintersectionistheset{x:x∈Siforeveryi∈I}anditsunionistheset{x:x∈Siforsomei∈I}.
A.
2Sets437Finite-dimensionalspacesThesymbolsIR,IR+,IR,IR++andIRdenote,respectively,thesetofrealnumbers,thesetofnonnegativenumbers,thesetofnegativenumbers,thesetofpositivenumbers,andthesetofnegativenumbers.
ThesymbolsIRn,IRn+,IRn,IRn++andIRndenote,respectively,then-foldcartesianproductofthesetsIR,IR+,IR,IR++andIR.
–IRn+iscalledthenonnegativeorthantofRn.
–IRn++iscalledthepositiveorthantofRn.
–IRniscalledthenonpositiveorthantofRn.
–IRniscalledthenegativeorthantofRn.
SupremumandinmumLetSbeasubsetoftherealline.
–ArealnumberαissaidtobeanupperboundofSifx≤αforeveryx∈S.
AsetSIRisnotguaranteedtohaveanupperbound;ifitdoes,however,thesetSissaidtobeboundedabove.
–ArealnumberαissaidtobealowerboundofSifx≥αforeveryx∈S.
AsetSIRisnotguaranteedtohavealowerbound;ifitdoes,however,thesetSissaidtobeboundedbelow.
RemarkA.
1.
Asalogicalconsequenceofthedenitions,everyrealnumberisbothanupperboundandlowerboundoftheemptyset.
LetSbeasubsetoftherealline.
–IfSisboundedabove,thenanupperboundofSissaidtobeasupremumorleastupperboundofSifitislessthananyotherupperboundofS.
IfthesupremumofSalsobelongstoS,itissaidtobeamaximumofS.
–IfSisboundedbelow,thenalowerboundofSissaidtobeaninmumorgreatestlowerboundofSifitisgreaterthananyotherlowerboundofS.
IftheinmumofSalsobelongstoS,itissaidtobeaminimumofS.
RemarkA.
2.
Afundamentalpropertyoftherealnumbersystem,calledcompleteness,guaranteesthateverynonemptysetofrealnumbersthatis(i)boundedabovehasasupremumand(ii)boundedbelowhasaninmum.
Thesupremumandinmummustbeunique,andwillberespectivelydenotedbysupSandinfS.
Specialsetsdenotesthesetwithoutanyelements,otherwiseknownastheemptyset.
Ndenotesthesetofpositiveintegers{1,2,3,438ANotationandMathematicalPreliminariesZdenotesthesetofintegers3,2,1,0,1,2,3,Thenotationforintervalsofthereallineareasfollows:–(a,b)denotestheset{x:aymeansthatxi>yiforeachi=1,2,n.
–x≤ymeansthatxi≤yiforeachi=1,2,n.
–xymeansthatx≤yandx=y.
–xf(α):={x∈S:f(x)>α}(strictupperlevelset).
L≤f(α):={x∈S:f(x)≤α}(lowerlevelset).
Lf(x)wheneveryx.
–f(·)issaidtobenonincreasingonSiff(y)≤f(x)whenevery≥x.
–f(·)issaidtobedecreasingonSiff(y)0forallx=0.
Ann*nsymmetricmatrixAisnegativedeniteifxTAx33333333333Fig.
A.
1.
Exampleofasupergradient.
446ANotationandMathematicalPreliminaries"Littleoh"o(·)functionsThelittleohfunctionsarestandardnotationaldevicesinanalysisdenedasfollows:Letα∈IR.
Thesymbol"o(α)"isagenericexpressionforanyreal-valuedfunctionh(α)thatsatisesthepropertythath(α)/α→0asα→0.
Letd∈IRn.
Thesymbol"o(||d||)"isagenericexpressionforanyreal-valuedfunctionh(d)thatsatisesthepropertythath(d)/||d||→0as||d||→0.
Thissaysthatas||d||→0theremaindertermo(||d||)goesto0fasterthan||d||does.
Forexample,thefunctionynofthescalaryiso(y)aslongasn>1.
Letd∈IRn.
Thesymbol"o(||d||2)"isagenericexpressionforanyreal-valuedfunctionh(d)thatsatisesthepropertythath(d)/||d||2→0as||d||→0.
Thissaysthatas||d||→0theremaindertermo(||d||2)goesto0fasterthan||d||2does.
Forexample,thefunctionynofthescalaryiso(y2)aslongasn>2.
RemarkA.
7.
Thesumordierenceoftwoo(·)functionsandascalarmul-tipleofano(·)functionarestillo(·)functions.
DierentiablefunctionsAfunctionf(·)isdierentiableatxintheinteriorofSifthereexistsavectorf(x),calledthegradientvector,forwhichf(x+d)=f(x)+f(x)·d+o(||d||)(A.
5)holdsforalldforwhichx+d∈S.
Afunctionf(·)isdierentiableifitisdierentiableateachpointintheinteriorofS.
WhenSIRandf(·)isdierentiableatx,thederivativeoff(·)atxisdenotedbythesymbolf(x).
Supposef(·)isdierentiableatx.
Thelinearfunctionf(x)+f(x)·dofd∈IRniscalledtherst-orderTaylorseriesapproximationoff(·)atx.
RemarkA.
8.
Oftendreferstothedirectionbetweenxandanothervectory,andonewishestoapproximatethefunctionf(·)nearxinthedirectiond.
Onemayuse(A.
5)towritef(x+αd)=f(x)+αf(x)·d+o(α).
(A.
6)(Itisunderstoodthatαissucientlysmallsothatx+αd∈S.
)Supposef(·)isdierentiableatx.
Thepartialderivativeoff(·)withrespecttoxiatxisdenedasf(x)xi:=limα→0f(x+αei)f(x)α.
(A.
7)Itcoincideswiththeithcoordinateofthevectorf(x).
A.
7Dierentiability447RemarkA.
9.
Dierentiabilityoff(·)atxguaranteesexistenceofallpar-tialderivatives.
Theconverse,however,isnottrue:theexistenceofallpartialderivativesatapointdoesnotguaranteethatthefunctionwillbedierentiableatthatpoint.
Ifarst-orderTaylorseriesapproximationexists,itshouldbeunique;thatis,therecanonlybeonegradientvector.
Furthermore,everysupergradientorsubgradientmustcoincidewiththegradient.
TheoremA.
10.
Iff(·)bedierentiableatx,then(a)f(x)isunique,and(b)ifxisasubgradientorsupergradient,thenx=f(x).
Thefollowingtwowell-knowntheoremshavemanyapplications.
TheoremA.
11.
Mean-valuetheorem.
Supposef(·)isdierentiableandSisopen.
Foreveryx1andx2inSthereexistsanx=λx1+(1λ)x2forwhichf(x2)=f(x1)+f(x)·(x2x1).
(A.
8)TheoremA.
12.
L'Hopital'srule.
Letf(·)andg(·)betworeal-valueddierentiablefunctionsdenedonSIRsuchthata∈S.
Iff(a)=g(a)=0,andifthelimitoftheratiof(x)/g(x)asxapproachesaexists,thenlimx→af(x)g(x)=limx→af(x)g(x).
(A.
9)TwicedierentiablefunctionsAfunctionf(·)istwicedierentiableifitisdierentiableandeachpartialderivativeisdierentiable.
Foratwicedierentiablefunctionf(·)theHessianmatrixH(x)isthen*nmatrixwhose(i,j)thentryis(f(x)/xj)xi.
Itismorecommonlydenotedbythesymbol2f(x)xixj.
RemarkA.
13.
TheHessianmatrixissymmetric.
Thatis,2f(x)xixj=2f(x)xjxisothatH(x)=H(x)T.
Atwicedierentiablefunctionf(·)istwicecontinuouslydierentiableifH(x)iscontinuousforeveryx∈S.
RemarkA.
14.
AsaconsequenceofTaylor'stheorem,fortwicecontinu-ouslydierentiablefunctionsf(x+d)=f(x)+d·f(x)+1/2dTH(x)d+o(||d||2)(A.
10)holdsforalldforwhichx+d∈S.
448ANotationandMathematicalPreliminariesLetf(·)beatwicedierentiablefunctionatx.
Thequadraticfunctionf(x)+f(x)·d+12dTH(x)dofd∈realniscalledthesecond-orderTaylorseriesapproximationoff(·)atx.
RemarkA.
15.
Oftendreferstothedirectionbetweenxandanothervectory,andwewishtoapproximatethefunctionf(·)nearxinthedirectiond.
Wethenuse(A.
10)towritef(x+αd)=f(x)+αf(x)·d+1/2α2dTH(x)d+o(α2).
(A.
11)Ausefulpropertyisthefollowingsecond-orderformofTaylor'stheorem.
TheoremA.
16.
Second-orderformofTaylor'stheorem.
Assumef(·)istwice-dierentiableandSisopen.
Foreachx1andx2inSthereexistsanx=λx1+(1λ)x2forwhichf(x2)=f(x1)+f(x1)·(x2x1)+1/2(x2x1)TH(x)(x2x1).
(A.
12)BRealAnalysisB.
1LinearSpacesVectorsinIRncanbeaddedtogetherandmultipliedbyascalar.
Theseadditionandmultiplicationoperationsarecommutative,associative,anddistributive.
Inaddition,avectorx∈IRnhas"length,"oftengivenby||x||:=ni=1x2i.
Alinearspaceisanysetthatpossessesthesetypesofoperations,andanormabstractsthenotionoflength.
B.
1.
1DenitionDenitionB.
1.
AnonemptysetLofelementsx,y,z,.
.
.
isareallinearorvectorspaceifitsatisesthefollowingproperties:a)Anytwoelementsx,y∈Luniquelydetermineathirdelementx+y∈L,calledthesumofxandy,suchthat–x+y=y+x(commutativity);–(x+y)+z=x+(y+z)(associativity);–Thereexistsanelement0∈L,calledthezeroelement,suchthatx+0=xforeveryx∈L;–Foreveryx∈Lthereexistsanelementx∈L,calledthenegativeofx,suchthatx+(x)=0.
b)Foranyrealnumberαandelementx∈Lthereexistsauniqueelementαx∈L,calledtheproductofαandx,suchthat–α(βx)=(αβ)x;–1x=x.
c)Theadditionandmultiplicationlawssatisfythefollowingtwodistribu-tivelaws:–(α+β)x=αx+βx;–α(x+y)=αx+αy.
TheelementsofLarecalledpointsorvectorsandtherealnumbersα,β,.
.
.
arecalledscalars.
450BRealAnalysisB.
1.
2ExamplesExampleB.
2.
Thereallinewiththeusualarithmeticoperationsofadditionandmultiplicationisalinearspace.
ExampleB.
3.
Thesetoforderedn-tuplesx=(x1,x2,xn)ofrealnumberswithadditionandscalarmultiplicationdenedcoordinatewiseby(x1,x2,xn)+(y1,y2,yn):=(x1+y1,x2+y2,xn+yn)α(x1,x2,xn):=(αx1,αx2,αnxn)isalinearspace.
Ofcourse,thisspaceisrecognizedasIRn.
ExampleB.
4.
ThesetIR∞ofallinnitesequencesx=(x1,x2,xk,ofrealnumberswithadditionandscalarmultiplicationdenedcoordinatewiseisalinearspace.
ExampleB.
5.
ThereareanumberofsubsetsofIR∞thatdenelinearspaces.
Hereareafewnotableexamples.
Thesubset1ofIR∞isthecollectionofallxsuchthat∞i=1|xi|0suchthat|xi|0thereexistsanNsuchthatxk∈B(x,)forallk>N.
Thenotationxn→xwillbeusedtodenotethisconvergenceorxnd→xwillbeusedwhenitisimportanttoemphasizethemetric.
Thepointxiscalledthelimitpointoftheconvergentsequence.
Aninnitesequence{xn}Xthatdoesnotconvergeissaidtodiverge.
PropositionB.
39.
Convergentsequencesofametricspacehavethefollow-ingproperties:a)Thelimitpointofaconvergentsequenceisunique.
b)Ifasequence{xn}convergestox,thensodoeseverysubsequenceof{xn}.
Thefollowingpropositionprovidesanequivalent,usefuldenitionofaclosedset.
PropositionB.
40.
Sisclosedifandonlyifwhenevertheinnitesequence{xn}Sconverges,itslimitpointbelongstoS.
PropositionB.
41.
OnIRnxnd1→xxnd2→xxnd∞→x.
5RemarkB.
42.
Thispropositionshowsthatametricisnotanintrinsictoolforanalyzingconvergencepropertiesofsequences.
B.
4.
5CompletenessOften,onewishestoestablishthataparticularsequenceconverges.
Toshowthatasequenceconvergesinacompletemetricspace,itissucienttoshowthateventuallyalloftheremainingpointsinthesequencecanbemadearbi-trarilyclosetooneanother.
Inacompletemetricspace,onedoesnothavetoknowwhatthelimitisinordertoprovethatitexists.
5Thed1,d2andd∞metricsaretheonesrespectivelyinducedfromthe1,2and∞norms.
B.
4MetricSpaces457DenitionB.
43.
Let(X,d)beametricspace.
Asequenceofpoints{xn}XissaidtobeaCauchysequenceifforevery>0,thereexistsanintegerNsuchthatd(xn,xm)N.
RemarkB.
44.
ForaCauchysequence,limm,n→∞d(xn,xm)=0.
DenitionB.
45.
Ametricspace(X,d)issaidtobecompleteifeveryCauchysequenceconvergestoapointinX.
ExampleB.
46.
Herearesomenotableexamplesofcompletemetricspaces:IRn.
TheLpspaces.
Thespaceofreal-valuedcontinuousfunctionsofonevariabledenedonaclosedandboundedsetunderthesupnorm.
PropositionB.
47.
Aclosedsubsetofacompletemetricspaceisitselfacom-pletemetricspace.
B.
4.
6CompactnessDenitionB.
48.
AfamilyF={Uα}isacoverofSifS∪αUα.
Ifeverysetinacoverisopen,thenthecoverissaidtobeanopencover.
AsubcoverofacoverisasubfamilyofFthatalsocoversS.
DenitionB.
49.
SiscompactifeveryopencoverofShasanitesubcover.
DenitionB.
50.
ThediameterofSisdenedtobediam(S):=sup{d(x,y):x,y∈S}.
DenitionB.
51.
Sisboundedifitsdiameterdiam(S)isnite.
RemarkB.
52.
IfXisanormedlinearspaceanddisthemetricinducedfromthenormonX,thenSXisboundedifSB(0,r)forsomeniterealnumberr.
ThefollowingtheoremprovidesanequivalentdenitionofcompactnessinIRnequippedwithanyofthethreemetricsd1,d2ord∞.
TheoremB.
53.
Heine-BorelTheoremLetSIRn.
SiscompactifandonlyifSisclosedandbounded.
CorollaryB.
54.
AclosedsubsetofacompactsetinIRnisitselfcompact.
Oneofthemostusefulpropertiesofcompactsubsetsofcompletemetricspaces(suchasIRn)isgiveninthefollowingtheorem.
TheoremB.
55.
LetXbeacompletemetricspaceandletSXbecompact.
Everyinnitesequence{xn}Shasaconvergentsubsequence.
458BRealAnalysisB.
4.
7ContinuityDenitionB.
56.
Let(X,d)beametricspaceandletf:X→IR.
Thereal-valuedfunctionfdenedonXissaidtobecontinuousatthepointx0∈Xifforevery>0thereexistsaδ>0suchthat|f(x)f(x0)|0thereexistsaδ>0suchthat|f(x)f(x0)|0thereexistsaδ>0suchthatf(x)f(x0)0thereexistsaδ>0suchthatf(x)f(x0)>wheneverd(x,x0)0andusetheuppersemicontinuityoff(·)atxtondaδ>0suchthatf(x)f(x0)0andsetα:=f(x0).
Sincex0/∈L≥f(α+),aclosedset,theremustexistaδ>0suchthattheopenballB(x0,δ)centeredatx0doesnotintersectL≥f(α+).
Butthismeansthatf(x).
)Animportantclassofconvexsetsarehyperplanesandtheirassociatedclosedandopenhalfspaces.
DenitionC.
3.
AhyperplaneinIRnisthesetdenedbyH(p,α):={x∈IRn:p·x=α}forsomenontrivialp∈IRnandrealnumberα.
Thevectorpiscalledthenormaltothehyperplane.
EachhyperplaneH(p,α)inducesfourhalfspacesdenedas:H≥(p,α):={x:p·x≥α}(allpointslyingonorabovethehyperplane).
H>(p,α):={x:p·x>α}(allpointslyingabovethehyperplane).
H≤(p,α):={x:p·x≤α}(allpointslyingonorbelowthehyperplane).
H0suchthat00,andtheresultfollowsbytakingptobeaandsettingα=p·p/2.
CorollaryC.
11.
LetXbeanonempty,closedconvexsubsetofIRn.
Foreachx0∈Xthereexistsa(nontrivial)p0∈IRnandγ∈IRsuchthatp0·x0p·zforallz∈S.
SinceSisacone,itmustbethecasethatp·z≤0forallz∈S,whichshowsthatp∈S.
SinceSisalsoclosed,theoriginbelongstoS,whichimpliesthatp·x>0.
Thus,x/∈S,asclaimed.
C.
4PolyhedraCorollaryC.
12showsthatanyclosedconvexsetistheintersectionofallclosedhalfspacesthatcontainit.
Forapolyhedrononlyanitenumberofclosedhalfspacesisneededtorepresentit.
C.
4.
1DenitionandExamplesDenitionC.
17.
ApolyhedronSIRkisaniteintersectionofclosedhalfspaces(andhenceclosedandconvex).
Thatis,S={x∈IRk:ai·x≤bi,1≤i≤M},wheretheai∈IRkarenontrivialandeachbi∈IR.
Sinceanequationa·x=bcanberepresentedviatwoinequalities,namely,a·x≥banda·x≤b,apolyhedroncanbeexpressedviaanitenumberofinequalitiesand/orequalities.
ExampleC.
18.
LetAbeann*mmatrixandletb∈IRm.
Setsoftheform{x∈IRn:Ax≤b},{x∈IRn:Ax=b,x≥0}or{x∈IRn:Ax≥b,x≥0}areexamplesofpolyhedron.
SinceIRn+={x∈IRn:x≥0},thelastset,forexample,canbeexpressedas{x∈IRn+:Ax≥b}.
DenitionC.
19.
Apolytopeisaboundedpolyhedron(andhencecompactandconvex).
ExampleC.
20.
Thesubsetoftheplanedenedby{(x1,x2):x1+x2≤5,2x1+x2≤9,x1+2x2≤9,x1≥0,x2≥0}isapolytope.
SeeFigureC.
2.
466CConvexSetsTEx1x2r(0,4.
5)r(1,4)r(4,1)r(4.
5,0)rrrrddddddddddeeeex1+2x2=92x1+x2=9x1+x2=5Fig.
C.
2.
Exampleofapolytope.
C.
4.
2ExtremePointsandDirectionsDenitionC.
21.
LetCbeaconvexset.
Apointc∈CisanextremepointofCifitcannotberepresentedasaconvexcombinationoftwootherpointsinC.
Equivalently,cisanextremepointifwheneverc=λc1+(1λ)c2withc1,c2∈Candλ∈(0,1),thenc1=c2=c.
ExampleC.
22.
InFigureC.
2,thepoints(0,4.
5),(1,4),(4,1)and(4.
5,0)aretheextremepointsofthispolytope.
EachpointinthepolytopeinFigureC.
2canberepresentedasaconvexcombinationofthefourextremepoints.
Thisistrueforpolytopes,sincetheyarecompact,butnottrueforunboundedpolyhedron,asthefollowingexampleillustrates.
ExampleC.
23.
ConsiderthesubsetoftheplanedenedbyC:={(x1,x2):x1+2x2≤0,2x1x2≤0,x1≥0,x2≥0}anddepictedinFigureC.
3.
Cisaconvexconewithasinglevertex,namely,theorigin.
Obviously,thesetCinFigureC.
3cannotberepresentedasaconvexcombi-nationofitsextremepoints.
However,eachpointinCcanberepresentedasanonnegativelinearcombinationofthevectorsd1:=(2,1)andd2:=(1,2),i.
e.
,foreachc∈Cthereexistsμ1,μ2≥0suchthatc=μ1d1+μ2d2.
ThediherearecalledextremedirectionsofC.
DenitionC.
24.
LetSIRnbenonemptyandclosed.
C.
4Polyhedra467TEx1x2123123!
¨¨¨¨¨¨¨¨¨¨¨¨BrrrrrrrrjFig.
C.
3.
Exampleofanunboundedpolyhedron.
Anontrivialvectord∈IRnisadirectionofSifforeachx∈Stheset{x+λd:λ≥0}iscontainedwithinS.
Twodirectionsd1andd2aredistinctiftheredoesnotexistapositiveαforwhichd1=αd2.
AdirectiondofSisanextremedirectionifitcannotbeexpressedasapositivelinearcombinationoftwodistinctdirections.
Geometrically,disadirectionofSifforeachx∈StherayemanatingfromxandpassingthroughdalsobelongstoS.
Obviously,adirectionisuniqueuptoapositivescalarmultiplication,hencethedenitionofdistinctdirection.
Algebraically,anextremedirectiondhasthepropertythatwheneverd=λ1d1+λ2d2fortwodirectionsd1,d2withλ1,λ2>0,thend1=αd2forsomepositiveα.
C.
4.
3CharacterizationofExtremePointsandDirectionsItwillbeusefulforthedevelopmenttofollowtodeneastandardformatforapolyhedron.
DenitionC.
25.
Thestandardformatforapolyhedronistherepresenta-tiongivenby{x:Ax=b,x≥0}.
ThematrixAisoffullrank.
RemarkC.
26.
Byremovingredundantequations,wemayassumetherankofAismwhenAisanm*n.
Moreover,m≤n.
EverypolyhedronScanbeequivalentlyexpressedinthestandardformat.
Forexample,theinequalitya·x≤bcanbetransformedtoanequalitybyaddinganonnegativeslackvariablessothata·x+s=b.
Similarly,theinequality468CConvexSetsa·x≥bcanbetransformedintoanequalitybyaddinganonnegativeslackvariabletsothata·xt=b.
Ineithercase,notethatthedimensionofxincreasesbyoneandacolumncorrespondingtothecoordinatevectorek+1isaddedtotheendoftheoriginalmatrixA.
Inthisbook,theeconomicvariablesofinterestarealmostalwaysnonnegative.
However,ifavariable,sayxj,isoriginally"unrestricted,"namely,itisnotconstrainedtobenonnegative,thenonesimplyreplacesitwiththedierenceoftwononnegativevariablesx+jxj.
Again,thedimensionofxwillincreasebyoneandthejthcolumnofAismultipliedbyminusoneandinsertedintotheoriginalmatrixAnexttothejthcolumn.
DenitionC.
27.
LetSbeanonemptypolyhedroninstandardformat.
Sup-posethecolumnsofAcanbepermutedsothatA=[BN]suchthatthesubmatrixBisanm*minvertiblematrixsatisfyingB1b≥0.
Thevectorx=xBxN=B1b0iscalledabasicfeasiblesolutionforSwithbasisB.
RemarkC.
28.
AnarbitraryselectionofmcolumnsfromthencolumnsofAwillnotnecessarilybelinearlyindependent.
TheoremC.
29.
LetSbeanonemptypolyhedroninstandardformat.
ApointxisanextremepointofSifandonlyifitisabasicfeasiblesolutionofSforsomebasisB.
CorollaryC.
30.
ThenumberofextremepointsofSisnite.
Proof.
ThenumberofwaystoselectmcolumnsfromthencolumnsinAisnm=n!
(nm)!
m!
,whichisnite.
2Theproofofthefollowingpropositionisimmediatefromthedenitions.
PropositionC.
31.
LetSbeanonemptypolyhedroninstandardformat.
ThenonzerovectordisadirectionofSifandonlyifd≥0andAd=0.
CharacterizingtheextremedirectionsofStakesalittlemorework.
Wemotivatewiththefollowingexample.
Considerthepolyhedronintheplanedenedby{(x1,x2):x1+x2≤1,x1+2x2≤10,x1≥0,x2≥0}.
SeeFigureC.
4.
Thereisoneextremedirectiongivenbyd=(10,10)(8,9)=(2,1).
Instandardformatthepolyhedronisrepresentedas(x1,x2,s1,s2):11101201x1x2s1s2=110.
2n!
denotes"nfactorial,"i.
e.
,n(n1)(n2)···1.
C.
4Polyhedra469TEx1x2246810246810¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨¨Brrrrx1+2x2=10x1+x2=1¨¨¨¨¨¨¨Fig.
C.
4.
Exampleofanextremedirectionofapolyhedron.
Constructthebasisfromthersttwocolumns3sothatB=1112andB1=2111.
NowmultiplybothsidesoftheequationAx=bbyB1toobtain10210111x1x2s1s2=89.
ConsistentwithTheoremC.
29,theextremepoint(8,9)isabasicfeasiblesolutionwithbasisB.
Notehowthethirdcolumnhasnonpositiveentries(infact,negativeentries).
Theextremedirectionthatisgeneratedfromthisnonpositivenonbasiccolumnisd:=2110andisconstructedinthefollowingway.
Onemultipliesthenonbasiccolumnbyminusoneandplacesthesetwoentriesatthe"top"ofd.
Thisproducesthesubvector(2,1)T.
Tocompletethedenitionofd—keepinmindithasfourentries—oneplacesaoneinthethirdposition,sincethisistheposition3Thex1andx2entriesmustbepositivesothisistheonlybasis.
470CConvexSetsofthenonbasiccolumn,andplaceszeroeseverywhereelse(thelastpositionofdinthiscase).
Thatd=(2,1,1,0)TisadirectionofthepolyhedroniseasilyveriedsinceAd=0.
RemarkC.
32.
Thatdisadirectionisnomystery.
Hereisthealgebraicproof.
Letjdenotetheindexofthenonbasiccolumnwhoseentriesarenonpositive,andletajdenotethenonbasiccolumn.
(Inthisexamplej=3.
)Letejdenotethejthunitvectorejtruncatedbyremovingtherstmzeroes.
Thelengthofthevectorejisnm.
(Here,eTj=(0,0,1,0)andeTj=(1,0).
)Inthisnotation,d=B1ajejandB1Nej=B1aj.
(KeepinmindthenonbasiccolumnisobtainedaftermultiplyingAbyB1.
)WehaveB1Ad=B1[BN]d=[IB1N]B1ajej=B1aj+B1aj=0,4whichimpliesthatAd=0;otherwise,Bwouldnotbeinvertible.
Itcanbeshownthatthedsoconstructedis,infact,anextremedirection.
Thus,ifanonbasiccolumnassociatedwithabasicfeasiblesolutionhasnon-positiveentries,thenitgeneratesanextremedirectionofthepolyhedron.
Conversely,everyextremedirectioncanbegeneratedinthisfashion.
Thischaracterizesextremedirections.
Forproofsofthesefacts,seeBazarraetal.
[1993],p.
59.
PropositionC.
33.
Thenumberofextremedirectionsisnite.
Proof.
ForeverychoiceofmatrixBtherearenmchoicesforthenonbasiccolumn.
Thus,thenumberofextremedirectionsisboundedaboveby(nm)nm,whichisnite.
C.
4.
4RepresentationTheoremforPolyhedraThefollowingtheoremcharacterizesnonemptypolyhedraviaextremepointsandextremedirections.
Foraproof,seeBazarraetal.
[1993],pp.
60–61.
TheoremC.
34.
LetSbeanonemptypolyhedroninstandardformat.
Letx1,x2,xKbetheextremepointsofSandletd1,d2,dLbetheextremedirectionsofS.
Thenx∈Sifandonlyifthereexistsaλ=(λ1,λ2,λK)≥0andμ=(μ1,μ2,μL)≥0suchthatx=Kk=1λkxk+L=1μdandKk=1λk=1.
4Algebraically[A1A2]a1a2=A1a1+A2a2wheneverAiisanm*nimatrixandaiisanni-dimensionalvector,i=1,2.
C.
5ApplicationtoLinearProgramming471CorollaryC.
35.
ShasatleastoneextremedirectionifandonlyifSisunbounded.
Proof.
Clearly,ifShasanextremedirection,itisunbounded.
NowsupposeShasnoextremedirections.
Thenxmustbelongtotheconvexhullofanitenumberofpoints,andsoitsnormmustbenite.
5AseparateproofestablishesthatanonemptypolyhedronSwillalwayshaveatleastoneextremepoint—seeBazarraetal.
[1993],p.
58.
C.
5ApplicationtoLinearProgrammingAlinearprogrammingproblemistheminimizationormaximizationofalinearfunctionoverapolyhedron.
Withoutlossofgenerality,weconsiderthelinearprogram(P):min{cTx:Ax=b,x≥0}.
(C.
1)Wemakethefollowingassumptions:Assumption10(i)Aisanm*nmatrixoffullrankm.
(ii)Thefeasibleregion{x:Ax=b,x≥0}isnotempty.
Letx1,x2,xKdenotetheextremepointsandd1,d2,dLdenotetheextremedirectionsofthefeasibleregion.
TheoremC.
36.
UnderAssumption10:a)Thelinearprogram(P)hasaniteoptimalsolutionifandonlyifcTd≥0for1≤≤L.
b)Ifthelinearprogram(P)hasaniteoptimalsolution,thenatleastoneextremepointisanoptimalsolution.
Proof.
Asadirectapplicationoftherepresentationtheorem,thelinearpro-grammingproblem(P)canbereformulatedas(P)min(KXk=1λk(cTxk)+LX=1μ(cTd):Xkλk=1,λk,μ≥0forallk,).
(C.
2)IfcTdθ(λ)=λf(xλ)·d,wherexλ:=x1+λd.
Thus,f(xλ)·disnegative.
Sinceθ(λ)f(x)forallxinsomeneighborhoodofx(excludingxofcourse),thenxisastrictlocalmaximizer.
DenitionE.
2.
Thegradientatxissaidtovanishiff(x)=0.
TheoremE.
3.
Supposef:IRn→IRisdierentiableatx.
Ifxisalocalmaximizer,thenthegradientatxvanishes.
Proof.
Iff(x)=0,thenthedirectiond=f(x)haspositivenorm.
Forαsucientlysmall,x+αdliesintheneighborhoodwherexisamaximum,andthusf(x+αd)≤f(x).
Sincef(·)isdierentiableatx,f(x+αd)=f(x)+αf(x)·d+o(α)=f(x)+α||f(x)||2+o(α),whichcontradictsthelocalmaximalityofxforαsucientlysmall.
480EOptimalityConditionsTheoremE.
3isanexampleofanecessarycondition.
Thefollowingtheoremestablishesasucientconditionforxtobeastrictlocalmaximizer.
TheoremE.
4.
Supposef:IRn→IRistwicecontinuouslydierentiableatx.
Iff(x)=0andH(x)isnegativedenite,thenxisastrictlocalmaximizer.
Proof.
Ifxisnotastrictlocalmaximizer,thenthereexistsaninnitese-quencexkconvergingtoxforwhichf(xk)≥f(x),xk=x.
Letdk=xkxforeachk.
Using(A.
10),p.
447,andthefactthatf(x)vanishes,f(x+dk)=f(x)+1/2dTkH(x)dk+o(||dk||2).
Sincef(xk)≥f(x),1/2dTkH(x)dk+o(||dk||2)≥0,or,equivalently,1/2dTkH(x)dk+o(||dk||2)||dk||2≥0(E.
1)wheredk:=dk/||dk||.
The{dk}'sbelongtotheunitball,whichiscompact,andsowemayextractaconvergentsubsequence,saydnk→d.
Bylettingnk→∞in(E.
1),weconcludethatdTH(x)d≥0.
ThiscontradictsthenegativesemidenitenessofH(x).
RemarkE.
5.
TheoremsE.
3andE.
4bothholdiff:IRn→IRisdenedonanopensetSIRn.
E.
2ProblemswithInequalityConstraintsWeconsiderthegeneralmaximizationproblemdenedby(P):{maxf(x):gi(x)≥0,i=1,2,m}.
(E.
2)Inthissectionwemakethefollowingassumptions.
Assumption11f(·)andeachgi(·)arereal-valued,dierentiablefunctionsdenedonanopensetSIRn.
Thevectorsgi(x),i∈I(x),arelinearlyindependent,1whereI(x):={i:gi(x)=0}foreachfeasiblex.
(Thisconditionisanexampleofwhatistermedaconstraintqualication.
)1ThismeansthatifPi∈I(x)μigi(x)=0,theneachμi=0.
E.
2ProblemswithInequalityConstraints481Letg(x)denotethevector(g1(x)gm(x))andg(x)denotethevector(g1(x)gm(x)).
DenitionE.
6.
Vectorsx∈Sandλ∈IRmaresaidtosatisfythecomple-mentaryslacknessconditionsifλigi(x)=0fori=1,2,m.
DenitionE.
7.
Avectorxissaidtosatisfytherst-orderoptimalityconditions[orthe(KKT)conditions]ifi)xisfeasiblefor(P).
ii)Thereexistsanon-negativevectorλ∈IRmforwhich(x,λ)satisesthecomplementaryslacknessconditions.
iii)f(x)+λ·g(x)=0.
ThefollowingtheoremestablishestheKarush-Kuhn-Tucker(KKT)Nec-essaryConditionsforavectorxtobealocalmaximizerof(P).
TheoremE.
8.
UnderAssumption11,ifxisalocalmaximizerof(P),thenxsatisesthe(KKT)conditions.
Proof.
LetAdenotethematrixwhoserowsconsistofthevectorf(x)andgi(x)fori∈I(x).
Werstestablishtheclaimthattherecannotbeavectord∈IRnforwhichAd>0.
TothisendconsiderthesetF={d∈IRn:gi(x)·d>0foralli∈I(x)},(E.
3)andsupposeFisnon-empty.
Pickad∈F.
Foreachi∈I(x),thereexistsaδ>0forwhichg(x+αd)≥0forallα∈[0,δ].
Foreachi/∈I(x),thecontinuityofgiensuresexistenceofaneighborhoodaboutxforwhichgi(x)remainspositive.
GiventhatSisopen,thereexistsaδ>0forwhichx+αdisfeasiblefor(P)forallα∈[0,δ].
Sincexisalocalmaximum,itimmediatelyfollowsthatf(x)·dcannotbepositive.
Thus,theclaimhasbeenshown.
IfthesystemAd>0hasnosolution,thenapplicationoftheseparationtheoremforconvexsetsshowstheremustexistanonnegativevectoryforwhichyTA=0.
2Thatis,y0f(x)+i∈I(x)yigi(x)=0.
(E.
4)WithaslightabuseofnotationextendytoallofIRm+1bydeningyj=0forj/∈I(x)sothaty0f(x)+mi=1yigi(x)=0.
(E.
5)Thelinearindependenceassumptionensuresthaty0ispositive,andsowemaydividebothsidesof(E.
5)byy0toobtainthedesiredresult.
2SeeExercise8.
4,p.
143.
482EOptimalityConditionsThe(KKT)conditionsareextremelyusefulforidentifyingpossible(local)solutionsto(P).
WhenthesetSisclosed,onemustalsochecktheboundaryofS.
Inmanyeconomicproblems,itwillbeclearasolutionexistsandcannotlieontheboundary.
Wenowestablishanexampleofsucientconditionsforoptimalityof(P).
Thestatementbelowonlyassumesthateachgi(·)isquasiconcave.
TheoremE.
9.
Supposef(x)=cTxislinearandeachgi(·)isquasiconcave.
UnderAssumption11,ifxsatisesthe(KKT)conditions,thenxisoptimalfor(P).
Proof.
UsingTheoremD.
12,weknowthegradientgi(x)inducesasup-portinghyperplanetotheupperlevelsetL≥gi(gi(x))atx.
Inparticular,foreachk∈I(x),wehavethatgk(x)·(zx)≥0foreachfeasiblez.
Sinceλk=0foreachk/∈I(x)itthenfollowsthatmk=1λkgk(x)·(zx)≥0foreachfeasiblez.
Sincetheinnerproduct(f(x)+λ·g(x))·(zx)isobviouslyzero,itnowfollowsthatf(x)·(zx)≤0.
Optimalityfollowsfromthelinearityoff(·)sincef(x)=cT.
E.
3LagrangianDualityWeonceagainconsiderproblem(P).
Inthissection,weimposethefollowingadditionalassumptions.
Assumption12f(·)andeachgi(·)areconcave.
3Sisconvex.
(P)hasaniteoptimalsolution.
Slater'sconditionholds,namely,thereexistsanx∈Sforwhichgi(x)>0foreachi.
3Concavityisnotrequiredforseveraloftheresultsbelow.
E.
3LagrangianDuality483UnderAssumptions11and12,problem(P)isintimatelyrelatedtoanunconstrainedproblemdenedbytheLagrangianfunction.
DenitionE.
10.
ThefunctionL(x,λ):=f(x)+mi=1λigi(x)=f(x)+λ·g(x)(E.
6)denedonS*IRmiscalledtheLagrangianfunction.
Thepoint(x,λ)∈S*IRmiscalledasaddlepointoftheLagrangianifL(x,λ)≤L(x,λ)≤L(x,λ)(E.
7)holdsforall(x,λ)∈S*IRm+.
Inthedevelopmentstofollow,weshallnditconvenienttousethefol-lowingtwoexpressionsforagiven(x,λ):ConditionA:L(x,λ)≤L(x,λ)holdsforallx∈S.
ConditionB:L(x,λ)≤L(x,λ)holdsforallλ∈IRm+.
LemmaE.
11.
UnderAssumptions11and12,if(x,λ)isasaddlepointoftheLagrangian,then(x,λ)satisescomplementaryslackness.
Proof.
Settingλ=0inConditionBandnotingthatλ·g(x)isalwaysnonnegativeshowsthat(x,λ)satisescomplementaryslackness.
TheoremE.
12.
UnderAssumptions11and12,if(x,λ)isasaddlepointoftheLagrangian,thenxisanoptimalsolutionto(P).
Proof.
ForConditionBtoholdeachgi(x)mustbenonnegative,sinceeachλimaytakeonarbitrarilylargepositivevalues.
Thus,xisfeasible.
LemmaE.
11(complementaryslackness),ConditionA,andthefactthatλ·g(x)isnonnegativeforeachfeasiblexshowsthatf(x)≤f(x)foreachx∈S.
Sincexisfeasible,itisobviouslyoptimal.
TheoremE.
13.
UnderAssumptions11and12,ifxisanoptimalsolutionto(P),thenaλexistsforwhich(x,λ)isasaddlepointoftheLagrangian.
Proof.
DenethesetC≡{(α,β)∈IR*IRm:α≤f(x)f(x),β≤g(x)forsomex∈S}.
(E.
8)CisconvexanddoesnotintersecttheconvexconeD=IR++*IRm+.
Thesep-arationtheoremforconvexsetsensuresexistenceofa(non-trivial)hyperplane{(α,β):αα+β·β=γ}that(weakly)separatesCfromD,namely,αα+β·β≥γ≥αα+β·β(E.
9)484EOptimalityConditionsholdsforall(α,β)∈Dand(α,β)∈C.
SincethereexistspointsinCthatcantakeonarbitrarilyhighnegativevalues,(E.
9)canonlyholdif(α,β)≥0.
Furthermore,since(0,0)∈Candtheleft-handsideoftheinequalityin(E.
9)canbearbitrarilycloseto0,itfollowsthatγ=0.
Slater'sconditionensuresthatα=0.
Nowsetλ=β/α,andusetheright-handsideof(E.
9)toestablishthatf(x)f(x)+λg(x)≤0,whichisConditionA.
Since(0,g(x))∈Ctheright-handsideof(E.
9)showsthatλ·g(x)≤0.
Sinceλ·g(x)isalwaysnon-negative,complementaryslacknessholds,andConditionBimmediatelyfollows.
Weturntothedierentiablesetting.
Areal-valued,dierentiableconcavefunctionh(·)denedonanopenconvexsetSischaracterizedbythefollowingintuitivegeometricalproperty:forallx∈Sandy∈S,h(y)≤h(x)+h(x)·(yx).
(E.
10)Notethatifh(x)=0,thenxmaximizesh(·)onS.
Anecessaryconditionforxtobealocalmaximizeristhatitsgradientmustvanish;forconcavefunctionsdenedonopensetsthispropertyissucientforxtobeaglobalmaximum.
TheoremE.
14.
Supposef(·)andeachgi(·)aredierentiable.
UnderAs-sumptions11and12,xoptimizes(P)ifandonlyifxsatisestherst-orderoptimalityconditions.
Proof.
Ifxoptimizes(P),thenobviouslyitisfeasible.
FromTheoremE.
13aλexistsforwhich(x,λ)isasaddlepointoftheLangrangian.
Comple-mentaryslacknessfollowsfromfeasibilityandConditionB.
ConditionAandcomplementaryslacknessshowsthatxoptimizesL(·,λ)onS,anopenset.
ThegradientofL(·,λ)mustvanish,whichiscondition(iii).
Asfortheconverse,thefunctionL(·,λ)isconcaveanditsgradientatxvanishes.
Consequently,xoptimizesL(·,λ).
Feasibilityofxandcomple-mentaryslacknessnowshowthatxoptimizes(P).
DenitionE.
15.
Thedualproblemtoproblem(P)isgivenas(D):infλ≥0V(λ)(E.
11)whereV(λ):=supx∈SL(x,λ).
(E.
12)foreachλ∈IRm+.
Wesaythat(x,λ)solves(D)ifV(λ)≤V(λ)forallλ≥0andV(λ)=L(x,λ).
TheoremE.
16.
WeakdualityUnderAssumptions11and12,theoptimalobjectivefunctionvaluefor(D)isanupperboundtotheoptimalobjectivefunctionvaluefor(P).
E.
3LagrangianDuality485Proof.
ObservethatV(λ)≥f(x)foreachfeasiblexandnonnegativeλ.
TheoremE.
17.
StrongdualityUnderAssumptions11and12,theoptimalobjectivefunctionvaluesfortheprimal(P)anddual(D)problemscoincide;thatis,f(x)=V(λ)forrespectiveoptimalsolutionsxandλ.
Inparticu-lar,xsolvesthemaximizationproblemdenedbyV(λ)and(x,λ)satisesthecomplementaryslacknesscondition.
Proof.
Letxdenoteanoptimalsolutionto(P).
ByTheoremE.
13,aλexistsforwhich(x,λ)isasaddlepointoftheLagrangian.
PropositionE.
11(x,λ)andConditionAimmediatelyimpliesthatV(λ)≤f(x).
TheresultnowfollowsfromTheoremE.
16.
FormanyoptimizationproblemsitispossibletoecientlysolveforV(λ)foragivenλ.
Itisoftenthecasethatthenumberofdecisionvariablesinthedualproblemisfarlessthanthenumberofdecisionvariablesintheprimalproblem.
Consequently,solvingthedualproblemcanbemucheasierfromacomputationalperspective.
Thefollowingtheoremshowsthatthedualproblemisaconvexminimizationproblem.
TheoremE.
18.
UnderAssumptions11and12,thefunctionV(·)isconvex.
Proof.
Pickλi∈IRm+,i=1,2,andanδ∈[0,1].
Bydenition,V(δλ1+(1δ)λ2)=supx{f(x)+(δλ1+(1δ)λ2)·g(x)}=supx{δ[f(x)+λ1·g(x)]+(1δ)[f(x)+λ2·g(x)]}≤δ{supx[f(x)+λ1·g(x)]}+(1δ){supx[f(x)+λ2·g(x)]}=δV(λ1)+(1δ)V(λ2).
Iftheobjectivefunctionissmooth(i.
e.
,sucientlydierentiable),thenthereareseveralrelativelysimplealgorithmstosolvethistypeofproblem.
Ingen-eral,theobjectivefunctionmaynotbesmooth.
However,thepast20yearshasseenanumberofecientalgorithmsdevelopedtosolvesuchnonsmoothconvexminimizationproblems.
RemarkE.
19.
Fromapracticalperspective,itisoftenunnecessarytondtheoptimalsolution,anear-optimalsolutionwillsuce.
TheoremE.
16thenbecomesanimportanttool:theratioofV(λ)tof(x)forafeasiblexandanychoiceofλprovidesanaposterioriboundonhowgoodxis.
Forexample,ifV(λ)/f(x)=1.
02,thenf(x)≤1.
02f(x),whichimpliesthatf(x)iswithin2%oftheoptimalobjectivefunctionvalue.
486EOptimalityConditionsE.
4ApplicationofDualitytoEconomicLotSizesWeconsiderthefollowingoptimizationproblem:(P):mini(aixi+bixi):irixi≤R.
(E.
13)Thisproblemhasveryspecialstructure—anadditively-separableobjectivefunctionandconstraint—weshallshortlyexploit,andiscommontomanyoftheeconomicoptimizationproblemsweshallformulateinthisbook.
Thefunctionfi(x):=ai/xi+bixiarisesinavarietyofcontexts,andiscommonlyreferredtoasanEOQform.
Inaninventorycontext,the(positive)decisionvariablexireferstohowmuchquantitytoorderofproducti.
Parameteraidenotesthesetupcostformakingasingleorder,bidenotestheholdingcostpenaltyperunittime,ridenotestheresourcerequiredbyitemi(typicallycashorspace),andRdenotesthemaximumresourceavailable.
Forfuturereference,wenotenowthatTheunconstrainedminimumoffi(xi)isachievedatxi=ai/biandfi(xi)=2√aibi.
Theaggregatedemandforresourceintheunconstrainedproblemisiriai/bi.
Sincetherearepossiblymanyitems,butonlyoneresourceconstraint,weshalltacklethisproblemviaduality.
First,weshallexpressthisproblemincanonicalform(E.
2)asmaxiaixi+bixi:Ririxi≥0.
(E.
14)TheLagrangianisL(x,λ)=iaixi+bixi+λRirixi=λRiaixi+(bi+λri)xi,(E.
15)andthedualobjectivefunctionisV(λ)=supxλRiaixi+(bi+λri)xi=λRinfxiaixi+(bi+λri)xi=λR2iai(bi+λri).
(E.
16)E.
5ApplicationofDualitytoLinearProgramming487Sinceai(bi+λri)isconvexandthesumofconvexfunctionsisconvex,V(·)isconvex,too,asrequired.
Itisobviouslydierentiable.
WeseektominimizeV(·)on[0,∞).
ItsderivativeisV(λ)=Riairiai(bi+λri),(E.
17)whichisclearlyastrictlyincreasingfunctionofλwhoselimitingvalueisR.
Ifthederivativeatzeroisnegative,theneventuallythederivativemustcrosszeroatauniquepoint,andthispointwillindeedbetheoptimalsolutiontothedualproblem.
Itispossible,however,thatthederivativenevervanishes,whichcanonlyhappenifthederivativeatzeroisnonnegative.
From(E.
17)V(0)=Ririai/bi,whichispreciselythedierencebetweenthesupplyoftheresource,R,andtheaggregatedemandfortheresourcefortheunconstrainedproblem.
Thus,iftheaggregatedemandintheunconstrainedproblemdoesnotviolatetheconstraint,theoptimalvalueofthedualvariableisindeedzero,andthesolu-tionforthedualproblemwillcoincidewiththesolutionoftheunconstrainedproblem.
(Notethattheoptimumdualvariableinthiscasemustbezerobycomplementaryslackness.
)LetusassumethatresourceisscarcesothatV(0)0,decreasetheupperboundforλ;otherwise,stop(whenV(0)issucientlyclosetozero).
Wecloseherebyprovidinganinterpretationtothebisectionsearchfromtheprimalproblem'sperspective.
Theaggregatedemandforresourceforagivenvalueofλisx(λ):=iairibi+λvi.
Attheoptimumvalueλ,weknowcomplementaryslacknessholds,whichmeansherethatλ[Rx(λ)]=0.
Thus,theconstraintwillbetightwhensupplyisscarce.
Sincex(·)isadecreasingfunction,thereisobviouslyauniquevalueforλ,anditmaybefoundbyperformingabisectionsearch.
ButnotethatV(λ)givenin(E.
17)ispreciselythedierencebetweenthesupply,R,andtheaggregatedemand,x(λ),andsothisisthesamebisectionsearch.
E.
5ApplicationofDualitytoLinearProgrammingWeapplyLagrangiandualitytoestablishthefamiliardualityoflinearpro-gramming.
Considerthelinearprogrammingproblemdenedas488EOptimalityConditionsmaxx≥0{cTx:Ax≤b},(E.
18)whereAdenotesanmbynmatrix(offullrank).
Weassumethelinearpro-gramhasanoptimalsolution.
Thenthedualproblem(D)maybeexpressedasminy≥0{yTb:yTA≥cT},(E.
19)andithasanoptimalsolutionwhoseobjectivevaluecoincideswiththatoftheprimalproblem.
ToderivethelinearprogrammingdualityfromLagrangianduality,webeginbyexpressingtheproblemasaninstanceofproblem(P),namely,asmax{cTx:bAx≥0,x≥0}.
LetydenotethedualvariablesassociatedwiththeconstraintsbAx≥0,letνdenotethedualvariablesassociatedwiththenonnegativityconstraints,whichareessentialtoinclude,andletλ=(y,ν).
TheLagrangianhereisL(x,λ)=cTx+yT(bAx)+νTx=(cTyTA+νT)x+yTb,andthedualobjectivefunctionV(λ)isV(λ)=supx[(cTyTA+νT)x+yTb].
(E.
20)Sinceaniteoptimalsolutionisassumedtoexistforproblem(P),Theorem(E.
17)ensuresthatthedualproblem(D)alsohasaniteoptimalsolution.
Sincexmaychosenarbitrarilyin(E.
20),aniteoptimalsolutionfor(D)canonlyexistifcTyTA+νT=0,(E.
21)whichimpliesthatV(λ)=yTb.
SincebothyandνarenonnegativeandsinceνT=yTAcT,thedualvariablesmustsatisfyyTA≥cT.
Toconclude,whenminimizingoverthedualvariablesλinproblem(D),itissucienttorestrictattentiontothedomainwhereyTA≥cT,andonthisdomainV(λ)=yTb.
Thelinearprogrammingdualproblem(E.
19)immediatelyfollowsfromthedenitionof(D),andTheoremE.
17guaranteesithasanoptimalsolutionwhoseobjectivevaluecoincideswiththatoftheprimalproblem.
RemarkE.
20.
Usingthefactthatanequalityconstraintmaybewrittenastwolinearinequalities,theduallinearprogramtothelinearprogramdenedbymin{cTx:Ax=b}isminy∈IRm{yTb:yTA≥cT}.
(E.
22)Thatis,itisthesameduallinearprogramasbefore,exceptthatthedualvariablesarenowunconstrained.
E.
6BibliographicalNotes489RemarkE.
21.
Linearprogrammingdualityholdsundermuchweakercondi-tionsthanwhatisassumedhere.
Lagrangiandualityis,however,aconvenientmeansforrememberingtheformoftheduallinearprogram!
E.
6BibliographicalNotesTheclassicreferenceonLagrangiandualityandconvexityisRockafellar[1970].
Bazarraet.
al.
[1993]providesamoreaccessibletreatment,andalsocoversthebasicsoflinearprogramming.
FEnvelopeTheoremSensitivityanalyzesplayamajorroleineconomics.
Inthischapter,forageneralclassofoptimizationproblemsweshowhowtoobtainthesensitivityoftheoptimalvaluetoachangeinaproblemparameter.
F.
1StatementandProofWeconsiderthegeneraloptimizationproblemgivenbyM(a):=maxx∈IRn{F(x,a):gk(x,a)≥0,k=1,K}.
(F.
1)Thevectoraisviewedasrepresentingtheparametersoftheoptimizationproblem,andweshallbeinterestedtoseehowM(a)varieswithchangesinthecoordinatesofa.
ExampleF.
1.
Theproducer'scostminimizationproblemis,ofcourse,aspecialcaseof(F.
1):identifyawith(u,p),MwithQ,F(x,a)withp·x,andgk(x,a)=xkfork=1,2,.
.
.
n,andgn+1(x,a)withΦ(x)u.
Forthestatementandprooftofollow,wemakethefollowingassumptions:Assumption13AIRmisopen.
F(·,·)andeachgk(·,·)aredierentiableonIRn*A.
Foreacha∈A:–thereisauniquesolutionx(a);–x(·)isdierentiableonA;–therst-orderoptimality(KKT)conditionsaresatised;–thereisanopenneighborhoodNacontainingaforwhichthesetofbindingconstraintsI(a):={j:gj(x(a),a)=0}doesnotchange.
492FEnvelopeTheoremTheLagrangianfortheoptimizationproblemisL(x,λ,a)=F(x,a)+kλkgk(x,a),(F.
2)wherewehaveexplicitlydenoteditsdependenceona.
Foreacha,letλ(a)denoteavectorofLagrangemultipliersthatsatisfythe(KKT)conditions.
TheoremF.
2.
EnvelopeTheoremUnderAssumption13,M(a)an=L(x(a),λ(a),a)an.
(F.
3)Proof.
ItisworthwhiletorecallhowShephard'sLemma,Section5.
4.
2,p.
77,wasestablished.
Webeganbyusingthechainrule,thenusedthefactsthatthegradientoftheLagrangian(withrespecttox)mustvanish,andthattheconstraintmustbetightattheoptimum.
Asimilarapproachwillbeusedinthismoregeneralsetting.
Fixa∈A.
Fromthechainrule1Man=iFxixian+Fan.
(F.
4)Sincex(a)andλ(a)jointlysatisfythe(KKT)conditions,Fxi=kλk(a)gkxiforalli=1,2,.
.
.
K.
(F.
5)Substituting(F.
5)into(F.
4)andinterchangingtheorderofsummation,weobtainthatMan=kλk(a)igkxixian+Fan.
(F.
6)Sincethereisaneighborhoodofaforwhichthesetoftightconstraintsdoesnotchange,igkxixian+gkan=0forallk∈I(a),(F.
7)whichshowsthattheexpressioninthebracketsfork∈I(a)in(F.
6)isidenticallygk/an.
Sinceλk(a)=0whenk/∈I(a),wemaysubstitutegk/anfortheexpressioninbracketsforallktoobtainMan=kλk(a)gkan+Fan=Lan,(F.
8)whichcompletestheproof.
1Keepinmindthatthepartialderivativestofollowareevaluatedatthepointsa,(x(a),a),and(x(a),λ(a),a)whereappropriate.
F.
3AMonopolyPricingExample493F.
2ApplicationtoSensitivityAnalysisofCostWeconsiderthesensitivityanalysisofthecostfunctionQ(u,p).
Fixuandpandletx=x(u,p)andλ=λ(u,p).
TheLagrangianofthecostminimizationproblemisL(x,λ,p,u)=p·xλ(Φ(x)u).
(F.
9)AsanimmediateapplicationoftheTheoremF.
2,Q(u,p)pi=L(x,λ,p,u)pi=xi,(F.
10)andQ(u,p)u=L(x,λ,p,u)u=λ.
(F.
11)F.
3AMonopolyPricingExampleWeconsideraveryspecialcaseofourgeneraloptimizationprobleminwhichthedimensionofbothxandaisoneandtherearenoconstraints.
InsuchacasetheEnvelopetheoremreducestothestatementthatM(a)=F/a.
Hereisaninterpretation.
Whenachanges,itdirectlyaectsM(·)viaitsdirecteectonF(·,·),butitalsoindirectlyaectsM(·)sincetheoptimalchoicex(a)willchange.
TheoremF.
2saysthatsincex(a)isanoptimalchoice,thisindirecteectwillbenegligible.
Tomakemattersconcrete,weshallconsideramonopolypricingprob-lemandderivetheEnvelopetheoremgraphically.
Tothisend,weconsideramonopolistwhofacestheinversedemandcurveP=eQ/4,(F.
12)andwhosemarginalcost,c,isconstant.
Themonopolist'sprotfunctionis[eQ/4]QcQ,whichmaybeequivalentlyexpressedasπ(Q,a):=aQQ2/4,(F.
13)wherewehaveseta=ec.
Themonopolist,ofcourse,willchoosethevalueforoutput,Q(a),tooptimizeπ(·,·),andweletM(a)=π(Q(a),a)denotethecorrespondingoptimalprot.
WewanttoexaminehowM(·)varieswiththeparametera.
Notethatanincrease(decrease)inaduetoanincrease(decrease)ineshiftstheinversedemandcurveoutward(inward),whichwillleadtoanincrease(decrease)inprot(andoutput)forthemonopolist.
Thesameeectswillholdifthereisadecrease(increase)intheunitmarginalcost.
ForeachxedvalueforQ,theprotfunction,viewedasafunctionπQ(·)ofa,isobviouslylinearandincreasingina.
Itintersectsthey-axisatQ2/4,494FEnvelopeTheoremthex-axisatQ/4,andtheverticallinex=aforanyvalueofa.
TheoptimalchoiceQ(a)willbethatvalueforQwhoseliney=πQ(a)intersectstheverticallinex=aatthehighestpoint.
NowxvaluesforaandQ,sayataandQ.
WhenwillitbethecasethatQequalsQ(a)ForanyQthetwolinesy=πQ(a)andy=πQ(a)intersectatthepointa=(Q+Q)/4.
Consequently,Q=Q(a)=(Q+Q)/4≤aifQ≤Q,(Q+Q)/4≥aifQ≥Q.
(F.
14)SinceonechoiceforQisQ,itthenfollowsfrom(F.
14)thatQ(a)=2aandM(a)=a2.
(F.
15)Obviously,M(a)=2a.
Moreimportantly,weseefrom(F.
15)thatM(a)alsoequalsQ(a),whichjusthappenstoequaltheslopeofthelineπQ(a)(a).
Inotherwords,M(a)=π(Q(a),a)a,(F.
16)exactlyaspredictedbyTheorem(F.
2)!
F.
4BibliographicalNotesConsultthegraduatemicroeconomictextbookspreviouslymentioned.
GCorrespondenceTheoryThecostfunction,Q(u,p),andindirectproductionfunction,Γ(p),denetwoparametricoptimizationproblems.
Intherstcase,theparametersaregivenbytherequiredoutput,u,andprices,p,whereasinthesecondcasethepa-rametersaregivensimplybythepricesp.
Itisoftendesirabletoknowhowsuchfunctionsvarywithrespecttotheirparameters.
Forexample,arethecostandindirectproductionfunctionscontinuousinpricesItisalsodesirabletoknowhowtheoptimalsolutionsoftheseoptimizationproblemsvarywithre-specttotheparameters.
Forexample,howdothecost-minimizinginputsortheoutput-maximizinginputsvarywithrespecttooutputand/orpricesIngeneral,therecanbeseveraloptimalsolutions.
Consequently,thesequestionscannotbeansweredbyapplyingtheusualnotionofcontinuityoffunctions.
Forsuchanalyses,afunctionmustbereplacedwiththeconceptofacorre-spondence,andcontinuityofafunctionmustbereplacedwiththeconceptofupperorlowerhemicontinuityofacorrespondence.
Correspondencescanbeviewedasapointtosetmapping.
Theinputandoutputpossibilitysetsofatechnologyareexamplesofcorrespondences.
Inwhatfollows,setsSandTwilldenotemetricspaces.
Ifitisuseful,thinkofSIRnandTIRm.
G.
1CoreConceptsDenitionG.
1.
ArelationφofasetStoTisasubsetofS*T.
Thedomainoftherelationφisthesetdom(φ):={x∈S:thereexistsay∈Twith(x,y)∈φ}.
ArelationφofSintoTisacorrespondenceifthedomainofφisS.
Weshallidentifythecorrespondenceφwithapointtosetmappingfφ:S→2Tdenedby11Here2YdenotesthepowersetofthesetY,namely,thecollectionofallsubsetsofY.
496GCorrespondenceTheoryfφ(x):={y∈T:(x,y)∈φ},andwithslightabuseofnotationsimplyrefertofφasφ.
Thus,φ(x)Tforeachx∈S.
DenitionG.
2.
Letφ(·)beacorrespondencefromStoT.
LetASandBT.
TheimageofAunderφisφ(A):=∪x∈Sφ(x).
Theimageofapointx∈Sunderφisφ({x})andwillbedenotedbyφ(x).
φissingle-valuedifφ(x)issingle-valuedforeachx∈S.
Asingle-valuedcorrespondenceφcanbeidentiedwithafunctionfromSintoT,andwithslightabuseofnotationweshalldenotethisfunctionbyφ,too.
ThegraphofφisGr(φ):={(x,y)∈S*T:y∈φ(x)}.
TheupperorstronginverseofBisφ+(B):={x∈S:φ(x)B}.
ThelowerorweakinverseofBisφ(B):={x∈S:φ(x)∩Bisnotempty.
}DenitionG.
3.
AcorrespondenceφfromStoTisupperhemicontinu-ous(u.
h.
c.
)atx∈Sifφ(x)isnonempty,andforeveryopenneighborhoodUofφ(x)thereexistsaneighborhoodVofxforwhichφ(z)Uforallz∈V.
Thecorrespondenceφisu.
h.
c.
ifitisu.
h.
c.
ateveryx∈S.
TheoremG.
4.
Characterizationofu.
h.
c.
LetφbeacorrespondencefromSintoT.
Thefollowingassertionsareequivalent:a)φisu.
h.
c.
b)φ+(G)isopenforeveryopensetGT.
c)φ(F)isclosedforeveryclosedsetFT.
Proof.
(a)=(b).
PickanopenGTandanx∈φ+(G).
SinceGisanopenneighborhoodofφ(x),by(a)weknowthereexistsanopenneighborhoodVofxforwhichφ(V)G,whichimpliesinparticularthatVφ+(G).
Thus,φ+(G)isopen.
(b)=(a).
Pickanx∈SandletUbeanopenneighborhoodofφ(x).
By(b)thesetV:=φ+(U)isanopenneighborhoodofxforwhichφ(z)Uforallz∈V,whichimpliesφisu.
h.
c.
atx.
(b)(c).
Thedenitionsofφ+andφimplythatG.
1CoreConcepts497φ+(G)=(φ(Gc))choldsforallGT.
(Here,thesymbol'c'denotescomplementoftherespectivesetineitherSorT.
)Thatis,φ(x)Gifandonlyifφ(x)∩Gc=ifandonlyifx/∈φ(Gc).
NowtakeGtobeopenandrecallthecomplementofanopen(closed)setisclosed(open).
DenitionG.
5.
Letφ(·)beacorrespondencefromStoT.
φisclosedatxifforeverysequence(xn,yn)∈S*Tforwhichyn∈φ(xn),xn→xandyn→y,itfollowsthaty∈φ(x).
φisclosedifitisclosedateveryx∈S.
φisclosed-valuedifφ(x)isclosedforeveryx∈S.
φiscompact-valuedifφ(x)iscompactforeveryx∈S.
AcorrespondenceφisclosedifandonlyifitsgraphGr(φ)isclosedinS*T.
Inparticular,aclosedcorrespondenceisclosed-valued.
Theconverseisingeneralnottrue.
If,ontheotherhand,thecorrespondenceisu.
h.
c.
,thenaclosed-valuedcorrespondencemustalsobeclosed,asthefollowingpropositionshows.
PropositionG.
6.
Letφ(·)beacorrespondencefromStoT.
a)Supposeφisclosed-valued.
Ifφisu.
h.
c.
,thenφisclosed.
b)SupposeTiscompact.
Ifφisclosed,thenφisu.
h.
c.
Proof.
Part(a).
WeshallshowthatthecomplementofGr(φ)(inS)isopen.
Pickapoint(x,y)/∈Gr(φ).
WeneedtondanopenneighborhoodNof(x,y)suchthatif(x,y)∈N,theny/∈φ(x).
Sincey/∈φ(x),aclosedset,thereexistsanopensetsAandBforwhichy∈ABandB∩φ(x)=.
LetUdenotethecomplementofB(inT).
SinceUisopenandφisu.
h.
c.
weknowV:=φ+(U)isopen,too.
Byconstruction,φ(z)∩A=foreachz∈V.
Thus,wehavefoundanopenneighborhoodN:=V*Athatfulllstherequisiteproperties.
Part(b).
Ifφisnotu.
h.
c.
,thenwecanndanx∈S,anopenneighborhoodUcontainingφ(x),andasequencexn→xsuchthatforeachnayn∈φ(xn)existsforwhichyn/∈U.
ThecomplementofUiscompactsinceTiscompact,andsowemayextractaconvergentsubsequenceofthe{yn}'swhoselimitpointyobviouslydoesnotbelongtoU.
Thus,φisnotclosed.
Thefollowingcorollarysummarizestheconditionsunderwhichu.
h.
c.
isequivalenttoclosureofthegraph.
CorollaryG.
7.
Letφ(·)beaclosed-valuedcorrespondencefromStoTandsupposeTiscompact.
Thenφisu.
h.
c.
ifandonlyifφisclosed.
Continuousfunctionspreservethetopologicalpropertyofcompactness;thatis,thecontinuousimageofacompactsetiscompact.
Thefollowingpropositionshowsthatthesamecanbesaidforupperhemicontinuouscorre-spondences.
498GCorrespondenceTheoryPropositionG.
8.
Letφ(·)beacorrespondencefromStoT.
Ifφisu.
h.
c.
,thenφ(E)iscompactforeverycompactES.
Proof.
LetESbecompactandlet{Uα}α∈Abeanopencoverofφ(E),whichisalsoanopencoverofφ(x)foreachx∈S.
Sinceφ(x)iscompactwemayextractanitesubcover,andletUxdenotetheunionoftheopensetsinthisnitesubcover.
Theu.
h.
c.
ofφensureseachVx:=φ+(Ux)isopen,andso{Vx}asxrangesoverEisanopencoverofE.
SinceEiscompact,wemayextractanitesubcover,say{Vxi}i∈I.
Clearly,φ(E)φ(i∈IVxi)=i∈Iφ(Vxi)i∈IUxi.
SinceeachUxiisaunionofanitenumberoftheUα's,wehaveshownanitesubsetoftheUα'sexiststhatcoversφ(E),asrequired.
G.
2CharacterizationbySequencesTheoremG.
9.
Characterizationofu.
h.
c.
bysequencesThecompact-valuedcorrespondenceφfromStoTisu.
h.
c.
atxifandonlyifΦ(x)isnonempty,andforeverysequencexn→xandeverysequenceyn∈φ(xn),thereisaconvergentsubsequenceoftheyn'swhoselimitybelongstoφ(x).
Proof.
(=)LetEdenotethecollectionofthexn'splusx.
Eiscompactsincexn→x,andsoφ(E)iscompactbyPropositionG.
8.
Thus,wecanextractaconvergentsubsequenceoftheyn'swithlimitpointy.
Sinceacompactsetisclosed,φisclosedbyPropositionG.
6(a),whichimmediatelyimpliesy∈φ(x),asrequired.
(=)Iftheconclusionisfalse,thenwecanndanx∈S,anopenneigh-borhoodUcontainingφ(x),andasequencexn→xsuchthatforeachnayn∈φ(xn)existsforwhichyn/∈U.
Byassumption,thereexistsaconvergentsubsequenceoftheyn'swithlimitpointy∈φ(x).
However,thisisnotpossi-ble,sinceobviouslyy/∈Uandsoy/∈φ(x).
Acontradictionhasbeenreached.
DenitionG.
10.
AcorrespondenceφfromStoTislowerhemicontinu-ous(l.
h.
c.
)atx∈SifΦ(x)isnonempty,andforeveryopenneighborhoodUthatmeetsφ(x)thereexistsaneighborhoodVofxforwhichφ(z)meetsUforallz∈V.
Thecorrespondenceφisl.
h.
c.
ifitisl.
h.
c.
ateveryx∈S.
Thefollowingtheoremcharacterizesl.
h.
c.
inamanneranalogoustoThe-oremG.
4.
Itsproofisleftasanexercise.
TheoremG.
11.
Characterizationofl.
h.
c.
LetφbeacorrespondencefromSintoT.
Thefollowingassertionsareequivalent:a)φisl.
h.
c.
G.
3BibliographicalNotes499b)φ+(F)isclosedforeveryclosedsetFT.
c)φ(G)isopenforeveryopensetGT.
TheoremG.
12.
Characterizationofl.
h.
c.
bysequencesThecorrespon-denceφfromStoTisl.
h.
c.
atxifandonlyifΦ(x)isnonempty,andforeverysequencexn→xandy∈φ(x),thereexistsasequenceyn∈φ(xn)forwhichyn→y.
Proof.
(=)Pickanx∈S,y∈φ(x)andasequencexn→x.
LetUkdenotetheopenballcenteredatywithradiusof1/kandletVk:=φ(Uk),k=1,2,Foreachkannkexistsforwhichxn∈Ukforalln≥nk.
Wemaypickthenk'stoformanincreasingsequence.
Foreachintegernmin{Φ(x),Φ(y)}foreachx,y∈IRk+andλ∈(0,1),thentheremustbeauniquemaximumin(H.
3),whichwouldimplythatDM(·)issingle-valued.
(Otherwise,anon-trivialconvexcombinationoftwodistinctmaximizerswouldbebudgetfeasibleandwouldyieldahigheroutput.
)IfitcanbeshownthatB(·)iscontinuous,thenasadirectapplicationoftheTheoremoftheMaximumH.
2itfollowsthatΓ(·)iscontinuousandDM(·)isu.
h.
c.
andthuscontinuousby(G.
13).
H.
2ApplicationtotheCostFunction503PropositionH.
5.
ThecorrespondenceB(·)in(H.
4)iscontinuous.
Proof.
Clearly,B(·)iscompact-valued,andsoweshalluseTheoremsG.
9andG.
12toestablishtheu.
h.
c.
andl.
h.
c.
,respectively.
Toestablishu.
h.
c.
,letpn→pandxn∈B(pn).
B(·)isclosedsincethedotproductisacontinuousfunctionofitsarguments.
ByTheoremG.
9,itissucienttoshowthexn'sarebounded.
Sincethecoordinatesofparepositiveandpnconvergestop,thecoordinatesofeachpnareeventuallyboundedbelowbyapositivenumber.
Sincepn·xn≤1foralln,iteasilyfollowsthexn'sarebounded,asrequired.
Toestablishl.
h.
c.
,letpn→pandpickx∈B(p).
Withoutlossofgeneralityweshallassumep·x=1.
(Divideeachpnandpbyp·x.
)Foreachnandcoordinatei,1≤i≤k,denexin=(pi/pin)xi.
Byconstruction,pn·xn=ipinxin=p·x=1,andsoxn∈B(pn).
Clearly,xn→x,asrequiredbyTheoremG.
12.
H.
2ApplicationtotheCostFunctionLetF={LΦ(u):u≥0}beawell-behavedtechnology.
InadditiontotheusualpropertiesonΦ(·)thatholdforawell-behavedtechnology,inthissectionwemakethefollowingassumption:Assumption14Φ(·)iscontinuous,strictlyquasiconcaveandincreasing.
ThecostfunctionisdenedasQ(u,p)=min{p·x:Φ(x)≥u}.
(H.
5)Ifallpricesarepositive,thecostfunctionhasaminimum.
Thisisbecauseitispossibletoconstrainthefeasibleregionof(H.
5)tothecompactdomain{x∈IRk+:p·x≤p·e(u)},wheree∈IRkdenotesthevectorwhosecoordinatesareidentically1andwheree(u):=e/D(e,u)forallu>0.
(HereD(·,·)istheinputdistancefunctionforF.
)Ifsomepricesarezero,however,thenanadditionalpropertymustbeassumedtoensurethat(H.
5)hasaminimum.
Inthiscase,weassumethattheEcientFrontierisbounded,seeAxiomA.
5,p.
38.
DenitionH.
6.
ThecostfeasiblecorrespondenceγfromIR+*IRk++intoIRk+denedasγ(u,p):={x∈IRk+:Φ(x)≥uandp·x≤p·e(u)}.
504HTheoremoftheMaximumDenitionH.
7.
TheHicksiandemandcorrespondenceDHfromIRk++intoIRk+isdenedasDH(p):={z∈γ(u,p):Q(u,p)=p·z}.
SinceΦ(·)isstrictlyquasiconcaveandincreasing,theremustbeauniquemaximumin(H.
5),whichwouldimplythatDH(·)issingle-valued.
1Ifitcanbeshownthatγ(·,·)iscontinuous,thenasadirectapplicationoftheTheoremoftheMaximum(seeH.
2,p.
501),itfollowsthatQ(·,·)isjointlycontinuousandDH(·)isu.
h.
c.
andthuscontinuousby(G.
13).
Undertheconditionshereintheinputdistancefunctioniscontinuousinu.
WestatethefollowingLemmawithoutproof.
LemmaH.
8.
UnderAssumption14,foreachx∈IRk++thefunctionf(u):=D(x,u)1iscontinuousinu.
PropositionH.
9.
ThecorrespondenceγfromIR+*IRk++intoIRk+denedbyγ(u,p):={x∈IRk+:Φ(x)≥uandp·x≤p·e(u)}iscontinuous.
Proof.
Clearly,γ(·,·)iscompact-valued,andsoweshalluseTheoremsG.
9andG.
12toestablishtheu.
h.
c.
andl.
h.
c.
,respectively.
Letpn→p,un→u,anddenebn:=pn·e(un)foreachnandb:=p·e(u).
Notethatbn→bbyLemmaH.
8.
Letpn=pn/bnandp=p/b.
Ofcoursepn→p.
Withthisnotation,γ(un,pn)=L(un)∩B(pn).
Toestablishu.
h.
c.
,letxn∈γ(un,pn).
SincethecorrespondenceB(·)inPropositionH.
5isu.
h.
c.
wemayextractasubsequence{xnk}whoselimitpointx∈γ(p).
ThecontinuityofΦ(·)ensuresx∈L(u)sinceΦ(xnk)≥unkforeachk.
Thus,aconvergentsubsequenceofthexn'shasbeenfoundwhoselimitpointliesinγ(u,p),asrequiredbyTheoremG.
9.
Toestablishl.
h.
c.
,pickx∈γ(u,p).
Sinceγ(·,·)iscompact-valued,foreachnavectorznexiststhatminimizesthedistancefromxtoγ(un,pn).
Sincezn∈γ(un,pn),andwehaveprovedthatγ(·,·)isu.
h.
c.
,itfollowsthatwemayextractaconvergentsubsequence{znk}whoselimitpointz∈γ(u,p).
Theresultwillfollowifwecanshowthatz=x.
Ifthiswerenotso,theny:=(x+z)/2=xandy∈γ(u,p)sinceγ(u,p)isconvex.
Forδ>0letyδ:=y/(1+δ).
ThevalueΦ(y)exceedsusinceΦ(·)isstrictlyquasiconcave.
Let:=(Φ(y)u)/2.
ThereexistsanNforwhichΦ(y)>u+≥un,foralln≥N.
(H.
6)1Otherwise,itwouldbepossibletoscaledownanon-trivialconvexcombinationoftwodistinctminimizerstostillachievetherequiredoutputbutatalowercost.
H.
3BibliographicalNotes505SinceΦ(·)isincreasingandcontinuous,Φ(yδ)≥u+(H.
7)forδsucientlysmall.
Usingthetriangleinequality,wehave||yδx||≤11+δ(1/2||zx||+δ|x||).
(H.
8)Itfollowsfrom(H.
8)thatwemaypickaδsucientlysmallforwhich||yδx||0hastheprobabilitymassfunction508IProbabilityBasicsP(X=i)=eλλii!
,i=0,1,2,.
.
.
.
Themean,E[X],andvariance,Var[X],bothequalλ.
ItturnsoutthatthePoissonprobabilitymassfunctioncloselyapproximatesabinomialprobabil-itymassfunctionunderthefollowingconditions.
LetX1denoteabinomialrandomvariablewithparametersnandpsuchthatnis"large,"pis"small"andtheirproductλ=npisof"moderate"magnitude,andletX2denoteaPoissonrandomvariablewithparameterλ.
ThenP(X1=k)≈P(X2=k).
I.
3PoissonProcessesAstochasticprocess{N(t),t≥0}isacountingprocessifN(t)recordsthetotalnumberofoccurrencesofaneventuptotimet(e.
g.
,customerorders,arrivalstoaqueue).
LetT1t.
(I.
3)(Whens=0,Λ(s)=0,too.
)Hereisaninterpretation.
Imagineasystemobservertaskedwithobservingthearrivaltimes.
Hefaithfullyrecordthetimesonseparateindexcards,butnottheeventindex.
(Theobserverkeepstrackoftheeventindex.
)Heinformsustherewerenindexcardsobtainedintheinterval[0,t],andhehandsusasealedenvelopecontaininganindexcardrandomlychosenfromthesetofnindexcards.
LetTdenotethetimelistedI.
5ConditionalExpectationandVariance509onthisrstindexcard.
ThepropertyaboveimpliesthatP(T≤τ)=G(τ).
Ifwewerehandedasecondindexcardandthenathird,andsoon,thesetimeswouldhavethesamedistributionasG(τ).
I.
4MomentGeneratingFunctionsThemomentgeneratingfunctionφX(u):=E[euX](foruinsomeneighborhoodof0)ofarandomvariableXissonamedbe-causeallofthemomentsofX,namely,E[Xk],k=1,2,canbeobtainedbysuccessivelydierentiatingφX(t)andevaluatingitatzero.
Forexample,E[X]=φX(0)andE[X2]=φX(0).
Sincethevariance,Var[X],ofXequalsE[X2](E[X])2,ittoocanbeobtainedfromthemomentgeneratingfunction.
ItturnsoutthatthemomentgeneratingfunctionofarandomvariableXuniquelydeterminesitsdistribution.
Thatis,ifφX(·)matchesaknownfunctionalformforacertaintypeofdistribution,thenXmusthavethistypeofdistributionwiththeparametersidentiedthroughitsmomentgeneratingfunction.
ThediscreterandomvariableXhasthebinomialdistributionwithpar-ametersnandpifandonlyifitsmomentgeneratingfunctionisφX(u)=[1+p(eu1)]n.
(I.
4)ArandomvariableXhasthePoissondistributionwithmeanλ>0ifandonlyifitsmomentgeneratingfunctionisφX(u)=eλ(eu1).
(I.
5)I.
5ConditionalExpectationandVarianceLetE[X|Y]denotethefunctionoftherandomvariableYwhosevalueatY=yisE[X|Y=y].
NotethatE[X|Y]isitselfarandomvariable.
AfundamentalpropertyofconditionalexpectationthatwerepeatedlyexploitisthatforallrandomvariablesXandYE[X]=E(E[X|Y]).
(I.
6)IfYisadiscreterandomvariable,then(I.
6)statesthatE[X]=yE[X|Y=y]P(Y=y),whereasifYisacontinuousrandomvariablewithprobabilitydensityfunctionfY(y),then(I.
6)statesthat510IProbabilityBasicsE[X]=∞∞E[X|Y=y]fY(y)dy.
TheconditionalvarianceofXgiventherandomvariableYisdenedbyVar[X|Y]:=E(XE[X|Y])2|Y.
ItcanbeshownthattheunconditionedvarianceofXcanbeexpressedasVar[X]=E(Var[X|Y])+Var(E[X|Y]).
(I.
7)I.
6BibliographicalNotesForadditionalbackgroundmaterialonstochasticprocesses,consultRoss[1985].
Foradenitivereferenceonpointprocesses,consultSerfozo[1990].
References1.
S.
N.
Afriat.
Theconstructionofutilityfunctionsfromexpendituredata.
In-ternationalEconomicReview,8:67–77,1967.
2.
S.
N.
Afriat.
Eciencyestimationofproductionfunctions.
InternationalEco-nomicReview,13:568–598,1967.
3.
G.
Alon,M.
Beenstock,S.
T.
Hackman,U.
Passy,andA.
Shapiro.
Nonparamet-ricestimationofconcaveproductiontechnologiesbyentropicmethods.
JournalofAppliedEconometrics,22:795–816,2007.
4.
J.
Asmundsson,R.
L.
Rardin,andR.
Uzsoy.
Tractablenonlinearproductionplanningmodelsforsemiconductorwaferfabricationfacilities.
IEEETransac-tionsonSemiconductorManufacturing,19:95–111,2006.
5.
R.
D.
Banker.
Estimatingmostproductivescalesizeusingdataenvelopmentanalysis.
EuropeanJournalofOperationalResearch,17:35–44,1984.
6.
R.
D.
Banker,A.
Charnes,andW.
W.
Cooper.
Modelsforestimationoftechnicalandscaleinecienciesindataenvelopmentanalysis.
ManagementScience,30:1078–1092,1984.
7.
R.
D.
BankerandA.
Maindiratta.
Nonparametricanalysisoftechnicalandallocativeecienciesinproduction.
Econometrica,56:1315–1332,1988.
8.
R.
D.
BankerandR.
Morey.
Eciencyanalysisforexogenouslyxedinputsandoutputs.
OperationsResearch,34:512–521,1984.
9.
R.
D.
BankerandR.
Morey.
Theuseofcategoricalvariablesindataenvelop-mentanalysis.
ManagementScience,32:1613–1627,1986.
10.
J.
J.
BartholdiandS.
T.
Hackman.
WarehouseandDistributionScience.
2007.
Availableonlineathttp://www.
warehouse-science.
com.
11.
R.
G.
Bartle.
TheElementsofRealAnalysis,2ndEdition.
JohnWileyandSons,NewYork,NY,1976.
12.
M.
J.
Bazarra,H.
D.
Sherali,andC.
M.
Shetty.
NonlinearProgramming:TheoryandAlgorithms,2ndEdition.
JohnWileyandSons,NewYork,NY,1993.
13.
C.
Blackorby,D.
Primont,andR.
R.
Russell.
Duality,SeparabilityandFunc-tionalStructure:TheoryandEconomicApplications.
North-Holland,NewYork,NY,1978.
14.
K.
C.
Border.
FixedPointTheoremswithApplicationstoEconomicsandGameTheory.
CambridgeUniversityPress,Cambridge,GreatBritain,1985.
15.
S.
Bouhnik,B.
Golany,S.
T.
Hackman,U.
Passy,andD.
A.
Vlatsa.
Lowerboundrestrictionsonintensitiesindataenvelopmentanalysis.
JournalofProductivityAnalysis,16:241–261,2001.
512References16.
M.
Bunge.
MetascienticQueries.
CharlesC.
ThomasPublishers,Springeld,IL,1959.
17.
M.
Bunge.
Method,ModelandMatter.
D.
ReidelPublishingCo.
,Boston,MA,1973.
18.
D.
W.
Caves,L.
R.
Christensen,andW.
E.
Diewert.
Theeconomictheoryofindexnumbersofthemeasurementofinput,outputandproductivity.
Econo-metrica,50:1393–1414,1982.
19.
R.
G.
Chambers.
AppliedProductionAnalysis.
CambridgeUniversityPress,NewYork,NY,1988.
20.
A.
Charnes,W.
Cooper,A.
Y.
Lewin,andL.
M.
Seiford,editors.
DataEnvel-opmentAnalysis;Theory,MethodologyandApplications.
KluwerAcademicPublishers,Norwell,MA,1996.
21.
A.
CharnesandW.
W.
Cooper.
ManagementModelsandIndustrialApplica-tions.
JohnWileyandSons,NewYork,NY,1961.
22.
A.
Charnes,W.
W.
Cooper,andE.
Rhodes.
Measuringtheeciencyofdecisionmakingunits.
EuropeanJournalofOperationalResearch,2:429–444,1984.
23.
W.
F.
ChristopherandC.
G.
Thor,eds.
HandbookforProductivityMeasurementandImprovement.
ProductivityPress,Portland,Ore,1993.
24.
W.
W.
Cooper,L.
M.
Seiford,andK.
Tone.
DEA:AComprehensiveTextwithModels,Applications,ReferencesandDEA-SolverSoftware.
Springer-Verlag,NewYork,NY,2007.
25.
T.
J.
Coelli,D.
S.
PrasadaRao,C.
J.
O'Donnell,andG.
E.
Battese.
AnIntro-ductiontoEciencyandProductivity,secondedition.
Springer-Verlag,NewYork,NY,2005.
26.
G.
B.
Dantzig.
LinearProgrammingandItsExtensions.
PrincetonUniversityPress,Princeton,NJ,1963.
27.
F.
deMateo,T.
CoelliandC.
O'Donnell.
Optimalpathsandcostsofadjust-mentindynamicDEAmodels:withapplicationtochileandepartmentstores.
AnnalsofOperationsResearch,145:211–227,2006.
28.
G.
Debreu.
Thecoecientofresourceutilization.
Econometrica,19:273–292,1951.
29.
G.
Debreu.
TheoryofValue:AnAxiomaticAnalysisofEconomicEquilibrium.
CowlesFoundation,YaleUniversityPress,NewHaven,CT,1959.
30.
A.
G.
deKokandS.
C.
Graves.
HandbooksinOperationsResearchandManage-mentScienceonSupplyChainManagement:Design,CoordinationandOper-ation,Vol.
11.
Elsevier,2003.
31.
W.
E.
Diewert.
Dualityapproachestomicroeconomictheory.
InK.
J.
ArrowandM.
J.
Intrilligator,editors,HandbookofMathematicalEconomics,VolumeII,pp.
535–599.
North-Holland,NewYork,NY,1982.
32.
W.
E.
DiewertandC.
Montmarquette,editors.
PriceLevelMeasurement:Pro-ceedingsfromaConferenceSponsoredbyStatisticsCanada,Ottawa,1983.
Statistics,Canada.
33.
W.
E.
DiewertandA.
O.
Nakamura,editors.
EssaysinIndexNumberTheory,VolumeI.
North-Holland,Amsterdam,1993.
34.
W.
E.
DiewertandC.
Parkan.
Linearprogrammingtestsofregularitycondi-tionsforproductionfunctions.
InW.
Eichorn,R.
Heen,K.
Neumann,andR.
W.
Shephard,editors,QuantitativeStudiesonProductionandPrices,pp.
131–158.
Physica-Verlag,Vienna,1983.
35.
A.
K.
Dixit.
OptimizationinEconomicTheory.
OxfordUniversityPress,NewYork,NY,1976.
References51336.
R.
Fare.
FundamentalsofProductionTheory.
Springer-Verlag,NewYork,NY,1988.
37.
R.
FareandS.
Grosskopf.
IntertemporalProductionFrontiers:WithDynamicDEA.
KluwerAcademicPublishers,Norwell,MA,1996.
38.
R.
Fare,S.
Grosskopf,andC.
A.
K.
Lovell.
TheMeasurementofEencyofProduction.
Kluwer-NijhoPublishing,Boston,MA,1985.
39.
R.
Fare,S.
Grosskopf,andC.
A.
K.
Lovell.
ProductionFrontiers.
CambridgeUniversityPress,Cambridge,GreatBritain,1994.
40.
R.
Fare,S.
Grosskopf,M.
Norris,andZ.
Zhang.
Productivitygrowth,technicalprogress,andeciencychangeinindustrializedcountries.
AmericanEconomicReview,84:66–83,1994.
41.
R.
FareandC.
A.
K.
Lovell.
Measuringthetechnicaleciencyofproduction.
JournalofEconomicTheory,19:250–262,1978.
42.
M.
J.
Farrell.
Themeasurementofproductiveeciency.
JournaloftheRoyalStatisticalSocietySeriesA,General,120:253–281,1957.
43.
M.
J.
FarrellandM.
Fieldhouse.
Estimatingecientproductionfunctionsun-derincreasingreturnstoscale.
JournaloftheRoyalStatisticalSocietySeriesA,General,125:252–267,1962.
44.
Z.
First,S.
T.
Hackman,andU.
Passy.
Matrix-criteriaforthepseudop-convexityofaquadraticform.
LinearAlgebraandItsApplications,136:235–255,1990.
45.
Z.
First,S.
T.
Hackman,andU.
Passy.
Local-globalpropertiesofbi-functions.
JournalofOptimizationTheoryandApplications,73:279–297,1992.
46.
Z.
First,S.
T.
Hackman,andU.
Passy.
Eciencyestimationanddualitytheoryfornonconvextechnologies.
JournalofMathematicalEconomics,22:295–307,1993.
47.
E.
H.
Frazelle.
World-ClassWarehousingandMaterialsHandling.
McGraw-Hill,NewYork,NY,2001.
48.
E.
H.
FrazelleandS.
T.
Hackman.
Thewarehouseperformanceindex:Asingle-pointmetricforbenchmarkingwarehouseperformance.
TechnicalReportTR-93-14,GeorgiaInstituteofTechnology,1993.
49.
H.
O.
Fried,C.
A.
K.
Lovell,andS.
S.
Schmidt,editors.
TheMeasurementofProductiveEciency:TechniquesandApplications.
OxfordUniversityPress,Oxford,GreatBritain,1993.
50.
M.
FussandD.
McFadden,editors.
ProductionEconomics:ADualApproachtoTheoryandApplications,VolumesIandII.
North-Holland,Amsterdam,1978.
51.
I.
M.
GelfandandS.
V.
Fomin.
CalculusofVariations.
DoverPublications,NewYork,NY,1963.
52.
R.
Gibbons.
GameTheoryforAppliedEconomists.
PrincetonUniversityPress,Princeton,NJ,1992.
53.
B.
Golany,S.
T.
Hackman,andU.
Passy.
Aneciencymeasurementframeworkformulti-stageproductionsystems.
AnnalsofOperationsResearch,145:51–68,2006.
54.
S.
C.
Graves.
Atacticalplanningmodelforajobshop.
OperationsResearch,34:552–533,1986.
55.
S.
C.
Graves,A.
H.
G.
RinnoyKan,andP.
H.
Zipkin,editors.
HandbooksinOperationsResearchandManagementScienceonLogisticsofProductionandInventory,Vol.
4.
North-Holland,Amsterdam,1993.
514References56.
S.
Grosskopf.
Eciencyandproductivity.
InH.
O.
Fried,C.
A.
K.
Lovell,andS.
S.
Schmidt,editors,TheMeasurementofProductiveEciency:TechniquesandApplications,pp.
160–194.
OxfordUniversityPress,Oxford,GreatBritain,1993.
57.
S.
T.
Hackman.
Anew,geometricproofofShephard'sdualitytheorem.
JournalofEconomics,46:299–304,1986.
58.
S.
T.
Hackman.
Anaxiomaticframeworkofdynamicproduction.
JournalofProductivityAnalysis,1:309–324,1990.
59.
S.
T.
Hackman,E.
H.
Frazelle,P.
Grin,S.
O.
Grin,andD.
A.
Vlatsa.
Bench-markingwarehousinganddistributionoperations:Aninput-outputapproach.
JournalofProductivityAnalysis,16:79–100,2001.
60.
S.
T.
HackmanandR.
C.
Leachman.
Anaggregatemodelofproject-orientedproduction.
IEEETransactionsonSystems,ManandCybernetics,19:220–231,1989.
61.
S.
T.
HackmanandR.
C.
Leachman.
Ageneralframeworkformodelingpro-duction.
ManagementScience,35:478–495,1989.
62.
S.
T.
HackmanandU.
Passy.
Projectively-convexsetsandfunctions.
JournalofMathematicalEconomics,17:55–68,1988.
63.
S.
T.
HackmanandU.
Passy.
Maximizingalinearfractionalfunctionovertheecientfrontier.
JournalofOptimizationTheoryandApplications,113:83–103,2002.
64.
S.
T.
Hackman,L.
K.
Platzman,andU.
Passy.
Explicitrepresentationofatwo-dimensionalsectionofaproductionpossibilityset.
JournalofProductivityAnalysis,5:161–170,1994.
65.
S.
T.
HackmanandR.
R.
Russell.
Dualityandcontinuity.
JournalofProduc-tivityAnalysis,6:99–116,1995.
66.
G.
HanochandM.
Rothschild.
Testingtheassumptionsofproductiontheory:anonparametricapproach.
JournalofPoliticalEconomy,80:256–275,1972.
67.
P.
T.
Harker,ed.
TheServiceProductivityandQualityChallenge.
KluwerAcademicPublishers,Norwell,MA,1995.
68.
W.
Hildenbrand.
CoreandEquilibriaofaLargeEconomy.
PrincetonUniver-sityPress,Princeton,NJ,1974.
69.
G.
A.
JehleandP.
J.
Reny.
AdvancedMicroeconomicTheory,2ndEdition.
Addison-Wesley,NewYork,NY,2001.
70.
C.
H.
Jenkins.
CompleteGuidetoModernWarehouseManagement.
Prentice-Hall,NewYork,1990.
71.
J.
L.
Kelly.
GeneralTopology.
VanNostrand,NewYork,NY,1955.
72.
J.
Kendrick.
ImprovingCompanyProductivity:HandbookwithCaseStudies.
TheJohnsHopkinsUniversityPress,Baltimore,MD,1984.
73.
A.
N.
KolmogorovandS.
V.
Fomin.
IntroductoryRealAnalysis.
DoverPubli-cations,NewYork,NY,1970.
74.
A.
A.
Konus.
Theproblemofthetrueindexofthecostofliving.
Econometrica,7:10–29,1939.
75.
T.
C.
Koopmans.
Ananalysisofproductionasanecientcombinationofactivities.
InT.
C.
Koopmans,editor,ActivityAnalysisofProductionandAllocation.
CowlesCommissionforResearchinEconomics,MonographNo.
13,NewYork,NY,1951.
76.
W.
W.
Leontief.
TheStructureoftheAmericanEconomy.
OxfordUniversityPress,NewYork,NY,1953.
References51577.
S.
Malmquist.
Indexnumbersandindierencesurfaces.
TrabajosdeEstatistica,4:209–242,1953.
78.
A.
Mas-Colel,M.
D.
Whinston,andJ.
R.
Green.
MicroeconomicTheory.
OxfordUniversityPress,Oxford,GreatBritain,1995.
79.
L.
F.
McGinnis,A.
Johnson,andM.
Villareal.
BenchmarkingWarehousePer-formanceStudy.
W.
M.
KeckVirtualFactoryLab,SchoolofIndustrialandSystemsEngineering,GeorgiaInstituteofTechnology,Atlanta,GA,30332-0205.
80.
D.
E.
Mulcahy.
WarehouseDistributionandOperationsHandbook.
McGraw-Hill,NewYork,NY,1993.
81.
J.
Pahl,S.
Vos,andD.
L.
Woodru.
Productionplanningwithloaddependentleadtimes:anupdateofresearch.
AnnalsofOperationsResearch,153:297–345,2007.
82.
N.
C.
Petersen.
Dataenvelopmentanalysisonarelaxedsetofassumptions.
ManagementSciences,36:305–314,1990.
83.
A.
Rapoport.
N-PersonGameTheory.
UniversityofMichiganPress,AnnArbor,MI,1970.
84.
M.
J.
Real,J.
C.
Ammons,andD.
J.
Newton.
Robustreverseproductionsystemdesignforcarpetrecycling.
IIETransactions,36:767–776,2004.
85.
S.
A.
Reveliotis.
Real-TimeManagementofResourceAllocationSystems:ADiscrete-EventSystemsApproach.
InternationalSeriesinOperationsResearchandManagementScience.
Springer,NewYork,NY,2004.
86.
G.
Riano.
TransientBehaviorofStochasticNetworks:ApplicationstoProduc-tionPlanningwithLoad-DependentLeadTimes.
PhDthesis,IndustrialandSystemsEngineering,GeorgiaInstituteofTechnology,Atlanta,GA30332-0205,2002.
87.
G.
Riano,R.
F.
Serfozo,andS.
T.
Hackman.
Transientbehaviorofqueuingnetworks.
Workingpaper,2007.
88.
R.
T.
Rockafellar.
ConvexAnalysis.
PrincetonUniversityPress,Princeton,NJ,1970.
89.
S.
Ross.
IntroductiontoProbabilityModels.
AcademicPress,NewYork,NY,1985.
90.
H.
L.
Royden.
RealAnalysis,2ndEdition.
MacMillanPublishingCo.
,NewYork,NY,1985.
91.
R.
R.
Russell.
Measuresoftechnicaleciency.
JournalofEconomicTheory,35:109–126,1985.
92.
M.
Schefczyk.
Industialbenchmarking:Acase-studyofperformanceanalysistechniques.
InternationalJournalofProductionEconomics,32:1–11,1993.
93.
R.
SchmalenseeandR.
Willig,editors.
HandbookofIndustialOrganization,VolumeI.
North-Holland,Amsterdam,1989.
94.
J.
K.
Sengupta.
EciencyAnalysisByProductionFrontiers:TheNonparamet-ricApproach.
KluwerAcademicPublishers,Norwell,MA,1989.
95.
R.
F.
Serfozo.
Pointprocesses.
InD.
P.
HeymanandM.
J.
Sobel,editors,StochasticModels,pp.
1–93.
ElsevierScience/North-Holland,Amsterdam,1990.
96.
R.
W.
Shephard.
CostandProductionFunctions.
PrincetonUniversityPress,Princeton,NJ,1953.
97.
R.
W.
Shephard.
TheoryofCostandProductionFunctions.
PrincetonUniver-sityPress,Princeton,NJ,1970.
516References98.
R.
W.
Shephard,R.
Al-Ayat,andR.
C.
Leachman.
Shipbuidingproductionfunction:anexampleofadynamicproductionfunction.
InQuantitativeWirtschaftsforschungFestschriftVolume(WilhelmKrelle),H.
Alback(ed.
),J.
B.
C.
Mohr,Tubingen,1977.
99.
R.
W.
ShephardandR.
Fare.
DynamicTheoryofProductionCorrespondences.
Oelgeschlager,GunnandHain,Cambridge,MA,1980.
100.
O.
Shy.
IndustrialOrganization.
M.
I.
T.
Press,Cambridge,MA,1995.
101.
D.
Simchi-Levi,P.
Kaminsky,andE.
Simchi-Levi.
DesigningandManagingtheSupplyChain,SecondEdition.
McGraw-Hill,Boston,MA,2002.
102.
R.
Solow.
Technicalchangeandtheaggregateproductionfunction.
ReviewofEconomicandStatistics,39:312–320,1985.
103.
R.
Starr.
GeneralEquilibriumTheory:AnIntroduction.
CambridgeUniversityPress,Cambridge,GreatBritain,1997.
104.
G.
J.
Stigler.
TheXistenceofX-eciency.
AmericanEconomicReview,66:213–216,1976.
105.
J.
Tirole.
TheTheoryofIndustrialOrganization.
M.
I.
T.
Press,Cambridge,MA,1988.
106.
J.
A.
TompinsandJ.
Smith.
WarehouseManagementHandbook,secondedition.
TompkinsPress,1998.
107.
L.
Tornqvist.
Thebankofnland'sconsumptionpriceindex.
BankofFinlandMonthlyBulletin,10:1–8,1936.
108.
H.
Tulkens.
OnFDHeciencyanalysis:Somemethodologicalissuesandap-plicationstoretailbanking,courtsandurbantransit.
JournalofProductivityAnalysis,4:183–210,1993.
109.
H.
R.
Varian.
Thenonparametricapproachtoproductionanalysis.
Economet-rica,52:579–597,1984.
110.
H.
R.
Varian.
MicroeconomicAnalysis,3rdEdition.
W.
W.
NortonandCo.
,NewYork,NY,1992.
111.
D.
A.
Vlatsa.
DataEnvelopmentAnalysiswithIntensityRestriction.
PhDthesis,IndustrialandSystemsEngineering,GeorgiaInstituteofTechnology,Atlanta,GA30332-0205,1995.
112.
S.
VossandD.
L.
Woodru.
IntroductiontoComputationalOptimizationMod-elsforProductionPlanninginaSupplyChain,SecondEdition.
Springer-Verlag,Berlin,2006.
113.
L.
A.
WolseyandG.
L.
Nemhauser.
IntegerandCombinatorialOptimization.
Wiley-Interscience,NewYork,NY,1999.
Indexactivityintensity56aggregateoperatingintensity,denition359allocativeeciency153bi-convextechnology41budgetfeasible97budgetset97Cobb-Douglasproductionfunction20expenditureshares75ConsistentPricingPrinciple204constantelasticity-of-substitution(CES)productionfunction20constantreturns-to-scalegeneralLeontieftechnology56simpleLeontieftechnology54constantreturns-to-scaletechnology43convextechnology41convexhullofthedataset41convextechnology41correspondenceinputpossibility36outputpossibility36costeciencydecomposition153denition152costfunction71Cobb-Douglas74factorability85generalLeontief78homothetic84HRtechnology79properties71simpleLeontief78VRSandCRSEcientFrontiers80costorexpenditureshare74DataEnvelopmentAnalysis61ConstantReturns-to-Scale(CRS)technology62multiplierformulation,CRS155VariableReturns-to-Scale(VRS)technology62withlowerbounds131Decision-MakingUnit(DMU)63derivedproductionfunction44denition40fromthetwo-dimensionalprojec-tionassociatedwiththeVRStechnology168properties40disposabilityfree37inputfree37outputfree37weak38weakinput37weakoutput37disposablehullconvex,free43free42inputfree42outputfree42duality518Indexapplicationtohomothetictechnolo-gies117betweenaprojectively-concaveandmulti-dimensionalindirectproductionfunctions141betweenthecostanddistancefunctions114betweenthecostandindirectproductionfunctions99betweentheproductionandcostfunctions80betweentheproductionandindirectproductionfunctions100dynamicproductionfunction11,295distribution-based310index-based299instantaneous298linear311two-pointboundaryapproximation348eciencyinput4output3eciencychangeinput248output249eciencyweightingfunction151EcientFrontierofatechnology38ofaninputpossibilityset38ofanoutputpossibilityset38elasticitydenition24ofcost76ofoutput25ofscale26ofsubstitution28elasticityofcost76elasticityofoutputsimpleLeontief54elasticityofscalesimpleLeontief54equilibriumdenition272event-basedow10,298First-In,First-Outservicediscipline322,340xedproportionsdynamicmodel300,394xed-coecientstechnology53owline,description361freedisposability37freedisposablehull42functioncost71production2,19generalizedquadraticproductionfunction20Hanoch-Rothschildmodeloftechnology60homotheticproductionfunction29indexhedonistic224indirectproductionfunctiondenition97fortheCobb-Douglastechnology98properties99inputexogenouslyxed66non-discretionary66inputcurveshape296inputdistancefunctiondenition109properties111inputeciency4linearmeasureof150radialmeasureof149Russellmeasureof4weightedmeasureof151inputfreedisposability,denition37inputfreedisposablehull42inputpossibilitycorrespondence36inputpossibilitysetdenition36EcientFrontier38family36innerapproximation82outerapproximation82input-outputdataset36instantaneousgrowthrate242intensity300inventorybalanceequationsIndex519workqueue340isocostline72jointinput-outputeciency153jointinput-outputspace36Lagrangianfunction74Cobb-Douglascostfunction75lawofdiminishingreturns22leadtimedensityconstant,denition312event-based,denition311piecewiseconstant,denition312rate-based,denition311linearprogramfortestingoutput84generalLeontieftechnology56Little'squeuinglaw340marginalproduct,denition23materialbalance,denition393mostproductivescalesize172nested,denition37normalizedindirectproductionfunction98output-costset79outputdistancefunctiondenition110properties112outputeciency3radialmeasureof149,150weightedmeasureof151outputfreedisposability,denition37outputfreedisposablehull42outputpossibilitycorrespondence36outputpossibilityset36EcientFrontier38family36ParetoecientFrontiermulti-stageeciencyanalysis197partialeciencyscores133perioddenition324pipelineinventories399pivotelement179priceindexFisherideal231Konuscost-of-living227Laspeyres229Laspeyres-Konus228Paasche229Paasche-Konus228Tornqvist232productionfunctionaggregate126Cobb-Douglas20constantelasticity-of-substitution(CES)20denition2,19derivedfromawell-behavedtechnology40xed-coecients54generalLeontief56generalizedquadratic20homothetic29indirect97inputpossibilitysetof19multi-dimensionalindirect129normalizedindirect98quasiconcave60translog20upperlevelsetof19uppersemicontinuous60productivitychangeinput248output249project-orientedproductionsystems,description356projectively-convex(P-convex)set136projectively-convex(projectively-concave)function138quadrant139radialinputeciency113radialoutputeciency113rateoftechnicalsubstitutionCobb-Douglasproductionfunction23constantelasticityofsubstitution(CES)productionfunction23denition23rate-basedow10,298ratiotest180rectanglejoiningtwopoints136520Indexreferencerm154relativearearatio349returns-to-scaleconstant26,172decreasing26,172increasing26,172scaleeciencyinput-based152output-based152Shephard'sLemma78simpleLeontieftechnology53strictprecedence,amongactivities357tableau177technicalchangeinput247output249technicalcoecientvector53technicalcoecients300technologybi-convex41constantreturns-to-scale43constantreturns-to-scalehull44convex41convexconstantreturns-to-scalehull44CRSDEAmodel62DataEnvelopmentAnalysis61denition36EcientFrontier38xed-charge131xed-coecients53Hanoch-Rothschild(HR)60innerapproximation82outerapproximation82piecewiselinear59projectively-convex41sections41set36simpleLeontief53VRS-DEAmodel62well-behaved38technologyset36timegriddenition324standard,denition324uniform,denition324time-divisibility39time-of-completionfunction320time-reversibility327transform,denition29transformsdistribution-basedprocesses310translogproductionfunction20two-dimensionalprojection167derivedproductionfunction168EcientFrontier168utilityfunctionmulti-dimensionalindirect129weakdisposability,denition38weakinputdisposability,denition37weakoutputdisposability,denition37weaklynested,denition37well-behavedtechnologyaxiomsof38workqueue338,414