提出新松弛方法，高效求解带时间缩放的线性与分段仿射最优控制问题。
A New Semidefinite Relaxation for Linear and Piecewise-Affine Optimal Control with Time Scaling
- 通过变量替换和选择关键双线性项，实现轻量级紧致半定松弛。
- 将分段仿射系统建模为凸集图上的最短路径问题，统一求解。
- 单个半定规划即可求解复杂分段系统最优控制，适合工程优化场景。
我们提出了针对带时间缩放的线性系统最优控制问题的半定松弛方法。这类问题本质上是非凸的，因为系统动态涉及离散时间步长与状态、控制之间的双线性项。所提松弛方法与标准二次约束半定松弛密切相关，但通过精心选择部分双线性项并引入变量变换，在保持计算开销较低的同时实现了经验上紧密的松弛效果。进一步地，我们通过将分段仿射（PWA）系统的最优控制问题建模为凸集图（GCS）中的最短路径问题，扩展了该方法：不同路径代表PWA系统不同的模式切换序列，而凸集用于建模各模式内的松弛动力学。结合对GCS问题的紧致凸松弛与我们的时间缩放半定松弛，可将PWA最优控制问题通过单一半定规划求解。
原文摘要 · Abstract (English)
We introduce a semidefinite relaxation for optimal control of linear systems with time scaling. These problems are inherently nonconvex, since the system dynamics involves bilinear products between the discretization time step and the system state and controls. The proposed relaxation is closely related to the standard second-order semidefinite relaxation for quadratic constraints, but we carefully select a subset of the possible bilinear terms and apply a change of variables to achieve empirically tight relaxations while keeping the computational load light. We further extend our method to handle piecewise-affine (PWA) systems by formulating the PWA optimal-control problem as a shortest-path problem in a graph of convex sets (GCS). In this GCS, different paths represent different mode sequences for the PWA system, and the convex sets model the relaxed dynamics within each mode. By combining a tight convex relaxation of the GCS problem with our semidefinite relaxation with time scaling, we can solve PWA optimal-control problems through a single semidefinite program.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。