Abstract
Copositive programming (CP) provides a powerful framework for modeling NP-hard optimization problems in both discrete and continuous domains. While Sum-of-Squares (SOS) hierarchies are frequently used to relax these problems into tractable Semidefinite Programs (SDPs), the actual polynomial-time computability of these relaxations is often assumed rather than proven. This paper establishes sufficient conditions—specifically the Polynomially Bounded Optimal Solution (PBOS) and the existence of an interior SPN point (intSPN)—that guarantee these bounds can be computed in polynomial time. We demonstrate that these conditions are naturally satisfied by standard quadratic programs and graph-theoretic problems, while also providing pathological examples where the absence of these conditions leads to doubly-exponential solution sizes.
Introduction
Copositive programming has emerged as a heavy hitter in the optimization world, capable of representing complex problems ranging from the stability number of a graph to quadratic assignment problems. However, the "copositive cone" is mathematically difficult to handle directly. To bridge this gap, researchers utilize SOS hierarchies, such as those introduced by Parrilo, de Klerk, Pasechnik, Peña, Vera, and Zuluaga. These hierarchies relax the copositive constraints into a sequence of SDPs.
In theory, SDPs are solvable in polynomial time using the ellipsoid method or interior-point methods. However, a subtle but critical gap exists in this theory: an SDP is only truly solvable in polynomial time if the "bit size" of the solution remains manageable. If a feasible solution requires entries that are doubly-exponential in size, the problem becomes practically uncomputable. This paper investigates whether SOS relaxations for copositive programs stay "well-behaved" or fall into this exponential trap.
Methodology and Technical Conditions
The authors focus on two primary SOS hierarchies: the $\mathcal{K}_n^{(r)}$ hierarchy and the $\mathcal{Q}_n^{(r)}$ hierarchy. To ensure these are computable within a fixed precision $\epsilon$, the paper establishes two sufficient conditions:
- Polynomially Bounded Optimal Solution (PBOS): The optimal solution must reside within a box of size $2^{poly(n)}$. This prevents the optimal value from drifting toward infinity in a way that requires exponential bits to represent.
- Interior SPN Point (intSPN): The program must have a feasible point in the interior of the SPN cone (the cone of matrices that are the sum of a positive semidefinite matrix and a nonnegative matrix).
The core of the proof involves bounding the coefficients of the polynomials that appear in the SOS representations. By showing that a "strict" feasibility condition (intSPN) acts as a buffer, the authors prove that the resulting SDP does not suffer from bit-size blow-up, allowing for efficient computation.
Applications in Optimization and Graph Theory
The paper evaluates these theoretical conditions against several established mathematical benchmarks:
Standard Quadratic Programs (SQP)
A major contribution of this work is the proof that Standard Quadratic Programs—minimizing a quadratic form over a simplex—and their reciprocals naturally satisfy the PBOS and intSPN conditions. This provides a rigorous theoretical foundation for the widespread use of SOS bounds in these common applications.
Graph-Theoretic Bounds
The authors show that SOS bounds for the weighted stability number $\alpha(G)$ and the chromatic number $\chi(G)$ of a graph can be computed efficiently. This result is a significant "green light" for researchers in combinatorics who rely on these hierarchies to approximate hard graph metrics.
Pathological Counterexamples
To demonstrate that these conditions are necessary, the authors construct specific "bad" matrices based on the cycle graph $C_5$. They show that when the intSPN condition is violated, SOS relaxations can indeed produce solutions of $2^{2^n}$ size. In such cases, the relaxations are effectively uncomputable by any standard algorithm.
Key Results
- Theorem 1.3 (Computability): Under PBOS and intSPN conditions, the SOS bounds for a copositive program can be computed to an accuracy $\epsilon$ in $poly(n, \log(1/\epsilon))$ time.
- Coefficient Bounding: Theorem 3.2 provides a general result for bounding coefficients in SOS proofs, a tool likely to be useful for the broader field of polynomial optimization.
- Complexity Verification: The paper highlights that while SDPs are often called "tractable," their complexity is highly sensitive to the magnitude of the numbers involved.
Limitations and Future Outlook
While the paper provides a path forward, some challenges remain. For an arbitrary copositive program, verifying if the PBOS and intSPN conditions hold can be difficult without prior knowledge of the problem's structure. Additionally, while the authors provide a method to modify programs to satisfy these conditions (Theorem 1.5), this modification adds formulation overhead.
Finally, the results apply to a fixed level $r$ of the hierarchy. As $r$ increases to provide tighter bounds, the size of the SDP grows combinatorially. While this paper solves the "bit-size" problem, the combinatorial growth of the hierarchy itself remains the primary practical bottleneck for high-accuracy approximations.
Summary updated