An Adaptive Linear Approximation Algorithm for Copositive Programs
Stefan Bundfuss (bundfussmathematik.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: SIAM Journal on Optimization 20 (2009), 30-53.
Entry Submitted: 01/10/2008
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|