Exactness and Effective Degree Bound of Lasserre’s Relaxation for Polynomial Optimization over Finite Variety

References

• [1] Atiyah MF, Macdonald IG (1969) Introduction to Commutative Algebra (Addison-Wesley, Reading, MA).Google Scholar
• [2] Baldi L (2022) Représentations effectives en géométrie algébrique réelle et optimisation polynomiale. PhD thesis, Université Côte d’Azur, Nice, France.Google Scholar
• [3] Baldi L, Mourrain B (2023) On the effective Putinar’s Positivstellensatz and moment approximation. Math. Programming 200(1):71–103.Crossref, Google Scholar
• [4] Baldi L, Mourrain B (2025) Exact moment representation in polynomial optimization. J. Symbolic Comput. 129:102403.Crossref, Google Scholar
• [5] Baldi L, Slot L (2024) Degree bounds for Putinar’s Positivstellensatz on the hypercube. SIAM J. Appl. Algebra Geometry 8(1):1–25.Crossref, Google Scholar
• [6] Cox DA, Little J, O’Shea D (1998) Using Algebraic Geometry, Graduate Texts in Mathematics, vol. 185, 1st ed. (Springer, New York).Crossref, Google Scholar
• [7] Cox DA, Little J, O’Shea D (2015) Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 4th ed. (Springer, Cham, Switzerland).Crossref, Google Scholar
• [8] Curto R, Fialkow L (1996) Memoirs of the American Mathematical Society, vol. 568 (American Mathematical Society, Providence, RI).Google Scholar
• [9] de Castro Y, Gamboa F (2012) Exact reconstruction using Beurling minimal extrapolation. J. Math. Anal. Appl. 395(1):336–354.Crossref, Google Scholar
• [10] Demmel J, Nie J, Powers V (2007) Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals. J. Pure Appl. Algebra 209(1):189–200.Crossref, Google Scholar
• [11] Ed K, Laurent M (2019) A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis. Araujo C, Benkart G, Praeger CE, Tanbay B, eds. World Women Math. 2018 Proc. First World Meeting Women Math. (WM)² (Springer, Cham, Switzerland), 17–56.Google Scholar
• [12] Eisenbud D (1995) Commutative Algebra: With a View Toward Algebraic Geometry, Graduate Texts in Mathematics, vol. 150 (Springer, New York).Crossref, Google Scholar
• [13] Eisenbud D, Evans EG (1973) Every algebraic set in n-space is the intersection of n hypersurfaces. Inventiones Mathematicae 19:107–112.Crossref, Google Scholar
• [14] Fang K, Fawzi H (2021) The sum-of-squares hierarchy on the sphere and applications in quantum information theory. Math. Programming 190(1):331–360.Crossref, Google Scholar
• [15] Fawzi H, Saunderson J, Parrilo PA (2016) Sparse sums of squares on finite abelian groups and improved semidefinite lifts. Math. Programming 160(1):149–191.Crossref, Google Scholar
• [16] Fröberg R (1998) An Introduction to Gröbner Bases, Pure and Applied Mathematics (John Wiley & Sons, Chichester, UK).Google Scholar
• [17] García H, Hernández C, Junca M, Velasco M (2021) Approximate super-resolution of positive measures in all dimensions. Appl. Comput. Harmonic Anal. 52:251–278.Crossref, Google Scholar
• [18] Josz C, Henrion D (2016) Strong duality in Lasserre’s hierarchy for polynomial optimization. Optim. Lett. 10(1):3–10.Crossref, Google Scholar
• [19] Korda M, Henrion D, Jones CN (2017) Convergence rates of moment-sum-of-squares hierarchies for optimal control problems. Systems Control Lett. 100:1–5.Crossref, Google Scholar
• [20] Lasserre JB (2001) Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3):796–817.Crossref, Google Scholar
• [21] Lasserre JB (2002) Polynomials nonnegative on a grid and discrete optimization. Trans. Amer. Math. Soc. 354(2):631–649.Crossref, Google Scholar
• [22] Lasserre JB, Laurent M, Rostalski P (2008) Semidefinite characterization and computation of zero-dimensional real radical ideals. Foundations Comput. Math. 8:607–647.Crossref, Google Scholar
• [23] Laurent M (2005) Revisiting two theorems of Curto and Fialkow on moment matrices. Proc. Amer. Math. Soc. 133(10):2965–2976.Crossref, Google Scholar
• [24] Laurent M (2007) Semidefinite representations for finite varieties. Math. Programming 109(1):1–26.Crossref, Google Scholar
• [25] Laurent M, Rostalski P (2012) The approach of moments for polynomial equations. Anjos MF, Lasserre JB, eds. Handbook on Semidefinite, Conic and Polynomial Optimization (Springer, Cham, Switzerland), 25–60.Crossref, Google Scholar
• [26] Laurent M, Slot L (2024) Convergence rates of sums of squares hierarchies for polynomial optimization. Preprint, submitted August 8, https://arxiv.org/abs/2408.04417v1.Google Scholar
• [27] Magron V, Din MSE, Vu TH (2023) Sum of squares decompositions of polynomials over their gradient ideals with rational coefficients. SIAM J. Optim. 33(1):63–88.Crossref, Google Scholar
• [28] 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
• [29] Marshall M (2006) Representations of non-negative polynomials having finitely many zeros. Annales Faculté Sciences Toulouse Mathématiques 15(3):599–609.Crossref, Google Scholar
• [30] Marshall M (2008) Positive Polynomials and Sums of Squares, Mathematical Surveys and Monographs, vol. 146 (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• [31] Marshall M (2009) Representations of non-negative polynomials, degree bounds and applications to optimization. Canadian J. Math. 61(1):205–221.Crossref, Google Scholar
• [32] Möller HM, Sauer T (2000) H-bases for polynomial interpolation and system solving. Adv. Comput. Math. 12(4):335–362.Crossref, Google Scholar
• [33] Nie J (2013) An exact Jacobian SDP relaxation for polynomial optimization. Math. Programming 137(1):225–255.Crossref, Google Scholar
• [34] Nie J (2013) Certifying convergence of Lasserre’s hierarchy via flat truncation. Math. Programming 142(1):485–510.Crossref, Google Scholar
• [35] Nie J (2013) Polynomial optimization with real varieties. SIAM J. Optim. 23(3):1634–1646.Crossref, Google Scholar
• [36] Nie J (2014) Optimality conditions and finite convergence of Lasserre’s hierarchy. Math. Programming 146(1):97–121.Crossref, Google Scholar
• [37] Nie J (2019) Tight relaxations for polynomial optimization and Lagrange multiplier expressions. Math. Programming 178(1):1–37.Crossref, Google Scholar
• [38] Nie J, Schweighofer M (2007) On the complexity of Putinar’s Positivstellensatz. J. Complexity 23(1):135–150.Crossref, Google Scholar
• [39] Nie J, Demmel J, Sturmfels B (2006) Minimizing polynomials via sum of squares over the gradient ideal. Math. Programming 106(3):587–606.Crossref, Google Scholar
• [40] Parrilo PA (2002) An explicit construction of distinguished representations of polynomials nonnegative over finite sets. Working paper, ETH Zurich, Zurich.Google Scholar
• [41] Putinar M (1993) Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42(3):969–984.Crossref, Google Scholar
• [42] Sakaue S, Takeda A, Kim S, Ito N (2017) Exact semidefinite programming relaxations with truncated moment matrix for binary polynomial optimization problems. SIAM J. Optim. 27(1):565–582.Crossref, Google Scholar
• [43] Scheiderer C (2005) Distinguished representations of non-negative polynomials. J. Algebra 289(2):558–573.Crossref, Google Scholar
• [44] Schweighofer M (2005) Optimization of polynomials on compact semialgebraic sets. SIAM J. Optim. 15(3):805–825.Crossref, Google Scholar
• [45] Slot L (2022) Sum-of-squares hierarchies for polynomial optimization and the Christoffel–Darboux kernel. SIAM J. Optim. 32(4):2612–2635.Crossref, Google Scholar