A robust algorithm for semidefinite programming
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-6788Full text not available from this repository.
Official URL: http://dx.doi.org/10.1080/10556788.2011.610456
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.|
|Official Date:||October 2011|
|Page Range:||pp. 1-27|
|Access rights to Published version:||Restricted or Subscription Access|
Special issue in honour of Professor Florian A. Potra's 60th birthday
Actions (login required)