Rigorous error bounds for the optimal value in semidefinite programming

Journal
SIAM journal on numerical analysis  
Volume
46
Issue
1
Start Page
180
End Page
200
Citation
SIAM Journal on Numerical Analysis 1 (46): 180-200 (2007-12-01)
Publisher DOI
10.1137/050622870
Scopus ID
2-s2.0-55549133270
Publisher
SIAM
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.
Subjects
Interval arithmetic
Linear programming
NETLIB LP library
Rigorous error bounds
SDPLIB
Semidefinite programming
Sensitivity analysis
DDC Class
004: Informatik
510: Mathematik