Non-SOS Positivstellensätze for Semialgebraic Sets Defined by Polynomial Matrix Inequalities

References

• [1] Ahmadi AA, Majumdar A (2019) DSOS and SDSOS optimization: More tractable alternatives to sum of squares and semidefinite optimization. SIAM J. Appl. Algebra Geometry 3(2):193–230.Crossref, Google Scholar
• [2] Andersen ED, Andersen KD (2000) The Mosek interior point optimizer for linear programming: An implementation of the homogeneous algorithm. Frenk H, Roos K, Terlaky T, Zhang S, eds. High Performance Optimization, Applied Optimization, vol. 33 (Springer US, Boston), 197–232.Crossref, Google Scholar
• [3] Barvinok A (2002) A Course in Convexity (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• [4] Basu S, Pollack R, Roy MF (2006) Algorithms in Real Algebraic Geometry (Springer, Berlin).Crossref, Google Scholar
• [5] Blekherman G, Parrilo PA, Thomas RR (2012) Semidefinite Optimization and Convex Algebraic Geometry (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [6] Bochnak J, Coste M, Roy MF (1998) Real Algebraic Geometry (Springer, Berlin).Crossref, Google Scholar
• [7] Chandrasekaran V, Shah P (2016) Relative entropy relaxations for signomial optimization. SIAM J. Optim. 26(2):1147–1173.Crossref, Google Scholar
• [8] Dias da Silva JA, Machado A (2013) Multilinear algebra. Hogben L, ed. Handbook of Linear Algebra, 2nd ed. (Chapman and Hall/CRC, New York), 14-1.Google Scholar
• [9] Dickinson PJC, Povh J (2015) On an extension of Pólya’s Positivstellensatz. J. Global Optim. 61(4):615–625.Crossref, Google Scholar
• [10] Dinh TH, Ho MT, Le CT (2021) Positivstellensätze for polynomial matrices. Positivity 25(4):1295–1312.Crossref, Google Scholar
• [11] Dressler M, Iliman S, de Wolff T (2017) A Positivstellensatz for sums of nonnegative circuit polynomials. SIAM J. Appl. Algebra Geometry 1(1):536–555.Crossref, Google Scholar
• [12] Handelman D (1988) Representing polynomials by positive linear functions on compact convex polyhedra. Pacific J. Math. 132(1):35–62.Crossref, Google Scholar
• [13] Henrion D, Lasserre JB (2006) Convergent relaxations of polynomial matrix inequalities and static output feedback. IEEE Trans. Automatic Control 51(2):192–202.Crossref, Google Scholar
• [14] Henrion D, Lasserre JB (2012) Inner approximations for polynomial matrix inequalities and robust stability regions. IEEE Trans. Automatic Control 57(6):1456–1467.Crossref, Google Scholar
• [15] Henrion D, Korda M, Lasserre JB (2020) The Moment-SOS Hierarchy (World Scientific (Europe), Singapore).Crossref, Google Scholar
• [16] Huang L (2025) On the complexity of matrix Putinar’s Positivstellensätz. SIAM J. Optim. 35(1):567–591.Crossref, Google Scholar
• [17] Huang L, Nie J (2025) Finite convergence of the moment-SOS hierarchy for polynomial matrix optimization. Math. Programming 214:685–722.Crossref, Google Scholar
• [18] Huang L, Nie J, Yuan Y (2023) Homogenization for polynomial optimization with unbounded sets. Math. Programming 200(1):105–145.Crossref, Google Scholar
• [19] Ichihara H (2009) Optimal control for polynomial systems using matrix sum of squares relaxations. IEEE Trans. Automatic Control 54(5):1048–1053.Crossref, Google Scholar
• [20] Klep I, Nie J (2020) A matrix Positivstellensatz with lifting polynomials. SIAM J. Optim. 30(1):240–261.Crossref, Google Scholar
• [21] Kojima M (2003) Sums of squares relaxations of polynomial semidefinite programs. Research Report No. B-397, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo.Google Scholar
• [22] Kojima M, Muramatsu M (2009) A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones. Comput. Optim. Appl. 42(1):31–41.Crossref, Google Scholar
• [23] Krivine JL (1964) Anneaux préordonnés. J. d’Analyse Mathématique 12(1):307–326.Crossref, Google Scholar
• [24] Kuryatnikova O, Vera JC, Zuluaga LF (2024) Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets. SIAM J. Optim. 34(2):1970–2006.Crossref, Google Scholar
• [25] Lasserre JB (2001) Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3):796–817.Crossref, Google Scholar
• [26] Lasserre JB (2002) Semidefinite programming vs. LP relaxations for polynomial programming. Math. Oper. Res. 27(2):347–360.Link, Google Scholar
• [27] Lasserre JB (2005) Polynomial programming: LP-relaxations also converge. SIAM J. Optim. 15(2):383–393.Crossref, Google Scholar
• [28] Lasserre JB (2005) A unified criterion for positive definiteness and semidefiniteness. Research Report No. 05-283, LAAS-CNRS, Toulouse, France.Google Scholar
• [29] Lasserre JB (2009) Moments, Positive Polynomials and Their Applications (Imperial College Press, London).Crossref, Google Scholar
• [30] Lasserre JB (2015) An Introduction to Polynomial and Semi-Algebraic Optimization, Cambridge Texts in Applied Mathematics (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [31] Lasserre JB, Toh KC, Yang S (2017) A bounded degree SOS hierarchy for polynomial optimization. EURO J. Comput. Optim. 5(1):87–117.Crossref, Google Scholar
• [32] Laurent M (2009) Sums of squares, moment matrices and optimization over polynomials. Putinar M, Sullivant S, eds. Emerging Applications of Algebraic Geometry, IMA Volumes in Mathematics and Its Applications, vol. 149 (Springer, New York), 157–270.Crossref, Google Scholar
• [33] Lê CT, Dư THB (2018) Handelman’s Positivstellensatz for polynomial matrices positive definite on polyhedra. Positivity 22(2):449–460.Crossref, Google Scholar
• [34] Löfberg J (2004) YALMIP: A toolbox for modeling and optimization in MATLAB. 2004 IEEE Internat. Sympos. Comput. Aided Control System Design (IEEE, Taipei, Taiwan), 284–289.Google Scholar
• [35] Mai NHA, Lasserre JB, Magron V (2022) Positivity certificates and polynomial optimization on non-compact semialgebraic sets. Math. Programming 194(1):443–485.Crossref, Google Scholar
• [36] Marshall M (2008) Positive Polynomials and Sums of Squares, Mathematical Surveys and Monographs, vol. 146 (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• [37] Nie J (2023) Moment and Polynomial Optimization (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [38] Pólya G (1928) Über positive darstellung von polynomen. Vierteljahrsschrift Naturforschenden Gesellschaft Zürich 73:141–145.Google Scholar
• [39] Pozdyayev VV (2014) Atomic optimization. II. Multidimensional problems and polynomial matrix inequalities. Automation Remote Control 75(6):1155–1171.Crossref, Google Scholar
• [40] Putinar M (1993) Positive polynomials on compact semialgebraic sets. Indiana Univ. Math. J. 42(3):969–984.Crossref, Google Scholar
• [41] Putinar M, Vasilescu FH (1999) Solving moment problems by dimensional extension. Comptes Rendus l’Académie Sci. Ser. I Math. 328(6):495–499.Google Scholar
• [42] Ramana M, Goldman AJ (1995) Some geometric results in semidefinite programming. J. Global Optim. 7(1):33–50.Crossref, Google Scholar
• [43] Reznick B (1995) Uniform denominators in Hilbert’s seventeenth problem. Mathematische Zeitschrift 220(1):75–97.Crossref, Google Scholar
• [44] Roebers LM, Vera JC, Zuluaga LF (2021) Sparse non-SOS Putinar-type Positivstellensätze. Preprint October 12, https://arxiv.org/abs/2110.10079.Google Scholar
• [45] Scheiderer C (2009) Positivity and sums of squares: A guide to recent results. Putinar M, Sullivant S, eds. Emerging Applications of Algebraic Geometry, IMA Volumes in Mathematics and Its Applications, vol. 149 (Springer, New York), 1–54.Crossref, Google Scholar
• [46] Scherer CW, Hol CWJ (2006) Matrix sum-of-squares relaxations for robust semi-definite programs. Math. Programming 107(1):189–211.Crossref, Google Scholar
• [47] Schmüdgen K (1991) The K-moment problem for compact semi-algebraic sets. Mathematische Annalen 289(1):203–206.Crossref, Google Scholar
• [48] Stengle G (1974) A nullstellensatz and a positivstellensatz in semialgebraic geometry. Mathematische Annalen 207(2):87–97.Crossref, Google Scholar
• [49] VanAntwerp JG, Braatz RD (2000) A tutorial on linear and bilinear matrix inequalities. J. Process Control 10(4):363–385.Crossref, Google Scholar
• [50] Vasilescu FH (2003) Spectral measures and moment problems. Gheondea A, Şabac M, eds. Spectral Analysis and Its Applications (Theta Foundation, Bucharest, Romania), 173–215.Google Scholar
• [51] Weisser T, Lasserre JB, Toh KC (2018) Sparse-BSOS: A bounded degree SOS hierarchy for large scale polynomial optimization with sparsity. Math. Programming Comput. 10(1):1–32.Crossref, Google Scholar
• [52] Zheng Y (2019) Chordal sparsity in control and optimization of large-scale systems. PhD thesis, University of Oxford, Oxford, UK.Google Scholar
• [53] Zheng Y, Fantuzzi G (2023) Sum-of-squares chordal decomposition of polynomial matrix inequalities. Math. Programming 197(1):71–108.Crossref, Google Scholar