RankTools

A C++ library (with Python bindings) implementing CP-Cert, the Central-Path Certifier, together with supporting tools for exploring and exploiting the rank of semidefinite program (SDP) solutions.

CP-Cert is described in:

Following a Unique Path: A Fast Certifier Applied to Outlier-Robust Pose Registration, draft, August 2026.

Equation, algorithm, and table numbers referenced throughout this README refer to that paper.

What this library does

Certifiable methods endow a solution of a non-convex problem with a certificate of global optimality by way of a convex SDP relaxation. The efficient local-solve-then-certify recipe recovers the dual certificate variables from a linear system, but for the tightened relaxations common in robotics that system is underdetermined — the relaxation is primal degenerate — and the only recourse has been to solve the SDP outright with an interior-point method.

CP-Cert closes that gap. Its key observation is that although the dual variables at a degenerate solution are non-unique, the dual variables at any point on the primal central path are unique. Given a candidate solution X̂ = Ŷ Ŷᵀ, CP-Cert perturbs it into the interior of the PSD cone, then applies a primal-only Newton method to trace the central path back to the candidate, recovering the unique dual variables along the way. The trip is redundant in the primal but produces exactly the dual certificate that was missing.

Concretely, the library provides:

1. Global optimality certification via central-path tracing (CPCert) — CPCert.certify is an implementation of Algorithm 2 (CP-Cert) of the paper. Its efficiency comes from a matrix-free preconditioned conjugate gradient solve of the Schur-complement system, with a preconditioner built once from the candidate solution and reused at every iteration.
2. A specialized max-clique / Lovász-theta certifier — MaxCliqueCertifier builds the constraints of the (LT) relaxation of Section IV-A directly in C++, which matters because the data-association problems in the paper have tens of thousands of constraints.
3. Rank reduction — rank_reduction implements the algorithm of Lemon, So & Ye (2016), used to recover a low-rank solution from a higher-rank SDP solution (Section II-C1).
4. Interior point SDP solves through the MOSEK Fusion API, used as the reference solver that CP-Cert is compared against.

Problem form

The standard primal SDP (SDP in the paper) is

ρ_SDP = min   ⟨C, X⟩
        s.t.  ⟨A_i, X⟩ = b_i,   i = 1 ... m
              X ⪰ 0

CP-Cert works on the equivalent cost-constrained problem (CP, Section III-A), which moves the cost into a constraint and maximizes the log-det barrier:

min   -log det(X)
s.t.  ⟨A_i, X⟩ = b_i,   i = 1 ... m
      ⟨C, X⟩ = ρ_SDP + ϵ ρ_c,      ρ_c = |tr(C)|

The solution of this problem traces the central path as ϵ is varied, and converges to the solution of SDP as ϵ → 0. This is why the constraint count reported by the solver (m) is always len(A) + 1: the cost constraint is appended internally as the last constraint, and its multiplier y_{m+1} is the last entry of every multiplier vector. The certificate matrix is recovered from the multipliers by rescaling with that last entry (Eq. 15, 23):

λ_i = y_i / y_{m+1},    H = C + Σ_i A_i λ_i

Certification succeeds when H is PSD and complementary with the candidate to within numerical tolerances (Eq. 5, 24).

Requirements

See Docker/Dockerfile for the full list of required tools. The core dependencies are Eigen3, Boost (filesystem, system), yaml-cpp, OpenMP, and MOSEK 11.1 (Fusion C++ API, expected at /opt/mosek/11.1/tools/platform/linux64x86 — adjust MOSEK_DIR in CMakeLists.txt if yours differs).

Building the C++ library

cmake -S . -B build
cmake --build build -j

CMake options:

Option	Default	Description
BUILD_TESTS	ON	Build the GoogleTest test suite under test/.
BUILD_PYTHON_BINDINGS	OFF	Build the pybind11 ranktools module.
ENABLE_PARALLEL	ON	OpenMP parallelization of hot loops (RANKTOOLS_PARALLEL). Used for the per-constraint sparse-dense products in the matrix-free operator and preconditioner build.
ENABLE_TIMING	OFF	Print internal timing data (TIMING).
PROFILING	OFF	Add -pg -g -O0 profiling flags.

