Optimization Online


Rigorous Error Bounds for the Optimal Value in Semidefinite Programming

C. Jansson (jansson***at***tu-harburg.de)
D. Chaykin (denis.chaykin***at***tu-harburg.de)
C. Keil (c.keil***at***tu-harburg.de)

Abstract: 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.

Keywords: semidefinite programming, linear programming, interval arithmetic, rigorous error bounds, sensitivity analysis, SDPLIB, NETLIB lp library

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Linear, Cone and Semidefinite Programming (Linear Programming )


Download: [Compressed Postscript][PDF]

Entry Submitted: 01/18/2005
Entry Accepted: 01/18/2005
Entry Last Modified: 07/05/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society