The Library
A robust algorithm for semidefinite programming
Tools
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. doi:10.1080/10556788.2011.610456 ISSN 1055-6788.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1080/10556788.2011.610456
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 | ||||
Official Date: | October 2011 | ||||
Dates: |
|
||||
Volume: | 27 | ||||
Number: | 4-5 | ||||
Page Range: | pp. 1-27 | ||||
DOI: | 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 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |