TRFD: A Derivative-Free Trust-Region Method Based on Finite Differences for Composite Nonsmooth Optimization
(2025) SIAM Journal on Optimization — Vol. 35, n° 3, p. 1792-1821 (2025)
Files
trfd_preprint.pdf
Preprint
Open Access - Adobe PDF
- 720.61 KB
Details
- Authors
Davar, D. 
- Abstract
- In this work we present TRFD, a derivative-free trust-region method based on finite differences for minimizing composite functions of the form $f(x)=h(F(x))$, where $F$ is a black-box function assumed to have a Lipschitz continuous Jacobian, and $h$ is a known convex Lipschitz function, possibly nonsmooth, with a known Lipschitz constant. The method approximates the Jacobian of $F$ via forward finite differences. We establish an upper bound for the number of evaluations of $F$ that TRFD requires to find an $\epsilon$-approximate stationary point. For L1 and Minimax problems, we show that our complexity bound reduces to $\mathcal{O}(n\epsilon^{-2})$ for specific instances of TRFD, where $n$ is the number of variables of the problem. Assuming that $h$ is monotone and that the components of $F$ are convex, we also establish a worst-case complexity bound, which reduces to $\mathcal{O}(n\epsilon^{-1})$ for Minimax problems. Numerical results are provided to illustrate the relative efficiency of TRFD in comparison with existing derivative-free solvers for composite nonsmooth optimization.
- Affiliations
Citations
Davar, D., & Nunes Grapiglia, G. (2025). TRFD: A Derivative-Free Trust-Region Method Based on Finite Differences for Composite Nonsmooth Optimization. SIAM Journal on Optimization, 35(3), 1792-1821. https://doi.org/10.1137/24m1701587 (Original work published 2025)