Optimization Online


An Adaptive Linear Approximation Algorithm for Copositive Programs

Stefan Bundfuss (bundfuss***at***mathematik.tu-darmstadt.de)
Mirjam Duer (M.E.Dur***at***rug.nl)

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: SIAM Journal on Optimization 20 (2009), 30-53.

Download: [PDF]

Entry Submitted: 01/10/2008
Entry Accepted: 01/10/2008
Entry Last Modified: 08/17/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society