Optimization Online


Preprocessing and Reduction for Degenerate Semidefinite Programs

Yuen-Lam Cheung(yl2cheun***at***uwaterloo.ca)
Simon Schurr(spschurr***at***optserv.cas.mcmaster.ca)
Henry Wolkowicz(hwolkowciz***at***uwaterloo.ca)

Abstract: This paper presents a backward stable preprocessing technique for (nearly) ill-posed semidefinite programming, SDP, problems, i.e.,~programs for which Slater's constraint qualification, existence of strictly feasible points, (nearly) fails. Current popular algorithms for semidefinite programming rely on \emph{primal-dual interior-point, p-d i-p} methods. These algorithms require Slater's constraint qualification for both the primal and dual problems. This assumption guarantees the existence of Lagrange multipliers, well-posedness of the problem, and stability of algorithms. However, there are many instances of SDPs where Slater's constraint qualification fails or {\em nearly} fails. Our backward stable preprocessing technique is based on finding a {\em rank-revealing} rotation of the problem followed by facial reduction. This results in a smaller, well-posed, \emph{nearby} problem that can be solved by standard SDP solvers.

Keywords: Preprocessing, semidefinite programming, degeneracy, strong duality

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

Category 2: Optimization Software and Modeling Systems

Citation: CORR 2011-02, University of Waterloo

Download: [PDF]

Entry Submitted: 02/19/2011
Entry Accepted: 02/19/2011
Entry Last Modified: 02/19/2011

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