Preprint: STRIDE for solving SDP relaxations

November 10, 2021

Semidefinite relaxations, particularly the moment-SOS hierarchy (a.k.a. Lasserre's hierarchy), are a powerful tool for the global optimization of polynomial optimization problems. However, it is challenging to apply them to practical problems because they often lead to SDPs that are too large to be solved by existing SDP solvers.

In our new preprint, we propose STRIDE, the first solver of its kind that blends local search on the POP with global descent on the SDP. We deal with inexactness, we prove global convergence, we design new and modified scalable algorithms, and we test it on globally solving several challenging POPs.