컨벡스 완화 (Convex Relaxation)

SLAM의 핵심적인 추정 문제 대부분 --- 포즈 그래프 최적화, 회전 평균화, 포인트 클라우드 정합 --- 은 **비컨벡스(non-convex)**입니다: 회전 제약 조건 $R \in SO(3)$ 은 곡면의, 비컨벡스인 가능 영역(feasible set)을 만들며, 이 위에서의 이차 목적 함수는 여러 개의 지역 최솟값을 갖습니다. 반복적 솔버(가우스-뉴턴, 레벤버그-마쿼트)는 가장 가까운 최솟값으로만 수렴하므로, 초기화가 나쁘면 조용히 잘못된 답을 반환할 수 있습니다. 컨벡스 완화는 어려운 문제를 전역적으로 최적으로 풀 수 있는 컨벡스 문제로 대체함으로써 이 문제를 공격합니다 --- 그리고 유리한 조건에서는, 원래 문제의 전역 최적해를 인증서(certificate)와 함께 증명 가능하게 복원합니다.

핵심 아이디어

비컨벡스 문제 $\min_{\mathbf{x} \in \mathcal{C}} f(\mathbf{x})$ 가 주어졌을 때, 가능 영역이 $\mathcal{C}$ 를 포함하는(그리고 목적 함수가 $f$ 의 하한이 되는) 컨벡스 문제를 구성합니다. 완화된 가능 영역이 더 크기 때문에, 완화된 최적값 $p^{\ast}_{\text{relax}}$ 는 실제 최적값 $p^{\ast}$ 의 하한입니다. 두 가지 결과가 있습니다:

완화된 해가 마침 원래 문제에 대해서도 가능(feasible)한 경우입니다. 그러면 완화는 **타이트(tight)**합니다: 그 해가 전역 최적해이며, 여러분은 그것을 알 수 있습니다.
그렇지 않으면, 완화된 해는 여전히 하한을 제공하며 종종 지역 솔버를 위한 좋은 라운딩/초기화를 제공합니다.

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의 인증된 전역 최적해를 얻습니다.

인증서와 쌍대성

컨벡스 쌍대성은 실용적인 도구를 제공합니다: 쌍대 가능(dual-feasible)한 임의의 점은 최적값의 하한을 제공하며, 이 하한과 비용이 일치하는 후보 해는 전역 최적으로 인증됩니다(쌍대 간극 0). 이는 증명 가능하게 정확한(certifiably correct) SLAM 알고리즘이 사용하는 저렴한 두 단계 패턴을 가능하게 합니다: 빠른 지역 방법으로 비컨벡스 문제를 풀고, 쌍대 인증서를 확인(예: 인증 행렬의 양의 반정부호성 확인)하여 결과를 검증합니다 --- 검증이 성공할 때마다 지역 솔버의 속도로 전역 최적성 보장을 얻습니다.

SLAM에서 나타나는 곳

SE-Sync: 포즈 그래프 최적화( $SE(d)$ 에 대한 동기화)를 잡음 임계값 이하에서 증명 가능하게 타이트한 SDP로 완화하고, 이를 범용 내부점(interior-point) SDP 솔버가 아니라 저랭크 리만 최적화 “계단(staircase)” 방법을 통해 효율적으로 풀어냅니다 --- 실용적인 속도로 증명 가능하게 전역 최적인 포즈 그래프를 얻습니다.
회전 평균화와 정합: QUASAR는 쿼터니언 기반 회전 탐색을 완화하고, TEASER++는 강건한 포인트 클라우드 정합을 인증합니다. 둘 다 절단된 최소제곱(truncated-least-squares) 형식의 SDP 완화를 통해서이며, 추가로 큰 이상치 비율을 견딜 수 있습니다.
표준 백엔드의 검증: 시스템이 단순한 가우스-뉴턴/LM을 실행하더라도, 완화 기반 인증기는 포즈 그래프 해가 전역 최적이 아닌 경우 --- 예를 들어 나쁜 루프 클로저 이후 --- 를 표시할 수 있습니다.

관련 기법인 **점진적 비컨벡스화(graduated non-convexity, GNC)**는 동일한 목표(지역 최솟값 탈출, 이상치에 대한 강건성)를 다른 메커니즘으로 추구합니다: 강건 비용의 컨벡스 대체(surrogate)에서 시작하여 점차 비컨벡스인 원래 형태로 되돌리면서, 그 과정 동안 해를 추적합니다. 자체로는 인증서를 제공하지 않지만 위의 인증기들과 자연스럽게 짝을 이룹니다.

SLAM에서의 의미

SLAM 백엔드는 안전이 중요한 시스템에서 신뢰받지만, 지역 최적화는 반환된 맵이 최적에 가깝다는 어떠한 보장도 제공하지 않습니다 --- 단 한 번의 나쁜 초기화나 이상치 루프 클로저가 솔버를 심하게 뒤틀린 궤적에 가둘 수 있습니다. 컨벡스 완화는 *증명 가능한 SLAM(certifiable SLAM)*의 이론적 근간입니다: 언제, 왜 전역 최적성이 달성 가능한지(적당한 잡음, 타이트한 완화)를 설명하고, 해를 저렴하게 검증할 도구를 제공하며, 초기 추정값 없이도 성공하는 --- 가우스-뉴턴이 근본적으로 할 수 없는 --- 강건한 전역 솔버(SE-Sync, TEASER++)를 뒷받침합니다.