Speaker: Andrew Smith

Title: Affine lower bound functions for polynomials and their use in global optimisation

Abstract:

We address the problem of finding tight affine lower bound functions for multivariate polynomials. Such underestimating functions are needed if 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. In the univariate case we exploit the convex hull property of the Bernstein polynomials. In the multivariate case the construction of an affine lower bound function requires the solution of a system of linear equations together with a sequence of back substitutions and the computation of slopes. We present a bound on the distance between the given polynomial and its affine lower bound function. In the univariate case this bound exhibits quadratic convergence with respect to the width of the intervals. We also give some suggestions for obtaining a verified affine lower bound function in the presence of rounding errors and discuss the application to the solution of constrained global optimisation problems. Some numerical examples will be presented.

References:
[GJS1] Garloff J., Jansson C. and Smith A.~P. (2003), ``Lower bound functions for polynomials,'' J. Computational and Applied Mathematics Vol. 157, 207--225.
[GJS2] Garloff J., Jansson C. and Smith A.~P. (2003), ``Inclusion isotonicity of convex-concave extensions for polynomials based on Bernstein expansion,'' Computing Vol. 70, 111--119.
[GS] Garloff J. and Smith A.~P. (2004), ``An improved method for the computation of affine lower bound functions for polynomials,'' in ``Frontiers in Global Optimization,'' Floudas C.~A. and Pardalos P.~M., Eds., Series Nonconvex Optimization with its Applications, Kluwer Acad. Publ., Dordrecht, Boston, London.