{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T09:56:43Z","timestamp":1791021403547,"version":"4.1.0"},"reference-count":49,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Numer. Anal."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>A wide variety of problems in global optimization, combinatorial optimization, as well as systems and control theory can be solved by using linear and semidefinite programming. Sometimes, due to the use of floating point arithmetic in combination with ill-conditioning and degeneracy, erroneous results may be produced. The purpose of this article is to show how rigorous error bounds for the optimal value can be computed by carefully postprocessing the output of a linear or semidefinite programming solver. It turns out that in many cases the computational costs for postprocessing are small compared to the effort required by the solver. Numerical results are presented including problems from the SDPLIB and the NETLIB LP library; these libraries contain many ill-conditioned and real-life problems.<\/jats:p>","DOI":"10.1137\/050622870","type":"journal-article","created":{"date-parts":[[2007,12,20]],"date-time":"2007-12-20T18:32:01Z","timestamp":1198175521000},"page":"180-200","source":"Crossref","is-referenced-by-count":37,"title":["Rigorous Error Bounds for the Optimal Value in Semidefinite Programming"],"prefix":"10.1137","volume":"46","author":[{"given":"Christian","family":"Jansson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Denis","family":"Chaykin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Keil","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2007,12,20]]},"reference":[{"key":"R1","unstructured":"G. Alefeld and J. Herzberger,\n                      Introduction to Interval Computations\n                      , Academic Press, New York, 1983."},{"key":"R2","unstructured":"D. L. Applegate, W. Cook, S. Dash, and D. G. Espinoza,\n                      QSopt_ex\n                      , http:\/\/www.dii.uchile. cl\/~daespino\/QSoptExact_doc\/main.html."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1239(199611)6:9\/10<895::AID-RNC258>3.0.CO;2-V"},{"key":"R4","unstructured":"M. Berz et al.\n                      COSY Infinity\n                      , http:\/\/www.bt.pa.msu.edu\/index_files\/cosy.htm."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805769"},{"key":"R6","unstructured":"D. Chaykin,\n                      A\n                      C++\n                      implementation of rigorous error bounds in semidefinite programming\n                      , in progress."},{"key":"R7","unstructured":"C. A. Floudas,\n                      Deterministic Global Optimization\u2014Theory, Methods and Applications\n                      , Nonconvex Optim. Appl. 37, Kluwer Academic Publishers, Dordrecht, The Netherlands, Boston, London, 2000."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"R. Fourer and D. M. Gay,\n                      Experience with a primal presolve algorithm\n                      , in Large Scale Optimization: State of the Art, W. W. Hager, D. W. Hearn, and P. M. Pardalos, eds., Kluwer Academic Publishers, Norwell, MA, Dordrecht, The Netherlands, 1994, pp. 135\u2013154.","DOI":"10.1007\/978-1-4613-3632-7_8"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0035-y"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"K. Fujisawa, Y. Futakata, M. Kojima, K. Nakata, and M. Yamashita,\n                      SDPA-M (SemiDefinite Programming Algorithm in MATLAB) User's Manual\u2014Version\n                      2.00, Research report B-359, Tokyo Institute of Technology, Tokyo, Japan, 2000.","DOI":"10.1007\/978-1-4757-3216-0_11"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/1132973.1132980"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"R13","unstructured":"E. R. Hansen,\n                      Global Optimization Using Interval Analysis\n                      , Marcel Dekker, New York, 1992."},{"key":"R14","unstructured":"C. Jansson,\n                      VSDP: Verified SemiDefinite Programming, User's Guide\n                      , Beta Version 0.1, to appear."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"C. Jansson,\n                      A self-validating method for solving linear programming problems with interval input data\n                      , in Scientific Computation with Automatic Result Verification, Comput. Suppl. 6, Springer-Verlag, Vienna, 1988, pp. 33\u201345.","DOI":"10.1007\/978-3-7091-6957-5_4"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOGO.0000006720.68398.8c"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623402416839"},{"key":"R18","unstructured":"R. B. Kearfott,\n                      GlobSol\n                      , http:\/\/interval.louisiana.edu."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"R. B. Kearfott,\n                      Rigorous Global Search: Continuous Problems\n                      , Kluwer Academic Publishers, Dordrecht, The Netherlands, 1996.","DOI":"10.1007\/978-1-4757-2495-0"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02680551"},{"key":"R21","unstructured":"C. Keil,\n                      Lurupa\u2014Rigorous Error Bounds in Linear Programming\n                      , in Algebraic and Numerical Algorithms and Computer-Assisted Proofs, B. Buchberger, S. Oishi, M. Plum, and S. Rump, eds., no. 05391 in Dagstuhl Seminar Proceedings, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, 2006, http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2006\/445."},{"key":"R22","unstructured":"C. Keil,\n                      Verified linear programming\u2014a comparison\n                      , Reliable Computing, submitted."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/s11155-006-9004-7"},{"key":"R24","unstructured":"M. Kiyomi,\n                      exlp\n                      , http:\/\/members.jcom.home.ne.jp\/masashi777\/exlp.html."},{"key":"R25","unstructured":"O. Kn\u00fcppel,\n                      PROFIL\/BIAS and extensions, Version\n                      2.0, Technical report, Inst. f. Informatik III, Technische Universit\u00e4t Hamburg-Harburg, 1998."},{"key":"R26","unstructured":"T. Koch,\n                      perPlex\n                      , urlhttp:\/\/www.zib.de\/koch\/perplex."},{"key":"R27","doi-asserted-by":"crossref","unstructured":"R. Krawczyk,\n                      Fehlerabsch\u00e4tzung bei linearer Optimierung\n                      , in Interval Mathematics, K. Nickel, ed., Lecture Notes in Comput. Sci. 29, Springer-Verlag, Berlin, 1975, pp. 215\u2013222.","DOI":"10.1007\/3-540-07170-9_20"},{"key":"R28","unstructured":"Y. Lebbah,\n                      ICOS (Interval COnstraints Solver)\n                      , http:\/\/www.essi.fr\/~lebbah\/icos\/index.html."},{"key":"R29","unstructured":"MATLAB User's Guide, Version\n                      6, The MathWorks Inc., Natick, MA, 2000."},{"key":"R30","unstructured":"G. Mayer,\n                      Result verification for eigenvectors and eigenvalues\n                      , in Topics in Validated Computations, Proceedings of the IMACS-GAMM International Workshop, Oldenburg, Germany, Stud. Comput. Math. 5, J. Herzberger, ed., Elsevier, Amsterdam, 1994, pp. 209\u2013276."},{"key":"R31","doi-asserted-by":"crossref","unstructured":"R. E. Moore,\n                      Methods and Applications of Interval Analysis\n                      , SIAM, Philadelphia, 1979.","DOI":"10.1137\/1.9781611970906"},{"key":"R32","unstructured":"A. Nemirovski,\n                      Lectures on Modern Convex Optimization\n                      , http:\/\/www2.isye.gatech.edu\/ $\\!_{^{\\sim}}\\!$nemirovs\/Lect_ModConvOpt.pdf, 2003."},{"key":"R33","unstructured":"NETLIB linear programming library\n                      , http:\/\/www.netlib.org\/lp."},{"key":"R34","unstructured":"A. Neumaier,\n                      Interval methods for systems of equations\n                      , Encyclopedia Math. Appl., Cambridge University Press, Cambridge, UK, 1990."},{"key":"R35","doi-asserted-by":"crossref","unstructured":"A. Neumaier,\n                      Introduction to Numerical Analysis\n                      , Cambridge University Press, Cambridge, UK, 2001.","DOI":"10.1017\/CBO9780511612916"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492904000194"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0433-3"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623402401804"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623495288350"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585941"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1145\/363744.363779"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"S. M. Rump,\n                      Validated solution of large linear systems\n                      , in Validation Numerics: Theory and Applications, Comput. Suppl. 9, R. Albrecht, G. Alefeld, and H. Stetter, eds., Springer-Verlag, Berlin, 1993, pp. 191\u2013212.","DOI":"10.1007\/978-3-7091-6918-6_15"},{"key":"R43","unstructured":"S. M. Rump,\n                      Verification methods for dense and sparse systems of equations\n                      , in Topics in Validated Computations\u2014Studies in Computational Mathematics, J. Herzberger, ed., Elsevier, Amsterdam, 1994, pp. 63\u2013136."},{"key":"R44","unstructured":"S. M. Rump,\n                      INTLAB\u2014Interval Laboratory, a MATLAB Toolbox for Verified Computations, Version\n                      5.1, 2005."},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1109\/37.408458"},{"key":"R46","unstructured":"M. J. Todd,\n                      Detecting infeasibility in infeasible-interior-point methods for optimization\n                      , in Foundations of Computational Mathematics: Minneapolis, 2002, London Math. Soc. Lecture Note Ser. 312, F. Cucker, R. DeVore, P. Olver, and E. S\u00fcli, eds., Cambridge University Press, Cambridge, UK, 2004, pp. 157\u2013192."},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0347-5"},{"key":"R48","doi-asserted-by":"crossref","unstructured":"P. Van Hentenryck, P. Michel, and Y. Deville,\n                      Numerica: A Modelling Language for Global Optimization\n                      , MIT Press, Cambridge, MA, 1997.","DOI":"10.7551\/mitpress\/5073.001.0001"},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1137\/1038003"}],"container-title":["SIAM Journal on Numerical Analysis"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/050622870","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:09:31Z","timestamp":1787324971000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/050622870"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12,20]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/050622870"],"URL":"https:\/\/doi.org\/10.1137\/050622870","relation":{},"ISSN":["0036-1429","1095-7170"],"issn-type":[{"value":"0036-1429","type":"print"},{"value":"1095-7170","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,12,20]]}}}