STRIDE: SpecTrahedRal Inexact projected gradient Descent along vErtices

A Solver for Large-Scale Rank-One Semidefinite Relaxations

About

STRIDE is designed for solving high-order semidefinite programming (SDP) relaxations of nonconvex polynomial optimization problems (POPs) that admit rank-one optimal solutions. STRIDE is the first algorithmic framework that blends fast local search on the nonconvex POP with global descent on the convex SDP. Specifically, STRIDE follows a globally convergent trajectory driven by an inexact projected gradient method (PGM) for solving the SDP, while simultaneously probing long, but safeguarded, rank-one "strides", generated by fast nonlinear programming algorithms on the POP, to seek rapid descent.

If you want to learn more about how to relax a general polynomial optimization problem (POP) into a standard SDP via Lasserre's hierarchy (dense or sparse), please check out the tutorial and example for a binary quadratic programming problem, where we show how to use our efficient implementation of the hierarchy that outputs standard SDP data that can be used by various solvers, including STRIDE, MOSEK, SDPT3, Sedumi, SDPNAL+, and so on.

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

@article{Yang21arxiv-STRIDE,
  title={An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization},
  author={Yang, Heng and Liang, Ling and Carlone, Luca and Toh, Kim-Chuan},
  journal={arXiv preprint arXiv:2105.14033},
  year={2021}
}

Dependencies

In order to run the example code example_quasar.m, please download the following two packages and provide paths to them in example_quasar.m:

• SDPNAL+: STRIDE uses the ADMM+ subroutine in SDPNAL+ to warmstart. Note that the SDPNAL+ software package seems to have been updated after STRIDE was released. We recommend downloading a version of SDPNAL+ that is compatible with STRIDE from here.
• Manopt: in example_quasar.m, STRIDE uses Manopt to perform local search to generate rank-one strides.

Example

We provide a starting example about how to use STRIDE to solve the QUASAR semidefinite relaxation in the script example_quasar.m, you can simply run the script in Matlab.

We also provide an example about using MOSEK to solve the same QUASAR problems, you can run the script example_quasar_mosek.m in Matlab (for which please download MOSEK).

Surprise: you should see STRIDE being 50 times faster on data/quasar_100_1.mat (100 measurements, 20 seconds vs. 1000 seconds) and 30 times faster on data/quasar_50_1.mat (50 measurements, 2 seconds vs. 60 seconds). Note that MOSEK cannot solve larger problems than data/quasar_100_1.mat, but STRIDE has successfully solved problems with up to 1000 measurements (in which case the SDP has millions of constraints, see our paper). However, the goal of STRIDE is not to replace MOSEK -for generic SDP problems that have small to medium size, MOSEK is still the go-to solver- but to provide a solution for large-scale SDPs arising from rank-one semidefinite relaxations that are far beyond the reach of MOSEK.

For more examples of using STRIDE for machine perception applications, please navigate to the repo CertifiablyRobustPerception.

How to use STRIDE

The function signature for STRIDE is

[out,Xopt,yopt,Sopt] = PGDSDP(blk,At,b,C,X0,options)

where PGDSDP stands for projected gradient descent in solving a generic SDP problem (which is the backbone of STRIDE). We now describe the detailed input and out of STRIDE.

Input

• blk,At,b,C: standard SDP data in SDPT3 format. A standard SDP problem can be fully described by blk,At,b,C, where blk describes the sizes of the positive semidefinite constraints (i.e., blocks, we do not support other conic constraints such as second-order cone and nonnegative orthant), At,b describes the linear constraints, and C describes the linear cost function. blk,At,C should be Matlab cell arrays, while b should be a Matlab array. Please refer to the SDPT3 user guide for details. We provide two example problem data for the QUASAR SDP in the subfolder data. If you are interested in how to generate standard SDP problem data from semidefinite relaxations of polynomial optimization problems, please navigate to the repo CertifiablyRobustPerception.

• X0: a primal initial guess for the SDP problem. Set X0 = [] if no initial guess is available. A good way of providing an initial primal guess is to use fmincon in Matlab to solve the original polynomial optimization problem (if the POP admits a manifold structure, Manopt should be preferred), obtain a local optimizer, and lift the local optimizer to a rank-one feasible point of the SDP. Please read our paper for more details.

• options: a Matlab structure that provides more information. There are many available parameters in options, but there are two parameters that are required:

  • options.rrFunName: a string that provides the name of the Matlab function that implements a local search scheme. For example, in the provided example example_quasar.m, we use options.rrFunName = 'local_search_quasar' to tell STRIDE that the function local_search_quasar.m implements the local search scheme.

  • options.SDPNALpath: a string that provides the path to the software package SDPNAL+. STRIDE uses the admmplus subroutine in SDPNAL+ to warmstart. The other optional parameters are described in more details below.

Output

