Fast and Certifiable Trajectory Optimization

我们提出半定轨迹优化（STROM）框架，该框架计算由多项式目标和约束定义的非凸轨迹优化问题的快速且可证明最优解。STROM采用稀疏二阶Lasserre层次结构生成轨迹优化的半定程序（SDP）松弛。与现有工具（如Matlab中的YALMIP和SOSTOOLS）不同，STROM仅使用正半定（PSD）变量生成链状多块SDP。此外，STROM的速度快了两个数量级。STROM的基础是cuADMM，这是第一个在CUDA中实现的基于ADMM的SDP求解器，可在GPU上运行。cuADMM建立在对称高斯-赛德尔ADMM算法之上，并利用GPU并行化加速求解稀疏线性系统和投影到PSD锥上。在五个轨迹优化问题（倒立摆，倒置摆，车辆着陆，飞行机器人和汽车倒车）中，cuADMM在几分钟内计算出最优轨迹（其可证明次优度低于1％），而其他求解器需要数小时或内存不足。此外，在倒立摆问题中，当通过数据驱动的初始化进行热启动时，cuADMM提供实时性能：尽管SDP具有49,500个变量和47,351个约束，但在0.66秒内提供可证明的最优轨迹。

论文提出了semidefinite trajectory optimization (STROM)框架，用于解决由多项式目标和约束定义的非凸轨迹优化问题。

STROM使用稀疏二阶Lasserre层次结构生成半定规划（SDP）松弛，生成仅包含正半定（PSD）变量的链式多块SDP，比现有工具快两个数量级。STROM的核心是基于CUDA实现的cuADMM，它是第一个基于ADMM的SDP求解器，利用GPU并行化加速求解稀疏线性系统和投影到PSD锥。

在五个轨迹优化问题中，cuADMM在几分钟内计算出优化轨迹，并提供可证明的次优性低于1%的结果，而其他求解器需要数小时或内存不足。在倒立摆问题中，cuADMM通过数据驱动初始化实现实时性能，在0.66秒内提供可证明的最优轨迹，即使SDP具有49,500个变量和47,351个约束。

与本论文相关的研究包括YALMIP和SOSTOOLS等工具，以及基于ADMM的SDP求解器。