Copositive cones

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:

• determine how fast the complexity of 𝒞 grows with n
• find good tractable approximations of 𝒞
• describe the structure of copositive cones in low dimensions