  We propose semidefinite trajectory optimization (STROM), a framework that
computes fast and certifiably optimal solutions for nonconvex trajectory
optimization problems defined by polynomial objectives and constraints. STROM
employs sparse second-order Lasserre's hierarchy to generate semidefinite
program (SDP) relaxations of trajectory optimization. Different from existing
tools (e.g., YALMIP and SOSTOOLS in Matlab), STROM generates chain-like
multiple-block SDPs with only positive semidefinite (PSD) variables. Moreover,
STROM does so two orders of magnitude faster. Underpinning STROM is cuADMM, the
first ADMM-based SDP solver implemented in CUDA and runs in GPUs. cuADMM builds
upon the symmetric Gauss-Seidel ADMM algorithm and leverages GPU
parallelization to speedup solving sparse linear systems and projecting onto
PSD cones. In five trajectory optimization problems (inverted pendulum,
cart-pole, vehicle landing, flying robot, and car back-in), cuADMM computes
optimal trajectories (with certified suboptimality below 1%) in minutes (when
other solvers take hours or run out of memory) and seconds (when others take
minutes). Further, when warmstarted by data-driven initialization in the
inverted pendulum problem, cuADMM delivers real-time performance: providing
certifiably optimal trajectories in 0.66 seconds despite the SDP has 49,500
variables and 47,351 constraints.
