Termination and Verification for Ill-Posed Semidefinite Programming Problems

Christian Jansson (janssontu-harburg.de)

Abstract: We investigate ill-posed semidefinite programming problems for which Slater's constraint qualifications fail, and propose a new reliable termination criterium dealing with such problems. This criterium is scale-independent and provides verified forward error bounds for the true optimal value, where all rounding errors due to floating point arithmetic are taken into account. It is based on a boundedness qualification, which is satisfied for many problems. Numerical experiments, including combinatorial problems, are presented.

Keywords: Semidefinite Programming, ill-posed problems, combinatorial optimization

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Global Optimization

Category 3: Combinatorial Optimization

Citation: Informatik III, TU Hamburg-Harburg, Schwarzenbergstr. 95, 21073 Hamburg, submitted

Download: [Postscript][PDF]

Entry Submitted: 06/17/2005
Entry Accepted: 06/17/2005
Entry Last Modified: 06/17/2005

Modify/Update this entry