Univ.-Prof. Mag. Dr. Immanuel Bomze
Universität Wien, Österreich
Institut für Statistik und Decision Support Systems

A nasty cone with nice properties - new issues in copositive programming

A symmetric matrix is called copositive, if it generates a quadratic form taking no negative values over the positive orthant. Contrasting to positive-semidefiniteness, checking copositivity is NP-hard. In a copositive optimization problem, we have to minimize a linear function of a symmetric matrix over the copositive cone subject to linear constraints.This convex program has no non-global local solutions. On the other hand, there are several hard non-convex programs which can be formulated as copositive programs, among them mixed-binary QPs or Standard QPs. Applications range from machine learning to several combinatorial optimization problems, including the maximum-clique problem or the maximum-cut problem. Also, finding the best convex underestimator of a nonconvex quadratic function over polytopes can be written as copositive optimization problem.

The dual conic program, unlike the more popular SDP case, involves a different matrix cone, that of completely positive matrices (those which allow for a symmetric, possibly rectangular factorization with no negative entries). This conic optimization technique shifts complexity from global optimization towards sheer feasibility questions. Therefore it is of central importance to devise positive and negative certificates of copositivity and/or complete positivity.

Three new copositivity tests based upon difference-of-convex (d.c.) decompositions are presented, and combined to a branch-and-bound algorithm of omega-subdivision type. The tests employ LP or convex QP techniques, but also can be used heuristically if educated guesses are available and preferred. We also propose some preprocessing ideas, which result in a normal form for copositivity. Switching to complete positivity, a heuristic factorization procedure for obtaining an explicit factorization is also presented.