Introduction
In the field of convex optimization, the cone of copositive matrices ($\mathcal{C}$) and its dual, the cone of completely positive matrices ($\mathcal{C}^*$), play a pivotal role. Many NP-hard problems, such as the Maximum Clique problem or certain quadratic programs, can be reformulated as linear problems over these cones. However, the computational challenge lies in the fact that determining membership in these cones is itself NP-hard. This paper by Jean B. Lasserre introduces a novel hierarchy of semidefinite programming (SDP) relaxations that provide systematic outer approximations for the copositive cone and inner approximations for the completely positive cone.
The Copositivity Challenge
A matrix $A$ is defined as copositive if the quadratic form $x^T Ax \ge 0$ for all non-negative vectors $x \ge 0$. Conversely, a matrix is completely positive if it can be factored into $BB^T$ where $B$ is a non-negative matrix. Historically, most approximation hierarchies provided inner approximations of the copositive cone. Lasserre’s work addresses the critical need for outer approximations, which conversely provide inner approximations for the dual completely positive cone, answering a long-standing challenge in the field.
Methodology: The Moment-SOS Approach
The proposed method leverages the "Moment-SOS" (Sum of Squares) hierarchy. The core strategy involves treating the copositivity condition as a problem of polynomial non-negativity over the non-negative orthant.
- Reference Measure: A specific Borel measure $\mu$ (e.g., the exponential distribution) is introduced, with support exactly on the non-negative orthant.
- Moment and Localizing Matrices: The author constructs localizing matrices based on the moments of this measure. These matrices are linear functions of the entries of the matrix $A$ being tested.
- Spectrahedral Hierarchy: By requiring these localizing matrices to be positive semidefinite (PSD), a sequence of simpler cones $\mathcal{C}_d$ is defined. As the degree $d$ increases, these cones converge to the true copositive cone $\mathcal{C}$.
Key Results and Visualization
The paper proves that the hierarchy of spectrahedra $\mathcal{C}_d$ converges to the copositive cone as $d \to \infty$. A significant finding is the efficacy of even low-order approximations. For the $n=2$ case, the first level of the hierarchy ($\mathcal{C}_1$) provides a remarkably close approximation to the true cone.
This visualization demonstrates that the outer approximation is tight even at the earliest stages of the hierarchy, which is crucial for practical applications where higher-order computations become prohibitively expensive.
Discussion and Future Work
The "sandwich" effect created by having both inner and outer approximations allows researchers to bound these complex cones from both sides. Furthermore, the membership test for the outer hierarchy $\mathcal{C}_d$ simplifies to checking the eigenvalues of a specific matrix, allowing for the use of efficient numerical solvers.
While the theoretical convergence is guaranteed, practical limitations remain. The size of the moment matrices grows combinatorially with the dimension $n$ and degree $d$, limiting high-dimensional applications to low-degree approximations. Future research may focus on improving the scalability of these methods and exploring the rate of convergence for more complex, high-dimensional problems.
Summary updated