Lecture Notes in Mathematics 2062 Editors: J.-M.Morel,Cachan B.Teissier,Paris Forfurthervolumes: http://www.springer.com/series/304 FondazioneC.I.M.E.,Firenze C.I.M.E. stands for Centro Internazionale Matematico Estivo, that is, International MathematicalSummerCentre.Conceivedintheearlyfifties,itwasbornin1954inFlorence, Italy,andwelcomedbytheworldmathematical community:itcontinues successfully,year foryear,tothisday. Many mathematicians from all over the world have been involved in a way oranother in C.I.M.E.’sactivitiesovertheyears.ThemainpurposeandmodeoffunctioningoftheCentre maybesummarisedasfollows:everyyear,duringthesummer,sessionsondifferentthemes from pure and applied mathematics are offered byapplication to mathematicians from all countries. ASessionis generally basedonthree orfourmaincourses given byspecialists ofinternationalrenown,plusacertainnumberofseminars,andisheldinanattractiverural locationinItaly. TheaimofaC.I.M.E.sessionistobringtotheattentionofyoungerresearcherstheorigins, development, and perspectives of some very active branch of mathematical research. The topicsofthecoursesaregenerallyofinternationalresonance.Thefullimmersionatmosphere ofthecoursesandthedailyexchangeamongparticipantsarethusaninitiationtointernational collaborationinmathematicalresearch. C.I.M.E.Director C.I.M.E.Secretary PietroZECCA ElviraMASCOLO DipartimentodiEnergetica“S.Stecco” DipartimentodiMatematica“U.Dini” Universita`diFirenze Universita`diFirenze ViaS.Marta,3 vialeG.B.Morgagni67/A 50139Florence 50134Florence Italy Italy e-mail:zecca@unifi.it e-mail:[email protected]fi.it FormoreinformationseeCIME’shomepage:http://www.cime.unifi.it CIMEactivityiscarriedoutwiththecollaborationandfinancialsupportof: -INdAM(IstitutoNazionalediAltaMatematica) -MIUR(Ministerodell’Universita’edellaRicerca) Luigi Ambrosio Alberto Bressan (cid:2) Dirk Helbing Axel Klar Enrique Zuazua (cid:2) (cid:2) Modelling and Optimisation of Flows on Networks Cetraro, Italy 2009 Editors: Benedetto Piccoli Michel Rascle 123 LuigiAmbrosio AxelKlar ScuolaNormaleSuperiore TechnischeUniversita¨t DepartmentofMathematics Kaiserslautern Pisa,Italy FachbereichMathematik Kaiserslautern,Germany AlbertoBressan PennStateUniversity EnriqueZuazua StateCollege BCAM BasqueCenterfor DepartmentofMathematics AppliedMathema UniversityPark Depto.Matematicas PA,USA Bilbao,Spain DirkHelbing ETHZu¨rich SwissFederalInstituteofTechnology Zurich,Switzerland ISBN978-3-642-32159-7 ISBN978-3-642-32160-3(eBook) DOI10.1007/978-3-642-32160-3 SpringerHeidelbergNewYorkDordrechtLondon LectureNotesinMathematicsISSNprintedition:0075-8434 ISSNelectronicedition:1617-9692 LibraryofCongressControlNumber:2012949580 MathematicsSubjectClassification(2010):35R02,35L65,90B20 Thecontributionsco-authoredorauthoredbyHelbinghavepreviouslybeenpublishedin TheEuropeanPhysicalJournalB69(4),539–548,DOI:10.1140/epjb/e2009-00192-5(2009), (cid:2)c EDPSciences,SocietaItalianadiFisica,Springer-Verlag2009,reproductionwithkindpermissionof TheEuropeanPhysicalJournal(EPJ) TheEuropeanPhysicalJournalB69(4),549–562,DOI:10.1140/epjb/e2009-00182-7(2009), (cid:2)c EDPSciences,SocietaItalianadiFisica,Springer-Verlag2009,reproductionwithkindpermissionof TheEuropeanPhysicalJournal(EPJ) TheEuropeanPhysicalJournalB69(4),583–598,DOI:10.1140/epjb/e2009-00140-5(2009), (cid:2)c EDPSciences,SocietaItalianadiFisica,Springer-Verlag2009,reproductionwithkindpermissionof TheEuropeanPhysicalJournal(EPJ) Networks and Heterogeneous Media 2(2), 193–210 (2007), (cid:2)c American Institute of Mathematical Sciences,ReproductionwithkindpermissionofNetworksandHeterogeneousMedia(NHM). TheEuropeanPhysicalJournalB70(2),257–274,DOI:10.1140/epjb/e2009-00213-5 (2009),(cid:2)c EDP Sciences, Societa Italiana di Fisica, Springer-Verlag 2009, reproduction with kindpermission ofThe EuropeanPhysicalJournal(EPJ) (cid:2)c Springer-VerlagBerlinHeidelberg2013 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerptsinconnection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’slocation,initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer. PermissionsforusemaybeobtainedthroughRightsLinkattheCopyrightClearanceCenter.Violations areliabletoprosecutionundertherespectiveCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. While the advice and information in this book are believed to be true and accurate at the date of publication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityfor anyerrorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,with respecttothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) • Preface ThepresentvolumecollectsnotesfromlecturesdeliveredfortheCIMEcourseon Modellingandoptimisationofflowsonnetworks,heldinCetrarointhesummerof 2009. In recent years modelling of flows on networks has been the subject of many investigationsleadingtoanincreasingnumberofresearchpapers.Moreover,awide set of possible applications, such as vehicular traffic, blood flow, supply chains andothers,hasdirectedtheattentionofmathematicianstowardsresearchdomains usuallypopulatedbyengineers,physicistsorresearcherswithotherexpertise. The aim of the CIME school was to gather summer courses which could give a wide view of modelling, analysis, numerics and control for dynamic flows on networks. Encompassing all application domains (including irrigation channels, datanetworks,airtrafficmanagementandothers)wasimpossible,thuswefocused on mathematical approaches, which are feasible for a number of applications, and a restricted set of specific applications, in particular vehicular traffic and supplychains.Theattemptoffindingacommonground,fordifferentmathematical techniquestotreatflowsonnetworks,wasalreadysuccessfulinanumberofcases both at the levelof research projects (such as the Italian nationalINDAM project 2005)andeditorialinitiatives(thefoundationin2006ofanewappliedmathjournal entitledNetworksandHeterogeneousMedia). TheschooltookplaceinCetraro,Italy,onJune15–192009.Thecoursesubjects werethefollowing: 1. Introductiontoconservationlaws:AlbertoBressan(PennState) 2. Optimaltransportation:LuigiAmbrosio(SNS,Pisa) 3. Pedestrianmotionsandvehiculartraffic:DirkHelbing(ETH) 4. Controlandstabilizationofwaveson1-Dnetworks:EnriqueZuazua(BCAM) 5. Modelling and optimization of scalar flows on networks: Axel Klar (Kaiserlautern) 6. Fluid dynamic and kinetic models for supply chains: Christian Ringhofer (ArizonaState) vii viii Preface RationaleBehindtheChoiceof Courses for CIME School Taking into account the above-mentioned scientific background, courses for the CIME school were chosen in order to give a wide view over main mathematical techniquesandtheirapplicationsinspecificcontexts. 1. AnalysisandcontroloflinearPDEsonnetworks 2. AnalysisofnonlinearPDEsonnetworks 3. Optimizationtechniquesforcomplexnetworks 4. NumericalmethodsforPDEsonnetworks TocoverthefirsttopicandlastoneforthelinearPDEaspect,wedecidedtofocus onwaveequationsonnetworksofone-dimensionalstructuresand,inparticular,on the use of spectral methods. Therefore, the choice was made to contact Enrique Zuazua,DirectoroftheBasqueCenterforAppliedMathematicsandaworldleader on the subject. Prof. Zuazua also authoreda volume on the subject(SMAI series, Springer-Verlag,2006). In many applications it is natural to use conservation laws to model flows on networks, thus for the second course we contacted Alberto Bressan of PennState University, who was one of the major contributors of the theory of systems of conservation laws in last 20 years and author of a well-known monograph (CambridgeUniversityPress,2000). The fourth topic for the nonlinear aspect was covered in courses dealing also with applications, and illustrated below, of Klar and Ringhofer. Finally, for the third topic, we individuated optimal transportation as one of the most suited mathematical framework, and thus decided to contact Luigi Ambrosio of Scuola NormaleSuperioreofPisa,whoauthoredvariousrecentfundamentalpapersinthe subject and a monograph on the related topics of gradient flows in metric spaces (Birkauser,2008). For what concerns applications related to our main theme, Dirk Helbing of ETH of Zurich accepted to deliver a course covering both pedestrian dynamics and vehicular traffic. Helbing was one of the pioneers in providing advanced mathematicalmodellingforpedestrianswithcelebratedpapersinNature. Then we focused on supply chain dynamics and thus contacted Christian RinghoferofArizonaStateUniversity,whocoauthoredapioneeringpaperin2006 providing the first model of supply chains using PDEs. The course of Ringhofer dealtalsowithkineticapproaches. Finally, Axel Klar of Kaiserlautern TechnicalUniversity provideda course not onlydealingwithgeneralmodellingandnumericsofconservationlawsonnetworks butalsotreatingcoupledsystemsofODEsandPDEswithexamplesfromvehicular traffic,supplychainsandsewersystems. ThepresentvolumecontainslecturenotesfromthefirstfivecoursesoftheCIME school.Wewishreadersapleasantandfruitfulreading. Camden,NJ BenedettoPiccoli Nice,France MichelRascle Contents AUser’sGuidetoOptimalTransport ......................................... 1 LuigiAmbrosioandNicolaGigli 1 Introduction........................................................ 1 2 TheOptimalTransportProblem .................................. 3 2.1 MongeandKantorovichFormulationsofthe OptimalTransportProblem................................. 3 2.2 NecessaryandSufficientOptimalityConditions .......... 7 2.3 TheDualProblem........................................... 13 2.4 ExistenceofOptimalMaps................................. 16 2.5 BibliographicalNotes....................................... 26 3 TheWassersteinDistanceW ..................................... 28 2 3.1 X PolishSpace .............................................. 29 3.2 X GeodesicSpace........................................... 37 3.3 X RiemannianManifold.................................... 47 3.4 BibliographicalNotes....................................... 58 4 GradientFlows..................................................... 59 4.1 HilbertianTheoryofGradientFlows....................... 59 4.2 TheTheoryofGradientFlowsinaMetricSetting ........ 61 4.3 ApplicationstotheWassersteinCase ...................... 81 4.4 BibliographicalNotes....................................... 92 5 GeometricandFunctionalInequalities........................... 93 5.1 Brunn–MinkowskiInequality............................... 94 5.2 IsoperimetricInequality..................................... 94 5.3 SobolevInequality........................................... 95 5.4 BibliographicalNotes....................................... 96 6 VariantsoftheWassersteinDistance ............................. 97 6.1 BranchedOptimalTransportation.......................... 97 6.2 DifferentActionFunctional................................. 99 6.3 AnExtensiontoMeasureswithUnequalMass............ 100 6.4 BibliographicalNotes....................................... 102 ix x Contents 7 MoreontheStructureof.P .M/;W /.......................... 103 2 2 7.1 “Duality”BetweentheWassersteinandthe ArnoldManifolds............................................ 103 7.2 OntheNotionofTangentSpace............................ 106 7.3 SecondOrderCalculus...................................... 107 7.4 BibliographicalNotes....................................... 130 8 RicciCurvatureBounds........................................... 131 8.1 ConvergenceofMetricMeasureSpaces ................... 134 8.2 WeakRicciCurvatureBounds:Definitionand Properties .................................................... 137 8.3 BibliographicalNotes....................................... 150 References......................................................................... 152 HyperbolicConservationLaws:AnIllustratedTutorial .................... 157 AlbertoBressan 1 ConservationLaws ................................................ 158 1.1 TheScalarConservationLaw............................... 158 1.2 StrictlyHyperbolicSystems ................................ 160 1.3 LinearSystems .............................................. 161 1.4 NonlinearEffects............................................ 163 1.5 LossofRegularity........................................... 164 1.6 WaveInteractions............................................ 166 2 WeakSolutions .................................................... 167 2.1 Rankine–HugoniotConditions.............................. 168 2.2 ConstructionofShockCurves.............................. 172 2.3 AdmissibilityConditions.................................... 173 3 TheRiemannProblem............................................. 179 3.1 SomeExamples.............................................. 179 3.2 AClassofHyperbolicSystems............................. 182 3.3 ElementaryWaves........................................... 184 3.4 GeneralSolutionoftheRiemannProblem................. 187 3.5 TheRiemannProblemforthep-System ................... 190 3.6 ErrorandInteractionEstimates............................. 194 4 GlobalSolutionstotheCauchyProblem......................... 196 4.1 FrontTrackingApproximations............................ 197 4.2 BoundsontheTotalVariation .............................. 200 4.3 ConvergencetoaLimitSolution ........................... 203 5 TheGlimmScheme ............................................... 205 6 ContinuousDependenceontheInitialData...................... 210 6.1 UniqueSolutionstotheScalarConservationLaw......... 211 6.2 LinearHyperbolicSystems ................................. 212 6.3 NonlinearSystems........................................... 213 7 UniquenessofSolutions........................................... 216 7.1 AnErrorEstimateforFrontTrackingApproximations... 217 7.2 CharacterizationofSemigroupTrajectories................ 218 7.3 UniquenessTheorems....................................... 221