Choosing the Overshoot Factor for Real-Time Controllers Outside the Simulator

Many real-time controllers solve a small optimization problem at every control step. A standard example is model predictive control (MPC), which plans a short future trajectory with a model of the system and applies only the first action. The popular fast solvers for these problems are splitting methods such as ADMM (alternating direction method of multipliers). Their updates resemble repeated projections onto constraint sets, and they are almost always run with overrelaxation: each step deliberately overshoots the computed update by a factor $\alpha$ between 1 and 2, which stops the iterates from zig-zagging down narrow corridors between constraints. The theory recommends pushing $\alpha$ toward 2. That theory assumes the solver runs to convergence on a problem whose matrices are known exactly. On hardware, neither holds. The solver is cut off after a few iterations to meet the deadline, and the plant does not match the model. The inexact action from one step changes the next state, and therefore the next problem the solver must solve.

This note argues that the right overshoot factor for a real controller is a property of the coupled system formed by the plant and its truncated, warm-started solver, not of the optimization problem alone. We propose to model that coupled system explicitly and derive an overshoot rule from it. We would then test, on a ladder that runs from nominal simulation to physical rigs, whether simulation-tuned relaxation factors keep their ranking once the controller leaves the simulator. The expected result is that they do not. The value of $\alpha$ that minimizes iteration count on isolated problems ($\alpha \to 2$) should be the wrong choice under model mismatch at tight iteration budgets. A cheap, measurable quantity, the controller's own one-step prediction error, should predict the better value.

Core Claim

Overrelaxation has a well-developed theory in open-loop settings. Overshooting hyperplane projections breaks the orthogonal trap in Kaczmarz-type feasibility solvers (A Sampling Kaczmarz-Motzkin Algorithm for Linear Feasibility). Linearized overrelaxed alternating optimization is equivalent to block successive over-relaxation and inherits its speedup (Local convergence of alternating low-rank optimization methods with overrelaxation). The same idea accelerates Bregman projections in Sinkhorn iterations (Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transport). For ADMM on quadratic programs (optimization problems with a quadratic objective and linear constraints, abbreviated QP), closed-form spectral rules show $\alpha = 2$ is optimal for certain classes (Optimal Parameter Selection for ADMM: Quadratic Problems). These papers supply our method: we reuse their fixed-point iteration-matrix view of ADMM.

A second line of work motivates the gap. Overrelaxation amplifies inexact gradients and inexact proximal steps, and damping it restores stability under perturbation (Stability of Over-Relaxations for the Forward-Backward Algorithm, Application to FISTA). In CT reconstruction, the relaxed method is about twice as fast, but it develops oscillations once gradient approximation error grows with too many subsets (Relaxed Linearized Algorithms for Faster X-Ray CT Image Reconstruction). Both studies treat the perturbation as exogenous noise in an offline problem. In closed-loop control, by contrast, the solver's own truncation error is fed back through the plant and returns as a changed problem and a worse warm start.

That feedback is what we model. For linear MPC with a fixed set of active constraints, one ADMM iteration is an affine map $w^{j+1} = T(\alpha)\, w^j + G(\alpha)\, x_t$. Here $w$ stacks the solver's primal and dual variables, $x_t$ is the measured plant state at step $t$, and $T, G$ come from the problem matrices as in the Ghadimi et al. analysis. The controller runs $k$ iterations from a warm start $P w_{t-1}$, where $P$ shifts the previous solution forward one step, and applies $u_t = C w_t$. The true plant evolves as $x_{t+1} = (A + \Delta_A) x_t + (B + \Delta_B) u_t$, where $A, B$ are the model and $\Delta_A, \Delta_B$ the mismatch. Stacking plant state and solver state gives the joint linear system

$$ \begin{pmatrix} x_{t+1} \\ w_{t} \end{pmatrix} = M(\alpha, k, \Delta) \begin{pmatrix} x_{t} \\ w_{t-1} \end{pmatrix}, $$

in which $\alpha$, $k$, and the mismatch $\Delta$ all enter one matrix $M$. Its spectral radius $\rho(M)$, which we call the closed-loop contraction factor, governs how fast disturbances die out in the real loop.

