凸松弛
SLAM 中大多数核心估计问题 —— 位姿图优化、旋转平均、点云配准 —— 都是非凸的：旋转约束 刻画出一个弯曲的、非凸的可行集，其上的二次目标函数存在多个局部极小值。迭代求解器（高斯-牛顿法、Levenberg-Marquardt 法）只能收敛到最近的极小值，因此在初始化不佳的情况下，它们可能会悄无声息地返回一个错误的答案。**凸松弛（Convex relaxation）**通过将这个困难的问题替换为一个可以求解到全局最优的凸问题来解决这一困境 —— 并且在有利的条件下，能够可证明地恢复原问题的全局最优解，并附带一个证书（certificate）。
核心思想
给定一个非凸问题 ，构造一个凸问题，使其可行集包含 （且其目标函数是 的下界）。由于松弛后的可行集更大，松弛问题的最优值 是真实最优值 的下界。这会带来两种结果：
- 松弛解恰好对原问题也是可行的。此时该松弛是紧的（tight）：这个解就是全局最优解，而且你能确定这一点。
- 否则，松弛解仍能提供一个界，并且通常能为局部求解器提供良好的舍入解或初始化。
Shor 对 QCQP 的 SDP 松弛
这是最基础的构造方法。许多几何问题都可以写成**二次约束二次规划（QCQP）**的形式：
（例如，旋转矩阵的正交性约束 以及四元数的单位范数约束都是二次的）。引入提升变量 。则 ，问题就变成了关于 的线性问题：
除了秩为 1 的约束之外，其余全部都是凸的。去掉这个秩约束后得到一个半定规划（SDP）——凸问题，可在多项式时间内求解。如果 SDP 的最优解 恰好秩为 1，将其分解为 ，你就得到了原始 QCQP 问题的、经证书验证的全局最优解。
证书与对偶性
凸对偶性提供了一个实用的工具：任何对偶可行点都给出最优值的一个下界，而如果某个候选解的代价恰好与该下界相等，则该解被证书验证为全局最优（zero duality gap）。这催生了一种被*可证明正确（certifiably correct）*的 SLAM 算法所采用的、成本低廉的两步模式：先用快速的局部方法求解非凸问题，再通过检验一个对偶证书（例如某个证书矩阵是否半正定）来验证结果 —— 只要验证成功，就能以局部求解器的速度获得全局最优性保证。
在 SLAM 中出现的场景
- SE-Sync：将位姿图优化（在 上的同步问题）松弛为一个 SDP，该 SDP 在噪声低于某阈值时可证明是紧的，并通过低秩黎曼优化的”阶梯（staircase）“算法而非通用内点法 SDP 求解器高效求解 —— 以实用的速度得到可证明全局最优的位姿图。
- 旋转平均与配准：QUASAR 对基于四元数的旋转搜索进行松弛，TEASER++ 则对鲁棒点云配准进行证书验证，二者都是通过对截断最小二乘（truncated least squares）表述形式进行 SDP 松弛实现的，且都能额外容忍很大比例的外点。
- 标准后端的验证：即使系统只运行普通的高斯-牛顿/LM 方法，基于松弛的证书验证器也可以在位姿图解并非全局最优时发出标记 —— 例如在出现错误的回环检测之后。
一种相近的技术，渐进非凸化（graduated non-convexity，GNC），通过不同的机制追求同样的目标（逃离局部极小值、对外点具有鲁棒性）：它从一个鲁棒代价函数的凸替代形式出发，逐步将其变形回非凸的原始形式，并沿途跟踪解的变化。它本身不提供证书，但可以很自然地与上述证书验证方法配合使用。
对SLAM的意义
SLAM 后端被安全关键系统所信赖，但局部优化并不能保证返回的地图哪怕接近最优 —— 一次糟糕的初始化，或一次错误的外点回环检测，就可能把求解器锁死在一条严重弯曲的轨迹上。凸松弛是*可证明 SLAM（certifiable SLAM）*的理论基石：它解释了全局最优何时以及为何可以达成（噪声适中、松弛是紧的），提供了低成本验证解的工具，并支撑起了那些完全不需要初始猜测就能成功的鲁棒全局求解器（SE-Sync、TEASER++）——这是高斯-牛顿法从根本上做不到的事。