Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We consider the problem of computing the minimum of a polynomial function g on a basic closed semialgebraic set (Formula presented.). We present a probabilistic symbolic algorithm to find a finite set of sample points of the subset (Formula presented.) where the minimum of g is attained, provided that (Formula presented.) is non-empty and has at least one compact connected component. © 2014, Springer Science+Business Media New York.

Registro:

Documento: Artículo
Título:A Probabilistic Symbolic Algorithm to Find the Minimum of a Polynomial Function on a Basic Closed Semialgebraic Set
Autor:Jeronimo, G.; Perrucci, D.
Filiación:Departamento de Matemática, FCEN, Universidad de Buenos Aires, Buenos Aires, Argentina
IMAS, CONICET–UBA, Buenos Aires, Argentina
CONICET, Buenos Aires, Argentina
Palabras clave:Complexity; Deformation techniques; Polynomial optimization
Año:2014
Volumen:52
Número:2
Página de inicio:260
Página de fin:277
DOI: http://dx.doi.org/10.1007/s00454-014-9619-0
Título revista:Discrete and Computational Geometry
Título revista abreviado:Discrete Comput. Geom.
ISSN:01795376
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01795376_v52_n2_p260_Jeronimo

Referencias:

  • Basu, S., Pollack, R., Roy, M.-F., Algorithms in real algebraic geometry (2006) Algorithms and Computation in Mathematics, vol. 10, 2nd edn, , Springer, Berlin
  • Baur, W., Strassen, V., The complexity of partial derivatives (1983) Theor. Comput. Sci., 22 (3), pp. 317-330
  • Berkowitz, S., On computing the determinant in small parallel time using a small number of processors (1984) Inf. Process. Lett., 18 (3), pp. 147-150
  • Bürgisser, P., Clausen, M., Shokrollahi, M.A., (1997) Algebraic Complexity Theory. Grundlehren der Mathematischen Wissenschaften, , 315, Springer, Berlin
  • Canny, J., Improved algorithms for sign determination and existential quantifier elimination (1993) Comput. J., 36 (5), pp. 409-418
  • Emiris, I., Mourrain, B., Tsigaridas, E., The DMM bound: multivariate (aggregate) separation bounds (2010) ISSAC 2010—Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, pp. 243-250. , ACM, New York
  • Giusti, M., Lecerf, G., Salvy, B., A Gröbner free alternative for polynomial system solving (2001) J. Complexity, 17 (1), pp. 154-211
  • Greuet, A., Guo, F., Safey El Din, M., Zhi, L., Global optimization of polynomials restricted to a smooth variety using sums of squares (2012) J. Symb. Comput., 47 (5), pp. 503-518
  • Greuet, A., Safey El Din, M., Deciding reachability of the infimum of a multivariate polynomial (2011) ISSAC 2011—Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, pp. 131-138. , ACM, New York
  • Guo, F., Safey El Din, M., Zhi, L., Global optimization of polynomials using generalized critical values and sums of squares (2010) ISSAC 2010—Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, pp. 107-114. , ACM, New York
  • Heintz, J., Krick, T., Puddu, S., Sabia, J., Waissbein, A., Deformation techniques for efficient polynomial equation solving (2000) J. Complexity, 16 (1), pp. 70-109
  • Heintz, J., Schnorr, C.-P., Testing polynomials which are easy to compute (1982) Logic and Algorithmic (Zurich, 1980). Monographs of L’Enseignement Mathèmatique, vol. 30, pp. 237-254. , University of Genève, Geneva
  • Jeronimo, G., Perrucci, D., On the minimum of a positive polynomial over the standard simplex (2010) J. Symb. Comput, 45 (4), pp. 434-442
  • Jeronimo, G., Matera, G., Solernó, P., Waissbein, A., Deformation techniques for sparse systems (2009) Found. Comput. Math., 9 (1), pp. 1-50
  • Jeronimo, G., Perrucci, D., Sabia, J., On sign conditions over real multivariate polynomials (2010) Discrete Comput. Geom., 44 (1), pp. 195-222
  • Jeronimo, G., Perrucci, D., Tsigaridas, E., On the minimum of a polynomial function on a basic closed semialgebraic set and applications (2013) SIAM J. Optim., 23 (1), pp. 241-255
  • Kincaid, D., Cheney, W., (1991) Numerical Analysis. Mathematics of Scientific Computing, , Brooks/Cole Publishing Co., Pacific Grove, CA
  • Lasserre, J.B., Global optimization with polynomials and the problem of moments (2001) SIAM J. Optim., 11 (3), pp. 796-817
  • Nie, J., Demmel, J., Sturmfels, B., Minimizing polynomials via sum of squares over the gradient ideal (2006) Math. Program., 106 (3), pp. 587-606
  • Parrilo, P.A., Semi-definite relaxations for semi-algebraic problems (2003) Math. Program., 92 (2), pp. 293-320
  • Parrilo, P.A., Sturmfels, B., Minimizing polynomial functions (2003) Algorithmic and Quantitative Real Algebraic Geometry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 60, pp. 83-99. , American Mathematical Society, Providence, RI
  • Perrucci, D., Linear solving for sign determination (2011) Theor. Comput. Sci., 412 (35), pp. 4715-4720
  • Safey El Din, M., Computing the global optimum of a multivariate polynomial over the reals (2008) ISSAC, pp. 71-78. , ACM, New York
  • Shafarevich, I., (1977) Basic Algebraic Geometry, Study Edition, , Springer, Berlin
  • Schweighofer, M., Global optimization of polynomials using gradient tentacles and sums of squares (2006) SIAM J. Optim., 17 (3), pp. 920-942
  • von zur Gathen, J., Gerhard, J., (1999) Modern Computer Algebra, , Cambridge University Press, New York

Citas:

---------- APA ----------
Jeronimo, G. & Perrucci, D. (2014) . A Probabilistic Symbolic Algorithm to Find the Minimum of a Polynomial Function on a Basic Closed Semialgebraic Set. Discrete and Computational Geometry, 52(2), 260-277.
http://dx.doi.org/10.1007/s00454-014-9619-0
---------- CHICAGO ----------
Jeronimo, G., Perrucci, D. "A Probabilistic Symbolic Algorithm to Find the Minimum of a Polynomial Function on a Basic Closed Semialgebraic Set" . Discrete and Computational Geometry 52, no. 2 (2014) : 260-277.
http://dx.doi.org/10.1007/s00454-014-9619-0
---------- MLA ----------
Jeronimo, G., Perrucci, D. "A Probabilistic Symbolic Algorithm to Find the Minimum of a Polynomial Function on a Basic Closed Semialgebraic Set" . Discrete and Computational Geometry, vol. 52, no. 2, 2014, pp. 260-277.
http://dx.doi.org/10.1007/s00454-014-9619-0
---------- VANCOUVER ----------
Jeronimo, G., Perrucci, D. A Probabilistic Symbolic Algorithm to Find the Minimum of a Polynomial Function on a Basic Closed Semialgebraic Set. Discrete Comput. Geom. 2014;52(2):260-277.
http://dx.doi.org/10.1007/s00454-014-9619-0