Intrinsic complexity estimates in polynomial optimization

DOI10.1016/j.jco.2014.02.005zbMath1302.65296arXiv1304.5214OpenAlexW2033158463MaRDI QIDQ2251913

Mohab Safey El Din, Bernd Bank, Joos Heintz, Marc Giusti

Publication date: 15 July 2014

Published in: Journal of Complexity (Search for Journal in Brave)

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

zbMATH Keywords

polynomial optimizationdegree of varietiesintrinsic complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Abstract computational complexity for mathematical programming problems (90C60) Computational aspects of higher-dimensional varieties (14Q15) Semialgebraic sets and related spaces (14P10) Complexity and performance of numerical algorithms (65Y20) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25)

Related Items

Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients, Refined F5 Algorithms for Ideals of Minors of Square Matrices, Faster real root decision algorithm for symmetric polynomials, Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization, Solving determinantal systems using homotopy techniques, Exact algorithms for semidefinite programs with degenerate feasible set, Homotopy techniques for solving sparse column support determinantal polynomial systems, On exact Reznick, Hilbert-Artin and Putinar's representations, Computing critical points for invariant algebraic systems

Uses Software

• Kronecker
• RAGlib

Cites Work

• A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set
• Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets
• Complexity of computation on real algebraic numbers
• Definability and fast quantifier elimination in algebraically closed fields
• Lectures on results on Bezout's theorem. Notes by D. P. Patil
• Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals
• Solving polynomial optimization problems via the truncated tangency variety and sums of squares
• Solving systems of polynomial inequalities in subexponential time
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• NC algorithms for real algebraic numbers
• The red book of varieties and schemes
• Lower bounds for diophantine approximations
• Straight-line programs in geometric elimination theory
• An exact Jacobian SDP relaxation for polynomial optimization
• On the geometry of polar varieties
• Generalized polar varieties: geometry and algorithms
• A concise proof of the Kronecker polynomial system solver from scratch
• Global Optimization with Polynomials and the Problem of Moments
• Probabilistic Algorithm for Polynomial Optimization over a Real Algebraic Set
• Fast computation of a rational point of a variety over a finite field
• Practical and Theoretical Issues for the Computation of Generalized Critical Values of a Polynomial Mapping
• On the combinatorial and algebraic complexity of quantifier elimination
• Deciding reachability of the infimum of a multivariate polynomial
• Algorithms in real algebraic geometry
• On the time-space complexity of geometric elimination procedures
• A Gröbner free alternative for polynomial system solving
• Polar varieties and efficient real elimination
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item