Source-linked AI summary
Linear predictors for nonlinear dynamical systems: Koopman operator meets model predictive control
Milan Korda, Igor Mezić
TL;DR
The paper addresses how to predict and control nonlinear controlled systems using predictors with a linear structure. It extends the Koopman operator through structured, data-driven EDMD and applies the resulting predictors to MPC, achieving comparable optimization complexity to linear MPC while retaining nonlinear lifting. Numerical examples report superior predictor performance, while closed-loop guarantees remain future work.
Problem
The paper seeks simple linear-structure predictors for nonlinear controlled systems that enable established linear control design methods such as MPC.
Method
The method extends the Koopman operator to controlled systems and uses structured EDMD with nonlinear lifting and linear least-squares fitting to construct finite-dimensional linear predictors.
Results
The predictors showed superior performance in the tested numerical examples, while MPC optimization complexity was comparable to that for a linear system of the same size.
Takeaways & Limitations
The data-driven predictors support linear MPC for nonlinear systems, including linear handling of state and input inequalities, nonlinear state constraints, and nonlinear state costs.
Takeaways & Limitations
The paper leaves closed-loop guarantees such as stability and degree of suboptimality for future work.
Abstract
from arXiv · showhide
This paper presents a class of linear predictors for nonlinear controlled dynamical systems. The basic idea is to lift the nonlinear dynamics into a higher dimensional space where its evolution is approximately linear. In an uncontrolled setting, this procedure amounts to a numerical approximation of the Koopman operator associated to the nonlinear dynamics. In this work, we extend the Koopman operator to controlled dynamical systems and compute a finite-dimensional approximation of the operator in such a way that this approximation has the form a linear controlled dynamical system. In numerical examples, the linear predictors obtained in this way exhibit a performance superior to existing linear predictors such as those based on local linearization or the so-called Carleman linearization. Importantly, the procedure to construct these linear predictors is completely data-driven and extremely simple -- it boils down to a nonlinear transformation of the data (the lifting) and a linear least squares problem in the lifted space that can be readily solved for large data sets. These linear predictors can be readily used to design controllers for the nonlinear dynamical system using linear controller design methodologies. We focus in particular on model predictive control (MPC) and show that MPC controllers designed in this way enjoy computational complexity of the underlying optimization problem comparable to that of MPC for a linear dynamical system of the same size. Importantly, linear inequality constraints on the state and control inputs as well as nonlinear constraints on the state can be imposed in a linear fashion in the proposed MPC scheme. Similarly, cost functions nonlinear in the state variable can be handled in a linear fashion. Numerical examples (including a high-dimensional nonlinear PDE control) demonstrate the approach with the source code available online.
1 Introduction
The paper constructs linear predictors for nonlinear controlled systems by lifting their dynamics into a higher-dimensional space with approximately linear evolution. It extends the Koopman framework to controlled systems and uses these predictors for data-driven MPC with linear-control computational properties.
- Motivation: The proposed predictors approximate nonlinear controlled dynamics with artificial linear dynamical systems suitable for established linear control design methods.The predictor uses current state or output measurements together with current and future inputs.
- Koopman-based lifting: Lifting maps the nonlinear state into a higher-dimensional space where its evolution is approximately linear, connecting prediction to Koopman operator theory.For uncontrolled systems, finite-dimensional Koopman approximations predict the evolution of selected observables.
- Method: The controlled Koopman operator is approximated with modified EDMD using observables structured so the result is a linear controlled dynamical system.The construction is data-driven and does not require knowledge of the system model.
- MPC: The resulting predictors support MPC whose computational complexity is comparable to MPC for a linear system with the same numbers of states and inputs.The MPC scheme evaluates the lifting and solves a convex quadratic program at each closed-loop step.
- MPC: Nonlinear state costs and constraints can be handled linearly by including the relevant nonlinear terms among the lifting functions.The paper also describes extensions to input-output systems and systems with disturbances.
2 Linear predictors – basic idea
The predictor lifts the state into a higher-dimensional coordinate z while retaining linear dependence on inputs and predicted states. This structure enables linear control design, especially finite-horizon MPC, despite the original nonlinear dynamics.
- Objective: The paper seeks simple linear-structure predictors for nonlinear systems that support MPC and other linear control methodologies.The predictor estimates future trajectories from an initial condition and an input sequence.
- Predictor structure: The lifted state z evolves in a higher-dimensional space, while the control input remains unlifted and the predicted state is linear in z.Consequently, linear constraints on inputs and states can be imposed directly.
- Feedback design: A feedback controller designed in lifted coordinates induces a generally nonlinear feedback controller in the original state x.The lifted controller need not itself be linear in z.
- Prediction horizon: Finite-horizon prediction is the relevant operating regime because a linear predictor cannot generally remain accurate for all future times.MPC is particularly suited because it repeatedly uses finite-time predictions.
- Scope: More complex bilinear predictors may be asymptotically tight, but the paper focuses on linear predictors because they are immediately compatible with mature linear control techniques.Input-output lifting can apply the construction to measured outputs and their delays rather than the full state.
3 Koopman operator – rationale behind the approach
The paper extends the Koopman operator to controlled systems by augmenting the state with the control sequence, then uses structured EDMD to obtain finite-dimensional linear predictors. The linear structure improves control compatibility, while bilinear alternatives offer tighter asymptotic behavior under additional assumptions.
- Koopman rationale: The Koopman operator is linear and typically infinite-dimensional even when the underlying dynamical system is nonlinear.It fully captures the dynamics when the observable space contains the state components.
- Controlled Koopman operator: Controlled dynamics are represented as an uncontrolled system on the product of the original state space and the space of all control sequences.The control sequence evolves through a left-shift operator.
- EDMD: The paper targets time-domain trajectory prediction rather than spectral analysis and adapts EDMD to construct a finite-dimensional approximation of the controlled Koopman operator.EDMD fits a matrix to observed lifted transitions.
- Structured observables: Structured observables combine nonlinear state liftings with linear functionals of the control sequence, producing a computable linear predictor.The structure separates nonlinear state dependence from the current control input.
- Finite-dimensional construction: The predictor matrices are obtained by linear least-squares problems, including a least-squares projection from lifted coordinates back to the state.If the lifting contains the state observables, the output matrix can be selected directly.
- Bilinear extension: Bilinear predictors can be tight as the number of basis functions grows under continuous-time, vanishing-discretization, input-affine assumptions, but they are not the paper’s control-design focus.The paper leaves bilinear predictor controller design for future investigation.
4 Numerical algorithm – Finding A, B, C
The numerical algorithm lifts data with a chosen nonlinear dictionary and fits the predictor by least squares. Its normal-equation formulation reduces matrix sizes so computation can be largely independent of the number of samples.
- Data: The algorithm uses paired state, successor-state, and input data without requiring temporal ordering or a single trajectory.The samples satisfy the one-step relation y_i = f(x_i,u_i).
- Least-squares fitting: Matrices A and B are fitted as the best one-step linear predictor in the lifted space using a nonlinear-function dictionary.The matrix C is fitted as a least-squares estimate mapping lifted data back to the state.
- Solutions: The analytical least-squares solutions can be expressed using the Moore-Penrose pseudoinverse.The paper notes that direct pseudoinverse evaluation is not preferred for larger datasets.
- Large datasets: For K ≫ N, normal equations use matrices whose dimensions are independent of the number of samples K.This can make the computation more practical for large datasets.
- Scalability: Kernel methods are suggested when lifting into a very high-dimensional space makes explicit evaluation of the lifting map expensive.Such methods avoid explicitly evaluating the lifting mapping.
5 Model predictive control
The proposed lifting-based MPC replaces nonlinear prediction with a lifted linear predictor initialized from the measured state, while retaining convex optimization and allowing nonlinear costs and constraints through the lifting functions. A dense formulation makes the online optimization cost independent of the lifted dimension and comparable to standard linear MPC, although the resulting problem remains an approximation unless the original dynamics are linear.
- Computational structure: Unlike nonlinear MPC, the proposed scheme uses convex quadratic programming rather than a difficult non-convex optimization problem.This avoids the non-convex optimization issues described for nonlinear MPC and supports fast control-input evaluation.
- MPC formulation: Lifting-based MPC initializes linear predictions with z0 = ψ(xk) and solves a convex quadratic program over the prediction horizon.The optimization includes linear dynamics, state and input polyhedral constraints, and a cost function parameterized by the current nonlinear state.
- Encoding nonlinear objectives and constraints: Nonlinear state costs and constraints can be represented linearly by including the corresponding functions among the lifting functions ψi.This construction can encode nonlinear cost terms and scalar or vector-valued constraint components in the lifted formulation.
- Eliminating dependence on the lifting dimension: The dense MPC formulation has computational complexity independent of the lifted state dimension N.The Hessian size and constraint count do not depend on N after the dense transformation.
- Eliminating dependence on the lifting dimension: After evaluating z0 = ψ(xk), solving the dense problem is comparable to standard linear MPC with the same horizon, inputs, and original state dimension n.The relevant data matrices are precomputed offline, apart from an inexpensive matrix-vector multiplication during operation.
- Approximation boundary: Translating nonlinear MPC into the proposed formulation is approximate because the lifted linear predictor is not exact unless the dynamical system is linear.The lifting functions can encode nonlinear costs and constraints, but they do not make the nonlinear dynamics exactly linear in general.
6 Theoretical analysis
The theoretical analysis characterizes EDMD as an empirical L2 projection of the Koopman operator and establishes convergence results under basis, sampling, and continuity conditions. For the structured basis functions used by the linear predictors, finite-horizon prediction convergence is weaker than in the orthonormal-basis setting.
- 6.1 EDMD as L2 projection: Theorem 1 identifies the EDMD operator as the L2 projection of the Koopman operator onto the chosen basis-function span with respect to the empirical sample measure.
- 6.1 EDMD as L2 projection: EDMD computes a finite-dimensional Koopman approximation by projecting the operator onto the span of linearly independent basis functions using sampled data.The projection uses the empirical measure supported on the sample points.
- 6.2 Convergence of EDMD: Under the stated independence assumption, EDMD approximations converge in operator norm to the L2 projection of the Koopman operator onto the basis-function span.The assumption excludes measures supported on a zero level set of a nontrivial basis-function combination.
- 6.2 Convergence of EDMD: With an orthonormal basis of L2(µ) and a continuous Koopman operator, the projected operators converge strongly to the Koopman operator as the basis dimension increases.Strong convergence means convergence on every g ∈ H.
- 6.2 Convergence of EDMD: When the state observable lies in a finite-dimensional span, predictions over any finite horizon converge in L2(µ) under the theorem’s assumptions.The result applies to vector-valued observables, including the state observable, and finite prediction horizons.
- 6.2 Convergence of EDMD: The structured basis functions used to preserve linear predictor structure are not an orthonormal basis of H, so only convergence to the corresponding L2(µ) projection can be established directly.
7 Extensions
The paper extends the approach to input-output systems and systems with disturbances or noise. These extensions use output-based lifting, delayed measurements, state estimation, and data-driven least-squares predictors.
- The approach generalizes to input-output dynamical systems and systems with disturbances or noise.
- Input-output systems: With full-state dynamics known, the predictor can be combined with a state estimator or a linear observer designed directly for the lifted predictor.
- Input-output systems: When only input-output data are available, lifting functions can be restricted to outputs and their delayed measurements.
- Input-output systems: The output-based predictor initializes from recent output and input histories, and the lifted predictor is obtained by least-squares regression on collected data.
- Disturbances and noise: For disturbances or process noise, the predictor starts from ψ(x0) and can approximately compute future state distributions when the disturbance distribution is known.
- Disturbances and noise: Disturbances can be estimated from available data or generated by simulation when the dynamics and disturbance-sampling procedure are known.
8 Numerical examples
Numerical examples evaluate prediction accuracy and feedback control for a forced oscillator, a bilinear motor, and a nonlinear Korteweg–de Vries PDE. The lifting-based predictors outperform comparison predictors in reported tests and support constrained MPC using data-driven models.
- Prediction comparison: The experiments compare lifting-based Koopman prediction with local linearization at the origin, local linearization at an initial condition, and Carleman linearization.
- Prediction comparison: The proposed predictor is trained from simulated trajectories using Runge-Kutta discretization, random inputs, and randomly sampled initial conditions.
- Prediction comparison: The lifting-based Koopman predictor is far superior to the remaining predictors in average relative RMSE over 100 randomly sampled initial conditions.
- Prediction comparison: Average prediction RMSE decreases with increasing lift dimension, although the decrease is not monotonic.
- Feedback control of a bilinear motor: For the bilinear motor, an input-output predictor with N = 103 uses one delay and 100 thin plate spline radial basis functions.
- Feedback control of a bilinear motor: In constrained reference tracking, K-MPC completes the simulation without infeasibility or constraint violations, whereas the local-linearization controller becomes infeasible.
- Feedback control of a bilinear motor: K-MPC requires only output measurements and runs at 6.86 ms on average, compared with 103 ms for L-MPC.
9 Conclusion and outlook
The paper concludes that Koopman-based lifting produces linear predictors for nonlinear controlled systems that can support linear feedback design and MPC. It also identifies closed-loop guarantees and lifting-function selection as future work.
- The proposed predictors lift nonlinear controlled dynamics into a higher-dimensional space with approximately linear evolution and perform well in the tested numerical examples.
- The underlying optimization complexity is comparable to MPC for a linear dynamical system of the same size, while the control design uses only input-output measurements.
- Future work includes establishing closed-loop guarantees and selecting lifting functions optimally using prior information about the dynamical system.
Appendix
The appendix gives explicit dense-form MPC matrices in terms of the data defining the sparse-form problem. It specifies the Hessian, linear term, state-dependent term, prediction matrices, and block-diagonal weighting matrices.
- The dense-form MPC Hessian is H = R + B⊤QB, while its linear term is h = B⊤q + r.
- The state-dependent term is G = 2A⊤QB.
- The prediction matrices are assembled from powers of A and products involving B across the prediction horizon.
- Q and R are block-diagonal matrices formed from the stage and terminal cost matrices.