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

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_*$ with the linear convergence $\|x_{k+1}-x_*\|_2^2\leqslantρ^k \|x_1-x_*\|_2^2$ for a fixed $00$. Numerical experiments in various dimensions from $5$ to $500$ demonstrate the benefits of the FD-DFD method.