Full-low evaluation methods for derivative-free optimization. (4th March 2023)

• Record Type: Journal Article
• Authors: Berahas, A. S.; Sohab, O.; Vicente, L. N.
• Is Part Of: Optimization methods and software. Volume 38:Number 2(2023)
• Page Start: 386
• Page End: 411
• Publication Date: 2023-03-04
• Subjects: Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2022.2142582
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : We propose a new class of rigorous methods for derivative-free optimization with the aim of delivering efficient and robust numerical performance for functions of all types, from smooth to non-smooth, and under different noise regimes. To this end, we have developed a class of methods, called Full-Low Evaluation methods, organized around two main types of iterations. The first iteration type (called Full-Eval ) is expensive in function evaluations, but exhibits good performance in the smooth and non-noisy cases. For the theory, we consider a line search based on an approximate gradient, backtracking until a sufficient decrease condition is satisfied. In practice, the gradient was approximated via finite differences, and the direction was calculated by a quasi-Newton step (BFGS). The second iteration type (called Low-Eval ) is cheap in function evaluations, yet more robust in the presence of noise or non-smoothness. For the theory, we consider direct search, and in practice we use probabilistic direct search with one random direction and its negative. A switch condition from Full-Eval to Low-Eval iterations was developed based on the values of the line-search and direct-search stepsizes. If enough Full-Eval steps are taken, we derive a complexity result of gradient-descent type. Under failure of Full-Eval, the Low-Eval iterations become the drivers of convergence yielding non-smooth convergence. Full-Low Evaluation methods are shown to be efficient and robust in practice across problems with different levels of smoothness and noise.