Optimization Online


Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs

Yuzixuan (Melody) Zhu(zyzx***at***live.unc.edu)
Gabor Pataki(gabor***at***unc.edu)
Quoc Tran-Dinh(quoctd***at***email.unc.edu)

Abstract: We introduce Sieve-SDP, a simple algorithm to preprocess semidefinite programs (SDPs). Sieve-SDP belongs to the class of facial reduction algorithms. It inspects the constraints of the problem, deletes redundant rows and columns, and reduces the size of the variable matrix. It often detects infeasibility. It does not rely on any optimization solver: the only subroutine it needs is Cholesky factorization, hence it can be implemented in a few lines of code in machine precision. We present extensive computational results on several problem collections from the literature. We also highlight an issue arising in SDPs with positive duality gap: on such problems SDP solvers may compute a ``fake" solution with an arbitrarily small constraint violation, and arbitrarily small duality gap.

Keywords: Semidefinite programming; preprocessing; strict feasibility; strong duality; facial reduction

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

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: submitted

Download: [PDF]

Entry Submitted: 10/24/2017
Entry Accepted: 10/24/2017
Entry Last Modified: 10/24/2017

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