(246j) Data-Mining Assisted Coarse-Grained Optimization

Authors: 
Pozharskiy, D., Princeton University
Kevrekidis, I. G., Princeton University
The design of complex engineering systems usually leads to high-dimensional optimization
problems, where the objective function is expensive to evaluate and may possess a rugged
surface due to the presence of multiple local minima. In such cases gradient-based minimiza-
tion methods wonâ??t be able to locate the global minima unless very specific initial conditions
are chosen. We assume that some �coarse relaxation� of the objective function is smooth and
we can use this underlying structure to perform coarse-grained optimization. We show that
short runs of a stochastic optimization method, Simulated Annealing [1] can be described by
an effective stochastic differential equation (SDE). Using appropriate subsampling we can
estimate the drift and diffusion coefficients of this SDE [2] and extract information about
the coarse gradient to speed up the �dynamics� of the optimization method. In addition,
we show that if the data lies on a low-dimensional hyperplane in the parameter space, we
can uncover it using data mining techniques such as PCA or diffusion maps [3], making the
exploration of the objective function surface even more efficient.

References

[1] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, â??Optimization by Simulated Annealing,â?
Science, vol. 220, no. 4598, pp. 671â??680, 1983.

[2] G. A. Pavliotis and A. M. Stuart, â??Parameter Estimation for Multiscale Diffusions,â?
Journal of Statistical Physics, vol. 127, pp. 741â??781, mar 2007.

[3] R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. W.
Zucker, â??Geometric diffusions as a tool for harmonic analysis and structure definition of
data: diffusion maps.,� Proceedings of the National Academy of Sciences of the United
States of America, vol. 102, pp. 7426â??31, may 2005.