On the minimum of a positive polynomial over the standard simplex. (English) Zbl 1239.90086
Summary: We present a new positive lower bound for the minimum value taken by a polynomial \(P\) with integer coefficients in \(k\) variables over the standard simplex of \(\mathbb R^k\), assuming that \(P\) is positive on the simplex. This bound depends only on the number of variables \(k\), the degree \(d\) and the bitsize \(\tau \) of the coefficients of \(P\) and improves all the previous bounds for arbitrary polynomials which are positive over the simplex.
MSC:
| 90C26 | Nonconvex programming, global optimization |
| 13J30 | Real algebra |
| 14P10 | Semialgebraic sets and related spaces |
| 26C99 | Polynomials, rational functions in real analysis |
Software:
ISOLATEReferences:
| [1] | Basu, S., Leroy, R., Roy, M.-F., 2009. A bound on the minimum of a real positive polynomial over the standard simplex, Manuscript. Available at: arXiv:0902.3304.; Basu, S., Leroy, R., Roy, M.-F., 2009. A bound on the minimum of a real positive polynomial over the standard simplex, Manuscript. Available at: arXiv:0902.3304. |
| [2] | Basu, S.; Pollack, R.; Roy, M.-F., (Algorithms in Real Algebraic Geometry. Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics, vol. 10 (2006), Springer-Verlag: Springer-Verlag Berlin) · Zbl 1102.14041 |
| [3] | Bochnak, J.; Coste, M.; Roy, M. F., (Géométrie algébrique réelle. Géométrie algébrique réelle, Ergebnisse der Mathematik und ihrer Grenzgebiete (3), vol. 12 (1987), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0633.14016 |
| [4] | Canny, J., The Complexity of Robot Motion Planning (1987), MIT press |
| [5] | de Loera, J.; Santos, F., An effective version of Pólya’s theorem on positive definite forms, J. Pure Appl. Algebra, 108, 3, 231-240 (1996) · Zbl 0859.11029 |
| [6] | Emiris, I., Mourrain, B., Tsigaridas, E., 2009. The DMM bound: Multivariate (aggregate) separation bounds, Manuscript.; Emiris, I., Mourrain, B., Tsigaridas, E., 2009. The DMM bound: Multivariate (aggregate) separation bounds, Manuscript. · Zbl 1321.68528 |
| [7] | González-Vega, L.; Trujillo, F., Using symmetric functions to describe the solution set of a zero dimensional ideal, (Applied Algebra, Algebraic Algorithms and Error-correcting Codes. Applied Algebra, Algebraic Algorithms and Error-correcting Codes, Paris, 1995. Applied Algebra, Algebraic Algorithms and Error-correcting Codes. Applied Algebra, Algebraic Algorithms and Error-correcting Codes, Paris, 1995, Lecture Notes in Comput. Sci., vol. 948 (1995), Springer: Springer Berlin), 232-247 · Zbl 0894.12005 |
| [8] | Jeronimo, G., Perrucci, D., Sabia, J., On sign conditions over real multivariate polynomials. Discrete Comput. Geom, in press (doi:10.1007/s00454-009-9200-4).; Jeronimo, G., Perrucci, D., Sabia, J., On sign conditions over real multivariate polynomials. Discrete Comput. Geom, in press (doi:10.1007/s00454-009-9200-4). · Zbl 1216.05055 |
| [9] | Leroy, R., 2008. Certificats de positivité et minimisation polynomiale dans la base de Bernstein multivariée. Ph.D. Thesis, Université de Rennes 1.; Leroy, R., 2008. Certificats de positivité et minimisation polynomiale dans la base de Bernstein multivariée. Ph.D. Thesis, Université de Rennes 1. |
| [10] | Mignotte, M.; Stefanescu, D., (Polynomials. An Algorithmic Approach. Polynomials. An Algorithmic Approach, Springer Series in Discrete Mathematics and Theoretical Computer Science (1999), Springer-Verlag Singapore: Springer-Verlag Singapore Singapore), Centre for Discrete Math. & Theoret. Comput. Sci., Auckland · Zbl 0927.12004 |
| [11] | Powers, V.; Reznick, B., A new bound for Pólya’s theorem with applications to polynomials positive on polyhedra. Effective methods in algebraic geometry (Bath, 2000), J. Pure Appl. Algebra, 164, 1-2, 221-229 (2001) · Zbl 1075.14523 |
| [12] | Prestel, A.; Delzell, C., (Positive Polynomials. From Hilbert’s 17th Problem to Real Algebra. Positive Polynomials. From Hilbert’s 17th Problem to Real Algebra, Springer Monographs in Mathematics (2001), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0987.13016 |
| [13] | Rouillier, F., Solving zero-dimensional systems through the rational univariate representation, Appl. Algebra Eng. Commun. Comput., 9, 5, 433-461 (1999) · Zbl 0932.12008 |
| [14] | Schweighofer, M., On the complexity of Schmüdgen’s positivstellensatz, J. Complexity, 20, 4, 529-543 (2004) · Zbl 1161.68480 |
| [15] | Solernó, P., Effective Łojasiewicz inequalities in semialgebraic geometry, Appl. Algebra Engrg. Comm. Comput., 2, 1, 2-14 (1991) · Zbl 0754.14035 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
