Open Journal of Mathematical Optimization

Unifying view on sparse convex relaxations in polynomial optimization
Gennadiy Averkov1; Benjamin Peters2; Sebastian Sager2, 3
1Fakultät 1, Brandenburgische Technische Universität Cottbus-Senftenberg, Germany
2Otto-von-Guericke Universität Magdeburg, Germany
3Max Planck Institute for the Dynamics of Complex Technical Systems Magdeburg, Germany
Open Journal of Mathematical Optimization, Volume 7 (2026), article no. 2, 44 p.

We present a novel, general, and unifying point of view and use it to surveys parse and dual approaches to polynomial optimization. Solving polynomial optimization problems to global optimality is a ubiquitous challenge in many areas of science and engineering. Different approaches on how to solve nonconvex polynomial optimization problems based on convex relaxations have been developed in different scientific communities. Here, we introduce the concept of monomial patterns. A pattern determines what monomials are to be linked by convex constraints in a convex relaxation of a polynomial optimization problem. This concept helps understanding existing approaches from different schools of thought, developing novel relaxation schemes, and deriving a flexible duality theory, which can be specialized to many concrete situations that have been considered in the literature. We survey different approaches to polynomial optimization including polyhedral approximations, dense semidefinite relaxations, SONC, SAGE, and TSSOS in a self-contained, unifying exposition.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/ojmo.50
Keywords: Polynomial optimization, nonlinear optimization, convexification, sparsity, duality, sum of squares, SONC, SAGE, TSSOS, SDSOS

Gennadiy Averkov  1 ; Benjamin Peters  2 ; Sebastian Sager  2 , 3

1 Fakultät 1, Brandenburgische Technische Universität Cottbus-Senftenberg, Germany
2 Otto-von-Guericke Universität Magdeburg, Germany
3 Max Planck Institute for the Dynamics of Complex Technical Systems Magdeburg, Germany
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
Gennadiy Averkov; Benjamin Peters; Sebastian Sager. Unifying view on sparse convex relaxations in polynomial optimization. Open Journal of Mathematical Optimization, Volume 7 (2026), article  no. 2, 44 p.. doi: 10.5802/ojmo.50
@article{OJMO_2026__7__A2_0,
     author = {Gennadiy Averkov and Benjamin Peters and Sebastian Sager},
     title = {Unifying view on sparse convex relaxations in polynomial optimization},
     journal = {Open Journal of Mathematical Optimization},
     eid = {2},
     pages = {1--44},
     year = {2026},
     publisher = {Universit\'e de Montpellier},
     volume = {7},
     doi = {10.5802/ojmo.50},
     language = {en},
     url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.50/}
}
TY  - JOUR
AU  - Gennadiy Averkov
AU  - Benjamin Peters
AU  - Sebastian Sager
TI  - Unifying view on sparse convex relaxations in polynomial optimization
JO  - Open Journal of Mathematical Optimization
PY  - 2026
SP  - 1
EP  - 44
VL  - 7
PB  - Université de Montpellier
UR  - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.50/
DO  - 10.5802/ojmo.50
LA  - en
ID  - OJMO_2026__7__A2_0
ER  - 
%0 Journal Article
%A Gennadiy Averkov
%A Benjamin Peters
%A Sebastian Sager
%T Unifying view on sparse convex relaxations in polynomial optimization
%J Open Journal of Mathematical Optimization
%] 2
%D 2026
%P 1-44
%V 7
%I Université de Montpellier
%U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.50/
%R 10.5802/ojmo.50
%G en
%F OJMO_2026__7__A2_0

[1] C. S. Adjiman; I. P. Androulakis; C. A. Floudas A global optimization method, αBB, for general twice-differentiable constrained NLPs – II. Implementation and computational results, Comput. Chem. Eng., Volume 22 (1998) no. 9, pp. 1159-1179 http://www.sciencedirect.com/... | DOI

[2] Amir Ali Ahmadi; Cemil Dibek; Georgina Hall Sums of separable and quadratic polynomials, Math. Oper. Res., Volume 48 (2023) no. 3, pp. 1316-1343 | DOI | Zbl | MR

[3] Amir Ali Ahmadi; Anirudha Majumdar DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization, SIAM J. Appl. Algebra Geom., Volume 3 (2019) no. 2, pp. 193-230 | DOI | Zbl | MR

