Parallel implementation of simultaneous perturbation stochastic approximation with adaptive step sizes

The simultaneous perturbation stochastic approximation(SPSA) is an iterative gradient-free optimization algorithm. This algorithm approximates the optimal solution by estimating the gradient of the loss function and uses only 2 values of the loss function to estimate the gradient which is independent of the dimension of the problem. But for the high dimensional problem with large-scale, the convergence of classical SPSA algorithm is slow, even can not converge to the global minimum value. In order to accelerate the convergence of SPSA algorithm and improve the precision of the optimum solution, this paper proposes an improvement of SPSA algorithm based on the adaptive step sizes, which can adjust the step size of each iteration according to the gradient direction. The modified algorithm is implemented by Message Passing Interface (MPI) parallel in each iteration to widen the search scope for the better descending direction in order to accelerate the convergence. Numerical experiments of several classical nonlinear optimization problems shows that the modified SPSA algorithm can accelerate the convergence of nonlinear optimization problems and find the global extremum point of high-dimension for some optimization problems which the SPSA algorithm can not find. It proves that the modified algorithm with adaptive step sizes outperforms the classical SPSA algorithm.