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

DOI10.1137/110857751zbMATH Open1272.14042OpenAlexW2964089478MaRDI QIDQ5300525FDOQ5300525

Authors Gabriela Jeronimo, Daniel Perrucci, Elias P. Tsigaridas

Publication date 27 June 2013

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

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

zbMATH Keywords

polynomial optimizationseparation bounds

Mathematics Subject Classification ID

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

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.

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; zbMATH DE number 125290
• 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

Cited in

(12)

• 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
• RAC-Drawability is ∃ℝ-complete and Related Results
• 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}\)
• Exponential convexifying of polynomials
• Representing matroids over the reals is \(\exists \mathbb{R}\)-complete
• Computing real witness points of positive dimensional polynomial systems
• The complexity of subdivision for diameter-distance tests
• Fixed points, Nash equilibria, and the existential theory of the reals
• Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization

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)