[4] Martin Andersen; Joachim Dahl; Zhang Liu; Lieven Vandenberghe Interior-point methods for large-scale cone programming, Optimization for machine learning (Neural Information Processing series), MIT Press (2011) | DOI

[5] Handbook on semidefinite, conic and polynomial optimization (Miguel F. Anjos; Jean B. Lasserre, eds.), International Series in Operations Research & Management Science, 166, Springer, 2012, xii+960 pages | DOI | MR | Zbl

[6] Mosek ApS Mosek modeling cookbook, 2020

[7] Johannes Aspman; Gilles Bareilles; Vyacheslav Kungurtsev; Jakub Marecek; Martin Takáč Hybrid methods in polynomial optimisation (2023) | arXiv | Zbl

[8] Gennadiy Averkov Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization, SIAM J. Appl. Algebra Geom., Volume 3 (2019) no. 1, pp. 128-151 | DOI | MR | Zbl

[9] Gennadiy Averkov; Claus Scheiderer Convex hulls of monomial curves, and a sparse positivstellensatz, Math. Program., Volume 209 (2025) no. 1-2, pp. 113-131 | Zbl | DOI | MR

[10] Xiaowei Bao; Aida Khajavirad; Nikolaos V. Sahinidis; Mohit Tawarmalani Global optimization of nonconvex problems with multilinear intermediates, Math. Program. Comput., Volume 7 (2015) no. 1, pp. 1-37 | Zbl | MR

