  


Quadratic factorization heuristics for copositive programming
Immanuel M. Bomze(immanuel.bomzeunivie.ac.at) Abstract: Copositive optimization problems are particular conic programs: extremize linear forms over the copositive cone subject to linear constraints. Every quadratic program with linear constraints can be formulated as a copositive program, even if some of the variables are binary. So this is an NPhard problem class. While most methods try to approximate the copositive cone from within, we propose a method which approximates this cone from outside. This is achieved by passing to the dual problem, where the feasible set is an affine subspace intersected with the cone of completely positive matrices, and this cone is approximated from within. We consider feasible descent directions in the completely positive cone, and regularized strictly convex subproblems. In essence, we replace the intractable completely positive cone with a nonnegative cone, at the cost of a series of nonconvex quadratic subproblems. Proper adjustment of the regularization parameter results in short steps for the nonconvex quadratic programs. This suggests to approximate their solution by standard linearization techniques. Preliminary numerical results on three different classes of test problems are quite promising. Keywords: Combinatorial optimization, copositive programs, clique number Category 1: Linear, Cone and Semidefinite Programming (Other ) Category 2: Integer Programming ((Mixed) Integer Linear Programming ) Category 3: Global Optimization (Other ) Citation: Technical Report TR 200908, Oct. 2009. Institut fuer Statistik und Decision Support Systems, Universitaet Wien, Austria Download: [Postscript][PDF] Entry Submitted: 10/14/2009 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  