Algorithms for Testing Membership in Univariate Quadratic Modules over the Reals
Pages 429 - 437
Abstract
Quadratic modules in real algebraic geometry are akin to polynomial ideals in algebraic geometry, and have been found useful in the theory of Positivstellensatz to study Hilbert's 17th problem. Algorithms are presented in this paper for testing membership in univariate finitely generated quadratic modules over the reals and inclusion of two finitely generated quadratic modules. For a univariate unbounded quadratic module, an explicit upper bound on the degrees of sums of squares to construct any given polynomial is proved and then used to design an algorithm for testing membership in such a quadratic module. For a bounded quadratic module, a unique signature is associated with it based on the real values on which its finite basis is non-negative, and the signatures are used to furnish a criterion for inclusion of two finitely generated quadratic modules and a corresponding algorithm which solves the membership problem as a special case. It is also shown that a bounded quadratic module can be transformed to an equivalent one with two generators with an algorithm for performing this transformation. All the presented algorithms have been implemented.
References
[1]
Emil Artin. 1927. Über die Zerlegung definiter Funktionen in Quadrate. Abhandlungen aus dem mathematischen Seminar der Universit"at Hamburg, Vol. 5, 1 (1927), 100--115.
[2]
Doris Augustin. 2008. The Membership Problem for Quadratic Modules with Focus on the One Dimensional Case. Ph.,D. Dissertation. University of Regensburg.
[3]
Jacek Bochnak, Michel Coste, and Marie-Francc oise Roy. 2013. Real Algebraic Geometry. Springer Science & Business Media.
[4]
Maria Eugenia Canto Cabral. 2005. Archimedean Quadratic Modules: A Decision Problem in Dimension Two. Ph.,D. Dissertation. University of Konstanz.
[5]
George Collins and Hoon Hong. 1991. Partial cylindrical algebraic decomposition for quantifier elimination. Journal of Symbolic Computation, Vol. 12, 3 (1991), 299--328.
[6]
Thomas Jacobi. 1999. Uber die Darstellung strikt positiver Polynome auf semialgebraischen Kompakta. Ph.,D. Dissertation. University of Konstanz.
[7]
Thomas Jacobi and Alexander Prestel. 2001. Distinguished representations of strictly positive polynomials. Journal für die reine und angewandte Mathematik, Vol. 532 (2001), 223--235.
[8]
Jean-Louis Krivine. 1964. Anneaux préordonnés. Journal d'Analyse Mathématique, Vol. 12, 1 (1964), 307--326.
[9]
Jean-Bernard Lasserre. 2001. Global optimization with polynomials and the problem of moments. SIAM Journal on optimization, Vol. 11, 3 (2001), 796--817.
[10]
Henri Lombardi, Daniel Perrucci, and Marie-Francc oise Roy. 2020. An Elementary Recursive Bound for Effective Positivstellensatz and Hilbert's 17th Problem. Memoirs of the American Mathematical Society, Vol. 263. American Mathematical Society.
[11]
Victor Magron, Mohab Safey El Din, and Markus Schweighofer. 2019. Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials. Journal of Symbolic Computation, Vol. 93 (2019), 200--220.
[12]
Ngoc Hoang Anh Mai and Victor Magron. 2022. On the complexity of Putinar--Vasilescu's Positivstellensatz. Journal of Complexity (2022), in press.
[13]
Murray Marshall. 2008. Positive Polynomials and Sums of Squares. Mathematical Surveys and Monographs, Vol. 146. American Mathematical Society.
[14]
Tim Netzer. 2009. Stability of quadratic modules. Manuscripta Mathematica, Vol. 129, 2 (2009), 251--271.
[15]
Jiawang Nie and Markus Schweighofer. 2005. On the complexity of Putinar's Positivstellensatz. Journal of Complexity, Vol. 23, 1 (2005), 135--150.
[16]
Pablo Parrilo. 2000. Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. Ph.,D. Dissertation. California Institute of Technology.
[17]
Victoria Powers and Thorsten Wörmann. 1998. An algorithm for sums of squares of real polynomials. Journal of Pure and Applied Algebra, Vol. 127, 1 (1998), 99--104.
[18]
Mihai Putinar. 1993. Positive polynomials on compact semi-algebraic sets. Indiana University Mathematics Journal, Vol. 42, 3 (1993), 969--984.
[19]
Claus Scheiderer. 2003. Sums of squares on real algebraic curves. Mathematische Zeitschrift, Vol. 245, 4 (2003), 725--760.
[20]
Konrad Schmüdgen. 1991. The K-moment problem for compact semi-algebraic sets. Mathematische Annalen, Vol. 289, 1 (1991), 203--206.
[21]
Markus Schweighofer. 2004. On the complexity of Schmüdgen's Positivstellensatz. Journal of Complexity, Vol. 20, 4 (2004), 529--543.
[22]
Abraham Seidenberg. 1954. A new decision method for elementary algebra. Annals of Mathematics, Vol. 60, 2 (1954), 365--374.
[23]
Gilbert Stengle. 1974. A Nullstellensatz and a Positivstellensatz in semialgebraic geometry. Mathematische Annalen, Vol. 207, 2 (1974), 87--97.
[24]
Alfred Tarski. 1998. A decision method for elementary algebra and geometry. In Quantifier elimination and cylindrical algebraic decomposition. Springer, 24--84.
[25]
Lieven Vandenberghe and Stephen Boyd. 1996. Semidefinite programming. SIAM Review, Vol. 38, 1 (1996), 49--95.
[26]
Sven Wagner. 2009. Archimedean Quadratic Modules: A Decision Problem for Real Multivariate Polynomials. Ph.,D. Dissertation. University of Konstanz.
Index Terms
- Algorithms for Testing Membership in Univariate Quadratic Modules over the Reals
Recommendations
Certifying convergence of Lasserre's hierarchy via flat truncation
Consider the optimization problem of minimizing a polynomial function subject to polynomial constraints. A typical approach for solving it globally is applying Lasserre's hierarchy of semidefinite relaxations, based on either Putinar's or Schmüdgen's ...
On the complexity of Putinar's Positivstellensatz
Let S={x@?R^n|g"1(x)>=0,...,g"m(x)>=0} be a basic closed semialgebraic set defined by real polynomials g"i. Putinar's Positivstellensatz says that, under a certain condition stronger than compactness of S, every real polynomial f positive on S possesses ...
An Exact Duality Theory for Semidefinite Programming Based on Sums of Squares
Farkas' lemma is a fundamental result from linear programming providing linear certificates for infeasibility of systems of linear inequalities. In semidefinite programming, such linear certificates only exist for strongly infeasible linear matrix ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2022
547 pages
Copyright © 2022 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 05 July 2022
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
ISSAC '22
Sponsor:
ISSAC '22: International Symposium on Symbolic and Algebraic Computation
July 4 - 7, 2022
Villeneuve-d'Ascq, France
Acceptance Rates
Overall Acceptance Rate 395 of 838 submissions, 47%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 67Total Downloads
- Downloads (Last 12 months)9
- Downloads (Last 6 weeks)1
Reflects downloads up to 19 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in