Algorithms for computing the global infimum and minimum of a polynomial function
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
- Algorithms for computing the global infimum and minimum of a polynomial function
- Global minimization of multivariate polynomials using nonstandard methods
- Deciding reachability of the infimum of a multivariate polynomial
- Global minimization of a multivariate polynomial using matrix methods
- Semi-algebraically connected components of minimum points of a polynomial function
- Algorithms in real algebraic geometry
- An effective decision method for semidefinite polynomials
- Computing global minima to polynomial optimization problems using Gröbner bases
- Global minimization of a multivariate polynomial using matrix methods
- Global optimization of polynomials using generalized critical values and sums of squares
- scientific article; zbMATH DE number 1601215 (Why is no real title available?)
- scientific article; zbMATH DE number 417578 (Why is no real title available?)
- scientific article; zbMATH DE number 3689524 (Why is no real title available?)
- scientific article; zbMATH DE number 1201576 (Why is no real title available?)
- scientific article; zbMATH DE number 1984325 (Why is no real title available?)
- Lectures on formally real fields
- Minimizing polynomials via sum of squares over the gradient ideal
- On the extension of real places
- The search for the maximum of a polynomial
- Global optimization of polynomials over real algebraic sets
- Simple global minimization algorithm for one-variable rational functions
- Solving the equality-constrained minimization problem of polynomial functions
- Computing polynomial univariate representations of zero-dimensional ideals by Gröbner basis
- Determination of the limits for multivariate rational functions
- Globally minimizing polynomials without evaluating derivatives
- Global minimization of multivariate polynomials using nonstandard methods
- Algorithms for computing the global infimum and minimum of a polynomial function
- Deciding reachability of the infimum of a multivariate polynomial
- Computing the global optimum of a multivariate polynomial over the reals
- Minimizing polynomial functions
- Semi-algebraically connected components of minimum points of a polynomial function
- Equality-constrained minimization of polynomial functions
This page was built for publication: Algorithms for computing the global infimum and minimum of a polynomial function
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q424330)
