Sum of Squares Submodularity
Operations Research · Tue
Abstract
We introduce the notion of t-sum of squares (sos) submodularity , which is a hierarchy, indexed by t , of sufficient algebraic conditions for certifying submodularity of set functions. We show that, for fixed t , each level of the hierarchy can be verified via a semidefinite program of size polynomial in n , the size of the ground set of the set function. This is particularly relevant given existing results by Crama around testing whether a set function is submodular. We derive several equivalent algebraic characterizations of t -sos submodularity and identify submodularity-preserving operations that also preserve t -sos submodularity. We further present a complete classification of the cases for which submodularity and t -sos submodularity coincide, as well as examples of t -sos-submodular functions. We demonstrate the usefulness of t -sos submodularity through three applications: (i) a new convex approach to submodular regression, involving minimal manual tuning; (ii) a systematic procedure to derive lower bounds on the submodularity ratio in approximate submodular maximization; and (iii) improved difference of submodular decompositions for difference of submodular optimization. Overall, our work builds a new bridge between discrete optimization and real algebraic geometry by connecting sum of squares-based algebraic certificates to a fundamental discrete structure, submodularity. Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2025.2422 .
Keywords
Optimization, submodularity, sum of squares polynomials, approximate submodularity, submodular regression, difference of submodular optimization
Enable JavaScript for citation tools and additional paper interactions.