Exploiting Chordal Sparsity for Fast Global Optimality with Application to Localization

近年来，机器人学中的许多估计问题已被证明可以使用它们的半定松弛方法全局最优地解决。然而，现成的半定规划求解器的运行时间复杂度在问题规模上高达立方级，这阻碍了涉及大状态维度的问题的实时解决方案。我们展示了对于一大类问题，即那些具有和弦稀疏性的问题，我们可以将这些求解器的复杂度降低到问题规模的线性级别。特别地，我们展示了如何使用众所周知的和弦分解方法将大的正半定变量替换为许多较小的相互连接的变量。这种公式还允许直接应用交替方向乘子方法（ADMM），该方法可以利用并行性以实现更高的可伸缩性。我们在仿真中展示了算法为两个示例问题提供了显著的加速：矩阵加权和仅距离定位。

降低半正定规划求解器的复杂度以实现实时解决大规模问题

使用基于弦图分解的方法将大型半正定规划问题转化为多个小型问题，从而将求解器的复杂度从立方级别降低到线性级别

该方法在两个例子问题中提供了显著的加速，实现了实时解决大规模问题，同时使用ADMM算法可以利用并行性进一步提高可扩展性

近年来，在机器人学中，使用半正定松弛方法求解估计问题已成为一种全局最优解决方案，但是求解器的复杂度仍然是制约实时解决大规模问题的瓶颈。