Global Convergence of Online Optimization for Nonlinear Model Predictive Control

Sen NaNeurIPS 2021 · OpenReview

Executive Summary

This paper introduces a modified Real-Time Iteration (RTI) scheme for Nonlinear Model Predictive Control (NMPC) that guarantees global convergence. By replacing the standard full Newton step with an adaptive step-size selection based on a differentiable exact augmented Lagrangian, the algorithm ensures that the system converges to a stationary point (KKT point) regardless of its starting initialization.

The Challenge with Standard RTI

Model Predictive Control (MPC) is a powerful tool for controlling complex systems by solving an optimization problem over a "prediction horizon" at every time step. For nonlinear systems (NMPC), solving these problems to absolute optimality is often too computationally expensive for real-time applications.

To accelerate this process, researchers frequently employ Real-Time Iterations (RTI), which perform only a single Newton step per time step. While RTI is fast, it suffers from a major theoretical and practical weakness: local convergence. Existing mathematical proofs only guarantee that the algorithm works if it starts very close to the optimal solution. If the system experiences a large disturbance or starts from a random initialization, standard RTI can easily fail. This paper bridges that gap, providing a framework that is both fast enough for real-time use and mathematically guaranteed to converge from any starting point.

Proposed Methodology: Adaptive RTI

The authors propose an Adaptive RTI-based MPC Scheme that introduces several key innovations over standard RTI:

  • Stepsize Selection (Line Search): Instead of blindly taking a full Newton step (where stepsize $\alpha=1$), the algorithm uses a backtracking line search to find a step size that demonstrably improves a specific "merit function."
  • Differentiable Exact Augmented Lagrangian: The authors utilize this specific merit function because it is smooth (differentiable) and couples both primal variables (state/control) and dual variables (constraint multipliers). Crucially, this avoids the "Maratos effect"—a common optimization issue where otherwise good steps are rejected by non-differentiable merit functions, such as the standard $\ell_1$ penalty.
  • Adaptive Penalty Parameters: The algorithm automatically tunes the penalty parameters ($\eta$) of the Lagrangian on the fly. The authors prove that these parameters eventually stabilize, ensuring the algorithm doesn't become infinitely "stiff" over time.
  • Moving Horizon Analysis: The most significant technical challenge addressed in the paper is proving that the merit function continues to decrease even though the underlying optimization problem changes at every time step as the prediction horizon shifts forward.

Experimental Setup

As is common in control theory research, the paper evaluates the algorithm using simulated benchmarks rather than static datasets. The primary testbed is a 1D Trigonometric Perturbed LQR, a nonlinear variation of the classic Linear Quadratic Regulator.

The algorithm is tested across three distinct scenarios:

  1. Case 1: Time-invariant coefficients (serving as the "easy" baseline).
  2. Cases 2 & 3: Time-varying coefficients featuring linear and quadratic increases, respectively. These simulate more volatile, real-world dynamics where the system's "goalposts" are constantly moving.

(Note: The code for these experiments is implemented in Julia and is publicly available on GitHub.)

Key Insights and Results

Theoretical Guarantees

The authors provide a rigorous mathematical proof (Theorem 4.7) demonstrating that the KKT residuals—the standard measure of how far the system is from a true solution—converge to zero as time progresses. The paper emphasizes that "global convergence" in nonlinear optimization means converging to a stationary point (KKT point), not necessarily the absolute global minimum, which is a standard but vital distinction in the field.

Furthermore, the paper highlights that a simple "warm start" is insufficient for stability. While RTI relies on the previous step's solution to warm start the next one, the authors show that without a proper merit function, the "shift" in the prediction horizon introduces enough perturbation to break the algorithm's stability.

Empirical Performance

  • Superiority over $\ell_1$ MPC: In the more difficult time-varying simulations (Cases 2 and 3), the proposed augmented Lagrangian method successfully reached high-precision solutions (a $10^{-8}$ residual) within a moderate number of iterations. In stark contrast, the standard $\ell_1$ penalized approach plateaued, failing to reach high precision even after 250 iterations.
  • Robustness: The algorithm proved highly robust to the choice of the quadratic penalty parameter ($\mu$), performing consistently well across a wide range of values (from 1 to 1000).
  • Computational Efficiency: By using a differentiable merit function, the authors can rely on a simple backtracking line search. This is significantly more computationally efficient for real-time systems than the complex "watchdog" or "second-order correction" methods required by non-differentiable $\ell_1$ functions.

Limitations and Future Directions

While the proposed scheme offers strong guarantees, the authors note a few limitations and areas for future work:

  • Assumption Relaxations: The core proof relies on a technical assumption (Assumption 4.3) relating the size of the dual step to the primal step. While common in MPC literature and empirically true in their experiments, finding ways to relax or remove this assumption is a key area for future theoretical research.
  • Quasi-Newton Extensions: The current framework uses exact Newton steps. Replacing these with quasi-Newton methods (like BFGS) could further reduce the computational burden per step.
  • Stochastic Environments: The current model assumes known, deterministic system dynamics. Extending this global convergence proof to stochastic environments with noise or randomness is a significant next step.
  • Reinforcement Learning: Finally, the authors express interest in applying these RTI principles to model-free Reinforcement Learning, though the exact mathematical path to achieving this remains an open question.

Summary updated

Abstract

We study a real-time iteration (RTI) scheme for solving online optimization problem appeared in nonlinear optimal control. The proposed RTI scheme modifies the existing RTI-based model predictive control (MPC) algorithm, by selecting the stepsize of each Newton step at each sampling time using a differentiable exact augmented Lagrangian. The scheme can adaptively select the penalty parameters of augmented Lagrangian on the fly, which are shown to be stabilized after certain time periods. We prove under generic assumptions that, by involving stepsize selection instead of always using a full Newton step (like what most of the existing RTIs do), the scheme converges globally: for any initial point, the KKT residuals of the subproblems converge to zero. A key step is to show that augmented Lagrangian keeps decreasing as horizon moves forward. We demonstrate the global convergence behavior of the proposed RTI scheme in a numerical experiment.
BibTeX
@inproceedings{na2021global,
  author = {Sen Na},
  title = {{Global Convergence of Online Optimization for Nonlinear Model Predictive Control}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=XI72RT3hnnF},
}
Figure