Doan, Xuan Vinh, Kruk, Serge and Wolkowicz, Henry. (2011) A robust algorithm for semidefinite programming. Optimization Methods and Software, 27 (4-5). pp. 1-27. ISSN 1055-6788

Full text not available from this repository.

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.

Item Type:	Journal Article
Subjects:	H Social Sciences > HA Statistics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences Faculty of Social Sciences > Warwick Business School
Journal or Publication Title:	Optimization Methods and Software
Publisher:	Taylor & Francis Ltd.
ISSN:	1055-6788
Date:	October 2011
Volume:	27
Number:	4-5
Page Range:	pp. 1-27
Identification Number:	10.1080/10556788.2011.610456
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Description:	Special issue in honour of Professor Florian A. Potra's 60th birthday
URI:	http://wrap.warwick.ac.uk/id/eprint/49209

Request changes to a record

Actions (login required)

View Item