On the Construction of Converging Hierarchies for Polynomial Optimization Based on Certificates of Global Positivity

References

• [1] Ahmadi AA (2012) On the difficulty of deciding asymptotic stability of cubic homogeneous vector fields. Proc. Amer. Control Conf. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 3334–3339.Google Scholar
• [2] Ahmadi AA, Majumdar A (2016) Some applications of polynomial optimization in operations research and real-time decision making. Optim. Lett. 10(4):709–729.Crossref, Google Scholar
• [3] Ahmadi AA, Majumdar A (2019) DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization. SIAM J. Appl. Algebra Geometry. Forthcoming.Crossref, Google Scholar
• [4] Artin E (1927) Über die Zerlegung definiter Funktionen in Quadrate. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 5(1):100–115.Google Scholar
• [5] Averkov G (2013) Constructive proofs of some Positivstellensätze for compact semialgebraic subsets of {\mathbb R}^{d}. J. Optim. Theory Appl. 158(2):410–418.Crossref, Google Scholar
• [6] Blekherman G, Parrilo PA, Thomas RR (2012) Semidefinite Optimization and Convex Algebraic Geometry (SIAM, Philadelphia).Crossref, Google Scholar
• [7] Datta RS (2002) Computing with polynomials: A personal odyssey. Working paper, Ohio State University, Columbus.Google Scholar
• [8] de Klerk E, Pasechnik DV (2002) Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4):875–892.Crossref, Google Scholar
• [9] de Klerk E, Laurent M, Parrilo P (2005) On the equivalence of algebraic approaches to the minimization of forms on the simplex. Henrion D, Garulli A, eds. Positive Polynomials in Control, Lecture Notes in Control and Information Science, vol. 312 (Springer, Berlin), 580–580.Google Scholar
• [10] de Klerk E, Laurent M, Parrilo PA (2006) A PTAS for the minimization of polynomials of fixed degree over the simplex. Theoret. Comput. Sci. 361(2–3):210–225.Crossref, Google Scholar
• [11] Habicht W (1939) Über die Zerlegung strikte definiter Formen in Quadrate. Commentarii Mathematici Helvetici 12(1):317–322.Crossref, Google Scholar
• [12] Johnson SC (1974) Sparse polynomial arithmetic. SIGSAM Bull. 8(3):63–71.Crossref, Google Scholar
• [13] Krivine JL (1964) Anneaux préordonnés. J. d’Analyse Mathématique 12(1):307–326.Crossref, Google Scholar
• [14] Lasserre JB (2001) Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3):796–817.Crossref, Google Scholar
• [15] Lasserre JB (2009) Moments, Positive Polynomials and their Applications, vol. 1 (World Scientific, Singapore).Crossref, Google Scholar
• [16] Laurent M (2009) Sums of squares, moment matrices and optimization over polynomials. Emerging Applications of Algebraic Geometry (Springer, New York), 157–270.Crossref, Google Scholar
• [17] Lombardi H, Perrucci D, Roy MF (2014) An elementary recursive bound for effective Positivstellensatz and Hilbert 17-th problem. Working paper, Université de Franche-Comté, Besançon, France.Google Scholar
• [18] Nie J, Schweighofer M (2007) On the complexity of Putinar’s Positivstellensatz. J. Complexity 23(1):135–150.Crossref, Google Scholar
• [19] Pardalos PM, Vavasis SA (1991) Quadratic programming with one negative eigenvalue is NP-hard. J. Global Optim. 1(1):15–22.Crossref, Google Scholar
• [20] Parrilo PA (2000) Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Doctoral dissertation, California Institute of Technology, Pasadena.Google Scholar
• [21] Parrilo PA (2003) Semidefinite programming relaxations for semialgebraic problems. Math. Programming 96(2):293–320.Crossref, Google Scholar
• [22] Pólya G (1928) Über positive Darstellung von Polynomen. Vierteljschr. Naturforsch. Ges. Zürich 73:141–145.Google Scholar
• [23] Powers V, Reznick B (2001) A new bound for Pólya’s theorem with applications to polynomials positive on polyhedra. J. Pure Appl. Algebra 164(1):221–229.Crossref, Google Scholar
• [24] Prestel A, Delzell C (2013) Positive Polynomials: From Hilbert’s 17th Problem to Real Algebra (Springer Science & Business Media, Berlin).Google Scholar
• [25] Putinar M (1993) Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42(3):969–984.Crossref, Google Scholar
• [26] Reznick B (1995) Uniform denominators in Hilbert’s 17th problem. Mathematische Zeitschrift 220(1):75–97.Crossref, Google Scholar
• [27] Schmüdgen K (1991) The k-moment problem for compact semi-algebraic sets. Mathematische Annalen 289(1):203–206.Crossref, Google Scholar
• [28] Schweighofer M (2002) An algorithmic approach to Schmüdgen’s Positivstellensatz. J. Pure Appl. Algebra 166(3):307–319.Crossref, Google Scholar
• [29] Schweighofer M (2004) On the complexity of Schmüdgen’s Positivstellensatz. J. Complexity 20(4):529–543.Crossref, Google Scholar
• [30] Schweighofer M (2005) Optimization of polynomials on compact semialgebraic sets. SIAM J. Optim. 15(3):805–825.Crossref, Google Scholar
• [31] Stengle G (1974) A Nullstellensatz and a Positivstellensatz in semialgebraic geometry. Mathematische Annalen 207(2):87–97. Crossref, Google Scholar