[11] P. Belotti Couenne, an exact solver for nonconvex MINLPs, 2015 (IBM and Carnegie Mellon University, https://projects.coin-or.org/Couenne/)

[12] Aharon Ben-Tal; Arkadi Nemirovski Lectures on modern convex optimization: analysis, algorithms, and engineering applications, Society for Industrial and Applied Mathematics, 2001 | DOI | Zbl | MR

[13] Semidefinite optimization and convex algebraic geometry (Grigoriy Blekherman; Pablo A. Parrilo; Rekha R. Thomas, eds.), MOS-SIAM Series on Optimization, 13, Society for Industrial and Applied Mathematics; Mathematical Optimization Society, Philadelphia, PA, 2013, xx+476 pages | MR | Zbl | DOI

[14] Natashia Boland; Santanu S. Dey; Thomas Kalinowski; Marco Molinaro; Fabian Rigterink Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions, Math. Program., Volume 162 (2017) no. 1-2, pp. 523-535 | DOI | Zbl | MR

[15] Venkat Chandrasekaran; Parikshit Shah Relative entropy relaxations for signomial optimization, SIAM J. Optim., Volume 26 (2016) no. 2, pp. 1147-1173 | DOI | MR | Zbl

[16] Evrim Dalkiran; Hanif D. Sherali Theoretical filtering of RLT bound-factor constraints for solving polynomial programming problems to global optimality, J. Glob. Optim., Volume 57 (2013) no. 4, pp. 1147-1172 | MR | DOI | Zbl

[17] Steven Diamond; Stephen Boyd CVXPY: A Python-embedded modeling language for convex optimization, J. Mach. Learn. Res., Volume 17 (2016), 83, 5 pages | MR | Zbl

[18] H. Diedam; S. Sager Global optimal control with the direct multiple shooting method, Optim. Control Appl. Methods, Volume 39 (2018) no. 2, pp. 449-470 | DOI | Zbl | MR

[19] Mareike Dressler; Sadik Iliman; Timo de Wolff A Positivstellensatz for sums of nonnegative circuit polynomials, SIAM J. Appl. Algebra Geom., Volume 1 (2017) no. 1, pp. 536-555 | DOI | MR | Zbl

[20] W. R. Esposito; C. A. Floudas Deterministic Global Optimization in Nonlinear Optimal Control Problems, J. Glob. Optim., Volume 17 (2000) no. 1–4, pp. 97-126 http://titan.princeton.edu/research.htm | DOI | Zbl | MR

[21] W. R. Esposito; C. A. Floudas Global Optimization for the Parameter Estimation of Differential-Algebraic Systems, Ind. Eng. Chem. Res., Volume 39 (2000) no. 5, pp. 1291-1310 http://titan.princeton.edu/research.htm | DOI

[22] Hamza Fawzi On representing the positive semidefinite cone using the second-order cone, Math. Program., Volume 175 (2019) no. 1-2, pp. 109-118 | DOI | Zbl | MR

[23] Michael Garstka; Mark Cannon; Paul Goulart COSMO: A conic operator splitting method for convex conic problems, J. Optim. Theory Appl., Volume 190 (2021) no. 3, pp. 779-810 | DOI | MR | Zbl

[24] Bernd Gärtner; Jiri Matousek Approximation algorithms and semidefinite programming, Springer, 2012 | Zbl | MR

[25] Michel X Goemans; David P Williamson Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach., Volume 42 (1995) no. 6, pp. 1115-1145 | DOI | Zbl | MR

[26] Paul Goulart; Yuwen Chen Clarabel: An interior-point solver for conic programs with quadratic objectives (2024) | arXiv | Zbl

[27] Michael Grant; Stephen Boyd CVX: Matlab Software for Disciplined Convex Programming, version 2.1, http://cvxr.com/cvx, 2014

[28] Sander Gribling; Sven Polak Mutually unbiased bases: polynomial optimization and symmetry, Quantum, Volume 8 (2024), p. 1318 | DOI

[29] David Handelman Representing polynomials by positive linear functions on compact convex polyhedra, Pac. J. Math., Volume 132 (1988) no. 1, pp. 35-62 | DOI | Zbl | MR

[30] Didier Henrion; Jean-Bernard Lasserre; Johan Löfberg GloptiPoly 3: moments, optimization and semidefinite programming, Optim. Methods Softw., Volume 24 (2009) no. 4-5, pp. 761-779 | Zbl | DOI | MR

[31] Marie Ioannou; Denis Rosset Noncommutative polynomial optimization under symmetry (2021) | arXiv

[32] Shucheng Kang; Guorui Liu; Heng Yang Global contact-rich planning with sparsity-rich semidefinite relaxations (2025) | arXiv

[33] Shucheng Kang; Guorui Liu; Heng Yang Global contact-Rich planning with sparsity-rich semidefinite relaxations, Robotics: Science and Systems (2025) (paper ID 46)

[34] Lukas Katthän; Helen Naumann; Thorsten Theobald A unified framework of SAGE and SONC polynomials and its duality theory, Math. Comput., Volume 90 (2021) no. 329, pp. 1297-1322 | DOI | MR | Zbl

[35] A. H. Land; A. G. Doig An automatic method of solving discrete programming problems, Econometrica, Volume 28 (1960), pp. 497-520 | DOI | Zbl | MR

[36] Jean B. Lasserre Global optimization with polynomials and the problem of moments, SIAM J. Optim., Volume 11 (2001) no. 3, pp. 796-817 | DOI | Zbl | MR

[37] Jean B. Lasserre Moments, positive polynomials and their applications, Imperial College Press Optimization Series, 1, Imperial College Press, 2010 | Zbl | MR

[38] Jean B. Lasserre An introduction to polynomial and semi-algebraic optimization, Cambridge Texts in Applied Mathematics, Cambridge University Press, 2015, xiv+339 pages | DOI | MR

[39] Monique Laurent Sums of squares, moment matrices and optimization over polynomials, Emerging applications of algebraic geometry (The IMA Volumes in Mathematics and its Applications), Volume 149, Springer, 2009, pp. 157-270 | DOI | MR | Zbl

[40] Benoît Legat; Chris Coey; Robin Deits; Joey Huchette; Amelia Perry Sum-of-squares optimization in Julia, The First Annual JuMP-dev Workshop (2017)

[41] John D. C. Little; Katta G. Murty; Dura W. Sweeney; Caroline Karel An Algorithm for the Traveling Salesman Problem, Oper. Res., Volume 11 (1963) no. 6, pp. 972-989 | DOI | Zbl

[42] Johan Löfberg YALMIP: A Toolbox for Modeling and Optimization in MATLAB, Proceedings of the CACSD Conference (2004), pp. 284-289 | DOI

[43] Benoît Lubin; Oscar Dowson; Joaquim Garcia Garcia; Joey Huchette; Miles Lubin; Juan P. Vielma JuMP 1.0: recent improvements to a modeling language for mathematical optimization, Math. Program. Comput., Volume 15 (2023) no. 3, pp. 581-589 | DOI | Zbl | MR

[44] Victor Magron; Jie Wang TSSOS: a Julia library to exploit sparsity for large-scale polynomial optimization (2021) | arXiv

[45] Victor Magron; Jie Wang Sparse polynomial optimization: theory and practice, World Scientific, 2023 | DOI | Zbl | MR

[46] Murray Marshall Positive polynomials and sums of squares, Mathematical Surveys and Monographs, 146, American Mathematical Society, 2008, xii+187 pages | DOI | MR | Zbl

[47] A. Mitsos; B. Chachuat; P. I. Barton McCormick-Based Relaxations of Algorithms, SIAM J. Optim., Volume 20 (2009) no. 2, pp. 573-601 | DOI | Zbl | MR

[48] Hans D. Mittelmann; Frank Vallentin High-accuracy semidefinite programming bounds for kissing numbers, Exp. Math., Volume 19 (2010) no. 2, pp. 175-179 | MR | DOI | Zbl

[49] R. E. Moore Interval analysis, Prentice Hall, 1966 | Zbl | MR

[50] MOSEK ApS The MOSEK optimization toolbox for MATLAB manual. Version 9.0., 2019 (http://docs.mosek.com/9.0/toolbox/index.html)

[51] Philippe Moustrou; Cordian Riener; Hugues Verdure Symmetries in polynomial optimization, Polynomial Optimization, Moments, and Applications, Springer, 2023, pp. 53-111 | DOI

[52] A. Neumaier Complete Search in Continuous Global Optimization and Constraint Satisfaction, Acta Numer., Volume 13 (2004), pp. 271-369 | Zbl | DOI | MR

[53] Jiawang Nie Moment and Polynomial Optimization, Society for Industrial and Applied Mathematics, 2023 (MOS-SIAM Series on Optimization) | MR

[54] B. O’Donoghue; E. Chu; N. Parikh; S. Boyd Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding, J. Optim. Theory Appl., Volume 169 (2016) no. 3, pp. 1042-1068 | DOI | Zbl | MR

[55] I. Papamichail; C. S. Adjiman A Rigorous Global Optimization Algorithm for Problems with Ordinary Differential Equations, J. Glob. Optim., Volume 24 (2002) no. 1, pp. 1-33 | DOI | Zbl | MR

[56] B. Peters Monomial Patterns in Polynomial Optimization, Ph. D. Thesis, Otto von Guericke University Magdeburg (2021) https://mathopt.de/publications/Peters2021.pdf

[57] Stephen Prajna; Antonis Papachristodoulou; Peter Seiler; Pablo A. Parrilo New developments in sum of squares optimization and SOSTOOLS, Proceedings of the 2004 American control conference. Vol. 6, IEEE Press (2004), pp. 5606-5611 | DOI

[58] Mihai Putinar Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., Volume 42 (1993) no. 3, pp. 969-984 | DOI | MR | Zbl

[59] Prasad Raghavendra Optimal algorithms and inapproximability results for every CSP?, Proceedings of the fortieth annual ACM symposium on Theory of computing, ACM Press (2008), pp. 245-254 | DOI | Zbl

[60] Cordian Riener; Thorsten Theobald; Lina Jansson Andrén; Jean B. Lasserre Exploiting symmetries in SDP-relaxations for polynomial optimization, Math. Oper. Res., Volume 38 (2013) no. 1, pp. 122-141 | MR | Zbl | DOI

[61] Nikolaos V. Sahinidis BARON 17.8.9: Global Optimization of Mixed-Integer Nonlinear Programs, Users Manual, 2017

[62] James Saunderson Limitations on the expressive power of convex cones without long chains of faces, SIAM J. Optim., Volume 30 (2020) no. 1, pp. 1033-1047 | Zbl | DOI | MR

[63] Rolf Schneider Convex bodies: the Brunn-Minkowski theory, Encyclopedia of Mathematics and Its Applications, 151, Cambridge University Press, 2014, xxii+736 pages | Zbl | MR

[64] Joseph K. Scott; Matthew D. Stuber; Paul I. Barton Generalized McCormick relaxations, J. Glob. Optim., Volume 51 (2011) no. 4, pp. 569-606 | Zbl | DOI | MR

[65] Henning Seidler; Timo de Wolff An Experimental Comparison of SONC and SOS Certificates for Unconstrained Optimization (2018) | arXiv

[66] Daria Shaydurova; Volker Kaibel; Sebastian Sager Refined TSSOS, SIAM J. Optim., Volume 35 (2025) no. 2, pp. 1246-1273 | MR | DOI | Zbl

[67] Hanif D. Sherali; Warren P. Adams A reformulation-linearization technique for solving discrete and continuous nonconvex problems, Nonconvex Optimization and Its Applications, 31, Springer, 2013 | Zbl | MR

[68] Edward M. B. Smith; Costas C. Pantelides; Gintaras Reklaitis A symbolic reformulation spatial branch-and-bound algorithm for the global optimization of nonconvex MINLPs, Comput. Chem. Eng., Volume 25 (2001), pp. 1399-1401 | DOI

[69] Jos F. Sturm Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., Volume 11 (1999) no. 1-4, pp. 625-653 | MR | Zbl | DOI

[70] Ole Tange GNU Parallel 20201022, 2020 (GNU Parallel is a general parallelizer to run multiple serial command line programs in parallel without changing them.) | DOI

[71] Mohit Tawarmalani; Nikolaos V. Sahinidis A polyhedral branch-and-cut approach to global optimization, Math. Program., Volume 103 (2005), pp. 225-249 | DOI | Zbl | MR

[72] Mohit Tawarmalani; Nikolaos V. Sahinidis A polyhedral branch-and-cut approach to global optimization, Math. Program., Volume 103 (2005) no. 2, pp. 225-249 | MR | DOI | Zbl

[73] Mohit Tawarmalani; Nikolaos V. Sahinidis Convexification and global optimization in continuous and mixed-integer nonlinear programming: theory, algorithms, software, and applications, Nonconvex Optimization and Its Applications, 65, Springer, 2013 | Zbl | MR

[74] The Mathworks, Inc. MATLAB version 9.6.0.1174912 (R2019a) Update 5, 2019

[75] Kim-Chuan Toh; Michael J. Todd; Reha H. Tütüncü SDPT3—a MATLAB software package for semidefinite programming, version 2.1, Optim. Methods Softw., Volume 11 (1999) no. 1-4, pp. 545-581 | Zbl | MR

[76] Lloyd N. Trefethen Approximation Theory and Approximation Practice, Extended Edition, Society for Industrial and Applied Mathematics, 2019 | DOI | MR

[77] Lieven Vandenberghe; Martin Andersen et al. Chordal graphs and semidefinite optimization, Found. Trends Optim., Volume 1 (2015) no. 4, pp. 241-433 | DOI

[78] Stefan Vigerske; Ambros Gleixner SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework, Optim. Methods Softw., Volume 33 (2018) no. 3, pp. 563-593 | DOI | Zbl | MR

[79] Hayato Waki; Sunyoung Kim; Masakazu Kojima; Masakazu Muramatsu Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity, SIAM J. Optim., Volume 17 (2006) no. 1, pp. 218-242 | Zbl | DOI | MR

[80] Hayato Waki; Sunyoung Kim; Masakazu Kojima; Masakazu Muramatsu; Hiroshi Sugimoto Algorithm 883: SparsePOP—a software package for polynomial optimization problems with structured sparsity, ACM Trans. Math. Softw., Volume 35 (2008) no. 2, pp. 1-13 | DOI

[81] Jie Wang; Victor Magron; Jean-Bernard Lasserre Chordal-TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity with Chordal Extension, SIAM J. Optim., Volume 31 (2021) no. 1, pp. 114-141 | DOI | MR | Zbl

[82] Henry Wolkowicz; Romesh Saigal; Lieven Vandenberghe Handbook of semidefinite programming: theory, algorithms, and applications, International Series in Operations Research & Management Science, 27, Springer, 2012 | Zbl

[83] Chenyang Yuan SumOfSquares.py (https://github.com/yuanchenyang/SumOfSquares.py)

[84] Yang Zheng; Giovanni Fantuzzi; Antonis Papachristodoulou Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization, Annu. Rev. Control, Volume 52 (2021), pp. 243-279 | DOI | MR

Cited by Sources: