Sums of Separable and Quadratic Polynomials

References

• [1] Ahmadi AA, Hall G (2018) DC decomposition of nonconvex polynomials with algebraic techniques. Math. Programming 169(1):69–94.Crossref, Google Scholar
• [2] Ahmadi AA, Parrilo PA (2012) A convex polynomial that is not sos-convex. Math. Programming 135(1):275–292.Crossref, Google Scholar
• [3] Ahmadi AA, Parrilo PA (2013) A complete characterization of the gap between convexity and sos-convexity. SIAM J. Optim. 23(2):811–833.Crossref, Google Scholar
• [4] Ahmadi AA, Olshevsky A, Parrilo PA, Tsitsiklis JN (2013) NP-hardness of deciding convexity of quartic polynomials and related problems. Math. Programming 137(1):453–476.Crossref, Google Scholar
• [5] Aylward EM, Itani SM, Parrilo PA (2007) Explicit SOS decompositions of univariate polynomial matrices and the Kalman-Yakubovich-Popov lemma. IEEE Conf. Decision Control (IEEE), 5660–5665. https://ieeexplore.ieee.org/document/4434001.Google Scholar
• [6] Belousov EG, Klatte D (2002) A Frank–Wolfe type theorem for convex polynomial programs. Comput. Optim. Appl. 22(1):37–48.Crossref, Google Scholar
• [7] Bertsekas D (1999) Nonlinear Programming (Athena Scientific, Belmont, MA).Google Scholar
• [8] Blekherman G (2009) Convex forms that are not sums of squares. Preprint, submitted October 5, https://arxiv.org/abs/0910.0656.Google Scholar
• [9] Blekherman G, Parrilo PA, Thomas RR (2012) Semidefinite Optimization and Convex Algebraic Geometry (SIAM). https://epubs.siam.org/doi/abs/10.1137/1.9781611972290.ch1.Crossref, Google Scholar
• [10] Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press). https://www.cambridge.org/gb/academic/subjects/statistics-probability/optimization-or-and-risk/convex-optimization?format=HB.Crossref, Google Scholar
• [11] Choi MD, Lam TY (1977) Extremal positive semidefinite forms. Mathematische Annalen 231(1):1–18.Crossref, Google Scholar
• [12] Choi MD, Lam TY (1977) An old question of Hilbert. Queen’s Papers Pure Appl. Math. 46(4):385–405.Google Scholar
• [13] Choi MD, Lam TY, Reznick B (1980) Real zeros of positive semidefinite forms. I. Mathematische Zeitschrift 171(1):1–26.Crossref, Google Scholar
• [14] Choi MD, Lam TY, Reznick B (1995) Sums of squares of real polynomials. Proc. Sympos. Pure Math. 58(2):103–126. https://www.ams.org/books/pspum/062.1/.Google Scholar
• [15] Curmei M, Hall G (2020) Shape-constrained regression using sum of squares polynomials. Preprint, submitted April 8, https://arxiv.org/abs/2004.03853.Google Scholar
• [16] De Klerk E, Laurent M (2011) On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems. SIAM J. Optim. 21(3):824–832.Crossref, Google Scholar
• [17] Garey MR, Johnson DS (2002) Computers and Intractability, vol. 29 (WH Freeman, New York).Google Scholar
• [18] Hall G (2020) Applications of sum of squares polynomials. Sum of Squares: Theory and Applications, vol. 77. https://bookstore.ams.org/psapm-77/.Google Scholar
• [19] Helton JW, Nie J (2010) Semidefinite representation of convex sets. Math. Programming 122(1):21–64.Crossref, Google Scholar
• [20] Henrion D, Lasserre JB (2005) Detecting global optimality and extracting solutions in GloptiPoly. Positive Polynomials in Control (Springer, Berlin), 293–310.Crossref, Google Scholar
• [21] Hilbert D (1888) Über die Darstellung definiter Formen als Summe von Formenquadraten. Mathematische Annalen 32(3):342–350.Crossref, Google Scholar
• [22] Lasserre JB (2001) Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3):796–817.Crossref, Google Scholar
• [23] Lasserre JB (2009) Convexity in semialgebraic geometry and polynomial optimization. SIAM J. Optim. 19(4):1995–2014.Crossref, Google Scholar
• [24] Lasserre JB (2010) Moments, Positive Polynomials and Their Applications, vol. 1 (Imperial College Press). https://www.worldscientific.com/worldscibooks/10.1142/p665#t=aboutBook.Google Scholar
• [25] 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
• [26] MOSEK (2019) Mosek optimization toolbox for matlab. User’s Guide and Reference Manual, version 4.Google Scholar
• [27] Motzkin T (1967) The arithmetic-geometric inequality. Proc. Sympos. Inequalities, Wright-Patterson Air Force Base, OH, 1965 (Academic Press, New York), 205–224.Google Scholar
• [28] Murty KG, Kabadi SN (1987) Some NP-complete problems in quadratic and nonlinear programming. Math. Programming 39:117–129.Crossref, Google Scholar
• [29] Natarajan BK (1995) Sparse approximate solutions to linear systems. SIAM J. Comput. 24(2):227–234.Crossref, Google Scholar
• [30] 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
• [31] Parrilo PA (2000) Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Unpublished PhD thesis, California Institute of Technology, Pasadena.Google Scholar
• [32] Peyrl H, Parrilo PA (2008) Computing sum of squares decompositions with rational coefficients. Theoretical Comput. Sci. 409(2):269–281.Crossref, Google Scholar
• [33] Powers V, Reznick B (2000) Polynomials that are positive on an interval. Trans. Amer. Math. Soc. 352(10):4677–4692.Crossref, Google Scholar
• [34] Raghavendra P, Ryder N, Srivastava N (2017) Real stability testing. Proc. Innovations Theoretical Comput. Sci. https://drops.dagstuhl.de/opus/volltexte/2017/8202/pdf/LIPIcs-ITCS-2017-0.pdf.Google Scholar
• [35] Reznick B (1978) Extremal PSD forms with few terms. Duke Math. J. 45(2):363–374.Crossref, Google Scholar
• [36] Reznick B (2000) Some concrete aspects of Hilbert’s 17th problem. Contemporary Math. 253:251–272.Crossref, Google Scholar
• [37] Robinson RM (1969) Some definite polynomials which are not sums of squares of real polynomials. Notices Amer. Math. Soc. 16:554. https://www.ams.org/journals/proc/1989-106-04/S0002-9939-1989-0976367-8/.Google Scholar
• [38] Stoer J, Witzgall C (2012) Convexity and Optimization in Finite Dimensions I, vol. 163 (Springer Science & Business Media). https://link.springer.com/book/10.1007/978-3-642-46216-0.Google Scholar