凸緩和(Convex Relaxation)

SLAMにおける主要な推定問題——ポーズグラフ最適化、回転平均化、点群レジストレーション——のほとんどは非凸である。回転制約 $R \in SO(3)$ は湾曲した非凸な可行領域を作り出し、その上の二次目的関数は複数の局所最小値を持つ。反復ソルバー(Gauss-Newton、Levenberg-Marquardt)は最も近い最小値にしか収束しないため、初期化が悪いと誤った答えを静かに返してしまう可能性がある。**凸緩和(convex relaxation)**は、この難問を、大域的最適性まで解ける凸問題に置き換えることでこれに対抗する——そして、条件が良い場合には、証明書付きで元の問題の大域的最適解を証明可能な形で回復する。

中心的なアイデア

非凸問題 $\min_{\mathbf{x} \in \mathcal{C}} f(\mathbf{x})$ が与えられたとき、可行領域が $\mathcal{C}$ を含む(かつ目的関数が $f$ の下界となる)凸問題を構築する。緩和後の可行領域はより大きいため、緩和後の最適値 $p^{\ast}_{\text{relax}}$ は真の最適値 $p^{\ast}$ の下界となる。結果は2つに分かれる。

緩和後の解が、たまたま元の問題に対して可行である場合。このとき緩和は**タイト(引き締まっている)**であり、その解こそが大域的最適解であり、それを知ることができる。
そうでない場合でも、緩和はやはり下界を与え、しばしば局所ソルバーのための良い丸め処理や初期化を提供する。

QCQPに対するShorのSDP緩和

その主力となる構成法である。多くの幾何学的問題は**二次制約付き二次計画問題(QCQP)**として書ける。

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

(例えば、回転行列の直交性 $R^T R = I$ やクォータニオンの単位ノルム制約は二次式である)。持ち上げ変数 $X = \mathbf{x}\, \mathbf{x}^T$ を導入する。すると $\mathbf{x}^T Q \mathbf{x} = \mathrm{tr}(Q X)$ となり、問題は $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$

ここではランク1制約を除いて、すべてが凸である。この制約を除くと**半正定値計画(SDP)**が得られる——凸であり、多項式時間で解ける。SDPの最適解 $X^{\ast}$ がランク1であることがわかれば、 $X^{\ast} = \mathbf{x}^{\ast} \mathbf{x}^{\ast T}$ として分解でき、元のQCQPの証明済み大域的最適解が得られる。

証明書と双対性

凸双対性は実用的な手段を提供する。任意の双対可行点は最適値の下界を与え、そのコストがその下界と一致する候補解は大域的最適性が証明されたことになる(双対ギャップがゼロ)。これにより、*証明可能に正しい(certifiably correct)*SLAMアルゴリズムで使われる安価な2ステップのパターンが可能になる。すなわち、非凸問題を高速な局所解法で解き、その結果を双対証明書(例: 証明書行列の半正定値性)を確認することで検証する——検証が成功する限り、局所ソルバーの速度で大域的最適性の保証を得られる。

SLAMにおける応用例

SE-Sync: ポーズグラフ最適化( $SE(d)$ 上の同期問題)を、あるノイズ閾値以下で証明可能にタイトなSDPに緩和し、汎用の内点法SDPソルバーではなく低ランクのリーマン最適化による「階段(staircase)」法で効率的に解く——実用的な速度で証明済みに大域的最適なポーズグラフを得る。
回転平均化とレジストレーション: QUASARはクォータニオンベースの回転探索を緩和し、TEASER++はロバストな点群レジストレーションを証明する。両者とも、切断最小二乗法(truncated-least-squares)formulationのSDP緩和を通じて、さらに大きな割合のアウトライアも許容できる。
標準バックエンドの検証: システムが単純なGauss-Newton/LMで動作している場合でも、緩和ベースの証明器はポーズグラフの解が大域的最適でないことを検出できる——例えば悪いループクロージングの後など。

近縁の手法である**graduated non-convexity(GNC)**は、同じ目標(局所最小値からの脱出、アウトライアへのロバスト性)を異なる仕組みで追求する。すなわち、ロバストなコストの凸サロゲートから出発し、それを徐々に非凸な元の形へと変形させながら、解を追跡していく。それ自体は証明書を提供しないが、上記の証明器と自然に組み合わせられる。

SLAMにおける意義

SLAMバックエンドは安全性が重要なシステムから信頼されているが、局所最適化は返されたマップが最適解に近いことを何ら保証しない——一度の悪い初期化やアウトライアのループクロージングだけで、ソルバーがひどく歪んだ軌跡に固定されてしまう可能性がある。凸緩和は*証明可能なSLAM(certifiable SLAM)*の理論的な支柱であり、大域的最適性がいつ、なぜ達成可能なのか(適度なノイズ、タイトな緩和)を説明し、解を安価に検証する手段を与え、そして初期推定なしでも成功するロバストな大域的ソルバー(SE-Sync、TEASER++)の基盤となる——これはGauss-Newtonが本質的にできないことである。