Copositive matrices are real symmetric matrices which, if considered as quadratic forms, are nonnegative on the positive orthant.
For a fixed matrix size n, these matrices form a convex cone, the copositive cone 𝒞ⁿ. Many optimization problems, among them difficult
combinatorial problems, can be formulated as the problem of minimization of a linear function over the intersection of the cone 𝒞ⁿ with an affine subspace.
A problem in this form is called a copositive program.
If we replace the condition of nonnegativity on the nonnegative orthant by the condition of global nonnegativity on ℝⁿ, then we obtain the smaller
positive semi-definite cone 𝒮ⁿ. A quadratic form which is not in the positive semi-definite cone must assume a negative value at its global
minimum on the unit sphere of ℝⁿ. By the first-order optimality condition the global minimizer must be an eigenvector of the matrix representing the form,
with negative eigenvalue. Therefore the membership of a real symmetric matrix in the cone 𝒮ⁿ is easy to check, by checking the nonnegativity of its eigenvalues.
Likewise, if a quadratic form is not in the copositive cone, then its global minimum on the intersection of the unit sphere with the nonnegative orthant must assume a negative value.
However, now this minimizer can be situated in the relative interior of any of the 2ⁿ-1 non-zero faces of the nonnegative orthant. In order to check the membership of a real symmetric matrix A
in the cone 𝒞ⁿ, one has therefore to exclude the existence of a positive eigenvector with negative eigenvalue for every one of the 2ⁿ-1 principal
submatrices of A. Solving a generic copositive program, even for moderate n, is thus a very difficult task.
In optimization the research on copositive cones therefore concentrates on approximation rather than exact solution of copositive programs. A selection of topics on copositive cones I am working on: