An Adaptive Linear Approximation Algorithm for Copositive Programs

Stefan Bundfuss(bundfussmathematik.tu-darmstadt.de)
Mirjam Duer(duermathematik.tu-darmstadt.de)

Abstract: We study linear optimization problems over the cone of copositive matrices. These problems appear in nonconvex quadratic and binary optimization, for instance the maximum clique problem and other combinatorial problems can be reformulated as such a problem. We present new polyhedral inner and outer approximations of the copositive cone which we show to be exact in the limit. In contrast to previous approximation schemes, our approximation is not necessarily uniform for the whole cone but can be guided adaptively through the objective function, yielding a good approximation in those parts of the cone that are relevant for the optimization and only a coarse approximation in those parts that are not. Using these approximations, we derive an adaptive linear approximation algorithm for copositive programs. Numerical experiments show that our algorithm gives very good results for certain nonconvex quadratic problems.

Keywords: copositive cone, copositive programming, quadratic programming, approximation algorithms

Category 1: Linear, Cone and Semidefinite Programming

Citation: Preprint, Department of Mathematics, TU Darmstadt

Download: [PDF]

Entry Submitted: 01/10/2008
Entry Accepted: 01/10/2008
Entry Last Modified: 01/10/2008

Modify/Update this entry