Rigorous Affine Lower Bound Functions for Multivariate Polynomials and Their Use in Global Optimisation
Jürgen Garloff, Andrew Smith · KOPS (University of Konstanz) · 2008
This paper addresses the problem of finding tight affine lower bound functions for multivariate polynomials, which may be employed when global optimisation problems involving polynomials are solved with a branch and bound method. These bound functions are constructed by using the expansion of the given polynomial into Bernstein polynomials. The coefficients of this expansion over a given box yield a control point structure whose convex hull contains the graph of the given polynomial over the box. We introduce a new method for computing tight affine lower bound functions based on these control points, using a linear least squares approximation of the entire control point structure. This is demonstrated to have superior performance to previous methods based on a linear interpolation of certain specially chosen control points. The problem of how to obtain a verified affine lower bound function in the presence of uncertainty and rounding errors is also considered. Numerical results with error bounds for a series of randomly-generated polynomials are given. Key words: Constrained global optimisation, relaxation, affine bound functions, Bernstein polynomials, linear least squares 1