Rigorous error bounds for finite dimensional linear programming problems [Elektronische Ressource] / von Christian Keil

Rigorous Error Bounds forFinite Dimensional Linear Programming ProblemsVom Promotionsausschuss derTechnischen Universität Hamburg–Harburgzur Erlangung des akademischen GradesDoktor Ingenieur (Dr. Ing)genehmigte DissertationvonChristian KeilausHamburg20091. Gutachter: Prof. Dr. Siegfried M. Rump2. Prof. Dr. Dr. h.c. Frerich J. KeilTag der mündlichen Prüfung: 17. Dezember 2008Rigorous Error Boundsfor Finite DimensionalLinear ProgrammingProblemsCHRISTIAN KEIL© 2009 Christian Keilerschienen bei: Books on Demand GmbH, NorderstedtISBN 9783837093353ContentsContents vAcknowledgements viiIntroduction ix1 Theory 11.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Rounding errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3 Interval arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . 21.4 Linear programming . . . . . . . . . . . . . . . . . . . . . . . . . 4Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10Condition numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 111.5 Rigorous bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . 13Certificates of infeasibility . . . . . . . . . . . . . . . . . . . . . . 241.6 Generalizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25Mixed integer linear programming . . . . . . . . . . . . . . . . . 26Conic programming . . .