  


A Robust Algorithm for Semidefinite Programming
Xuan Vinh Doan (vanxuanuwaterloo.ca) Abstract: Current successful methods for solving semidefinite programs, SDP, are based on primaldual interiorpoint 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 illconditioning in the Newton equation and singularity of the Jacobian of the optimality conditions at the optimum. In order to avoid the illconditioning, we derive and test a backwards stable primaldual interiorpoint 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 GaussNewton approach applied to a single bilinear form of the optimality conditions. The wellconditioned Jacobian allows for a preconditioned (matrixfree) iterative method for finding the search direction at each iteration. Keywords: Semidefinite Programming, interiorpoint algorithm, stabillity Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Category 2: Optimization Software and Modeling Systems (Optimization Software Benchmark ) Citation: CORR 201009, Department of Combinatorics and Optimization, University of Waterloo, Nov. 2010 Download: [PDF] Entry Submitted: 11/14/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  