The build also produces the cpcert_certify CLI (src/cpcert_cli.cpp), which runs certification on a problem described by a YAML config.

Python install instructions (uv)

Install system dependencies (needed for scikit-sparse):

sudo apt update
sudo apt install -y build-essential pkg-config libsuitesparse-dev libopenblas-dev gfortran

Install uv:

curl -LsSf https://astral.sh/uv/install.sh | sh
source ~/.bashrc

Create the environment and install all project dependencies (including CUDA 12.1 PyTorch wheels):

cd /workspace
uv sync

Activate the environment:

source .venv/bin/activate

Add specific modules

uv pip install extern/clipper/build/bindings/python

Hereafter, if syncing with uv use the flag --inexact to avoid removing the manually added modules.

Run tests:

pytest

Legacy pip install instructions

Run

pip install -v .

Install-time flags are passed through pip's -C / --config-settings:

pip install .                                        # Release, no debug output
pip install . -C cmake.define.DEBUG_FLAG=ON          # Release + debug prints
pip install . -C cmake.define.ENABLE_PARALLEL=OFF    # disable parallel loops
pip install . -C cmake.define.CMAKE_BUILD_TYPE=Debug # Debug build

---

Python API

Everything below is exposed by the compiled ranktools extension module (see bindings/python/cpcert_bindings.cpp and the type stubs in bindings/python/ranktools.pyi).

Conventions used throughout:

• n is the SDP dimension, r the rank of the candidate solution, and m the number of constraints including the internally-appended cost constraint (so m == len(A) + 1).
• Cost matrices C / M, solutions X, certificates H and factors Y are dense numpy.ndarray of dtype float64.
• Constraint matrices A_i are scipy.sparse matrices (CSC preferred) stored upper-triangular; the lower triangle is implied by symmetry and is ignored if present. Dense numpy.ndarray inputs are also accepted and converted.
• Low-rank factors Y are (n, r) and encode X = Y @ Y.T. The paper's candidate is the rank-one X̂ = x̂ x̂ᵀ with ‖x̂‖ = 1, i.e. r == 1; the implementation generalizes to arbitrary r, testing complementarity as ‖Yᵀ H Y‖_F in place of |x̂ᵀ H x̂|.

Quick start

Certifying a candidate solution, with the paper's recommended solver configuration (matrix-free PCG with the reusable low-rank preconditioner):

import numpy as np
import scipy.sparse as sp
import ranktools

n = 4
C = np.eye(n)                                  # min trace(X)
A = [sp.csc_matrix(np.triu(np.eye(n)))]        # trace(X) = 1
b = [1.0]
rho = 1.0                                      # known optimal value ρ_SDP

params = ranktools.CPCertParams()
params.verbose = False

# Section III-D / III-E: indirect solve with the candidate-based preconditioner
params.lin_solver = ranktools.LinearSolverType.MFCG_LRP
params.lrp_params.method = ranktools.LowRankPrecondMethod.SparseLDLT

# Table VI: τ is set equal to the initial primal perturbation δ
params.delta = 1e-5
params.lrp_params.tau = params.delta
params.eps_cost = params.delta                 # ϵ_0 = δ
params.max_iter = 10                           # K_max
params.early_stop_angle = True                 # θ_max divergence test

cert = ranktools.CPCert(C, rho, A, b, params)

Y0 = np.eye(n) / np.sqrt(n)                    # candidate X̂ = Y0 @ Y0.T
result = cert.certify(Y0)

print(result.certified, result.min_eig, result.complementarity)

Algorithm 2 in terms of the API

Algorithm 2 step	Where it lives
Line 1–2: initialize X ← x̂x̂ᵀ + δI, ϵ ← ϵ_0	certify(Y_0) / get_central_path_point(Y_0); params.delta, params.eps_cost, or an explicit perturb matrix
Line 3: factorize the augmented preconditioner system (32)	Built once inside the solver from params.lrp_params
Line 6: PRECONDCONJGRAD solve of (19)	params.lin_solver = MFCG_LRP, params.lin_solve_*, params.lrp_params
Line 7–8: S ← A*(y), dX ← X − XSX	Internal; A* is exposed as build_adjoint
Line 9–10: LINESEARCH (Algorithm 1) and primal update	params.enable_line_search, alpha_init, ln_search_red_factor, alpha_min
Line 11–12: adaptive ϵ update (22)	params.adaptive_perturb, eps_inc_step_thresh, eps_inc, eps_dec_step_thresh, eps_dec, eps_mult_min
Line 14: candidate certificate Ĥ = S / y_{m+1} (23)	CPCertResult.H; also build_adjoint(result.multipliers)
Line 15–17: complementarity (24) then Cholesky PSD test	params.early_stop_cert, tol_cert_complementarity, tol_cert_psd; exposed as check_certificate
Line 20–21: angle divergence test (25)	params.early_stop_angle, max_angle
Line 23–24: step-norm convergence without a certificate	params.tol_step_norm, eps_mult_min
Line 27: max iterations reached	params.max_iter

