Efficient calculation of regular simplex gradients

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Numerical computation of matrix norms, conditioning, scaling (65F35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Derivative-free methods and methods using generalized derivatives (90C56)

Abstract: Simplex gradients are an essential feature of many derivative free optimization algorithms, and can be employed, for example, as part of the process of defining a direction of search, or as part of a termination criterion. The calculation of a general simplex gradient in

m a t h b b R^{n}

can be computationally expensive, and often requires an overhead operation count of

m a t h c a l O (n^{3})

and in some algorithms a storage overhead of

m a t h c a l O (n^{2})

. In this work we demonstrate that the linear algebra overhead and storage costs can be reduced, both to

m a t h c a l O (n)

, when the simplex employed is regular and appropriately aligned. We also demonstrate that a second order gradient approximation can be obtained cheaply from a combination of two, first order (appropriately aligned) regular simplex gradients. Moreover, we show that, for an arbitrarily aligned regular simplex, the gradient can be computed in only

m a t h c a l O (n^{2})

operations.

Recommendations

Cites work

Cited in

(11)

Describes a project that uses

Uses Software

This page was built for publication: Efficient calculation of regular simplex gradients

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2419521)