Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

RiemannianStaircaseOptimizer: Burer–Monteiro certification

RiemannianStaircaseOptimizer solves matrix-valued Rot2/Rot3 QCQPs through a low-rank Burer–Monteiro factorization, verifies an SDP dual certificate, and increases rank only when the certificate exposes a negative-curvature direction.

Open In Colab

From QCQP to the staircase

The SDP variable Z⪰0Z\succeq0 is factorized as Z=YY⊤Z=YY^\top with Y∈Rr×pY\in\mathbb R^{r\times p}. At rank pp, the optimizer:

  1. constructs QcqpProblem(graph, p);

  2. solves the rank-pp constrained problem with AugmentedLagrangianOptimizer;

  3. builds the certificate S=Q+A∗(λ)S=Q+\mathcal A^*(\lambda);

  4. certifies when S⪰−ηIS\succeq-\eta I;

  5. otherwise appends a column along the most-negative eigenvector and continues at rank p+1p+1.

The current matrix QCQP traits support Rot2 and Rot3. Their solutions share a common right-orthogonal gauge, so rounded absolute rotations must be gauge-aligned before comparison.

certified: True
final rank: 2
certificate eigenvalue/bound: -0.001
ranks visited: [2.]

result.values contains the final unrounded rank-pp matrices. When certification succeeds, result.roundedValues() contains the SVD projection to the intrinsic rotation rank. See RiemannianStaircaseResult.ipynb for diagnostics and recovery details.