Noise – it is a common problem in our environment: traffic horns, loud music from neighbors, the grinding of machines carrying out road repairs. But noise is also a problem in numerical computations. Such noise can occur, for example, from using iterative methods or from conducting Monte Carlo simulations. And just as environmental noise can impair one’s health (“That noise is giving me a headache”), numerical noise can harm a calculation, hampering the ability of an algorithm to converge, for example, or even creating spurious results.
Optimization problems – which represent a major role in real-world applications – are particularly sensitive to noise. Researchers in Argonne’s Mathematics and Computer Science (MCS) Division have now developed a novel trust region algorithm to optimize a function when noise is present in the function evaluations.
Traditional methods for solving such problems include stochastic approximation techniques. While these techniques converge to a stationary point under suitable conditions, however, the convergence is slow. Another common technique involves repeated sampling of the function. But if the noise is deterministic, repeated evaluations provide no additional information.
The new algorithm developed at Argonne is based on model-based trust region methods, one of the most successful classes of methods for solving problems without derivative information. “We believed that such methods would be similarly useful when the function evaluations are corrupted by noise,” said Jeffrey Larson, an assistant computational mathematician in the MCS Division.
To test this belief, the researchers formulated a method that gathers Information about the function by building models using function values from points in the region of interest. This approach allows the algorithm to take larger steps when the models are accurate and more conservative steps when the models are less accurate in predicting the behavior of the function. Further, the new method does not require repeated sampling of the function.
“Our strategy offers a potential advantage because sampling at distinct points provides information about the behavior of the function, whereas repeated sampling provides information only about the noise at a point,” said Larson. “This approach allows the algorithm to take larger steps when the model and function agree.”
The advantages were borne out on a benchmark set consisting of 53 problems containing significant random noise. Three popular approximation methods were tested, along with a prototype of the new algorithm. All four techniques were allowed 10 attempts to solve each problem. The prototype significantly outperformed the three approximation methods, solving 60% of the problems first.
Arguably, the new algorithm does have a potential disadvantage: the cost in evaluating a large number of function values at nearby points. The researchers plan to investigate this issue as part of their ongoing work.
For a full description of the algorithmic approach, see the paper
“Stochastic Derivative-Free Optimization Using a Trust Region Framework”, by J. Larson and S. C. Billups, Computational Optimization and Applications, 2016.