A Finite-Difference Trust-Region Method for Convexly Constrained Smooth Optimization

Abstract

We propose a derivative-free trust-region method based on finite-difference gradient approximations for smooth optimization problems with convex constraints. For nonconvex problems, we establish a worst-case complexity bound of $\mathcal{O}\left(n{\left(\frac{L}{\ddot{I}}ƒ\hat{I}\mu \right)}^{-2}\right)$ function evaluations for the method to reach an $\left(\frac{L}{\ddot{I}}ƒ\hat{I}\mu \right)$-approximate stationary point, where $n$ is the number of variables, $L$ is the Lipschitz constant of the gradient, and $\ddot{I}ƒ$ is a user-defined estimate of $L$. If the objective function is convex, the complexity to reduce the functional residual below $(L/\ddot{I}ƒ)\hat{I}\mu$ is shown to be of $\mathcal{O}\left(n{\left(\frac{L}{\ddot{I}}ƒ\hat{I}\mu \right)}^{-1}\right)$ function evaluations, while for Polyak-Lojasiewicz functions on unconstrained domains, the bound further improves to $\mathcal{O}\left(n\log \left({\left(\frac{L}{\ddot{I}}ƒ\hat{I}\mu \right)}^{-1}\right)\right)$. Numerical experiments on benchmark problems with noise-free and noisy objective functions, as well as a model-fitting application, show the efficiency of the proposed method relative to state-of-the-art derivative-free solvers for unconstrained and bound-constrained problems.