⚡ electrical engineering

Disjunctive Sum of Squares

This paper introduces the concept of disjunctive sum of squares, a method for certifying polynomial nonnegativity through multiple parallel algebraic identities that enables the construction of converging optimization hierarchies with fixed-size semidefinite constraints and optimization-free alternatives, while demonstrating practical applications in polynomial, copositive, and combinatorial optimization.

Original authors: Amir Ali Ahmadi, Sanjeeb Dash, Yixuan Hua, Bartolomeo Stellato

Published 2026-05-28

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Amir Ali Ahmadi, Sanjeeb Dash, Yixuan Hua, Bartolomeo Stellato

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to prove that a mysterious, complex machine (a mathematical polynomial) never produces a negative number. In the world of math, this is called proving "nonnegativity."

For decades, the standard way to solve this mystery was to find one single, perfect algebraic equation that acts like a magic key. If you could write the machine's output as a sum of squares (like $A^2 + B^2 + C^2$ ), you knew for a fact it could never be negative, because squares are always positive.

However, this "single key" approach has a major flaw: sometimes, to make that one equation work, you have to use incredibly complex, high-degree numbers. It's like trying to open a simple door with a giant, 50-foot-long skeleton key. It works, but it's heavy, expensive to build, and computationally impossible to use in many real-world scenarios.

The New Idea: A Team of Small Keys

This paper introduces a new strategy called Disjunctive Sum of Squares. Instead of looking for one giant, complex key, the authors propose using a team of smaller, simpler keys.

Here is the core concept:

Split the World: Imagine the universe of possible inputs is a large room. Instead of trying to prove the machine is safe for the entire room at once, we divide the room into smaller, manageable zones (like splitting a pizza into slices).
Local Proof: In each zone, we only need to prove the machine is safe using a simple, low-degree equation.
The "Or" Logic: We don't need one equation to cover everything. We just need to prove: "If you are in Zone A, the machine is safe OR if you are in Zone B, the machine is safe OR if you are in Zone C..." As long as every possible point in the room falls into at least one of these safe zones, the whole machine is proven safe.

Why is this a game-changer?

Simplicity: The "keys" (algebraic identities) used in each zone are much simpler and smaller than the giant key required by the old method.
Parallel Processing: Because each zone is independent, you can check them all at the same time. It's like having a team of detectives checking different rooms simultaneously, rather than one detective trying to check the whole building alone.
Efficiency: The authors prove mathematically that you can always find these simple, low-degree proofs, no matter how complex the machine is. You don't need to make the equations more complicated; you just need to add more zones.

Real-World Applications Mentioned in the Paper

The authors tested this "team of keys" approach on several difficult problems:

The "Motzkin" Puzzle: They used this method to prove the safety of a famous mathematical puzzle (the Motzkin polynomial) that the old method struggled with. They found proofs using simple equations that the old method couldn't find without becoming impossibly complex.
Matrix Copositivity: This is a specific type of problem involving grids of numbers (matrices). The authors showed how to break down the problem into smaller geometric shapes (triangles and cones) to prove these matrices are safe, which is useful in optimization and economics.
Finding the "Clique": In graph theory (networks of dots and lines), a "clique" is a group of dots where everyone is connected to everyone else. Finding the largest clique is a notoriously hard problem. The authors used their method to solve this by breaking the problem into smaller pieces, successfully finding the exact size of the largest group in several random networks.

The Bottom Line

The paper argues that we don't need to force a single, massive, complicated solution to prove a mathematical truth. Instead, by dividing the problem into smaller, overlapping pieces and solving each piece with a simple tool, we can prove the whole thing is true much faster and more efficiently. It's the difference between trying to lift a boulder with one giant lever versus using a team of people with small, simple levers working together.

Technical Summary: Disjunctive Sum of Squares

Problem Statement

The paper addresses the fundamental problem of certifying the nonnegativity of polynomials. While a polynomial $p$ is nonnegative if $p(x) \geq 0$ for all $x \in \mathbb{R}^n$ , determining this property is generally NP-hard. The standard approach, the Sum of Squares (SOS) method, certifies nonnegativity by expressing $p$ as a single algebraic identity $p(x) = \sum q_i^2(x)$ . However, not all nonnegative polynomials are SOS (a fact established by Hilbert), and proving nonnegativity for those that are not typically requires multiplying $p$ by a high-degree SOS polynomial (e.g., via Artin's solution to Hilbert's 17th problem). This results in algebraic identities with degrees significantly higher than the original polynomial, leading to Semidefinite Programs (SDPs) that grow exponentially in size and become computationally intractable.

The central question motivating this research is: Can the complexity of an SOS-based proof of polynomial nonnegativity be reduced by constructing several algebraic identities instead of a single one?

Methodology

The authors introduce the concept of Disjunctive Sum of Squares (Disjunctive SOS). Instead of a single global identity, nonnegativity is certified by a collection of algebraic identities, each valid on a specific subregion of the domain. These subregions form a partition (or cover) of the space, defined by an algebraic disjunction.

Core Definitions

