Paper Info
Title
Probabilistic Algorithm for Polynomial Optimization over a Real Algebraic Set.
Abstract
Let f, f(1),..., f(s) be n-variate polynomials with rational coefficients of maximum degree D and let V be the set of common complex solutions of F = (f(1),..., f(s)). We give an algorithm which, up to some regularity assumptions on F, computes an exact representation of the global infimum f* of the restriction of the map x -> f(x) to V boolean AND R-n, i.e., a univariate polynomial vanishing at f* and an isolating interval for f*. Furthermore, it decides whether f* is reached, and if so, it returns x* is an element of V boolean AND R-n such that f(x*) = f*. This algorithm is probabilistic. It makes use of the notion of polar varieties. Its complexity is essentially cubic in (sD)(n) and linear in the complexity of evaluating the input. This fits within the best known deterministic complexity class D-O(n). We report on some practical experiments of a first implementation that is available as a Maple package. It appears that it can tackle global optimization problems that were unreachable by previous exact algorithms and can manage instances that are hard to solve with purely numeric techniques. As far as we know, even under the extra genericity assumptions on the input, it is the first probabilistic algorithm that combines practical efficiency with good control of complexity for this problem.
Year
DOI
Venue
2013
10.1137/130931308
SIAM JOURNAL ON OPTIMIZATION
Keywords
DocType
Volume
global optimization,polynomial optimization,polynomial system solving,real solutions
Journal
24
Issue
ISSN
Citations 
3
1052-6234
17
PageRank 
References 
Authors
0.63
22
2
Name
Order
Citations
PageRank
Aurélien Greuet1391.74
Mohab Safey El Din245035.64