×

zbMATH — the first resource for mathematics

On an extension of Pólya’s Positivstellensatz. (English) Zbl 1379.11037
Summary: In this paper, we provide a generalization of a Positivstellensatz by G. Pólya [Vierteljahrsschrift Zürich 73, 141–145 (1928; JFM 54.0138.01)]. We show that if a homogeneous polynomial is positive over the intersection of the non-negative orthant and a given basic semialgebraic cone (excluding the origin), then there exists a “Pólya type” certificate for non-negativity. The proof of this result uses the original Positivstellensatz by Pólya, and a Positivstellensatz by M. Putinar and F.-H. Vasilescu [C. R. Acad. Sci., Paris, Sér. I, Math. 328, No. 7, 585–589 (1999; Zbl 0973.14031)].

MSC:
11E25 Sums of squares and representations by other particular quadratic forms
14P05 Real algebraic sets
14P10 Semialgebraic sets and related spaces
90C30 Nonlinear programming
PDF BibTeX Cite
Full Text: DOI
References:
[1] Bomze, IM, Copositive optimization-recent developments and applications, Eur. J. Oper. Res., 216, 509-520, (2012) · Zbl 1262.90129
[2] Cplex optimizer. http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/. Apr 2014 · Zbl 1035.90058
[3] Dickinson, P.J.C.: The copositive cone, the completely positive cone and their generalisations. PhD thesis, University of Groningen, Groningen, The Netherlands (2013) · Zbl 1161.68480
[4] Klerk, E; Laurent, M; Parrilo, PA, A PTAS for the minimization of polynomials of fixed degree over the simplex, Theor. Comput. Sci., 361, 210-225, (2006) · Zbl 1115.90042
[5] Klerk, E; Pasechnik, DV, Approximation of the stability number of a graph via copositive programming, SIAM J. Optim., 12, 875-892, (2002) · Zbl 1035.90058
[6] Dong, H, Symmetric tensor approximation hierarchies for the completely positive cone, SIAM J. Optim., 23, 1850-1866, (2013) · Zbl 1291.90129
[7] Dickinson, P.J.C., Povh, J.: New linear and positive semidefinite programming based approximation hierarchies for polynomial optimisation. Preprint, submitted. Available at http://www.optimization-online.org/DB_HTML/2013/06/3925.html (2013)
[8] Dür, M; Diehl, M (ed.); Glineur, F (ed.); Jarlebring, E (ed.); Michiels, W (ed.), Copositive programming-a survey, 3-20, (2010), Berlin
[9] Faybusovich, L.: Global optimization of homogeneous polynomials on the simplex and on the sphere. Frontiers in Global Optimization, In: Floudas, C.A., Pardalos, P. (eds.) Nonconvex Optimization and its Application, vol. 74, pp. 109-121. Kluwer, Boston (2004) · Zbl 1165.90592
[10] Hardy, G.H., Littlewood, J.E., Pólya, G.: Inequalities, 2nd edn. Cambridge University Press, Cambridge (1988) · Zbl 0634.26008
[11] Krivine, J-L, Anneaux préordonnés, J. Anal. Math., 12, 307-326, (1964) · Zbl 0134.03902
[12] Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. Emerging Applications of Algebraic Geometry, In: Putinar, M., Sullivant, S. (eds.) IMA Volumes in Mathematics and its Applications, vol. 149, pp. 157-270. Springer, New York (2009) · Zbl 1163.13021
[13] Decision tree for optimization software. http://plato.asu.edu/guide.html. Apr 2014 · Zbl 1262.90129
[14] Murray, M; Tim, N, Positivstellensätze for real function algebras, Math. Z., 270, 889-901, (2012) · Zbl 1242.13029
[15] Mosek optimization software. http://mosek.com/. Apr 2014 · Zbl 0796.12002
[16] Nie, J; Schweighofer, M, On the complexity of putinar’s positivstellensatz, J. Complex., 23, 135-150, (2007) · Zbl 1143.13028
[17] Parrilo, P.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology (2000)
[18] Pólya, G.: Über positive darstellung von polynomen vierteljschr. In: Naturforsch. Ges. Zürich, 73: 141-145, 1928. In: Boas, R.P. (ed.) Collected Papers. vol. 2, pp. 309-313. MIT Press, Cambridge. Available at http://hal.archives-ouvertes.fr/docs/00/60/96/87/PDF/RAG2011-Rennes.pdf (1974) · Zbl 1291.90129
[19] Povh, J.: Towards the Optimum by Semidefinite and Copositive Programming: New Approach to Approximate Hard Optimization Problems. VDM, Saarbrücken (2009)
[20] Powers, V.: Positive polynomials and sums of squares: theory and practice. Real Algebraic, Geometry, p. 77 (2011) · Zbl 1115.90042
[21] Powers, V., Reznick, B.: A new bound for Pólya’s theorem with applications to polynomials positive on polyhedra. J. Pure Appl. Algebra, 164(1-2):221-229, (2001) Effective methods in algebraic geometry (Bath, 2000) · Zbl 1075.14523
[22] Putinar, M, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., 42, 969-984, (1993) · Zbl 0796.12002
[23] Putinar, M; Vasilescu, F-H, Positive polynomials on semi-algebraic sets, C. R. Acad. Sci. Ser. I Math., 328, 585-589, (1999) · Zbl 0973.14031
[24] Putinar, M; Vasilescu, F-H, Solving moment problems by dimensional extension, Ann. of Math. (2), 149, 1087-1107, (1999) · Zbl 0939.44003
[25] Reznick, B, Uniform denominators in hilbert’s seventeenth problem, Math. Z., 220, 75-97, (1995) · Zbl 0828.12002
[26] Schmüdgen, K, The \(K\)-moment problem for compact semi-algebraic sets, Math. Ann., 289, 203-206, (1991) · Zbl 0744.44008
[27] Schweighofer, M, On the complexity of schmüdgen’s positivstellensatz, J. Complex., 20, 529-543, (2004) · Zbl 1161.68480
[28] Scheiderer, C.: Positivity and sums of squares: a guide to recent results. Emerging applications of algebraic geometry, volume 149 of IMA Volumes in Mathematics and its Applications, pp. 271-324. Springer, New York (2009) · Zbl 1156.14328
[29] Stengle, G, A nullstellensatz and a positivstellensatz in semialgebraic geometry, Math. Ann., 207, 87-97, (1974) · Zbl 0253.14001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.