-

 

 

 




Optimization Online





 

A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization

Albert S. Berahas (albertberahas***at***gmail.com)
Liyuan Cao (lic314***at***lehigh.edu)
Krzysztof Choromanski (kchoro***at***google.com)
Katya Scheinberg (katyas***at***lehigh.edu)

Abstract: In this paper, we analyze several methods for approximating the gradient of a function using only function values. These methods include finite differences, linear interpolation, Gaussian smoothing and smoothing on a unit sphere. The methods differ in the number of functions sampled, the choice of the sample points and the way in which the gradient approximations are derived. For each method, we derive bounds on the number of samples and the sampling radius which guarantee favorable convergence properties for a line search or fixed step size descent method. To this end, we derive one common condition on the accuracy of gradient approximations which guarantees these convergence properties and then show how each method can satisfy this condition. We analyze the convergence properties even when this condition is only satisfied with some sufficiently large probability at each iteration, as happens to be the case with Gaussian smoothing and smoothing on a unit sphere. Finally, we present numerical results evaluating the quality of the gradient approximations as well as their performance in conjunction with a line search derivative-free optimization algorithm.

Keywords: derivative-free optimization, gradient approximations, finite differences, linear interpolation, smoothing

Category 1: Nonlinear Optimization

Category 2: Nonlinear Optimization (Unconstrained Optimization )

Category 3: Nonlinear Optimization (Other )

Citation: Lehigh University 2019. 33 pages, 4 figures.

Download: [PDF]

Entry Submitted: 05/03/2019
Entry Accepted: 05/03/2019
Entry Last Modified: 05/09/2019

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society