Paper Info
Title
Deciding reachability of the infimum of a multivariate polynomial
Abstract
Let f ∈ Q[X_1,...,Xn] be of degree D. Algorithms for solving the unconstrained global optimization problem f*=infx∈Rn f(x) are of first importance since this problem appears frequently in numerous applications in engineering sciences. This can be tackled by either designing appropriaten quantifier elimination algorithms or by certifying lower bounds on f* by means of sums of squares decompositions but there is no efficient algorithm for deciding if f* is a minimum. This paper is dedicated to this important problem. We design a probabilistic algorithm that decides, for a given f and the corresponding f*, if f* is reached over Rn and computes a point x* ∈ Rn such that f(x*)=f* if such a point exists. This algorithm makes use of algebraic elimination algorithms and real root isolation. If L is the length of a straight-line program evaluating f, algebraic elimination steps run in O(log(D-1)n6(nL+n4)U((D-1)n+1)3) arithmetic operations in Q where D=deg(f) and U(x)=x(log (x))2 log log (x). Experiments show its practical efficiency.
Year
DOI
Venue
2011
10.1145/1993886.1993910
ISSAC
Keywords
Field
DocType
appropriaten quantifier elimination algorithm,degree d,unconstrained global optimization problem,important problem,algebraic elimination algorithm,multivariate polynomial,probabilistic algorithm,log log,arithmetic operation,efficient algorithm,algebraic elimination step,lower bound,program evaluation,quantifier elimination,polynomials,global optimization,sum of squares
Quantifier elimination,Log-log plot,Discrete mathematics,Randomized algorithm,Combinatorics,Algebraic number,Global optimization,Polynomial,Infimum and supremum,Reachability,Mathematics
Conference
Citations 
PageRank 
References 
11
0.53
19
Authors
2
Name
Order
Citations
PageRank
Aurélien Greuet1391.74
Mohab Safey El Din245035.64