Navegar

Colección

Datos Estadísticas

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 give an explicit upper bound for the algebraic degree and an explicit lower bound for the absolute value of the minimum of a polynomial function on a compact connected component of a basic closed semialgebraic set when this minimum is not zero. We also present extensions of these results to noncompact situations. As an application, we obtain a lower bound for the separation of two disjoint connected components of basic closed semialgebraic sets, when at least one of them is compact. © 2013 Society for Industrial and Applied Mathematics.

Registro:

Documento: Artículo
Título:On the minimum of a polynomial function on a basic closed semialgebraic set and applications
Autor:Jeronimo, G.; Perrucci, D.; Tsigaridas, E.
Filiación:Departamento de Matemática, FCEN, Universidad de Buenos Aires, Buenos Aires, 1428, Argentina
POLSYS Project, INRIA Paris-Rocquencourt, UPMC, Univ. Paris 06, Paris, France
Palabras clave:Polynomial optimization; Separation bounds; Absolute values; Algebraic degrees; Connected component; Lower bounds; Polynomial functions; Polynomial optimization; Semi-algebraic set; Semi-algebraic sets; Functions; Separation; Set theory
Año:2013
Volumen:23
Número:1
Página de inicio:241
Página de fin:255
DOI: http://dx.doi.org/10.1137/110857751
Título revista:SIAM Journal on Optimization
Título revista abreviado:SIAM J. Optim.
ISSN:10526234
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_10526234_v23_n1_p241_Jeronimo

Referencias:

  • Bajaj, C., The algebraic degree ofgeometric optimizationproblems (1988) Discrete Comput. Geom., 3, pp. 177-191
  • Basu, S., Pollack, R., Roy, M.-F., (2006) Algorithms in Real Algebraic Geometry, 2nd Ed., 10. , Algorithms Comput. Math. Springer-Verlag, Berlin
  • Basu, S., Roy, M.-F., Bounding the radii of balls meeting every connected component of semi-algebraic sets (2010) J. Symbolic Comput., 45, pp. 1270-1279
  • Canny, J., (1987) The Complexity of Robot Motion Planning, ACM Doctoral, , Dissertation Award Series, MIT Press, Cambridge, MA
  • Emiris, I.Z., Mourrain, B., Tsigaridas, P.E., The DMMbound: Multivariate (aggregate) separation bounds (2010) Proceedings of the 35th Annual ACM International Symposium on Symbolic & Algebraic Computation (ISSAC), pp. 243-250. , S. Watt, ed., Munich, Germany ACM, New York
  • Gelfand, I.M., Kapranov, M.M., Zelevinsky, A.V., (1994) Discriminants, Resultants, and Multidimensional Determinants, , Birkḧauser Boston, Boston
  • Graf Von Bothmer, H.-C., Ranestad, K., A general formula for the algebraic degree in semidefinite programming (2009) Bull. Lond. Math. Soc., 41, pp. 193-197
  • Hansen, K.A., Koucky, M., Lauritzen, N., Miltersen, P.B., Tsigaridas, E.P., Exact algorithms for solving stochastic games (extended abstract) (2011) STOC'11\\-Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pp. 205-214. , ACM, New York
  • Hansen, K.A., Koucky, M., Lauritzen, N., Miltersen, P.B., Tsigaridas, E.P., Separa- tion bounds for real roots of polynomial systems (2011) Proceedings of the 11th International Symposium on Effective Methods in Algebraic Geometry (MEGA)
  • Jeronimo, G., Perrucci, D., On the minimum of a positive polynomial over the standard simplex (2010) J. Symbolic Comput., 45, pp. 434-442
  • Jeronimo, G., Perrucci, D., Sabia, J., On sign conditions over real multivariate polynomials (2010) Discrete Comput. Geom., 44, pp. 195-222
  • Mantzaflaris, A., Mourrain, B., Tsigaridas, E.P., On continued fraction expansion ofreal roots ofpolynomial systems, complexity and condition numbers (2011) Theoret. Comput. Sci., 412, pp. 2312-2330
  • Mignotte, M., Ştefǎnescu, D., (1999) Polynomials: An Algorithmic Approach, , Springer-Verlag, Singapore
  • Nie, J., Ranestad, K., Algebraic degree of polynomial optimization (2009) SIAM J. Optim., 20, pp. 485-502
  • Nie, J., Ranestad, K., Sturmfels, B., The algebraic degree ofsemidefinite programming (2010) Math. Program., 122, pp. 379-405
  • Nocedal, J., Wright, S.J., (1999) Numerical Optimization, , Springer Ser. Oper. Res., Springer-Verlag, New York
  • Schweighofer, M., On the complexity of Schmüdgen's Positivstellensatz (2004) J. Complexity, 20, pp. 529-543
  • Shafarevich, I.R., (1994) Basic Algebraic Geometry 1, 2nd Ed., , Springer-Verlag, Berlin
  • Sombra, M., The height of the mixed sparse resultant (2004) Amer. J. Math., 126, pp. 1253-1260
  • Yakoubsohn, J.C., Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions (2005) J. Complexity, 21, pp. 652-690

Citas:

---------- APA ----------
Jeronimo, G., Perrucci, D. & Tsigaridas, E. (2013) . On the minimum of a polynomial function on a basic closed semialgebraic set and applications. SIAM Journal on Optimization, 23(1), 241-255.
http://dx.doi.org/10.1137/110857751
---------- CHICAGO ----------
Jeronimo, G., Perrucci, D., Tsigaridas, E. "On the minimum of a polynomial function on a basic closed semialgebraic set and applications" . SIAM Journal on Optimization 23, no. 1 (2013) : 241-255.
http://dx.doi.org/10.1137/110857751
---------- MLA ----------
Jeronimo, G., Perrucci, D., Tsigaridas, E. "On the minimum of a polynomial function on a basic closed semialgebraic set and applications" . SIAM Journal on Optimization, vol. 23, no. 1, 2013, pp. 241-255.
http://dx.doi.org/10.1137/110857751
---------- VANCOUVER ----------
Jeronimo, G., Perrucci, D., Tsigaridas, E. On the minimum of a polynomial function on a basic closed semialgebraic set and applications. SIAM J. Optim. 2013;23(1):241-255.
http://dx.doi.org/10.1137/110857751