论文标题
多尺度半决赛编程方法，用于定位成对结构的定位问题
Multiscale semidefinite programming approach to positioning problems with pairwise structure
论文作者
论文摘要
我们考虑对成对目标函数的优化，即形式的$ h（\ mathbf {x}）= h（x_1，\ ldots，x_n）= \ sum_ {1 \ leq i <j \ leq n} $ \ mathcal {x} _i $。在这种环境中的全局优化通常与虚假的本地最小值的可能存在以及由于维度的诅咒而无法进行全局搜索的可能性。在本文中，我们通过在图形建模中考虑的边缘多层的凸松弛来解决此类问题，以多尺度的方式进行，从而利用了成本函数的平稳性。从理论上讲，与现有方法相比，即使在简单的传感器网络本地化（SNL）中，这种方法也是有利的。我们成功地将方法应用于SNL问题，尤其是噪音高的困难实例。我们还验证了Lennard-Jones电位优化的性能，这受到许多近乎最佳的配置的困扰。我们证明，在MMR中，我们可以有效地探索这些配置。
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.
