Geometry of sample sets in derivative-free optimization: polynomial regression and underdetermined interpolation
Department of Mathematical Sciences, IBM T. J. Watson Research Center, Route 134, PO Box 218, Yorktown Heights, NY 10598, USA
CMUC, Department of Mathematics, University of Coimbra, 3001-454 Coimbra, Portugal
Email: arconn{at}us.ibm.com
Email: katya{at}us.ibm.com
Corresponding author. Email: lnv{at}mat.uc.pt
Received on 14 December 2006. Accepted for publication 21 April 2008.
 |
Abstract |
|---|
In recent years there has been a considerable amount of work on the development of numerical methods for derivative-free optimization problems. Some of this work relies on the management of the geometry of sets of sampling points for function evaluation and model building. In this paper we continue the work developed in Math. Program., 111, 141–172) for complete or determined interpolation models (when the number of interpolation points equals the number of basis elements), considering now the cases where the number of points is higher (regression models) and lower (underdetermined models) than the number of basis components. We show that the regression and underdetermined models essentially have similar properties to the interpolation model in that the mechanisms and concepts which control the quality of the sample sets, and hence of the approximation error bounds, of the interpolation models can be extended to the over- and underdetermined cases. We also discuss the trade-offs between using a fully determined interpolation model and the over- or underdetermined ones.
Key Words: multivariate polynomial interpolation; error estimates; poisedness; least squares regression; minimum norm; derivative-free optimization
Dedicated to Prof. M. J. D. Powell on the occasion of his 70th birthday.