Sum of Squares Submodularity

References

• Ahmadi AA, Hall G (2018) DC decomposition of nonconvex polynomials with algebraic techniques. Math. Programming 169(1):69–94.Crossref, Google Scholar
• Ahmadi AA, Parrilo PA (2013) A complete characterization of the gap between convexity and sos-convexity. SIAM J. Optim. 23(2):811–833.Crossref, Google Scholar
• Ahmadi AA, Olshevsky A, Parrilo PA, Tsitsiklis JN (2013) NP-hardness of deciding convexity of quartic polynomials and related problems. Math. Programming 137(1):453–476.Crossref, Google Scholar
• Atamtürk A, Gómez A (2020) Submodularity in conic quadratic mixed 0–1 optimization. Oper. Res. 68(2):609–630.Abstract, Google Scholar
• Bach F (2013) Learning with submodular functions: A convex optimization perspective. Foundations Trends Machine Learn. 6(2–3):145–373.Crossref, Google Scholar
• Bach F (2019) Submodular functions: From discrete to continuous domains. Math. Programming 175(1):419–459.Crossref, Google Scholar
• Balcan MF, Harvey NJ (2011) Learning submodular functions. Fortnow L, Vadhan SP, eds. Proc. 43rd Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 793–802.Google Scholar
• Balcan MF, Harvey NJ (2018) Submodular functions: Learnability, structure, and optimization. SIAM J. Comput. 47(3):703–754.Crossref, Google Scholar
• Bian Y, Buhmann JM, Krause A (2020) Continuous submodular function maximization. Preprint, submitted June 24, https://arxiv.org/abs/2006.13474.Google Scholar
• Bian AA, Buhmann JM, Krause A, Tschiatschek S (2017) Guarantees for greedy maximization of non-submodular functions with applications. Precup D, Teh YW, eds. Internat. Conf. Machine Learn., vol. 70 (PMLR, New York), 498–507.Google Scholar
• Billionnet A, Minoux M (1985) Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions. Discrete Appl. Math. 12(1):1–11.Crossref, Google Scholar
• Bilmes J (2022) Submodularity in machine learning and artificial intelligence. Preprint, submitted January 31, https://arxiv.org/abs/2202.00132v1.Google Scholar
• Blekherman G, Parrilo PA, Thomas RR (2012) Semidefinite Optimization and Convex Algebraic Geometry (SIAM, Philadelphia).Crossref, Google Scholar
• Bomze IM, Locatelli M (2004) Undominated d.c. decompositions of quadratic functions and applications to branch-and-bound approaches. Comput. Optim. Appl. 28(2):227–245.Crossref, Google Scholar
• Boyd SP, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Brandenburg MC, Grillo M, Hertrich C (2024) Decomposition polyhedra of piecewise linear functions. Preprint, submitted October 7, https://arxiv.org/abs/2410.04907v1.Google Scholar
• Burer S, Natarajan K (2025) On the semidefinite representability of continuous quadratic submodular minimization with applications to moment problems. Preprint, submitted April 4, https://arxiv.org/abs/2504.03996v1.Google Scholar
• Chatterjee S, Guntuboyina A, Sen B (2015) On risk bounds in isotonic and other shape restricted regression problems. Ann. Statist. 43(4):1774–1800.Crossref, Google Scholar
• Crama Y (1989) Recognition problems for special classes of polynomials in 0–1 variables. Math. Programming 44(1):139–155.Crossref, Google Scholar
• Crama Y, Hammer PL (2011) Boolean Functions: Theory, Algorithms, and Applications (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Curmei M, Hall G (2025) Shape-constrained regression using sum of squares polynomials. Oper. Res. 73(1):543–559.Link, Google Scholar
• Das A, Kempe D (2018) Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection. J. Machine Learn. Res. 19(3):1–34.Google Scholar
• De A, Chakrabarti S (2022) Neural estimation of submodular functions with applications to differentiable subset selection. Koyejo S, Mohamed S, Agarwal A, Belgrave D, Cho K, Oh A, eds. Adv. Neural Inform. Processing Systems 35 (Curran Associates, Red Hook, NY), 19537–19552.Google Scholar
• Dolhansky BW, Bilmes JA (2016) Deep submodular functions: Definitions and learning. Lee D, Sugiyama M, Luxburg U, Guyon I, Garnett R, eds. Adv. Neural Inform. Processing Systems 29 (Curran Associates, Red Hook, NY), 3404–3412.Google Scholar
• Dunning I, Huchette J, Lubin M (2017) JuMP: A modeling language for mathematical optimization. SIAM Rev. 59(2):295–320.Crossref, Google Scholar
• Edmonds J (2003) Submodular functions, matroids, and certain polyhedra. Jünger M, Reinelt G, Rinaldi G, eds. Combinatorial Optimization—Eureka, You Shrink! (Springer, Berlin), 11–26.Crossref, Google Scholar
• El Halabi M, Orfanides G, Hoheisel T (2023) Difference of submodular minimization via DC programming. Krause A, Brunskill E, Cho K, Engelhardt B, Sabato S, Scarlett J, eds. Proc. 40th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 202 (PMLR, New York), 9172–9201.Google Scholar
• Feldman V, Vondrák J (2016) Optimal bounds on approximation of submodular and XOS functions by juntas. SIAM J. Comput. 45(3):1129–1170.Crossref, Google Scholar
• Feldman V, Kothari P, Vondrák J (2013) Representation, approximation and learning of submodular functions using low-rank decision trees. Shalev-Swartz S, Steinwart I, eds. Proc. 26th Annual Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 30 (PMLR, New York), 711–740.Google Scholar
• Frank A (1993) Submodular functions in graph theory. Discrete Math. 111(1–3):231–243.Crossref, Google Scholar
• Fujishige S (2005) Submodular Functions and Optimization, Annals of Discrete Mathematics, vol. 58 (Elsevier, Amsterdam).Google Scholar
• Gallo G, Simeone B (1989) On the supermodular knapsack problem. Math. Programming 45(1):295–309.Crossref, Google Scholar
• Goemans MX, Harvey NJ, Iwata S, Mirrokni V (2009) Approximating submodular functions everywhere. Mathieu C, ed. Proc. 2009 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 535–544.Google Scholar
• Goujaud B, Moucer C, Glineur F, Hendrickx JM, Taylor AB, Dieuleveut A (2024) PEPit: Computer-assisted worst-case analyses of first-order optimization methods in Python. Math. Programming Comput. 16(3):337–367.Crossref, Google Scholar
• Grabisch M, Marichal JL, Roubens M (2000) Equivalent representations of set functions. Math. Oper. Res. 25(2):157–178.Link, Google Scholar
• Helton JW, Nie J (2010) Semidefinite representation of convex sets. Math. Programming 122(1):21–64.Crossref, Google Scholar
• Horel T, Singer Y (2016) Maximization of approximately submodular functions. Lee D, Sugiyama M, Luxburg U, Guyon I, Garnett R, eds. Adv. Neural Inform. Processing Systems 29 (Curran Associates, Red Hook, NY), 3053–3061.Google Scholar
• Iyer R, Bilmes J (2012) Algorithms for approximate minimization of the difference between submodular functions, with applications. Preprint, submitted July 3, https://arxiv.org/abs/1207.0560v1.Google Scholar
• Jegelka S, Bilmes J (2011) Submodularity beyond submodular energies: Coupling edges in graph cuts. Proc. 2011 IEEE Conf. Comput. Vision Pattern Recognition (IEEE, New York), 1897–1904.Google Scholar
• Krause A, Singh A, Guestrin C (2008) Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. J. Machine Learn. Res. 9(8):235–284.Google Scholar
• Legat B (2020) SumOfSquares.jl: Sum-of-squares optimization in Julia. Accessed May 29, 2026, https://github.com/jump-dev/SumOfSquares.jl.Google Scholar
• Lin H, Bilmes JA (2012) Learning mixtures of submodular shells with application to document summarization. Preprint, submitted October 16, https://arxiv.org/abs/1210.4871.Google Scholar
• Majumdar A, Hall G, Ahmadi AA (2020) Recent scalability improvements for semidefinite programming with applications in machine learning, control, and robotics. Annual Rev. Control Robotics Autonomous Systems 3(1):331–360.Crossref, Google Scholar
• Narasimhan M, Bilmes J (2005) A submodular-supermodular procedure with applications to discriminative structure learning. Bacchus F, Jaakola T, eds. Proc. 21st Conf. Uncertainty Artificial Intelligence (AUAI Press, Arlington, VA), 404–412.Google Scholar
• Narayanan H (1997) Submodular Functions and Electrical Networks, Annals of Discrete Mathematics, vol. 54 (Elsevier, Amsterdam).Google Scholar
• Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions—I. Math. Programming 14(1):265–294.Crossref, Google Scholar
• O’Donoghue B, Chu E, Parikh N, Boyd S (2016) Conic optimization via operator splitting and homogeneous self-dual embedding. J. Optim. Theory Appl. 169(3):1042–1068.Crossref, Google Scholar
• Owen G (1972) Multilinear extensions of games. Management Sci. 18(5-part-2):64–79.Link, Google Scholar
• Punnen AP (2022) The Quadratic Unconstrained Binary Optimization Problem (Springer International Publishing, Cham, Switzerland).Crossref, Google Scholar
• Queyranne M, Schulz AS (1994) Polyhedral approaches to machine scheduling. Preprint 408/1994, Department of Mathematics, Technical University of Berlin, Berlin. Google Scholar
• Rubinstein A, Singla S (2017) Combinatorial prophet inequalities. Klein PN, ed. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1671–1687.Google Scholar
• Schrijver A (2000) A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory Ser. B 80(2):346–355.Crossref, Google Scholar
• Seshadhri C, Vondrák J (2014) Is submodularity testable? Algorithmica 69(1):1–25.Crossref, Google Scholar
• Sipos R, Shivaswamy P, Joachims T (2012) Large-margin learning of submodular summarization models. Daelemans W, ed. Proc. 13th Conf. Eur. Chapter Assoc. Comput. Linguistics (Association for Computational Linguistics, Stroudsburg, PA), 224–233.Google Scholar
• Sipser M (1996) Introduction to the theory of computation. ACM SIGACT News 27(1):27–29.Crossref, Google Scholar
• Stobbe P, Krause A (2012) Learning Fourier sparse set functions. Lawrence ND, Girolami M, eds. Proc. 15th Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 22 (PMLR, New York), 1125–1133.Google Scholar
• Topkis DM (1978) Minimizing a submodular function on a lattice. Oper. Res. 26(2):305–321.Link, Google Scholar
• Topkis DM (1998) Supermodularity and Complementarity (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Tschiatschek S, Iyer RK, Wei H, Bilmes JA (2014) Learning mixtures of submodular functions for image collection summarization. Ghahramani Z, Welling M, Cortes C, Lawrence N, Weinberger K, eds. Adv. Neural Inform. Processing Systems 27 (MIT Press, Cambridge, MA), 1413–1421.Google Scholar
• Yuille AL, Rangarajan A (2003) The concave-convex procedure. Neural Comput. 15(4):915–936.Crossref, Google Scholar