A general framework for floating point error analysis of simplex derivatives
This work addresses the need for understanding floating point error in simplex derivatives, which is crucial for practitioners in numerical optimization, but the contribution is incremental as it extends existing error analysis to a general framework.
The paper provides a general framework for floating point error analysis of simplex derivatives, applicable to various gradient approximations in derivative-free optimization. It derives accuracy bounds and gives recommendations for minimal sample set diameters.
Gradient approximations are a class of numerical approximation techniques that are of central importance in numerical optimization. In derivative-free optimization, most of the gradient approximations, including the simplex gradient, centred simplex gradient, and adapted centred simplex gradient, are in the form of simplex derivatives. Owing to machine precision, the approximation accuracy of any numerical approximation technique is subject to the influence of floating point errors. In this paper, we provide a general framework for floating point error analysis of simplex derivatives. Our framework is independent of the choice of the simplex derivative as long as it satisfies a general form. We review the definition and approximation accuracy of the generalized simplex gradient and generalized centred simplex gradient. We define and analyze the accuracy of a generalized version of the adapted centred simplex gradient. As examples, we apply our framework to the generalized simplex gradient, generalized centred simplex gradient, and generalized adapted centred simplex gradient. Based on the results, we give suggestions on the minimal choice of approximate diameter of the sample set.