Enclosure Methods for Systems of Polynomial Equations and Inequalities

Abstract

Many problems in applied mathematics can be formulated as a system of nonlinear equations or inequalities, and a broad subset are those problems consisting either partially or completely of multivariate polynomials. Broadly speaking, an ‘enclosure’ method attempts to solve such a problem over a specified region of interest, commonly a box subset of Rn, where n is the number of unknowns. Subdivision (or branch-and-bound) is a commonlyapplied scheme, wherein a starting box is successively subdivided into sub-boxes; sub-boxes for which a proof of non-existence of a solution can be completed are discarded. As a component of such, a boundary method attempts to exploit the properties of component functions over the boundary of a sub-box, without considering their behaviour within it.Two main types of non-existence proof are considered for polynomial systems over boxes or sub-boxes. Firstly, the topological degree of a system of equations (considered as a mapping from Rn to Rn) can be computed over a sub-box, which possesses a root-counting property. Together with an enclosure for the determinant of the Jacobian, the existence (or otherwise) of roots in the sub-box can be ascertained. Secondly, and alternatively, a range-enclosing method can be used to compute a guaranteed outer enclosure for the range of a multivariate polynomial over a sub-box; if it does not contain zero, a root is excluded. The Bernstein expansion is used, due to the tightness of the enclosure yielded and its rate of convergence to the true enclosure. In both cases, interval arithmetic is employed to obtain guaranteed enclosures and ensure the rigour of these existence tests.Advances have been made in four main areas. Firstly, an existing recursive algorithm for the computation of topological degree is investigated in detail, including a complexity analysis, and algorithmic improvements are proposed. Secondly, a simple branch-and-bound method for systems of polynomial equations, utilising Bernstein expansion and an existence test by Miranda, is developed, and alternative subdivision strategies are considered. Thirdly, a major improvement of the Bernstein expansion itself is achieved with the development of the implicit Bernstein form, which exhibits greatly improved performance for many categories of polynomials. Finally, several new methods are developed and compared for the computation of affine lower bounding functions for polynomials, which may be employed in branch-and-bound schemes for problems involving inequalities, such as global optimisation problems. Numerical results and an overview of the developed software are given.