  We propose a new gradient descent algorithm with added stochastic terms for
finding the global optimizers of nonconvex optimization problems. A key
component in the algorithm is the adaptive tuning of the randomness based on
the value of the objective function. In the language of simulated annealing,
the temperature is state-dependent. With this, we prove the global convergence
of the algorithm with an algebraic rate both in probability and in the
parameter space. This is a significant improvement over the classical rate from
using a more straightforward control of the noise term. The convergence proof
is based on the actual discrete setup of the algorithm, not just its continuous
limit as often done in the literature. We also present several numerical
examples to demonstrate the efficiency and robustness of the algorithm for
reasonably complex objective functions.
