Geometry of interpolation sets in derivative free optimization (Q2467163)

The aim of the paper is to describe derivative free optimization methods and to prove their convergence. To compute new iterates in those methods a polynomial interpolation model of the objective function is minimized. An essential tool for proving convergence of those algorithms is an error bound between the interpolation model and the objective function. To derive this error bound the authors use an interesting, intuitive, new concept for the basis of Lagrange polynomials of the interpolation set. The power of this concept is shown in the cases when the interpolation polynomials are linear and quadratic functions. The relation to ``well-posedness'' of the interpolation points is also shown.