Optimization Online


A simple preprocessing algorithm for semidefinite programming

Preston Faulk(pfaulk***at***live.unc.edu)
Gabor Pataki(gabor***at***unc.edu)
Quoc Tran-Dinh(quoctd***at***email.unc.edu)

Abstract: We propose a very simple preprocessing algorithm for semidefinite programming. Our algorithm inspects the constraints of the problem, deletes redundant rows and columns in the constraints, and reduces the size of the variable matrix. It often detects infeasibility. Our algorithm does not rely on any optimization solver: the only subroutine it needs is Cholesky factorization, hence it can be implemented with a few lines of code in machine precision. We present computational results on a set of problems arising mostly from polynomial optimization.

Keywords: semidefinite programming; preprocessing; facial reduction

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

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Optimization Software and Modeling Systems (Optimization Software Benchmark )


Download: [PDF]

Entry Submitted: 08/07/2016
Entry Accepted: 08/08/2016
Entry Last Modified: 08/07/2016

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