Geodesic
Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization
Canadian journal of mathematics, Tome 61 (2009) no. 1, pp. 205-221

Voir la notice de l'article provenant de la source Cambridge University Press

Natural sufficient conditions for a polynomial to have a local minimum at a point are considered. These conditions tend to hold with probability 1. It is shown that polynomials satisfying these conditions at each minimum point have nice presentations in terms of sums of squares. Applications are given to optimization on a compact set and also to global optimization. In many cases, there are degree bounds for such presentations. These bounds are of theoretical interest, but they appear to be too large to be of much practical use at present. In the final section, other more concrete degree bounds are obtained which ensure at least that the feasible set of solutions is not empty. 
Marshall, M. Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization. Canadian journal of mathematics, Tome 61 (2009) no. 1, pp. 205-221. doi: 10.4153/CJM-2009-010-4
@article{10_4153_CJM_2009_010_4,
     author = {Marshall, M.},
     title = {Representations of {Non-Negative} {Polynomials,} {Degree} {Bounds} and {Applications} to {Optimization}},
     journal = {Canadian journal of mathematics},
     pages = {205--221},
     year = {2009},
     volume = {61},
     number = {1},
     doi = {10.4153/CJM-2009-010-4},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-2009-010-4/}
}
TY  - JOUR
AU  - Marshall, M.
TI  - Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization
JO  - Canadian journal of mathematics
PY  - 2009
SP  - 205
EP  - 221
VL  - 61
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-2009-010-4/
DO  - 10.4153/CJM-2009-010-4
ID  - 10_4153_CJM_2009_010_4
ER  - 
%0 Journal Article
%A Marshall, M.
%T Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization
%J Canadian journal of mathematics
%D 2009
%P 205-221
%V 61
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-2009-010-4/
%R 10.4153/CJM-2009-010-4
%F 10_4153_CJM_2009_010_4

[1] [1] Bochnak, J., Coste, M., and Roy, M.-F., Real Algebraic Geometry. Ergebnisse der Mathematik und ihrer Grenzgebiete 36, Springer-Verlag, Berlin, 1998. Google Scholar

[2] [2] Jacobi, T., A representation theorem for certain partially ordered commutative rings. Math. Zeit. 237 (2001), no. 2, 259–273. Google Scholar

[3] [3] Jacobi, T. and Prestel, A., Distinguished presentations of strictly positive polynomials. J. Reine Angew. Math. 532 (2001), 223–235. Google Scholar

[4] [4] Kuhlmann, S., Marshall, M., and Schwartz, N., Positivity, sums of squares and the multi-dimensional moment problem. II. Adv. Geom. 5 (2005), no. 4, 583–606. Google Scholar

[5] [5] Lasserre, J. B., Optimisation globale et théorie des moments. C. R. Acad. Sci. Paris Sér. I Math. 331 (2000), no. 11, 929–934. Google Scholar

[6] [6] Laurent, M., Semidefinite representations for finite varieties.Math. Program. 109 (2007), no. 1, 1–26. Google Scholar

[7] [7] Marshall, M., Positive polynomials and sums of squares. Dottorato de Ricerca in Matematica, Universita Pisa, 2000. Google Scholar

[8] [8] Marshall, M., Optimization of polynomial functions. Canad. Math. Bull. 46 (2003), no. 4, 575–587. Google Scholar

[9] [9] Marshall, M., Representation of non-negative polynomials with finitely many zeros. Ann. Fac. Sci., Toulouse, 15 (2006), 599–609. Google Scholar

[10] [10] Nie, J., Demmel, J., and Sturmfels, B.,Minimizing polynomials via sum of squares over the gradient ideal. Math. Program. 106 (2006), no. 3, 587–606. Google Scholar

[11] [11] Parrilo, P., An explicit construction of distinguished representations of polynomials nonnegative over finite sets. http://www.control.ee.ethz.ch/_parrilo/pubs/files/aut02-02.pdf. Google Scholar

[12] [12] Parrilo, P., and Sturmfels, B.,Minimizing polynomial functions. In: Algorithmic and Quantitative Real Algebraic Geometry. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 60, American Mathematical Society, Providence, RI, 2003, pp. 83–100. Google Scholar

[13] [13] Prestel, A., Bounds for polynomials positive on compact semialgebraic sets. In: Valuation Theory and Its Applications. Fields Inst. Commun. 32, American Mathematical Society, Providence, RI, 2002, pp. 253–260. Google Scholar

[14] [14] Putinar, M., Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42 (1993), no. 3, 969–984. Google Scholar

[15] [15] Reznick, B., Uniform denominators in Hilbert's seventeenth problem. Math. Zeit. 220 (1995), no. 1, 75–98. Google Scholar

[16] [16] Scheiderer, C., Sums of squares of regular functions on real algebraic varieties. Trans. Amer. Math. Soc. 352 (2000), no. 3, 1039–1069. Google Scholar

[17] [17] Scheiderer, C., Sums of squares on real algebraic curves. Math. Zeit. 245 (2003), no. 4, 725–760. Google Scholar

[18] [18] Scheiderer, C., Non-existence of degree bounds for weighted sums of squares representations. J. Complexity 21 (2005), no. 6, 823–844. Google Scholar

[19] [19] Scheiderer, C., Sums of squares on real algebraic surfaces. ManuscriptaMath. 119 (2006), no. 4, 395–410. Google Scholar

[20] [20] Scheiderer, C., Distinguished representations of non-negative polynomials. J. Algebra 289 (2005), no. 2, 558–573. Google Scholar

[21] [21] Schmüdgen, K., The K-moment problem for compact semi-algebraic sets. Math. Ann. 289 (1991), no. 2, 203–206. Google Scholar

[22] [22] Schweighofer, M., On the complexity of Schmüdgen's positivstellensatz. J. Complexity 20 (2004), no. 4, 529–543. Google Scholar

[23] [23] Schweighofer, M., Global optimization of polynomials using gradient tentacles and sums of squares. SIAMJ. Optim. 17 (2006), no. 3, 920–942. (electronic) Google Scholar

Cité par Sources :