• Xopt,yopt,Sopt: an (approximate) optimal solution to the SDP. In many cases, STRIDE can solve the SDP to very high accuracy (even better than MOSEK). The printout of STRIDE will show the KKT residuals at Xopt,yopt,Sopt.
• out: a Matlab structure that contains other information such as run history and runtime.

Available parameters

We now list all the available but optional parameters in options:

• options.S0: a dual initial guess. Typically it is difficult to have a good guess on the dual variables. If not provided, STRIDE uses ADMM+ to generate dual initial guess. However, in some cases, one can exploit problem structure to provide clever dual initializations, please checkout our paper for details.

• options.tolADMM: accuracy tolerance for using ADMM+. We note that this is perhaps the most important parameter to tune for a fast performance. Setting options.tolADMM very low (e.g., 1e-12) will ask ADMM+ to provide a very accurate warmstart (in the price of more ADMM+ iterations and runtime) so that the main STRIDE algorithm will converge very fast. Setting options.tolADMM very high (e.g., 1e-4) will not require an accurate warmstart from ADMM+ (so very few ADMM+ iterations and less runtime), but it may take many STRIDE main PGD iterations. We recommend tuning this parameter for each specific problem. For the QUASAR examples in this repo, options.tolADMM = 1e-4 works very well.

• options.maxiterADMM: maximum ADMM+ iterations, default 1e4.

• options.tolPGD: accuracy tolerance for STRIDE, in terms of maximum relative KKT residual, default 1e-6.

• options.pgdStepSize: step size for projected gradient descent. We recommend setting options.pgdStepSize = 10.

• options.maxiterPGD: maximum outer iterations of STRIDE (in performing projected gradient descent), default 10.

• options.lbfgsmemory: memory of L-BFGS, default 10.

• options.maxiterLBFGS: maximum iterations of L-BFGS, default 1000.

• options.lbfgseps: boolean value to decide if using inexactness in L-BFGS (what we call modified L-BFGS), default options.lbfgseps = true. In practice we found this does not have significant effect on the convergence speed.

• options.rrOpt: a array that contains the indices of the eigenvectors to be rounded in local search, default options.rrOpt = 1:3 and STRIDE generates rounded hypotheses from the leading 3 eigenvectors.

• options.rrPar: a Matlab structure that contains all user-defined information needed to perform local search. For a template about how to implement a local search scheme, please see below.

Implement your local search scheme

The function signature for a local search scheme is

[Xhat,fhat,info] = local_search_func(Xbar,C,rrPar,rrOpt,roundonly)

where local_search_func is the string that needs to be passed to STRIDE's function call by using options.rrFunName = 'local_search_func', so that STRIDE can evaluate the local_search_func.m function to generate rank-one hypotheses.

We now explain the input and output of local_search_func.

Input

• Xbar: a primal SDP iterate, generated by STRIDE's projected gradient descent backbone. Xbar has the same format as X0 and Xopt and is a cell array of positive semidefinite matrices (block structure defined by blk).

• C: linear cost function, same as the C in standard SDP data.

• rrPar: a Matlab structure that contains any data that are necessary for performing local search using Xbar. For example, rrPar can contain suitable data from the original POP. This rrPar is provide by using options.rrPar when calling STRIDE.

• rrOpt: a array that contains the indices of the eigenvectors to be rounded in local search. This rrOpt is provided by using options.rrOpt when calling STRIDE.

• roundonly: a boolean value that decides if STRIDE should just perform rounding (without local search). If roundonly = true, then the user should specify a routine that generates a rounded feasible POP point from Xbar. If roundonly = false, then the user should specify a routine that not only generates a rounded POP iterate, but also perform local search starting from the rounded POP iterate, using suitable nonlinear programming techniques.

Output

• Xhat: a rank-one SDP iterate, generated by rounding, local search and lifting from Xbar.

• fhat: value of the SDP objective function attained by Xhat, by using the cost matrix C.

• info (optional output): a structure that contains the following information:

  • info.nlpsuccess: a boolean value that indicates whether the local search has been successful (for example, if the nonlinear programming solver has failed, then info.nlpsuccess = false).
  • info.minidx: the index of the eigenvector, from which the local search solution is best. For example, if rrOpt = 1:3, and the local solution obtained from rounding the second eigenvector attained the lowest cost, then info.minidx = 2.
  • info.pobjs: the objective values of all local search solutions.
  • info.diffpobj: which is simply info.diffpobj = info.pobjs(1) - fhat.

Although the local_search_func may sound complicated to implement, it is quite natural, because it is simply how one would implement a local optimization method for the POP. Please see utils/local_search_quasar.m for how we implemented a local search scheme for the QUASAR SDP relaxation. Note that one of the major contributions of STRIDE is to use the original POP to attain fast convergence, so please spend time on implementing this local search function for your problem.

Acknowledgements

STRIDE is implemented by Heng Yang (MIT) and Ling Liang (NUS). We would like to thank the feedback and resources from Prof. Kim-Chuan Toh (NUS), and Prof. Luca Carlone (MIT).