Our central claim is that the minimizer $\alpha^\star(k, \Delta)$ of $\rho(M)$ departs from the open-loop optimum as $k$ shrinks and $\|\Delta\|$ grows. We also claim this departure explains the transfer failures of simulation-tuned solvers better than open-loop convergence rate does. When constraints saturate, the map becomes piecewise affine. That regime, which matters for systems with hard actuator limits (Adaptive fault-tolerant controller design for airbreathing hypersonic vehicle with input saturation), is handled empirically rather than analytically.

Research Program

The work has three parts.

The first part is analytic. We would compute $\rho(M)$ over grids of $\alpha$, iteration budget $k$, and mismatch magnitude for the quadruple-tank MPC problem used by Ghadimi et al. and for a linearized quadrotor tracking model. For each point we would locate $\alpha^\star$ and relate it to the open-loop optimal $\alpha$. Two results would be informative. If $\alpha^\star$ barely moves, the question closes cheaply. If it moves systematically downward with mismatch, the direction and size of the shift become a testable prediction.

The second part is an online rule, prediction-error-scheduled relaxation. At each step the controller measures its one-step prediction error $\|x_{t+1} - (A x_t + B u_t)\|$, an inexpensive running estimate of mismatch. It then looks up $\alpha_t$ from a table of $\alpha^\star(k, \Delta)$ precomputed offline. The table costs nothing at runtime and requires no hardware tuning.

The rule differs from adaptive relaxed ADMM (Adaptive Relaxed ADMM) in what it responds to. ARADMM adapts penalty and relaxation to local curvature of the single problem being solved, aiming at convergence of that problem. Our rule adapts to how badly the closed loop is being perturbed, aiming at the plant's behaviour under a fixed iteration budget.

The third part is an evaluation ladder that exposes the reality gap in stages. The rungs are:

  • nominal simulation;
  • simulation with structured, time-correlated noise, actuation delay, and parameter mismatch;
  • hardware-in-the-loop, with the solver running on an embedded ARM board against a simulated plant, so that real compute jitter and deadline misses appear;
  • physical plants: a laboratory quadruple-tank rig and, where available, an agile quadrotor setup of the kind used by Efficient and Robust Time-Optimal Trajectory Planning and Control for Agile Quadrotor Flight, which runs MPC on an Intel NUC11 with OptiTrack.

On each rung we record the full closed-loop cost, constraint-violation rate, tracking error, and deadline-miss rate as functions of $\alpha$. This lets us ask directly whether the ranking of $\alpha$ values is preserved from rung to rung.

Baselines

The naive reference point is unrelaxed ADMM ($\alpha = 1$) at the same iteration budget. This is the conservative engineering choice when noise is a worry. It shows what overrelaxation buys at all in the closed loop, where the file reports only open-loop penalties: roughly twice the iterations in CT and hundreds to thousands of iterations instead of 20–40 in the quadruple-tank simulations of Ghadimi et al.

The production default is OSQP (OSQP: An Operator Splitting Solver for Quadratic Programs) with its fixed $\alpha = 1.6$, using warm starting and factorization caching. OSQP is roughly ten times faster than interior-point solvers on its 1,400-problem library, and it is what practitioners actually embed.

The theory-optimal fixed rule is Ghadimi et al.'s spectrally chosen penalty with $\alpha = 2$. On the simulated quadruple tank it reported convergence in 20–40 iterations, versus hundreds or thousands for default settings, and it outperformed Nesterov-style Fast-ADMM there. It is the strongest fixed competitor and the one our claim most directly contradicts.

The strongest adaptive method is ARADMM, which reported 10x to 50x fewer iterations than vanilla ADMM and, on News20 Elastic Net, convergence in 71 iterations where vanilla ADMM had not converged after 2,000. We would run it with the same per-step iteration cap and the same warm starts, adapting its parameters inside each control step.

A domain-randomized tuning baseline picks the single $\alpha$ that minimizes average closed-loop cost over simulations with randomized mismatch, noise, and delay. It uses the same simulation budget we spend building our table.

A hardware-tuned oracle grid-searches $\alpha$ directly on the physical rig. It gives an upper bound no simulation-only method should beat.

