Autonomous navigation requires an accurate model or map of the environment.
While dramatic progress in the prior two decades has enabled large-scale SLAM,
the majority of existing methods rely on non-linear optimization techniques to
find the MLE of the robot trajectory and surrounding environment. These methods
are prone to local minima and are thus sensitive to initialization. Several
recent papers have developed optimization algorithms for the Pose-Graph SLAM
problem that can certify the optimality of a computed solution. Though this
does not guarantee a priori that this approach generates an optimal solution, a
recent extension has shown that when the noise lies within a critical threshold
that the solution to the optimization algorithm is guaranteed to be optimal. To
address the limitations of existing approaches, this paper illustrates that the
Pose-Graph SLAM and Landmark SLAM can be formulated as polynomial optimization
programs that are SOS convex. This paper then describes how the Pose-Graph and
Landmark SLAM problems can be solved to a global minimum without initialization
regardless of noise level using the Sparse-BSOS hierarchy. This paper also
empirically illustrates that convergence happens at the second step in this
hierarchy. In addition, this paper illustrates how this Sparse-BSOS hierarchy
can be implemented in the complex domain and empirically shows that convergence
happens also at the second step of this complex domain hierarchy. Finally, the
superior performance of the proposed approach when compared to existing SLAM
methods is illustrated on graphs with several hundred nodes.

该文章介绍了如何用稀疏 BSOS 分层算法将姿态 - 图和地标 - 图问题表述为多项式优化问题，并以全局最小化解决了这些问题，同时通过实验展示了该方法的卓越性能。

通过稀疏有界平方和规划实现全局保证最优平面位姿图和地标 SLAM

Guaranteed Globally Optimal Planar Pose Graph and Landmark SLAM via  Sparse-Bounded Sums-of-Squares Programming

We provide a sparse version of the bounded degree SOS hierarchy BSOS [7] for
polynomial optimization problems. It permits to treat large scale problems
which satisfy a structured sparsity pattern. When the sparsity pattern
satisfies the running intersection property this Sparse-BSOS hierarchy of
semidefinite programs (with semidefinite constraints of fixed size) converges
to the global optimum of the original problem. Moreover, for the class of
SOS-convex problems, finite convergence takes place at the first step of the
hierarchy, just as in the dense version.

本文提出了一种稀疏版本的有界次数 SOS 层次结构 BSOS，适用于多项式优化问题，特别针对结构稀疏模式问题。当稀疏模式满足运行交替性质时，这种具有固定大小的半定规划的稀疏 - BSOS 层次结构会收敛于原问题的全局最优解。此外，对于 SOS - 凸问题类，在层次结构的第一步就会出现有限收敛，就像在密集版本中一样。