TL;DR
Copositive programming is a powerful framework for solving "hard" optimization problems, but its standard approximations—Sum-of-Squares (SOS) hierarchies—aren't always as tractable as they seem. This paper identifies the specific technical conditions under which these bounds can actually be computed in polynomial time and proves that these conditions hold for classic problems like finding the stability and chromatic numbers of a graph.
What Problem Does This Paper Address?
Copositive programming (CP) is a heavy hitter in optimization, capable of modeling NP-hard problems in both discrete math (like graph theory) and continuous control. Because the "copositive cone" is mathematically difficult to handle, researchers typically use Sum-of-Squares (SOS) hierarchies to relax these problems into Semidefinite Programs (SDPs).
In theory, SDPs are solvable in polynomial time. However, there is a catch: standard algorithms (like the ellipsoid method) only work in polynomial time if the "bit size" of the solution is manageable. If a feasible solution requires entries that are doubly-exponential in size, you can't even write the answer down in polynomial time, let alone compute it. This paper investigates whether SOS relaxations for copositive programs actually stay "well-behaved" or if they fall into this exponential trap.
Methods
The authors focus on two well-known SOS hierarchies for the copositive cone: the $\mathcal{K}_n^{(r)}$ hierarchy (introduced by Parrilo, de Klerk, and Pasechnik) and the $\mathcal{Q}_n^{(r)}$ hierarchy (introduced by Peña, Vera, and Zuluaga).
To prove these are computable, they establish two sufficient conditions:
- PBOS (Polynomially Bounded Optimal Solution): The optimal solution must reside within a box of size $2^{poly(n)}$.
- intSPN (Interior SPN point): The program must have a "nice" 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 their proof involves bounding the coefficients of the polynomials that appear in the SOS representations. They show that if a "strict" feasibility condition is met, the resulting SDP doesn't blow up in bit size, allowing for efficient computation up to a fixed precision $\epsilon$.
Datasets
As a theoretical paper in mathematical optimization, it does not use traditional training datasets. Instead, it evaluates its findings against established mathematical benchmarks and structures:
- Standard Quadratic Programs (SQP): Minimizing a quadratic form over a simplex.
- Graph Problems: Specifically, the stability number $\alpha(G)$ and the chromatic number $\chi(G)$ of a graph.
- Pathological Examples: The authors construct specific "bad" matrices (like those based on the cycle graph $C_5$) to demonstrate what happens when their conditions are violated.
Key Insights and Ideas
- The "Bit Size" Trap: The paper highlights a subtle but critical gap in optimization theory—just because a problem is an SDP doesn't mean it's computationally easy. The magnitude of the numbers matters.
- Strict Feasibility is Key: The
intSPNcondition acts as a "buffer." If a problem has a solution that is "deep" inside a simpler cone (the SPN cone), the SOS hierarchy is much more likely to be well-behaved. - SQPs are Safe: A major "aha" moment is the proof that Standard Quadratic Programs and their reciprocals naturally satisfy these conditions. This provides a solid theoretical foundation for using SOS bounds in these common applications.
- Doubly-Exponential Danger: By constructing counterexamples, the authors prove that their technical assumptions aren't just for show—without them, SOS relaxations can indeed produce solutions of $2^{2^n}$ size, which are practically uncomputable.
Key Results
- Theorem 1.3 (The Main Result): Under the 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.
- Efficiency for Graphs: The authors show that SOS bounds for the weighted stability number and the chromatic number of a graph can be computed efficiently, providing a theoretical green light for researchers using these methods in combinatorics.
- Complexity Bounds: They provide a general result (Theorem 3.2) for bounding coefficients in SOS proofs, which is likely to be useful for researchers in the broader field of polynomial optimization.
Limitations and Future Work
- Verification Difficulty: For a general, arbitrary copositive program, it may still be difficult to verify if the
PBOSandintSPNconditions hold without prior knowledge of the problem's structure. - Modification Overhead: While the authors show how to modify a program to satisfy these conditions (Theorem 1.5), this modification adds a layer of complexity to the formulation.
- Beyond Fixed Degree: The results apply to a fixed level $r$ of the hierarchy. As $r$ increases (to get tighter bounds), the size of the SDP still grows combinatorially, which remains a practical bottleneck regardless of bit-size stability.
Summary updated