Convex Relaxation

Most core estimation problems in SLAM — pose-graph optimization, rotation averaging, point-cloud registration — are non-convex: the rotation constraints $R \in SO(3)$ carve a curved, non-convex feasible set, and quadratic objectives over it have multiple local minima. Iterative solvers (Gauss-Newton, Levenberg-Marquardt) only converge to the nearest minimum, so with a bad initialization they can silently return a wrong answer. Convex relaxation attacks this by replacing the hard problem with a convex one that can be solved to global optimality — and, in favorable regimes, provably recovers the global optimum of the original problem, with a certificate.

The core idea

Given a non-convex problem $\min_{\mathbf{x} \in \mathcal{C}} f(\mathbf{x})$ , construct a convex problem whose feasible set contains $\mathcal{C}$ (and whose objective lower-bounds $f$ ). Because the relaxed feasible set is larger, the relaxed optimum $p^{\ast}_{\text{relax}}$ is a lower bound on the true optimum $p^{\ast}$ . Two outcomes:

The relaxed solution happens to be feasible for the original problem. Then the relaxation is tight: the solution is the global optimum, and you know it.
Otherwise, the relaxed solution still provides a bound and often a good rounding/initialization for a local solver.

Shor’s SDP relaxation of a QCQP

The workhorse construction. Many geometric problems can be written as a quadratically constrained quadratic program:

$\min_{\mathbf{x}} \ \mathbf{x}^T Q\, \mathbf{x} \qquad \text{s.t.} \quad \mathbf{x}^T A_k\, \mathbf{x} = b_k$

(e.g., rotation-matrix orthogonality $R^T R = I$ and quaternion unit-norm constraints are quadratic). Introduce the lifted variable $X = \mathbf{x}\, \mathbf{x}^T$ . Then $\mathbf{x}^T Q \mathbf{x} = \mathrm{tr}(Q X)$ , and the problem becomes linear in $X$ :

$\min_{X} \ \mathrm{tr}(Q X) \qquad \text{s.t.} \quad \mathrm{tr}(A_k X) = b_k, \quad X \succeq 0, \quad \mathrm{rank}(X) = 1$

Everything here is convex except the rank-1 constraint. Dropping it yields a semidefinite program (SDP) — convex, solvable in polynomial time. If the SDP optimum $X^{\ast}$ turns out to have rank 1, factor it as $X^{\ast} = \mathbf{x}^{\ast} \mathbf{x}^{\ast T}$ and you have the certified global optimum of the original QCQP.

Certificates and duality

Convex duality supplies the practical tool: any dual-feasible point gives a lower bound on the optimum, and a candidate solution whose cost matches that bound is certified globally optimal (zero duality gap). This enables a cheap two-step pattern used by certifiably correct SLAM algorithms: solve the non-convex problem with a fast local method, then verify the result by checking a dual certificate (e.g., positive semidefiniteness of a certificate matrix) — getting global-optimality guarantees at local-solver speed whenever verification succeeds.

Where it shows up in SLAM

SE-Sync: relaxes pose-graph optimization (synchronization over $SE(d)$ ) to an SDP that is provably tight below a noise threshold, and solves it efficiently via a low-rank Riemannian-optimization “staircase” instead of a generic interior-point SDP solver — certifiably globally optimal pose graphs at practical speeds.
Rotation averaging and registration: QUASAR relaxes quaternion-based rotation search, and TEASER++ certifies robust point-cloud registration, both via SDP relaxations of truncated-least-squares formulations that additionally tolerate large outlier fractions.
Verification of standard back-ends: even when a system runs plain Gauss-Newton/LM, a relaxation-based certifier can flag when a pose-graph solution is not globally optimal — e.g., after bad loop closures.

A cousin technique, graduated non-convexity (GNC), pursues the same goal (escaping local minima, robustness to outliers) by a different mechanism: it starts from a convex surrogate of a robust cost and gradually morphs it back into the non-convex original, tracking the solution along the way. It provides no certificate by itself but pairs naturally with the certifiers above.

Why it matters for SLAM

SLAM back-ends are trusted by safety-critical systems, yet local optimization offers no guarantee that the returned map is even close to optimal — a single bad initialization or outlier loop closure can lock the solver into a badly bent trajectory. Convex relaxation is the theoretical backbone of certifiable SLAM: it explains when and why global optimality is achievable (moderate noise, tight relaxations), gives tools to verify solutions cheaply, and underlies robust global solvers (SE-Sync, TEASER++) that succeed with no initial guess at all — something Gauss-Newton fundamentally cannot do.