Algorithms for computing the global infimum and minimum of a polynomial function (Q424330)

The authors present a string of algorithms that combine to form a method to compute a polynomial's global infimum, and to determine whether it attains the infimum as a minimum. The introduction implies that this article does not add assumptions or restrictions used by previous works, such as approximating the infima and minima. For exact computation, this work codes the results in the form \((h,a,b)\), where \(h\) is a univariate polynomial which has a root on the open interval \((a,b)\) and \(a,b\in\mathbb Q\). Section 3 introduces the notion of ``strictly critical points [for] semi-algebraic sets''; these are a special kind of closed endpoint of a carefully chosen set. The algorithms presented compare real numbers in the interval representation given above (Algorithm 2.4); count the number of roots of a polynomial over an extension of the reals whose values, when evaluated in a rational function over the same field, are bounded either above and below (Algorithm 2.5) or above, but not below (Algorithm 2.6); compute the standardized minimum with respect to a rational univariate representation (Algorithm 2.8); decide the value of a polynomial with respect to a rational univariate representation (Algorithm 2.9); catch ``strictly critical points'' (Algorithm 3.8); catch ``possible points'' related to infima and minima (Algorithm 4.4); and compute the infimum and decide whether it is attained (4.5). Some of the algorithms may be of interest as applications of Wu's method and of the Sturm and general Sturm-Tarski theorems. The authors have written Maple software to demonstrate the method, and in Section 5 they describe the operation of the software for three examples, one of which is Motzkin's polynomial. The article is difficult to follow. It typically leaps from one algorithm to the next, or from one theorem to the next, with no commentary between the two, either to advise the reader on what is coming next, or to illuminate its purpose, motivation, or intuitive meaning. One would think that, since ``possible points related to the infima and minima'' are the entire purpose of Algorithm 4.4, these points deserve leisurely exposition, perhaps even an example, but none is provided; the exposition of these points is limited to three notation-heavy criteria listed in the ``Output'' section of the algorithm, one alone reading, ``\(\bullet\) \(\inf f(\mathbb R^n)\) is just the least element in the union \(\Pi_0\cup\Pi\), where \[ \Pi_0:=\{\pi(f(e_1\eta,\dots,e_n\eta))|e_i=\pm1, i=1,\dots,n\}, \] and \[ \Pi:=\{\pi(\min(f_{\langle j_1,\dots,j_k\rangle}^{(e_1,\dots,e_j)}:\xi))|0\leq k<n,\langle j_1,\dots,j_k\rangle\in\langle1,\dots,n\rangle^k,(e_1,\dots,e_k)\in\{1,-1\}^k, \] and \(\xi\in\Xi_{\langle j_1,\dots,j_k\rangle}^{(e_1,\dots,e_j)}\).'' The poor quality of the editorial process is in full display in the bibliography. The authors refer readers interested in their Maple program RRUR to [17], a 2004 article they published in the Journal of Symbolic Computation. While this article does make reference to ``a general program for multivariate polynomials'', this is only to decide the semidefiniteness of polynomials; it does not appear to be RRUR. The big shock was citation [15], whose bibliographic entry reads, in its entirety: 15\quad Zeng G X. The software RRUR. In: shengaozhuanjia\@163.com, password: shengao2010