Copositive optimization is a quickly expanding scientific research domain with wide-spread applications ranging from global nonconvex problems in engineering to NP-hard combinatorial optimization. It falls into the category of conic programming (optimizing a linear functional over a convex cone subject to linear constraints), namely the cone of all completely positive symmetric nxn matrices, and its dual cone, which coincides with the cone of all copositive matrices. We provide structural algebraic properties of these cones, and numerous (counter-)examples which demonstrate that many relations familiar from semidefinite optimization may fail in the copositive context, illustrating the transition from polynomial-time to NP-hard worst-case behaviour. In course of this development we also present a systematic construction principle for non-attainability phenomena, which apparently has not been noted before in an explicit way. Last but not least, also seemingly for the first time, a somehow systematic clustering of the vast and scattered literature is attempted in this paper.
Citation
to appear in J. Global Optimization (special issue dedicated to the memory of Reiner Horst)