Abstract:
A real symmetric matrix X is called copositive (COP) if a'Xa = 0 for every nonnegative vector a, and completely positive (CP) if X = NN' for some nonnegative matrix N. The cones of nxn copositive and completely positive matrices are dual to one another. In recent years it has been shown that a variety of NP-hard optimization problems can be formulated as conic linear programs over the COP and CP cones. We describe these formulation results, as well as two different algorithmic approaches for problems posed over these cones. The first approach is based on computable matrix hierarchies that give better and better approximations of the CP and COP cones, and the second is based on generating COP cut matrices that separate a given non-CP matrix from the CP cone. Computational results show that these algorithmic approaches generate improved bounds on some difficult instances.

References:

I.M. Bomze. Copositive optimization - recent developments and applications. EJOR 216:509-520, 2012.
I.M. Bomze, M. Duer, E. de Klerk, C. Roos, A. Quist and T. Terlaky. On copositive programming and standard quadratic optimization problems. J. Global Optim.,18:301-320, 2000.
I.M. Bomze and E. de Klerk. Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Global Optim., 24:163-185, 2002.
I.M. Bomze, F. Frommlet and M. Locatelli. Copositivity cuts for improving SDP bounds on the clique number. Math. Prog. B, 124:13-32, 2010.
S. Bundfuss and M. Duer. An adaptive linear approximation algorithm for copositive programs. SIAM J. Optim., 20:30-53, 2009.
S. Burer. On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Prog., 120:479-495, 2009.
S. Burer, K.M. Anstreicher and M. Duer. The difference between 5x 5 doubly nonnegative and completely positive matrices. Linear Algebra Appl., 431:1539-1552, 2009.
E. de Klerk and D.V. Pasechnik. Approximation of the stability number of a graph via copositive programming. SIAM J. Optim., 12:875-892, 2002.
H. Dong and K.M. Anstreicher. Separating doubly nonnegative and completely positive matrices. To appear in Math. Prog , 2012