An optimization algorithm based on stochastic sensitivity analysis for noisy objective landscapes

Abstract

A function minimization algorithm that updates solutions based on approximated derivative information is proposed. The algorithm generates sample points with Gaussian white noise, and approximates derivatives based on stochastic sensitivity analysis. Unlike standard trust region methods which calculate gradients with n or more sample points, where n is the number of variables, the proposed algorithm allows the number of sample points M to be less than n. Furthermore, it ignores small amounts of noise within a trust region. This paper addresses the following two questions: how does the derivative approximation become worse when the number of sample points is small? Can the algorithm find good solutions with inexact derivative information when the objective landscape is noisy? Through intensive numerical experiments using quadratic functions, the algorithm is shown to be able to approximate derivatives when M is about n/10 or more. The experiments using a formulation of the traveling salesman problem show that the algorithm can find reasonably good solutions for noisy objective landscapes with inexact derivatives information. © 2002 Elsevier Science Ltd. All rights reserved.