Algorithms for computing the global infimum and minimum of a polynomial function
type: Item
instance of: scholarly article
title: Algorithms for computing the global infimum and minimum of a polynomial function
zbMATH Open document ID: 1260.68486
author: Shuijing Xiao
author: Guangxing Zeng
published in: Science China. Mathematics
publication date: 2012-05-31T00:00:00Z
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…
reviewed by: John Perry
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 12F10
zbMATH DE Number: 6040106
zbMATH Keywords: polynomial optimization
zbMATH Keywords: global infimum
zbMATH Keywords: global minimum
zbMATH Keywords: strictly critical point
zbMATH Keywords: transfer principle
zbMATH Keywords: Wu's method
zbMATH Keywords: rational univariate representation
zbMATH Keywords: interval representation
describes a project that uses: Maple
MaRDI profile type: Publication
full work available at URL: s11425-011-4326-2
OpenAlex ID: W2257286100
cites work: Algorithms in real algebraic geometry
cites work: Q4210476
cites work: Global optimization of polynomials using generalized critical values and sums of squares
cites work: Global minimization of a multivariate polynomial using matrix methods
cites work: Computing global minima to polynomial optimization problems using Gröbner bases
cites work: Q3136296
cites work: On the extension of real places
cites work: Q3884218
cites work: Minimizing polynomials via sum of squares over the gradient ideal
cites work: Q4428719
cites work: Lectures on formally real fields
cites work: The search for the maximum of a polynomial
cites work: Q2716051
cites work: An effective decision method for semidefinite polynomials
DOI: 10.1007/S11425-011-4326-2
description: scientific article; zbMATH DE number 6040106