Think co(mpletely )positive ! Matrix properties, examples and a clustered bibliography on copositive optimization

Immanuel M. Bomze(immanuel.bomzeunivie.ac.at)
Werner Schachinger(werner.schachingerunivie.ac.at)
Gabriele Uchida(gabriele.uchidaunivie.ac.at)

Abstract: 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.

Keywords: conic optimization; copositive reformulation; duality gap; attainability; Hadamard product; Kronecker product

Category 1: Linear, Cone and Semidefinite Programming (Other )

Category 2: Global Optimization (Theory )

Category 3: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: to appear in J. Global Optimization (special issue dedicated to the memory of Reiner Horst)

Download: [PDF]

Entry Submitted: 06/07/2011
Entry Accepted: 06/07/2011
Entry Last Modified: 06/07/2011

Modify/Update this entry