Robust and Efficient Embedded Convex Optimization through First-Order Adaptive Caching
Ishaan Mahajan, Brian Plancher · 2025
Read Robust and Efficient Embedded Convex Optimization through First-Order Adaptive Caching by Ishaan Mahajan, Brian Plancher (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-2507-03231.txt.
Introduction
Ishaan Mahajan and Brian Plancher speed up control math on tiny computers in a 2025 paper. Model predictive control plans a robot's moves by solving an optimization problem many times per second. First-order solvers can now run even on microcontrollers, thanks in part to caching math done ahead of time. The cache, though, froze the solver's settings, which hurt flexibility and results.
Their method caches not just the math but how it shifts when settings change. The solver can then tune itself on the fly without rebuilding the cache. On drone tasks, wasted solver steps fell by up to about 63 percent. A 27-gram quadrotor flew figure-eight paths in wind gusts with the method. The code is shared openly for other robotics teams.
Catalog record
| CREATOR | Ishaan Mahajan, Brian Plancher |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 29 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-03231
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Robust and Efficient Embedded Convex Optimization through First-Order Adaptive Caching Ishaan Mahajan, Brian Plancher Abstract Recent advances in Model Predictive Control (MPC) leveraging a combination of first-order methods, such as the Alternating Direction Method of Multipliers (ADMM), and offline precomputation and caching of select operations, have excitingly enabled real-time MPC on microcontrollers. Unfortunately, these approaches require the use of fixed hyperparameters, limiting their adaptability and overall performance. In this work, we introduce First-Order Adaptive Caching, which precomputes not only select matrix operations but also their sensitivities to hyperparameter variations, enabling online hyperparameter updates without full recomputation of the cache. We demonstrate the effectiveness of our approach on a number of dynamic quadrotor tasks, achieving up to a 63.4% reduction in ADMM iterations over the use of optimized fixed hyperparameters and approaching 70% of the performance of a full cache recomputation, while reducing the computational cost from O ( n 3 ) O(n^{3}) to O ( n 2 ) O(n^{2}) complexity. This performance enables us to perform figure-eight trajectories on a 27g tiny quadrotor under wind disturbances. We release our implementation open-source for the benefit of the wider robotics community. I Introduction Model Predictive Control (MPC) is a state-of-the-art approach for real-time control of autonomous systems [ 1 , 2 , 3 , 4 , 5 ] . However, its computational complexity makes it difficult to deploy on tiny robots with limited onboard compute capabilities and fast control rates (e.g., tiny quadrotors) [ 6 , 7 ] . This has led to a number of past works to develop neural or explicit MPC solutions to precompute control laws and overcome these computational challenges [ 8 , 9 , 10 ] . Fig. 1 : A superimposed image of Crazyflie 2.1+ using First-Order Adaptive Caching under wind disturbances to perform a figure-eight (top) and a stable hover (bottom). At the same time, previous work has explored the use of first-order optimization methods, such as the Alternating Direction Method of Multipliers (ADMM), to improve the efficiency of embedded MPC solvers [ 11 ] . These solvers have demonstrated state-of-the-art performance across a range of hardware platforms, particularly in resource-constrained embedded systems [ 12 , 13 , 14 , 15 , 16 ] . More recently, techniques that precompute and cache select matrix operations within the ADMM algorithm, leveraging both an offline and online phase, have enabled real-time convex MPC on embedded microcontrollers, enabling dynamic obstacle avoidance on a 27-gram quadrotor [ 17 , 18 ] . These approaches have been further extended through strategic constraint removal [ 19 ] , model relaxations [ 20 ] , and learned dynamics [ 21 ] , among others. These developments pave the way for a future of highly dynamic, intelligent tiny robots. Although caching-based methods do significantly reduce computational overhead, and enable real-time performance, they require fixing key hyperparameters in the ADMM solver offline. Unfortunately, hyperparameters such as the ADMM penalty parameter \rho are crucial for ensuring both fast and reliable convergence. In fact, state-of-the-art ADMM solvers typically adapt \rho online through heuristics or learning-based methods to ensure performant operation [ 11 , 15 , 22 , 23 ] . However, in existing caching approaches, modifying \rho online would require complete cache recomputation, negating the computational benefits of precomputation. In response, previous work [ 17 , 18 , 24 ] has attempted to precompute multiple cache sets for different hyperparameters. This approach faces scalability issues due to limited memory onboard embedded compute platforms. To address the above limitations, we introduce First-Order Adaptive Caching, a method leveraging first-order sensitivities to efficiently update cached variables in response to changes in key hyperparameters. Inspired by the use of first-order sensitivities to avoid re-training in machine learning based-algorithms [ 25 ] , our approach precomputes both the cache and its sensitivity to hyperparameter variations (e.g., changes in \rho ). This enables a first-order update to the cached values at runtime, eliminating the need for full recomputation. In the case of ADMM, this enables a reduction in the computational complexity of cache updates for varying \rho from O(n^{3}) to O(n^{2}) , while only incurring a 1.5x increase in cache size, enabling efficient embedded deployment. We evaluate our method on a range of dynamic quadrotor tasks, demonstrating a 63.4% decrease in ADMM iterations as compared to optimized fixed hyperparameters. In fact, our approach is able to achieve 70% of the performance of a full cache recomputation at the aforementioned much lower complexity. This enhanced efficiency allows a 27g tiny quadrotor to execute maneuvers despite wind disturbances. To benefit the wider robotics community, we release our implementation as an open-source extension to the TinyMPC software framework, which is available at: https://tinympc.org , providing a scalable and adaptable solution for embedded real-time control. II Background II-A Alternating Direction Method of Multipliers (ADMM) Consider the generic convex optimization problem: \displaystyle\minimize_{x}~ \displaystyle f(x), (1a) \displaystyle\subjectto~ \displaystyle x\in\mathcal{C}, (1b) where f is a twice differentiable cost function and \mathcal{C} is a convex set. ADMM solves ( 1 ) by forming the following equivalent problem: \displaystyle\minimize_{x,z}~ \displaystyle f(x)+I_{\mathcal{C}}(z), (2a) \displaystyle\subjectto~ \displaystyle x=z, (2b) where z is a slack variable and I is an indicator function for the set \mathcal{C} given by: I:=\begin{cases}0~&if~z\in\mathcal{C}\\ \infty~&otherwise.\end{cases} (3) The scaled form of the augmented Lagrangian for this problem is as follows, where \rho\geq 0 is a penalty parameter, r=x-z is the constraint residual, and y=\lambda/\rho is the scaled dual variable derived from the Lagrange multiplier, \lambda : \scalebox{1.0}{\mbox{$\displaystyle\mathcal{L}_{\rho}(x,z,y)=f(x)+I(z)+\frac{\rho}{2}\|r+y\|_{2}^{2}-\frac{\rho}{2}\|y\|_{2}^{2}$}}, (4) The ADMM algorithm solves this problem through the use of the following three-step iterative process [ 11 , 26 ] : \displaystyle x_{k+1} \displaystyle:=\argmin_{x}~\mathcal{L}_{\rho}(x,z^{k},y^{k}), (5a) \displaystyle z_{k+1} \displaystyle:=\argmin_{z}~\mathcal{L}_{\rho}(x_{k+1},z,y_{k}), (5b) \displaystyle y_{k+1} \displaystyle:=y_{k}+\rho r_{k+1}, (5c) where ( 5a ) minimizes x , ( 5b ) minimizes z , and ( 5c ), denoting a sum of residuals, updates y . In ADMM-based optimization, convergence and stability depend on balancing the primal and dual residuals [ 11 ] , which naturally scale with the magnitude of state deviations: r_{k}^{\text{prim}}=x_{k}-z_{k},\quad r_{k}^{\text{dual}}=-\rho(z_{k}-z_{k-1}). (6) Adaptive tuning of \rho is critical to ensure efficient convergence, particularly in dynamic systems where residual magnitudes can vary significantly [ 15 , 27 ] as the ADMM penalty parameter \rho directly influences solver emphasis on primal versus dual feasibility: • Higher \rho values prioritize primal feasibility (constraint satisfaction). • Lower \rho values prioritize dual feasibility (optimality). II-B ADMM for Convex Model-Predictive Control The Model Predictive Control (MPC) problem can be defined as follows: \displaystyle\minimize_{x_{1:N},u_{1:N-1}}~ \displaystyle J(x_{1:N},u_{1:N-1}), (7a) \displaystyle\subjectto~ \displaystyle x_{k+1}=h(x_{k},u_{k})\quad\forall k\in[1,N), (7b) \displaystyle x_{k}\in\mathcal{X},\quad u_{k}\in\mathcal{U}, (7c) where x_{k}\in\mathbb{R}^{n} and u_{k}\in\mathbb{R}^{m} represent the state and control input at time step k , N is the prediction horizon, h(\cdot) defines the system dynamics, and \mathcal{X} and \mathcal{U} are convex sets denoting additional state and input constraints. We can choose to separate the minimization of the cost function subject to the dynamics constraints from the remainder of the constraints, \mathcal{X} and \mathcal{U} , through the use of ADMM by introducing slack variables z and w associated with the states x and controls u , respectively. Hence, the optimization problem we solve using ADMM is the following: \displaystyle\minimize_{x,~u}~ \displaystyle\mathcal{L}_{\rho}(x,u,z,w,y,g) (8a) \displaystyle\subjectto~ \displaystyle x_{k+1}=h(x_{k},u_{k})\quad\forall k\in[1,N), (8b) \displaystyle x_{k}=z_{k},\quad u_{k}=w_{k}, (8c) where the augmented Lagrangian \mathcal{L}_{\rho}(\cdot) is