Solving Large-Scale Convex Relaxations via Solution Verification

Accelerating Certifiable Estimation with Preconditioned Eigensolvers

Solution verification (testing the global optimality of a given candidate solution) is a key step in many state-of-the-art (burer-monteiro
factorization-based) certifiable estimation methods, which entails computing a minimum eigenpair of a certain symmetric certificate matrix.In this paper, we show how to significantly accelerate this verification step, and thereby the overall speed of certifiable estimation methods.First, we show that the certificate matrices arising in the burer-monteiro approach
generically possess spectra that make the verification problem expensive tosolve using standard iterative eigenvalue methods.We then show how to address this challenge using preconditioned eigensolvers ; specifically, we design a specialized solution verification algorithm based upon the locally optimal block preconditioned conjugate gradient (lobpcg) method together with a simple yet highly effective algebraic preconditioner.