Copositivity detection by difference-of-convex decomposition and omega-subdivision

We present three new copositivity tests based upon difference-of-convex (d.c.) decompositions, and combine them to a branch-and-bound algorithm of $\omega$-subdivision type. The tests employ LP or convex QP techniques, but also can be used heuristically using appropriate test points. We also discuss the selection of efficient d.c.~decompositions and propose some preprocessing ideas based on the spectral d.c.~decomposition. We report on first numerical experience with this procedure which are very promising.

Citation

AM Preprint Series No. 333, Univ. Erlangen-Nuremberg; and Technical Report 2011-05, ISOR, Univ. Wien. To appear in: Math. Programming A