Module-level functions

solve_sdp_mosek(C, As, b, verbose=True) -> SDPResult

Solve the primal SDP min ⟨C, X⟩ s.t. ⟨A_i, X⟩ = b_i, X ⪰ 0 with MOSEK. This is the direct-solve baseline that CP-Cert is compared against in Section V, and is also how the paper verifies rank tightness (an interior-point solver converges to the maximally complementary solution, so a rank-one result implies the relaxation is rank tight).

Parameter	Type	Default	Description
C	ndarray (n, n)	—	Cost matrix.
As	list[scipy.sparse]	—	Constraint matrices, each (n, n).
b	list[float]	—	Right-hand side values, length len(As).
verbose	bool	True	Enable MOSEK solver log output.

Returns an SDPResult.

rank_reduction(As, V_init, params=RankReductionParams()) -> ndarray

Reduce the rank of an SDP solution while keeping all constraints satisfied. Implements the algorithm of Lemon, So & Ye (2016) — reference [29] of the paper, cited in Section II-C1 as the means of recovering a low-rank solution when a direct solve returns a solution of rank greater than one.

Parameter	Type	Default	Description
As	list[scipy.sparse]	—	Constraint matrices, each (n, n), upper-triangular storage.
V_init	ndarray (n, r)	—	Initial low-rank factor; the SDP solution is X = V_init @ V_init.T.
params	RankReductionParams	defaults	Algorithm parameters.

