Repository files navigation

This repository holds the implementation for certifiably solving outlier-robust geometric perception problems to global optimality. The certifiable outlier-robust geometric perception framework contains two main modules:

• A sparse semidefinite programming relaxation (SSR) scheme that relaxes nonconvex outlier-robust perception problems into convex semidefinite programs (SDPs); and

• A novel SDP solver, calledSTRIDE, that solves the generated SDPs at an unprecedented scale and accuracy.

We proposed a preliminary version of the SSR scheme in ourNeurIPS 2020 paper, and released a certifier (that certifies if a given estimate is optimal) based on Douglas-Rachford Splitting (DRS). Please switch to theNeurIPS2020 branch of this repo to checkout the NeurIPS2020 implementation.

If you find this library helpful or use it in your projects, please cite:

@article{Yang22tpami-certifiableperception,title={Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization},author={Yang, Heng and Carlone, Luca},journal={IEEE Transactions on Pattern Analysis and Machine Intelligence},year={2022}}

A general polynomial optimization problem (POP) is an optimization problem of the following standard form

minimize_{x ∈ R^d}      f(x)subject to              h_i(x) == 0, i=1,...,l_h                        g_j(x) >= 0, j=1,...,l_g

wherex ∈ R^d is ad-dimensional decision variable,f(x) is a scalar polynomial objective function,h_i(x),i=1,...,l_h are scalar polynomial functions that define equality constraints, andg_j(x),j=1,...,l_g are polynomial functions that define inequality constraints. POPs are in general nonconvex and NP-hard problems. For example, one can easily see that binary quadratic programming is an instance of POP, because binary constraintsx_i ∈ {+1, -1}, i=1,...,d can be easily written as polynomial equalitiesh_i(x) = x_i^2 - 1 = 0,i=1,...,d.

Semidefinite relaxations are a powerful tool for solving nonconvex POPs toglobal optimality. In this repo, we provide tools that can help the user exploit the power of semidefinite relaxations with minimum efforts.

Lasserre's hierarchy of moment relaxations is a standard technique for relaxing POPs into semidefinite programs (SDPs). The basic idea is as follows. Letkappa be a positive integer (called therelaxation order) such that2*kappa is no smaller than the maximum degree of the defining polynomialsf,h_i,g_j, and letv = [x]_kappa be the set of standard monomials inx with degree up tokappa. For example, supposex = [x_1; x_2], then[x]_kappa withkappa = 2 leads tov = [1; x_1; x_2; x_1*x_2; x_1^2; x_2^2]. The essential idea of Lasserre's hierarchy is to express the original POP problem in the matrix variableX = v*v' (called themoment matrix, by constructionX is positive semidefinite) and relax the POP into a convex SDP. In theseminal paper of Lasserre, it was proved that ifkappa is chosen large enough, then the convex SDP can solve the original nonconvex POP to global optimality.

Although the underlying mechanics of Lasserre's hierarchy can be complicated (the interested reader can refer to Section 2 of ourpaper for technical details), in this repo we provide a simple function that implements Lasserre's hierarchy:

[SDP,info] = dense_sdp_relax(problem,kappa)

where the inputs are:

• problem: a Matlab structure that contains the following fields:
  • vars: a vector of symbolic decision variables (i.e.,x in the POP);
  • objective: a multivariate polynomial that specifies the objective function of the POP (i.e.,f(x) in the POP);
  • equality (optional): a vector of multivariate polynomials with dimensionl_h that specifies the equality constraints of the POP (i.e.,h_i(x),i=1,...,l_h in the POP);
  • inequality (optional): a vector of multivariate polynomials with dimensionl_g that specifies the inequality constraints of the POP (i.e.,g_j(x),j=1,...,l_g in the POP).
• kappa (optional): a positive integer that specifies the relaxation order. Ifkappa is not provided, or provided such that2*kappa is smaller than the maximum degree of the defining polynomials, then our implementation uses the minimum relaxation orderkappa such that2*kappa is no smaller than the maximum degree.

and the outputs are:

• SDP: a Matlab structure that contains the following fields:
  • blk,At,b,C: standard SDP problem data in SDPT3 format. The interested reader should check outSDPT3 user manual for details. Section 2.1 of ourpaper also gives a quick introduction.
  • sedumi: a Matlab structure that provides the standard SDP problem data in sedumi format. The interested reader should checkoutsedumi user manual for details. It is easy to convert sedumi format to MOSEK format, as we will show in one of the examples later.
• info: a Matlab structure that contains additional information about the relaxation.

We now use a simple example on binary quadratic programming (BQP) to illustrate how to supply the POP problem description todense_sdp_relax. The sample code is given below.

%% Generate random binary quadratic programd       = 10; % BQP with d variablesx       = msspoly('x',d); % symbolic decision variables using SPOTLESSQ       = randn(d,d); Q = Q + Q'; % a random symmetric matrixc       = randn(d,1);f       = x'*Q*x + c'*x; % objective function of the BQPh       = x.^2 - 1; % equality constraints of the BQP (binary variables)g       = [x(1)]; % ask the first variable to be positive%% Relax BQP into an SDPproblem.vars            = x;problem.objective       = f;problem.equality        = h; problem.inequality      = g;kappa                   = 2; % relaxation order[SDP,info]              = dense_sdp_relax(problem,kappa);

In this demo code, we first generate a random binary quadratic programming problem using the package SPOTLESS (which is a submodule of this repo), and then pass theproblem structure with fieldsvars,objective,equality, andinequality to the functiondense_sdp_relax to generate SDP relaxations. We recommend the user to run the scriptexample_bqp.m to check how to solve theSDP data using MOSEK, and to see that SDP relaxations can actually solve BQP problems to global optimality.

Coming soon.