  


A Fully Sparse Implementation of a PrimalDual InteriorPoint Potential Reduction Method for Semidefinite Programming
Gun Srijuntongsiri (gunsrics.cornell.edu) Abstract: In this paper, we show a way to exploit sparsity in the problem data in a primaldual potential reduction method for solving a class of semidefinite programs. When the problem data is sparse, the dual variable is also sparse, but the primal one is not. To avoid working with the dense primal variable, we apply Fukuda et al.'s theory of partial matrix completion and work with partial matrices instead. The other place in the algorithm where sparsity should be exploited is in the computation of the search direction, where the gradient and the Hessianmatrix product of the primal and dual barrier functions must be computed in every iteration. By using an idea from automatic differentiation in backward mode, both the gradient and the Hessianmatrix product can be computed in time proportional to the time needed to compute the barrier functions of sparse variables itself. Moreover, the high space complexity that is normally associated with the use of automatic differentiation in backward mode can be avoided in this case. In addition, we suggest a technique to efficiently compute the determinant of the positive definite matrix completion that is required to compute primal search directions. The method of obtaining one of the primal search directions that minimizes the number of the evaluations of the determinant of the positive definite completion is also proposed. We then implement the algorithm and test it on the problem of finding the maximum cut of a graph. Keywords: semidefinite programming, Category 1: Linear, Cone and Semidefinite Programming (SecondOrder Cone Programming ) Citation: Cornell University, Ithaca, NY 14853, 12/2004. Also available at http://arxiv.org/ps/cs.NA/0412009 Download: [PDF] Entry Submitted: 12/08/2004 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  