Derivative-free global minimization for a class of multiple minima problems

Abstract

We prove that the finite-difference based derivative-free descent (FD-DFD) methods have a capability to find the global minima for a class of multiple minima problems. Our main result shows that, for a class of multiple minima objectives that is extended from strongly convex functions with Lipschitz-continuous gradients, the iterates of FD-DFD converge to the global minimizer $x_{\ast }$ with the linear convergence $\Vert x_{k+1}-x_{\ast }{\Vert }_2^2⩽{\rho }^k\Vert x_1-x_{\ast }{\Vert }_2^2$ for a fixed $0<\rho <1$ and any initial iteration $x_1\in {\mathbb{R}}^d$ when the parameters are properly selected. Since the per-iteration cost, i.e., the number of function evaluations, is fixed and almost independent of the dimension $d$, the FD-DFD algorithm has a complexity bound $\mathcal{O}(\log \frac{1}{\epsilon })$ for finding a point $x$ such that the optimality gap $\Vert x-x_{\ast }{\Vert }_2^2$ is less than $\epsilon >0$. Numerical experiments in various dimensions from $5$ to $500$ demonstrate the benefits of the FD-DFD method.

14 pages, 3 figures