Optimization Online


A Robust Algorithm for Semidefinite Programming

Xuan Vinh Doan (vanxuan***at***uwaterloo.ca)
Serge Kruk (sgkruk***at***acm.org)
Henry Wolkowicz (hwolkowi***at***uwaterloo.ca)

Abstract: Current successful methods for solving semidefinite programs, SDP, are based on primal-dual interior-point approaches. These usually involve a symmetrization step to allow for application of Newton's method followed by block elimination to reduce the size of the Newton equation. Both these steps create ill-conditioning in the Newton equation and singularity of the Jacobian of the optimality conditions at the optimum. In order to avoid the ill-conditioning, we derive and test a backwards stable primal-dual interior-point method for SDP. Relative to current public domain software, we realize both a distinct improvement in the accuracy of the optimum and a reduction in the number of iterations. This is true for random problems as well as for problems of special structure. Our algorithm is based on a Gauss-Newton approach applied to a single bilinear form of the optimality conditions. The well-conditioned Jacobian allows for a preconditioned (matrix-free) iterative method for finding the search direction at each iteration.

Keywords: Semidefinite Programming, interior-point algorithm, stabillity

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

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

Citation: CORR 2010-09, Department of Combinatorics and Optimization, University of Waterloo, Nov. 2010

Download: [PDF]

Entry Submitted: 11/14/2010
Entry Accepted: 11/14/2010
Entry Last Modified: 11/17/2010

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