On the Minimum of a Polynomial Function on a Basic Closed Semialgebraic Set and Applications

DOI10.1137/110857751zbMATH Open1272.14042arXiv1112.0544OpenAlexW2964089478MaRDI QIDQ5300525FDOQ5300525

Gabriela Jeronimo, Daniel Perrucci, Elias P. Tsigaridas

Publication date: 27 June 2013

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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. 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.

Full work available at URL: https://arxiv.org/abs/1112.0544

Recommendations

• Optimisation globale et théorie des moments
• Optimization of Polynomials on Compact Semialgebraic Sets
• Global optimization of polynomials over real algebraic sets
• Convexifying positive polynomials and sums of squares approximation
• scientific article
• Polynomial optimization on some unbounded closed semi-algebraic sets
• Sums of squares, moment matrices and optimization over polynomials
• Semi-algebraically connected components of minimum points of a polynomial function
• Complexity of integer quasiconvex polynomial optimization

zbMATH Keywords

polynomial optimizationseparation bounds

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Semialgebraic sets and related spaces (14P10)

Cited In (12)

• Complexity, exactness, and rationality in polynomial optimization
• Complexity, exactness, and rationality in polynomial optimization
• Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\)
• The complexity of subdivision for diameter-distance tests
• Representing matroids over the reals is \(\exists \mathbb{R}\)-complete
• Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
• RAC-Drawability is ∃ℝ-complete and Related Results
• A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set
• Divide and conquer roadmap for algebraic sets
• Computing real witness points of positive dimensional polynomial systems
• Exponential convexifying of polynomials
• Fixed points, Nash equilibria, and the existential theory of the reals

This page was built for publication: On the Minimum of a Polynomial Function on a Basic Closed Semialgebraic Set and Applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300525)