PROBABILISTIC ALGORITHM FOR POLYNOMIAL OPTIMIZATION OVER A REAL ALGEBRAIC SET
PROBABILISTIC ALGORITHM FOR POLYNOMIAL OPTIMIZATION OVER A REAL ALGEBRAIC SET
复制标题
DOI：
10.1137/130931308
复制
发表时间：
2014-01-01
影响因子：
3.1
通讯作者：
El Din, Mohab Safey
中科院分区：
文献类型：
--
作者：
Greuet, Aurelien;El Din, Mohab Safey
设\(f,f^{(1)},\cdots,f^{(s)}\)是次数至多为\(D\)且具有有理系数的\(n\)元多项式，设\(V\)是\(F=(f^{(1)},\cdots,f^{(s)})\)的公共复解集合。我们给出一种算法，在关于\(F\)的一些正则性假设下，计算映射\(x\to f(x)\)限制在\(V\cap\mathbb{R}^n\)上的全局下确界\(f^*\)的精确表示，即一个在\(f^*\)处取值为\(0\)的一元多项式以及\(f^*\)的一个隔离区间。此外，该算法判定\(f^*\)是否能取到，如果能取到，则返回\(x^*\in V\cap\mathbb{R}^n\)使得\(f(x^*) = f^*\)。这种算法是概率性的。它利用了极簇的概念。其复杂度在\((sD)^n\)上本质上是三次的，在计算输入的复杂度上是线性的。这符合已知的最佳确定性复杂度类\(D^{O(n)}\)。我们报告了首次实现的一些实际实验，该实现可作为一个Maple软件包使用。看起来它能够处理先前精确算法无法解决的全局优化问题，并且能够处理用纯数值技术难以解决的实例。据我们所知，即使在对输入有额外的一般性假设的情况下，它也是第一个将实际效率与对该问题复杂度的良好控制相结合的概率算法。
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.