Computational Complexity of Sum-of-Squares Bounds for Copositive Programs

Marilena Palomba, Lucas Slot, Luis Felipe Vargas, Monaldo Mastrolilli

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:

  1. PBOS (Polynomially Bounded Optimal Solution): The optimal solution must reside within a box of size $2^{poly(n)}$.
  2. 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 intSPN condition 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 PBOS and intSPN conditions 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

Abstract

In recent years, copositive programming has received significant attention for its ability to model hard problems in both discrete and continuous optimization. Several relaxations of copositive programs based on semidefinite programming (SDP) have been proposed in the literature, meant to provide tractable bounds. However, while these SDP-based relaxations are amenable to the ellipsoid algorithm and interior point methods, it is not immediately obvious that they can be solved in polynomial time (even approximately). In this paper, we consider the sum-of-squares (SOS) hierarchies of relaxations for copositive programs introduced by Parrilo (2000), de Klerk & Pasechnik (2002) and Pe\~na, Vera & Zuluaga (2006), which can be formulated as SDPs. We establish sufficient conditions that guarantee the polynomial-time computability (up to fixed precision) of these relaxations. These conditions are satisfied by copositive programs that represent standard quadratic programs and their reciprocals. As an application, we show that the SOS bounds for the (weighted) stability number of a graph can be computed efficiently. Additionally, we provide pathological examples of copositive programs (that do not satisfy the sufficient conditions) whose SOS relaxations admit only feasible solutions of doubly-exponential size.
BibTeX
@article{palomba2025computational,
  author = {Marilena Palomba and Lucas Slot and Luis Felipe Vargas and Monaldo Mastrolilli},
  title = {{Computational Complexity of Sum-of-Squares Bounds for Copositive Programs}},
  journal = {SIAM J. Optim.},
  year = {2025},
  doi = {10.1137/25m1724444},
}

Loading related content...

Figure