Algebraic Disjunction: A collection of polynomials $\mathcal{D} = \{\{q_{k,j}\}\}$ such that the union of the regions $\Omega_k = \{x \mid q_{k,j}(x) \geq 0, \forall j\}$ covers $\mathbb{R}^n$ .
Disjunctive SOS Proof: A polynomial $p$ is a disjunctive SOS with respect to $\mathcal{D}$ if, for each region $\Omega_k$ , there exist SOS polynomials $s_{k,j}$ such that:
$p(x) = s_{k,0}(x) + \sum_{j=1}^{n_k} s_{k,j}(x)q_{k,j}(x) \quad \text{for all } x \in \Omega_k.$
Crucially, the degree of the SOS polynomials $s_{k,j}$ can be kept low (specifically, bounded by the degree of $p$ ), unlike in global SOS proofs where the degree must often increase.

Theoretical Framework

The paper establishes two main theoretical results, termed Disjunctive Positivstellensätze:

SDP-Based Disjunctive Positivstellensatz (Theorem 1):
For any positive definite form $p$ of degree $d$ , there exists an explicit family of algebraic disjunctions (constructed via spherical caps) such that $p$ admits a disjunctive SOS proof where the degree of the SOS multipliers is at most $d$ . This allows for a converging hierarchy of lower bounds for polynomial minimization over the unit sphere using SDPs of fixed size (independent of the hierarchy level).
Optimization-Free Disjunctive Positivstellensatz (Theorem 8):
A stronger result showing that for any positive definite form, there exists a family of simplicial disjunctions (polyhedral cones) such that $p$ can be certified nonnegative simply by checking that its coefficients are nonnegative after a linear change of coordinates within each cone. This approach requires no optimization solver (only linear programming or direct coefficient checks) but may require a larger number of regions compared to the SDP approach.

Algorithmic Framework

The authors propose a Spatial Branch-and-Bound (SBB) framework to adaptively search for these disjunctive proofs. Rather than uniformly partitioning the space (as in the theoretical proofs), the algorithm:

Maintains a tree of subregions (simplicial cones).
Computes lower bounds via SDPs (or linear checks) on each subregion.
Computes upper bounds via projected gradient descent.
Branches by bisecting the longest edge of the subregion with the smallest lower bound.
This adaptive approach aims to find certificates with fewer subregions than uniform constructions.

Key Contributions and Results

1. Theoretical Guarantees

Fixed Degree: The paper proves that low-degree disjunctive SOS proofs always exist. The degree of the SOS polynomials in the proof does not need to grow with the hierarchy level; it can be fixed at the degree of the original polynomial.
Convergence: The authors construct a hierarchy of SDPs with fixed-size constraints that converges to the global minimum of a homogeneous polynomial over the unit sphere. They establish a convergence rate of $O(1/m)$ , where $m$ relates to the resolution of the spatial partition.
Optimization-Free Certificates: The second Positivstellensatz provides a method to certify nonnegativity without solving SDPs, relying instead on linear transformations and coefficient nonnegativity checks.

2. Application to Constrained Optimization

Polynomial Optimization: By combining the disjunctive approach with a reduction technique from [2], the authors construct a converging hierarchy of lower bounds for general polynomial optimization problems (POPs) over compact basic semialgebraic sets.
Copositive Programming: The method is specialized to certify the copositivity of matrices (checking $x^T Q x \geq 0$ for $x \geq 0$ ). The authors define a "Disjunctive P+N" condition where a matrix is certified copositive if, on each simplicial subregion of the nonnegative orthant, it can be decomposed into a positive semidefinite and a nonnegative matrix. This yields a complete hierarchy where the size of the SDP constraint remains fixed ( $n \times n$ ), contrasting with existing hierarchies where constraint size grows polynomially with the level.

3. Numerical Experiments

The authors present numerical experiments on:

Non-SOS Polynomials: Algorithms successfully certified the nonnegativity of classical non-SOS polynomials (e.g., Motzkin, Robinson, Choi-Lam, Delzell) using a small number of subregions (often fewer than 20) via the SBB framework.
Copositive Programs: The algorithm solved nonconvex quadratic programs and computed the clique number of graphs (via the Motzkin-Straus theorem) on random instances.
Performance: The results indicate that the disjunctive approach can certify nonnegativity and solve optimization problems with significantly fewer subregions than uniform partitioning, and the SDP constraints remain manageable in size.

Significance and Claims

The paper claims that the disjunctive sum of squares approach offers a viable alternative to traditional SOS hierarchies by decoupling the complexity of the proof (the degree of SOS polynomials) from the number of algebraic identities used.

Computational Efficiency: By keeping the degree of SOS polynomials low and fixed, the size of the underlying SDPs remains constant throughout the hierarchy, avoiding the "curse of dimensionality" associated with increasing polynomial degrees in standard SOS methods.
Flexibility: The framework supports both SDP-based searches (for tighter bounds with fewer regions) and optimization-free searches (for faster, albeit potentially coarser, certificates).
Completeness: The authors prove that this approach is complete; for any strictly positive polynomial (or strictly copositive matrix), a certificate exists within their framework.

The paper concludes by noting that while the theoretical constructions use uniform partitions, the practical SBB algorithm adaptively refines the space, suggesting that instance-specific disjunctions could further reduce the number of required regions. The work opens avenues for combining disjunctive SOS with sparsity and symmetry exploitation, and for exploring the dual moment side of the framework.