Algorithms for computing the global infimum and minimum of a polynomial function (Q424330): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 5 users not shown) | |||
Property / review text | |||
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 | |||
Property / review text: 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 / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: John Perry / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68W30 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 12F10 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6040106 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
polynomial optimization | |||
Property / zbMATH Keywords: polynomial optimization / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
global infimum | |||
Property / zbMATH Keywords: global infimum / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
global minimum | |||
Property / zbMATH Keywords: global minimum / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
strictly critical point | |||
Property / zbMATH Keywords: strictly critical point / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
transfer principle | |||
Property / zbMATH Keywords: transfer principle / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Wu's method | |||
Property / zbMATH Keywords: Wu's method / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
rational univariate representation | |||
Property / zbMATH Keywords: rational univariate representation / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
interval representation | |||
Property / zbMATH Keywords: interval representation / rank | |||
Normal rank | |||
Property / describes a project that uses | |||
Property / describes a project that uses: Maple / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s11425-011-4326-2 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2257286100 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algorithms in real algebraic geometry / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4210476 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Global optimization of polynomials using generalized critical values and sums of squares / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Global minimization of a multivariate polynomial using matrix methods / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computing global minima to polynomial optimization problems using Gröbner bases / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3136296 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the extension of real places / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3884218 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimizing polynomials via sum of squares over the gradient ideal / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4428719 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Lectures on formally real fields / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The search for the maximum of a polynomial / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2716051 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An effective decision method for semidefinite polynomials / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 07:35, 5 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algorithms for computing the global infimum and minimum of a polynomial function |
scientific article |
Statements
Algorithms for computing the global infimum and minimum of a polynomial function (English)
0 references
31 May 2012
0 references
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
0 references
polynomial optimization
0 references
global infimum
0 references
global minimum
0 references
strictly critical point
0 references
transfer principle
0 references
Wu's method
0 references
rational univariate representation
0 references
interval representation
0 references
0 references