A New Noise-Based Gradient Method and Its Applications

A new gradient method applicable to local minimization of arbitrary functions is proposed. The proposed method, referred to as stochastic noise reaction (SNR), injects a Gaussian white noise sequence into each variable, and approximates a gradient by averaging the products of the objective function values and the injected noise. Because the gradient approximation in SNR only uses noise and objective function values, the target objective function need not be differentiable, and may even be arbitrary subroutines in a computer program. This property of SNR make it applicable in parametric optimization heuristics
for discrete problems where an objective function is defined as a heuristic procedure that maps continuous parameters to a real value, and the continuous parameters are iteratively updated by a gradient-based method. Computational experiments using tanh**2(x) show that SNR can locally minimize nonlinear functions starting from appropriate initial solutions. A Hopfield-Tank-type, a Held-Karp-type, and a novel addition heuristic-based formulations for the traveling salesman problem are introduced to discuss SNR's applicability to combinatorial optimization problems. Through intensive numerical experiments, SNR is shown to be
applicable to these formulations.