A New Semidefinite Relaxation for Linear and Piecewise-Affine Optimal Control with Time Scaling
Lujie Yang, Tobia Marcucci, Pablo A. Parrilo, Russ Tedrake · 2025
Read A New Semidefinite Relaxation for Linear and Piecewise-Affine Optimal Control with Time Scaling by Lujie Yang, Tobia Marcucci, Pablo A. Parrilo, Russ Tedrake (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-13170.txt.
Introduction
Lujie Yang, Tobia Marcucci, Pablo Parrilo, and Russ Tedrake ease a hard class of control problems: steering a system to a goal while choosing how time itself is paced. Such problems are nonconvex, meaning standard solvers can get stuck, because time step multiplies the state and control variables. The authors build a relaxation, a simpler convex stand-in closely tracking the true problem.
Their relaxation adapts a known second-order method but keeps only a chosen subset of cross terms, then changes variables to cut computing cost while staying tight in practice. They extend the idea to systems switching among straight-line modes. Each mode sequence becomes a path through a graph of convex sets, and the whole problem solves as one program. Tests show it handles both plain and switching systems well. The work targets robotics and other fields planning motion under time pressure.
Catalog record
| CREATOR | Lujie Yang, Tobia Marcucci, Pablo A. Parrilo, Russ Tedrake |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-13170
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A New Semidefinite Relaxation for Linear and Piecewise-Affine Optimal Control with Time Scaling Thanks: Correspondence to: Lujie Yang < < [email protected] > > . Thanks: This work was supported by ONR N00014-22-1-2121. Lujie Yang, Tobia Marcucci, Pablo A. Parrilo, Russ Tedrake Abstract 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. I Introduction We consider the optimal-control problem (OCP) for discrete-time dynamical systems obtained by discretizing a continuous-time system with time step h>0 . Consider, for example, a system with continuous-time linear dynamics approximated with the Euler method: x_{k+1}=x_{k}+h(Ax_{k}+Bu_{k}), (1) where x_{k} and u_{k} are the state and control at discrete time k , and A and B are the matrices of the continuous-time system. When the time scaling h is fixed, optimizing the trajectory can be efficiently approached through convex optimization. Similarly, if the system trajectory is predetermined, the time-scaling problem can also be addressed as a convex program. However, if the trajectory and time scaling need to be optimized jointly, then the problem becomes nonconvex and considerably more complex to solve. In fact, most common approaches rely on nonconvex trajectory optimization and are prone to converging to local minima. Many existing works on trajectory optimization [ 1 , 2 ] generally require a predefined final time [ 3 , 4 ] , thereby limiting their ability to simultaneously optimize both the time scaling and trajectories. This restriction often overlooks low-cost trajectories that could emerge from varying terminal times, leading to less efficient or unsuitable solutions for time-critical applications [ 5 , 6 ] . Additionally, the fixed-duration requirement is impractical for systems that can only reach the final state within a specific time frame. To remedy this inflexibility, some methods adopt a bilevel optimization approach [ 7 , 8 , 9 , 10 ] , alternating between optimizing the time scaling on a fixed path and refining the path for a given time scaling. However, these algorithms are sensitive to the initial guess and easily get stuck in local optima. Direct-collocation techniques [ 11 , 2 ] offer an alternative by parameterizing trajectories with splines and support incorporating time as a decision variable, but they rely on nonlinear programming (NLP) solvers that may also struggle with local optima or fail to identify feasible trajectories. Fig. 1 : Minimum-time trajectories for a 7D double integrator moving among obstacles with robot arm geometry. The collision-free configuration space is approximately decomposed into convex polytopes. Our algorithm efficiently navigates these polytopes while respecting input limits. Videos of the trajectories can be found at (left) and (right) . Mixed-integer formulations for minimum-time control have been studied over the past decades [ 12 , 13 , 14 , 15 ] . By overcoming the localness of nonlinear programming, mixed-integer convex programming (MICP) has been applied to motion planning for autonomous vehicles [ 16 , 17 , 18 ] , locomotion [ 19 , 20 , 21 ] , and manipulation [ 22 , 23 ] . MICP approaches often handle the originally nonconvex constraints with piecewise convex approximations, and can be solved to global optimum given enough time budget. Additionally, MICP methods are naturally capable of generating optimal trajectories or feedback controllers for piecewise-affine (PWA) dynamical systems with contacts [ 24 , 25 , 26 ] . These strategies typically adopt integer variables to assign system modes, enabling the simultaneous planning of discrete mode sequences and continuous motions. Nevertheless, these methods typically require integer variables to decide the system mode at every time step for a predefined horizon, therefore imposing considerable computational challenges. Recently, the work [ 27 ] has proposed an efficient MICP formulation of hybrid OCPs as finding the shortest paths in a Graph of Convex Sets (GCS) (see also [ 28 , Ch. 10] ). The GCS approach enjoys a tight convex relaxation of the nonconvex control problem. By addressing the planning problem through a single convex program, GCS empowers a range of effective planners [ 29 , 30 , 31 ] capable of handling high-dimensional manipulation and contact problems. In this paper, we leverage semidefinite relaxation (SDR) [ 32 , 33 , 34 , 35 ] to convexify the nonconvex dynamical constraints and incorporate them in the GCS framework. We additionally allow the time step to be decision variables to jointly optimize trajectories and time scaling for PWA systems. Recent advances in SDRs have enabled applications to collision-free motion planning [ 36 , 37 , 38 ] and optimal control [ 39 , 40 , 41 , 42 ] . However, these methods have mostly been limited to path planning in low-dimensional spaces or smooth dynamics without mode switches. Moreover, previous studies [ 37 , 42 ] found that a computationally expensive complete higher-order SDR is necessary to tighten the relaxation with dynamical constraints. We show that by leveraging the specific structure of the system dynamics, our new formulation achieves empirical tightness with a smaller, more efficient relaxation, removing redundant terms and significantly improving computational efficiency. SDRs also play an important role in other robotics problems, including inverse kinematics [ 43 , 44 ] and certifiable perception algorithms [ 45 , 46 ] . Similar to our work, [ 31 ] uses SDR with GCS, but to relax the nonconvex quasi-static dynamics and solves a planar pushing task for fixed final times. In our work, we exploit the structure of the OCP with time scaling, applying and adapting the SDR technique to generate globally optimal trajectories for linear systems. We then further explore such relaxation’s potential in trajectory optimization for PWA dynamical systems using GCS. Our key contributions are summarized as follows: 1. We propose an SDR for nonconvex OCPs for linear systems with time scaling. This SDR exploits the problem structure to be both empirically tight and lightweight. 2. We extend the SDR to handle PWA systems by transcribing the mode optimization problem as a shortest-path problem in GCS. Our method simultaneously optimizes the mode sequence and system trajectory, within a unified convex-optimization framework. We validate our approach on an inverted pendulum with contact and a 7D double integrator approximation of the dynamics of a robot arm (see Fig. 1 ). By decomposing the nonconvex OCP into convex components, we are able to jointly optimize trajectories and time scaling for PWA systems that are otherwise challenging for traditional NLP