Paper Info
Title
A robust algorithm for semidefinite programming
Abstract
Current successful methods for solving semidefinite programs SDPs 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.
Year
DOI
Venue
2012
10.1080/10556788.2011.610456
Optimization Methods and Software
Keywords
Field
DocType
current public domain software,dual interior-point method,newton equation,dual interior-point approach,backwards stable primal,robust algorithm,preconditioned matrix-free iterative method,semidefinite programming,well-conditioned jacobian,newton approach,current successful method,optimality condition,public domain,interior point,preconditioning,iteration method,bilinear form
Discrete mathematics,Mathematical optimization,Bilinear form,Jacobian matrix and determinant,Iterative method,Algorithm,Singularity,Symmetrization,Mathematics,Semidefinite programming,Public domain software
Journal
Volume
Issue
ISSN
27
4-5
1055-6788
Citations 
PageRank 
References 
4
0.41
15
Authors
3
Name
Order
Citations
PageRank
XuanVinh Doan140.41
Serge Kruk2101.64
Henry Wolkowicz31444260.72