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.