For context outside the ADMM family, the interior-point solver PIQP (PIQP: A Proximal Interior-Point Quadratic Programming Solver) is run under the same wall-clock deadline.

Two ablations isolate our key ingredient. The first swaps the prediction-error signal for ARADMM's curvature signal while keeping everything else fixed. The second builds the table with $\Delta = 0$, which asks whether closed-loop modeling helps when mismatch is ignored.

All methods run on the same trajectories, disturbance seeds, embedded hardware, and per-step deadline. Every simulation-tuned method receives an equal offline simulation budget. Beating a baseline means lower closed-loop cost, or equal cost at a smaller iteration budget, with a constraint-violation rate that is no worse, on the physical and hardware-in-the-loop rungs.

No closed-loop or physical results for any of these solvers were found on Lacuna. The quadruple-tank numbers are simulation-only. The quadrotor paper reports 10.6 m/s with tracking error below 0.22 m using standard solvers, not overrelaxed splitting.

Why not just…?

Why not just set $\alpha = 1$ on hardware, since overrelaxation amplifies noise? The FISTA stability analysis supports damping under perturbation. However, the open-loop cost of $\alpha = 1$ is large in every source that reports it, and inside a fixed deadline more iterations means fewer iterations per step, not a longer wait. Whether the closed-loop penalty is as large is unknown. The $\alpha = 1$ baseline on each rung measures it directly. If it matches our rule on physical plants, overshoot is not worth scheduling, and we would report that.

Why not just use ARADMM, which already adapts relaxation? This is a real threat. ARADMM's adaptation is designed for convergence of one problem and estimates curvature from a few iterations. With a budget of five to twenty iterations per step, those estimates may be too noisy to act on, and they never see the plant mismatch that drives the feedback. The signal-swap ablation settles the question. If curvature-driven adaptation matches prediction-error scheduling, our contribution reduces to the analysis and the transfer study.

Why not just tune $\alpha$ once with domain randomization in simulation? This may well work if the best $\alpha$ is roughly constant across operating conditions. Our analysis predicts that it varies with the level of mismatch, which a single averaged value cannot track. The domain-randomized baseline, compared on rungs with time-varying mismatch such as changing tank outflow or payload changes on the quadrotor, tests exactly this.

Why not just use an interior-point solver or a learned policy and avoid the issue? Interior-point methods warm-start poorly and cost more per step, as the OSQP paper documents. They are more reliable at high accuracy: PIQP reports 0.72% failures at $\epsilon = 10^{-8}$ on Maros-Mészáros versus 31.16% for OSQP, and QPALM (QPALM) solves the whole convex set. But control rarely needs $10^{-8}$ accuracy. Learned policies drop constraint guarantees and the infeasibility certificates that splitting solvers provide (Accelerating Model Predictive Control for Real-Time Applications). We include PIQP under the deadline to measure rather than assume this.

Proposed Experiments

The first decisive check is rank transfer. For each rung we compute the Spearman correlation between the ordering of $\alpha$ values by nominal-simulation closed-loop cost and their ordering on that rung. We then ask whether $\rho(M)$ with the mismatch estimated on the rung predicts the physical ordering better than open-loop iteration count does. The hypothesis fails if nominal simulation already ranks $\alpha$ correctly on the physical rigs.

The second check tests the predicted shift. As the iteration budget per step drops from roughly 50 to 5, and as mismatch is injected in controlled steps (a deliberately mis-specified tank outflow coefficient, or added quadrotor mass), the empirically best $\alpha$ should move below the Ghadimi optimum in the direction and roughly the size that $\alpha^\star(k, \Delta)$ predicts.

The third check compares prediction-error-scheduled relaxation against all baselines on the hardware-in-the-loop and physical rungs. We report closed-loop cost, constraint violations, and the smallest iteration budget that keeps the loop stable. In the saturated regime, which the linear analysis does not cover, we specifically measure whether scheduling reduces the limit cycles and oscillations that the CT and FISTA results lead us to expect.

As a sanity check that the rule does not harm open-loop solving, we run the scheduled solver on Maros-Mészáros and the OSQP problem library with $\Delta = 0$. There it should reduce to the fixed-$\alpha$ behaviour.