  We consider the optimization of pairwise objective functions, i.e., objective
functions of the form $H(\mathbf{x}) = H(x_1,\ldots,x_N) = \sum_{1\leq i<j \leq
N} H_{ij}(x_i,x_j)$ for $x_i$ in some continuous state spaces $\mathcal{X}_i$.
Global optimization in this setting is generally confounded by the possible
existence of spurious local minima and the impossibility of global search due
to the curse of dimensionality. In this paper, we approach such problems via
convex relaxation of the marginal polytope considered in graphical modeling,
proceeding in a multiscale fashion which exploits the smoothness of the cost
function. We show theoretically that, compared with existing methods, such an
approach is advantageous even in simple settings for sensor network
localization (SNL). We successfully apply our method to SNL problems,
particularly difficult instances with high noise. We also validate performance
on the optimization of the Lennard-Jones potential, which is plagued by the
existence of many near-optimal configurations. We demonstrate that in MMR
allows us to effectively explore these configurations.
