Logo image
Back
ERROR BOUNDS AND SINGULARITY DEGREE IN SEMIDEFINITE PROGRAMMING
Journal article   Open access   Peer reviewed

ERROR BOUNDS AND SINGULARITY DEGREE IN SEMIDEFINITE PROGRAMMING

Stefan Sremac, Hugo J. Woerdeman and Henry Wolkowicz
SIAM journal on optimization, v 31(1), pp 812-836
01 Jan 2021
DOI: https://doi.org/10.1137/19M1289327
url
http://arxiv.org/abs/1908.04357View
SubmittedOpen Access (License Unspecified),  Open

Abstract

Mathematics Mathematics, Applied Physical Sciences Science & Technology
In semidefinite programming a proposed optimal solution may be quite poor in spite of having sufficiently small residual in the optimality conditions. This issue may be framed in terms of the discrepancy between forward error (the unmeasurable "true error") and backward error (the measurable violation of optimality conditions). In [SIAM J. Optim., 10 (2000), pp. 1228-1248], Sturm provided an upper bound on forward error in terms of backward error and singularity degree. In this work we provide a method to bound the maximum rank over all optimal solutions and use this result to obtain a lower bound on forward error for a class of convergent sequences. This lower bound complements the upper bound of Sturm. The results of Sturm imply that semidefinite programs with slow convergence necessarily have large singularity degree. Here we show that large singularity degree is, in some sense, also a sufficient condition for slow convergence for a family of external-type "central" paths. Our results are supported by numerical observations.

Metrics

13 Record Views
8 citations in Web of Science
10 citations in Scopus

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Collaboration types
Domestic collaboration
International collaboration
Web of Science research areas
Mathematics, Applied
Logo image