2013/07/31 by Aurélien Greuet, Greuet, Aurélien, Mohab Safey El Din +1 · 2 citations
Computer Science · Mathematics · #Advanced Differential Equations and Dynamical Systems #FOS: Computer and information sciences #FOS: Mathematics #Numerical Methods and Algorithms #Optimization and Control (math.OC) #Polynomial and algebraic computation #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.1307.8281
openalex publication_date 2013/07/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let f, f1, \…, f_ nV be polynomials with rational coefficients in the\nindeterminates bfX=X1, \…, Xn of maximum degree D and V be the set\nof common complex solutions of F=(f1,\…, f_ nV). We give an algorithm\nwhich, up to some regularity assumptions on F, computes an exact\nrepresentation of the global infimum f^\⋆=\infx\∈ V\∩ Rn f Parx,\ni.e. a univariate polynomial vanishing at f^\⋆ and an isolating interval\nfor f^\⋆. Furthermore, this algorithm decides whether f^\⋆ is reached\nand if so, it returns x^\⋆\∈ V\∩ Rn such that\nf Parx^\⋆=f^\⋆. This algorithm is probabilistic. It makes use of the\nnotion of polar varieties. Its complexity is essentially cubic in Par nV\nDn and linear in the complexity of evaluating the input. This fits within\nthe best known deterministic complexity class DO(n). We report on some\npractical experiments of a first implementation that is available as a Maple\npackage. It appears that it can tackle global optimization problems that were\nunreachable by previous exact algorithms and can manage instances that are hard\nto solve with purely numeric techniques. As far as we know, even under the\nextra genericity assumptions on the input, it is the first probabilistic\nalgorithm that combines practical efficiency with good control of complexity\nfor this problem.\n