Universität zu Köln
Mathematisch-Naturwissenschaftliche Fakultät
Arbeitsgruppe Faigle/Schrader
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.