An improved algorithm to test copositivity

An improved algorithm to test copositivity

0.00 Avg rating0 Votes
Article ID: iaor20122801
Volume: 52
Issue: 3
Start Page Number: 537
End Page Number: 551
Publication Date: Mar 2012
Journal: Journal of Global Optimization
Authors: , ,
Keywords: programming: quadratic, matrices, combinatorial optimization, programming: branch and bound
Abstract:

Copositivity plays a role in combinatorial and nonconvex quadratic optimization. However, testing copositivity of a given matrix is a co‐NP‐complete problem. We improve a previously given branch‐and‐bound type algorithm for testing copositivity and discuss its behavior in particular for the maximum clique problem. Numerical experiments indicate that the speedup is considerable.

Reviews

Required fields are marked *. Your email address will not be published.