Returns ndarray (n, r'): a reduced factor V with r' <= r such that V @ V.T still satisfies all constraints.

CPCert

The CP-Cert certifier. Constraints are supplied by the caller.

CPCert(C, rho, A, b, params=CPCertParams())

Parameter	Type	Default	Description
C	ndarray (n, n)	—	Cost matrix of SDP.
rho	float	—	The known optimal cost value ρ_SDP. CP-Cert assumes the candidate attains it, i.e. ρ_SDP = ⟨C, X̂⟩; it becomes the right-hand side of the cost constraint ⟨C, X⟩ = ρ_SDP + ϵ ρ_c of CP.
A	list[scipy.sparse]	—	Constraint matrices, each (n, n), upper-triangular storage.
b	list[float]	—	Right-hand side values for ⟨A_i, X⟩ = b_i.
params	CPCertParams	defaults	Algorithm parameters. Copied into the object; mutate afterwards through the params attribute.

The Python wrapper owns copies of A and b, so the caller's arrays may be garbage collected freely.

Note on Assumption 1: CP-Cert can only certify X̂ if it is the limit point of the primal central path. By Proposition 1 this holds whenever the relaxation is rank tight and at least one b_i ≠ 0. A certification failure therefore means either that the candidate is not globally optimal or that the relaxation is not rank tight — the two cannot be distinguished from a failed certificate alone.

Attributes

Attribute	Type	Access	Description
dim	int	read-only	SDP dimension n.
m	int	read-only	Number of constraints including the cost constraint, i.e. the dimension of y in Eq. 12–14. Equals len(A) + 1, or fewer if params.check_indep_constr filtered dependent constraints at construction.
params	CPCertParams	read/write	Live reference to the object's parameters; individual fields can be set in place (e.g. cert.params.max_iter = 10).

certify(Y_0, perturb=None) -> CPCertResult

Run CP-Cert (Algorithm 2) to certify the candidate solution Y_0 as globally optimal. This is the primary entry point: it traces the central path back to the candidate, builds the certificate matrix from the resulting multipliers, evaluates the optimality conditions, and reports timing and iteration count.

Parameter	Type	Default	Description
Y_0	ndarray (n, r)	—	Candidate low-rank factor; the candidate solution is X̂ = Y_0 @ Y_0.T.
perturb	ndarray (n, n) or None	None	Initial perturbation added to X̂ (Eq. 16) to place the starting iterate strictly inside the PSD cone. If None, params.delta * I is used, which is the paper's X_o = X̂ + δI. Pass an explicit matrix to perturb anisotropically.

Certification failure is reported through result.certified == False, together with the min_eig and complementarity values that failed the test.

solve_sdp_mosek() -> SDPResult

Solve this object's SDP (its C, A and b) with MOSEK. Takes no arguments; verbosity follows params.verbose. This is the convenient way to reproduce the paper's comparisons: construct the certifier once, then obtain both the CP-Cert certificate and the Mosek reference solution for the identical problem.

export_problem(file_path, problem_name, solution) -> None

Write the current problem to a text file in the format read by load_problem_from_file in the C++ test helpers (test/include/).

Parameter	Type	Default	Description
file_path	str	—	Destination file path.
problem_name	str	—	Value written to the name field.
solution	ndarray	—	Known solution written in the soln block; may be empty (0 rows).

MaxCliqueCertifier

Specialization of CPCert for the data-association relaxation LT of Section IV-A — the Lovász-theta-inspired relaxation of the maximum spectral radius clique problem MSRC:

max   ⟨M, X⟩
s.t.  X_ij = 0  if M_ij = 0
      tr(X) = 1
      X ⪰ 0

It exposes exactly the same attributes and methods as CPCert and differs only in construction: the constraints are built in C++ from the cost matrix rather than assembled by the caller. This matters at the scale the paper reports — with 200 associations and a high outlier ratio the relaxation has close to 20,000 constraints, and building that many sparse A_i in Python dominates the certification time it is meant to measure.

MaxCliqueCertifier(M, rho, params=CPCertParams())

Parameter	Type	Default	Description
M	ndarray (n, n)	—	Cost matrix, used directly as C. Its off-diagonal zero entries define the non-edge constraints.
rho	float	—	Known optimal cost value ρ_SDP of the minimization form.
params	CPCertParams	defaults	Algorithm parameters.

The generated constraint set is one constraint per non-edge — an off-diagonal (i, j) with M[i, j] == 0.0 exactly — forcing X[i, j] = 0, plus a final trace constraint tr(X) = 1.

Sign convention. LT is a maximization over the affinity matrix, while this library minimizes, so pass the negated affinity matrix and the negated optimal value: C = -affinity, rho = -⟨affinity, X̂⟩. Zeroing is preserved under negation, so the non-edge pattern is unaffected. This is the convention used by the test fixtures (test/include/lovasz_theta_problems.hpp and python/tests/fixtures.py), where C = -1 on all entries of a complete graph and rho = -|clique|.

Candidate solutions come from a local solver — CLIPPER in the paper. For a discrete candidate set (from PMC or RANSAC) use Algorithm 3 of the paper first: verify the set is a clique, then take the leading eigenvector of the restricted affinity matrix as Y_0 (Theorem 2).

CPCertParams

Default-constructible parameter struct for CPCert and MaxCliqueCertifier; all fields are read/write. The Paper column gives the corresponding symbol from Table VI where one exists.

General

Parameter	Paper	Type	Default	Description
verbose	—	bool	True	Print per-iteration and summary diagnostics. Also controls MOSEK verbosity in solve_sdp_mosek().
max_iter	K_max	int	50	Maximum number of centering iterations; reaching it is a certification failure (Algorithm 2, line 27). The paper uses K_max = 10 for both applications.
tol_step_norm	τ_step	float	1e-8	Terminate when ‖dX‖ falls below this value. Combined with ϵ having reached its floor, this is the converged-without-certifying failure of line 23. Paper: 1e-10.
tol_rank_sol	—	float	1e-4	Eigenvalue threshold used to report the rank of the solution. Display only — does not affect convergence or the certificate.
rescale_lin_sys	—	bool	False	Rescale the Schur-complement system by a fixed factor, equivalent to scaling the log-det objective. Improves conditioning; normally only needed with the diagonal-preconditioned CG solver.
rescaling_factor	—	float	1e-5	Factor applied when rescale_lin_sys is enabled.
lin_solver	—	LinearSolverType	LDLT	Solver for the Schur-complement system D y = d (Eq. 19–20). The paper's method is MFCG_LRP; LDLT forms and factorizes D densely instead.
reuse_multipliers	—	bool	True	Warm-start each conjugate-gradient solve from the previous outer iteration's multipliers, as described in Section III-D (zeros on the first iteration).

Linear independence check

Not part of Algorithm 2. This supports footnote 9 of the paper, which assumes B̄ has full column rank; the check detects and removes the redundant constraints that would violate that.

Parameter	Paper	Type	Default	Description
check_indep_constr	—	bool	False	At construction, run a rank-revealing sparse QR over B̄ = [vec(A_1) ... vec(A_m) vec(C)] and drop linearly dependent constraints, keeping the cost column. Reduces m.
tol_indep_constr	—	float	1e-3	Pivot threshold for that QR, i.e. the tolerance for declaring a constraint dependent.

Perturbation and the ϵ schedule

The initial iterate is pushed into the interior of the PSD cone (Eq. 16), and the cost-constraint offset ϵ is then driven down adaptively (Eq. 22) so the iterates converge along the central path back to the candidate.

Parameter	Paper	Type	Default	Description
delta	δ	float	1e-5	Primal perturbation magnitude. Used as δ I in X_o = X̂ + δ I when no explicit perturb matrix is given. Zero disables perturbation.
perturb_cost	—	bool	True	Apply the ϵ ρ_c offset to the cost constraint. This is the perturbation of Eq. 14 and should stay enabled.
perturb_constraints	—	bool	False	Additionally offset the remaining constraints b_i. Not part of the paper's formulation, which perturbs only the cost constraint.
eps_cost	ϵ_0	float	1e-5	Initial value of ϵ for the cost constraint. The paper sets ϵ_0 = δ.
eps_constr	—	float	1e-5	Initial offset for the other constraints; only used when perturb_constraints is enabled.
adaptive_perturb	—	bool	True	Enable the line-search-driven update of ϵ (Eq. 22). With it disabled, ϵ stays at its initial value.
eps_mult_min	ϵ̃_min	float	1e-2	Floor for ϵ as a ratio of ϵ_0, so ϵ_min = ϵ̃_min ϵ_0 (footnote 7). The paper's runs correspond to ϵ̃_min = 1e-3.
eps_inc_step_thresh	α_inc	float	0.1	If the line-search step α ≤ α_inc — the iterate is crowding the cone boundary — increase ϵ to target a central-path point farther from the boundary.
eps_inc	σ_inc	float	2.0	Multiplicative factor applied on that increase.
eps_dec_step_thresh	α_dec	float	0.9	If α ≥ α_dec — large steps are being taken — it is safe to reduce ϵ.
eps_dec	σ_dec	float	0.6	Multiplicative factor applied on that decrease.

Iterative linear solve

Section III-D. Used when lin_solver is CG, MFCG_DP or MFCG_LRP. The matrix-free operator forms D y in three steps — S = A*(y), Y = X S X, z_i = ⟨B_i, Y⟩ — which is linear in m, exploits the sparsity of the A_i, and parallelizes over the final step.

Parameter	Paper	Type	Default	Description
lin_solve_max_iter	—	int	500	Maximum conjugate-gradient iterations per outer iteration.
lin_solve_tol	—	float	1e-5	Convergence tolerance for the conjugate-gradient solve. Note: convergence can be sensitive to this value since it governs the accuracy main linear solve.
lrp_params	—	LowRankPrecondParams	defaults	Low-rank preconditioner settings, used when lin_solver == MFCG_LRP. Returned by reference, so params.lrp_params.tau = 1e-6 works in place.
tau_lrp	τ	float	1e-5	Backward-compatible alias for lrp_params.tau.

Line search

Algorithm 1: backtrack until the updated iterate is strictly positive definite, tested via the diagonal of an LDL factorization.

Parameter	Paper	Type	Default	Description
enable_line_search	—	bool	True	Enable the backtracking line search.
alpha_init	α_0	float	1.0	Initial step size.
ln_search_red_factor	σ_α	float	0.8	Backtracking reduction factor; must lie in (0, 1).
alpha_min	α_min	float	1e-10	Smallest permitted step size; reaching it terminates the line search with failure.

Certificate and early stopping

Section III-C. These are the conditions under which Algorithm 2 returns.

Parameter	Paper	Type	Default	Description
early_stop_cert	—	bool	True	Test the certificate at every iteration and return as soon as it passes (Algorithm 2, lines 15–19). This is what makes CP-Cert cheap in the success case — exact convergence to the central path's limit point is neither achievable nor necessary.
tol_cert_psd	τ_p	float	1e-5	Tolerance for Ĥ + I τ_p ∈ S_+; also the diagonal shift used by check_certificate.
tol_cert_complementarity	τ_c	float	1e-5	Tolerance on |⟨Ĥ, X̂⟩| for the complementarity condition of Eq. 24.
tol_cert_primal_feas	—	float	1e-5	Primal feasibility tolerance (constraint violation) applied alongside the certificate test.
early_stop_angle	—	bool	False	Enable the angle test of Eq. 25 (Algorithm 2, lines 20–22): if the primal iterate diverges from the candidate, the candidate is not the central path's limit point and certification cannot succeed. The paper's Algorithm 2 always applies this test — enable it to reproduce the reported failure-case runtimes.
max_angle	θ_max	float	1e-2	Maximum permitted angle (radians) between X and X̂ when early_stop_angle is enabled. The paper uses 1e-2 for data association and 8e-5 for pose registration.
use_cert_centrality_metric	—	bool	False	Additionally use the centrality metric of He et al. (1997) in the certificate check. Not part of the paper's algorithm.
tol_cert_centrality	—	float	1e-5	Tolerance for that centrality metric.

LowRankPrecondParams

Section III-E. Settings for the preconditioner D̃ = τ² B̄ᵀB̄ + V Vᵀ (Eq. 30), applied by solving the sparse augmented system of Eq. 32. Because CP-Cert stays near a known candidate, this system is factorized once at the start and its factors reused at every iteration — which is the difference from general low-rank interior-point solvers that must periodically recompute their preconditioner.

Parameter	Paper	Type	Default	Description
tau	τ	float	1e-5	Diagonal perturbation of the candidate used to build the preconditioner, X̃ = X̂ + τ I. The paper recommends setting it equal to delta.
method	—	LowRankPrecondMethod	SparseLDLT	Factorization used to build and apply the preconditioner. SparseLDLT is the paper's choice: sparse LDL of Eq. 32 with the Appendix D form of V.
use_approx	—	bool	False	Use the cheaper approximation Z Zᵀ = 2τ I instead of Z Zᵀ = X + W_0. Only relevant to the Zhang–Lavaei formulation; the Appendix D derivation avoids the Cholesky factorization of X + W_0 entirely.
ldlt_zero_thresh	—	float	1e-14	Threshold below which eigenvalues are treated as zero in the LDLT-based builds.

RankReductionParams

Default-constructible settings for rank_reduction. All fields are read/write.

Parameter	Type	Default	Description
targ_rank	int	1	Target rank; supersedes the other stopping conditions. Set to -1 to ignore and rely on the null-space test.
null_tol	float	1e-5	Tolerance on the smallest singular value when testing for a null space. If there is no null space and no target rank is set, the algorithm exits.
eig_tol	float	1e-9	Eigenvalue tolerance used when removing dimensions from the SDP solution space.
max_iter	int	-1	Maximum number of reduction iterations; -1 for unlimited.
verbose	bool	True	Print per-iteration diagnostics.

Result types

CPCertResult

Returned by certify. All fields are read-only.

Field	Paper	Type	Description
X	X	ndarray (n, n)	Final primal iterate on the central path.
H	Ĥ	ndarray (n, n)	Certificate matrix S / y_{m+1} (Eq. 15, 23).
multipliers	λ	ndarray (m,)	Dual multipliers rescaled by the cost multiplier, λ_i = y_i / y_{m+1}.
violation	—	ndarray (m,)	Constraint residuals at X, as returned by eval_constraints.
certified	—	bool	True when min_eig >= -tol_cert_psd and complementarity <= tol_cert_complementarity — the test of Eq. 5. True means the candidate is certified globally optimal; False means either the candidate is not globally optimal or the relaxation is not rank tight.
min_eig	—	float	Minimum eigenvalue of Ĥ.
complementarity	—	float	‖Y_0ᵀ Ĥ Y_0‖_F, i.e. |⟨Ĥ, X̂⟩| of Eq. 24.
solver_time	—	float	Wall-clock time of the centering solve, in seconds. This is the quantity reported in Tables III and V.
num_iterations	—	int	Number of centering iterations performed, out of max_iter.

SDPResult

Returned by solve_sdp_mosek (module-level function and method). All fields are read-only.

Field	Type	Description
X	ndarray (n, n)	Primal solution. Maximally complementary, so a rank-one result implies the relaxation is rank tight.
y	ndarray (m,)	Dual multipliers for the equality constraints ⟨A_i, X⟩ = b_i.
S	ndarray (n, n)	Dual PSD matrix C - Σ_i y_i A_i.
obj_value	float	Objective value ⟨C, X⟩ at the solution.
solver_time	float	Time taken by MOSEK, in seconds.

Enumerations

LinearSolverType

Solver used for the Schur-complement system D y = d (Eq. 19–20), the computational bottleneck of the method. Values are also exported at module scope (e.g. ranktools.MFCG_LRP).

Value	Description
LDLT	Cholesky-based LDLT direct solver. Forms the dense m × m matrix D and factorizes it — tractable only for small m.
CG	Conjugate gradient on the explicitly formed D.
MFCG_DP	Matrix-free conjugate gradient with a diagonal (Jacobi) preconditioner. Section III-E reports that this did not give sufficient stability on the paper's test problems.
MFCG_LRP	Matrix-free conjugate gradient with the candidate-based low-rank preconditioner of Section III-E, configured by lrp_params. This is CP-Cert as evaluated in the paper.

LowRankPrecondMethod

Factorization used to build the low-rank preconditioner. Values are also exported at module scope.

Value	Description
SparseLDLT	Sparse LDL of the augmented system (Eq. 32), with the top-right block V in the Appendix D form (Eq. 31) that avoids a Cholesky factorization. The paper's method.
SparseLDLT_ZL	Same sparse LDL, but with V = B̄ᵀ(U ⊗ Z), Z Zᵀ = X + W_0 — the original Zhang & Lavaei (2017) formulation of reference [37]. More expensive; requires the Cholesky factorization that Appendix D removes.
DenseLDLT	Dense LDLT factorization of the augmented system.
DenseQR	Dense QR factorization of [τ B̄; Vᵀ], applied as Rᵀ R x = b.
SparseQR	Sparse QR of the same augmented matrix.
DenseLU	Dense LU factorization.
DirectInverse	Direct inverse of the preconditioner matrix.

Note: only SparseLDLT, SparseLDLT_ZL, DenseLDLT, DenseQR and SparseQR have build paths implemented; selecting DenseLU or DirectInverse raises LowRankPrecond: Unknown preconditioning method.

PyTorch reference implementation

python/ranktools_pytorch/ holds a pure-Python PyTorch implementation of the certifier (CPCertPyTorch) using the MFCG_LRP solver with the sparse LDLT preconditioner. It mirrors the C++ algorithm and exists for GPU experiments and cross-checking against the compiled implementation; see python/examples/ for usage and python/examples/benchmark_cpu_vs_gpu.py for a CPU/GPU comparison. Note that the paper's reported runtimes are all from the C++ implementation on CPU.

Tests

C++ tests (GoogleTest, built when BUILD_TESTS=ON):

cd build && ctest

The suite includes Lovász-theta / max-clique problems (test/max_clique_certifier_test.cpp, test/cpcert_test.cpp), which certify candidates obtained from Mosek and cross-check MaxCliqueCertifier against an CPCert built with explicitly supplied constraints.

Python tests:

pytest

A standalone smoke test / usage example for the bindings lives at bindings/python/test_cpcert.py.

Limitations

Per Section VI of the paper:

• Parameters must be tuned per problem class; there is no self-scaling parameterization yet (compare the δ/τ/θ_max columns of Table VI).
• The primal variable X is stored densely despite being low rank, and manipulating it is the remaining bottleneck. The library handles a single monolithic PSD variable, so chordal decomposition into multiple parallel PSD blocks is not currently supported.