Optimization Online


Error Bounds and Singularity Degree in Semidefinite Programming

Stefan Sremac(ssremac***at***uwaterloo.ca)
Hugo J. Woerdeman(hugo***at***math.drexel.edu)
Henry Wolkowicz(henry.wolkowicz***at***uwaterloo.ca)

Abstract: 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 his seminal work, Sturm provided an upper bound on forward error in terms of backward error and singularity degree. In this paper we provide a method to bound the maximum rank over all 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.

Keywords: error bounds, singularity degree, semidefinite programming, facial reduction

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

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 08/12/2019
Entry Accepted: 08/13/2019
Entry Last Modified: 08/12/2019

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 Optimization Society