Symbolic dynamics for active sets of a class of constrained nonlinear optimal control and MPC problems

IFAC PapersOnLine 58-18 (2024) 181–187 ScienceDirect ScienceDirect Available online at www.sciencedirect.com 2405-8963 Copyright © 2024 The Authors. This is an open access article under the CC BY-NC-ND license . Peer review under responsibility of International Federation of Automatic Control. 10.1016/j.ifacol.2024.09.028 10.1016/j.ifacol.2024.09.028 2405-8963 Symbolic dynamics for active sets of a class of constrained nonlinear optimal control and MPC problems 1 M. M¨onnigmann ∗R. Hill ∗∗ A. Bemporad ∗∗∗ G. Pannocchia ∗∗∗∗ ∗Automatic Control and Systems Theory, Ruhr-Universit¨at Bochum, Germany ∗∗ Electrical and Electronic Engineering, University of Melbourne, Australia ∗∗∗ IMT School for Advanced Studies Lucca, Italy ∗∗∗∗ Civil and Industrial Engineering, University of Pisa, Italy Abstract: Solutions to optimal control problems are usually understood to provide optimal trajectories. In this paper, we show that the optimal state-space system dynamics induce a dynamics of the active sets. More specifically, given the optimal active set at the solution obtained at the current time, its successor optimal active set (which, in turn, defines the successor solution) can be found with index set operations. These operations do not involve any optimal control (or other optimization or integration) problem, but they can be described with simple rules. These rules constitute the symbolic dynamics for active sets. The present paper treats a particular constrained nonlinear problem class, extending earlier results for the constrained linear-quadratic case. Keywords: optimal control, nonlinear model predictive control 1. INTRODUCTION Constrained optimal control problems are more demanding than their unconstrained counterparts. For example, discrete-time finite-horizon constrained linear optimal control problems, such as those that arise in linear model predictive control (MPC) formulations, admit a simple analytical linear state-feedback solution in the absence of constraints, while they require more substantial online or offline computation effort in the presence of linear constraints. It has proven to be useful to characterize the solution to constrained optimal control problems with the set of active sets, where we call a subset of the indices to all constraints active set if this combination of constraints is active for at least one feasible initial state. The set of active sets then is the set of all active sets that may appear when solving the optimal control problem (OCP). Constructing the set of active sets is often associated with constructing explicit solutions (Gupta et al., 2011; Herceg et al., 2013; Mitze and M¨onnigmann, 2020; Oberdieck et al., 2017; Herceg et al., 2015; Feller et al., 2013), specifically for the constrained linear-quadratic regulator (Bemporad et al., 2002; Tøndel et al., 2003; Seron et al., 2002). Even if no explicit feedback law is ultimately constructed, the set of active sets of an OCP is still useful, as it defines and characterizes its solution. We claim that this characterization is not only interesting per se but also 1MM and GP gratefully acknowledge funding by the European Commission under grant no. 101079342 (FrontSeat). in practice. If an explicit solution is not computable, either because it is too expensive to store and evaluate (even for moderately complex linear-quadratic problems), or not computable at all (as in the general nonlinear case), knowing the optimal active set can greatly simplify online optimization. For example in the simple case of upper and lower bounds only, the OCP becomes unconstrained and with a smaller or equal number of optimization variables to determine. Even in case an explicit solution is predetermined offline, knowing the optimal active set can greatly simplify the solution of the point-location problem online. The characterization with active sets has led to several interesting insights for the linear-quadratic case. Neighboring regions of the piecewise solution to the OCP can be identified from analyzing the active sets (AhmadiMoshkenani et al., 2018). Similarly, it has been shown that dynamic programming can be carried out with the active sets (M¨onnigmann, 2019), which helps to accelerate the construction of all active sets (Mitze and M¨onnigmann, 2020). Finally, symmetries of the solution to the OCP can be found in the set of active sets (Mitze et al., 2023). All these results are essentially based on geometric relations of the regions defined by the active sets without requiring geometric calculations. In the present paper, we focus on dynamic relations of active sets for a particular nonlinear problem class. Specifically, we show that the successor active set can be found with very simple operations on the current active set (such as index shifts of index sets). In particular, no Symbolic dynamics for active sets of a class of constrained nonlinear optimal control and MPC problems 1 M. M¨onnigmann ∗R. Hill ∗∗ A. Bemporad ∗∗∗ G. Pannocchia ∗∗∗∗ ∗Automatic Control and Systems Theory, Ruhr-Universit¨at Bochum, Germany ∗∗ Electrical and Electronic Engineering, University of Melbourne, Australia ∗∗∗ IMT School for Advanced Studies Lucca, Italy ∗∗∗∗ Civil and Industrial Engineering, University of Pisa, Italy Abstract: Solutions to optimal control problems are usually understood to provide optimal trajectories. In this paper, we show that the optimal state-space system dynamics induce a dynamics of the active sets. More specifically, given the optimal active set at the solution obtained at the current time, its successor optimal active set (which, in turn, defines the successor solution) can be found with index set operations. These operations do not involve any optimal control (or other optimization or integration) problem, but they can be described with simple rules. These rules constitute the symbolic dynamics for active sets. The present paper treats a particular constrained nonlinear problem class, extending earlier results for the constrained linear-quadratic case. Keywords: optimal control, nonlinear model predictive control 1. INTRODUCTION Constrained optimal control problems are more demanding than their unconstrained counterparts. For example, discrete-time finite-horizon constrained linear optimal control problems, such as those that arise in linear model predictive control (MPC) formulations, admit a simple analytical linear state-feedback solution in the absence of constraints, while they require more substantial online or offline computation effort in the presence of linear constraints. It has proven to be useful to characterize the solution to constrained optimal control problems with the set of active sets, where we call a subset of the indices to all constraints active set if this combination of constraints is active for at least one feasible initial state. The set of active sets then is the set of all active sets that may appear when solving the optimal control problem (OCP). Constructing the set of active sets is often associated with constructing explicit solutions (Gupta et al., 2011; Herceg et al., 2013; Mitze and M¨onnigmann, 2020; Oberdieck et al., 2017; Herceg et al., 2015; Feller et al., 2013), specifically for the constrained linear-quadratic regulator (Bemporad et al., 2002; Tøndel et al., 2003; Seron et al., 2002). Even if no explicit feedback law is ultimately constructed, the set of active sets of an OCP is still useful, as it defines and characterizes its solution. We claim that this characterization is not only interesting per se but also 1MM and GP gratefully acknowledge funding by the European Commission under grant no. 101079342 (FrontSeat). in practice. If an explicit solution is not computable, either because it is too expensive to store and evaluate (even for moderately complex linear-quadratic problems), or not computable at all (as in the general nonlinear case), knowing the optimal active set can greatly simplify online optimization. For example in the simple case of upper and lower bounds only, the OCP becomes unconstrained and with a smaller or equal number of optimization variables to determine. Even in case an explicit solution is predetermined offline, knowing the optimal active set can greatly simplify the solution of the point-location problem online. The characterization with active sets has led to several interesting insights for the linear-quadratic case. Neighboring regions of the piecewise solution to the OCP can be identified from analyzing the active sets (AhmadiMoshkenani et al., 2018). Similarly, it has been shown that dynamic programming can be carried out with the active sets (M¨onnigmann, 2019), which helps to accelerate the construction of all active sets (Mitze and M¨onnigmann, 2020). Finally, symmetries of the solution to the OCP can be found in the set of active sets (Mitze et al., 2023). All these results are essentially based on geometric relations of the regions defined by the active sets without requiring geometric calculations. In the present paper, we focus on dynamic relations of active sets for a particular nonlinear problem class. Specifically, we show that the successor active set can be found with very simple operations on the current active set (such as index shifts of index sets). In particular, no Symbolic dynamics for active sets of a class of constrained nonlinear optimal control and MPC problems 1 M. M¨onnigmann ∗R. Hill ∗∗ A. Bemporad ∗∗∗ G. Pannocchia ∗∗∗∗ ∗Automatic Control and Systems Theory, Ruhr-Universit¨at Bochum, Germany ∗∗ Electrical and Electronic Engineering, University of Melbourne, Australia ∗∗∗ IMT School for Advanced Studies Lucca, Italy ∗∗∗∗ Civil and Industrial Engineering, University of Pisa, Italy Abstract: Solutions to optimal control problems are usually understood to provide optimal trajectories. In this paper, we show that the optimal state-space system dynamics induce a dynamics of the active sets. More specifically, given the optimal active set at the solution obtained at the current time, its successor optimal active set (which, in turn, defines the successor solution) can be found with index set operations. These operations do not involve any optimal control (or other optimization or integration) problem, but they can be described with simple rules. These rules constitute the symbolic dynamics for active sets. The present paper treats a particular constrained nonlinear problem class, extending earlier results for the constrained linear-quadratic case. Keywords: optimal control, nonlinear model predictive control 1. INTRODUCTION Constrained optimal control problems are more demanding than their unconstrained counterparts. For example, discrete-time finite-horizon constrained linear optimal control problems, such as those that arise in linear model predictive control (MPC) formulations, admit a simple analytical linear state-feedback solution in the absence of constraints, while they require more substantial online or offline computation effort in the presence of linear constraints. It has proven to be useful to characterize the solution to constrained optimal control problems with the set of active sets, where we call a subset of the indices to all constraints active set if this combination of constraints is active for at least one feasible initial state. The set of active sets then is the set of all active sets that may appear when solving the optimal control problem (OCP). Constructing the set of active sets is often associated with constructing explicit solutions (Gupta et al., 2011; Herceg et al., 2013; Mitze and M¨onnigmann, 2020; Oberdieck et al., 2017; Herceg et al., 2015; Feller et al., 2013), specifically for the constrained linear-quadratic regulator (Bemporad et al., 2002; Tøndel et al., 2003; Seron et al., 2002). Even if no explicit feedback law is ultimately constructed, the set of active sets of an OCP is still useful, as it defines and characterizes its solution. We claim that this characterization is not only interesting per se but also 1MM and GP gratefully acknowledge funding by the European Commission under grant no. 101079342 (FrontSeat). in practice. If an explicit solution is not computable, either because it is too expensive to store and evaluate (even for moderately complex linear-quadratic problems), or not computable at all (as in the general nonlinear case), knowing the optimal active set can greatly simplify online optimization. For example in the simple case of upper and lower bounds only, the OCP becomes unconstrained and with a smaller or equal number of optimization variables to determine. Even in case an explicit solution is predetermined offline, knowing the optimal active set can greatly simplify the solution of the point-location problem online. The characterization with active sets has led to several interesting insights for the linear-quadratic case. Neighboring regions of the piecewise solution to the OCP can be identified from analyzing the active sets (AhmadiMoshkenani et al., 2018). Similarly, it has been shown that dynamic programming can be carried out with the active sets (M¨onnigmann, 2019), which helps to accelerate the construction of all active sets (Mitze and M¨onnigmann, 2020). Finally, symmetries of the solution to the OCP can be found in the set of active sets (Mitze et al., 2023). All these results are essentially based on geometric relations of the regions defined by the active sets without requiring geometric calculations. In the present paper, we focus on dynamic relations of active sets for a particular nonlinear problem class. Specifically, we show that the successor active set can be found with very simple operations on the current active set (such as index shifts of index sets). In particular, no Symbolic dynamics for active sets of a class of constrained nonlinear optimal control and MPC problems 1 M. M¨onnigmann ∗R. Hill ∗∗ A. Bemporad ∗∗∗ G. Pannocchia ∗∗∗∗ ∗ Automatic Control and Systems Theory, Ruhr-Universit¨at Bochum, Germany ∗∗ Electrical and Electronic Engineering, University of Melbourne, Australia ∗∗∗ IMT School for Advanced Studies Lucca, Italy ∗∗∗∗ Civil and Industrial Engineering, University of Pisa, Italy Abstract: Solutions to optimal control problems are usually understood to provide optimal trajectories. In this paper, we show that the optimal state-space system dynamics induce a dynamics of the active sets. More specifically, given the optimal active set at the solution obtained at the current time, its successor optimal active set (which, in turn, defines the successor solution) can be found with index set operations. These operations do not involve any optimal control (or other optimization or integration) problem, but they can be described with simple rules. These rules constitute the symbolic dynamics for active sets. The present paper treats a particular constrained nonlinear problem class, extending earlier results for the constrained linear-quadratic case. Keywords: optimal control, nonlinear model predictive control 1. INTRODUCTION Constrained optimal control problems are more demanding than their unconstrained counterparts. For example, discrete-time finite-horizon constrained linear optimal control problems, such as those that arise in linear model predictive control (MPC) formulations, admit a simple analytical linear state-feedback solution in the absence of constraints, while they require more substantial online or offline computation effort in the presence of linear constraints. It has proven to be useful to characterize the solution to constrained optimal control problems with the set of active sets, where we call a subset of the indices to all constraints active set if this combination of constraints is active for at least one feasible initial state. The set of active sets then is the set of all active sets that may appear when solving the optimal control problem (OCP). Constructing the set of active sets is often associated with constructing explicit solutions (Gupta et al., 2011; Herceg et al., 2013; Mitze and M¨onnigmann, 2020; Oberdieck et al., 2017; Herceg et al., 2015; Feller et al., 2013), specifically for the constrained linear-quadratic regulator (Bemporad et al., 2002; Tøndel et al., 2003; Seron et al., 2002). Even if no explicit feedback law is ultimately constructed, the set of active sets of an OCP is still useful, as it defines and characterizes its solution. We claim that this characterization is not only interesting per se but also 1MM and GP gratefully acknowledge funding by the European Commission under grant no. 101079342 (FrontSeat). in practice. If an explicit solution is not computable, either because it is too expensive to store and evaluate (even for moderately complex linear-quadratic problems), or not computable at all (as in the general nonlinear case), knowing the optimal active set can greatly simplify online optimization. For example in the simple case of upper and lower bounds only, the OCP becomes unconstrained and with a smaller or equal number of optimization variables to determine. Even in case an explicit solution is predetermined offline, knowing the optimal active set can greatly simplify the solution of the point-location problem online. The characterization with active sets has led to several interesting insights for the linear-quadratic case. Neighboring regions of the piecewise solution to the OCP can be identified from analyzing the active sets (AhmadiMoshkenani et al., 2018). Similarly, it has been shown that dynamic programming can be carried out with the active sets (M¨onnigmann, 2019), which helps to accelerate the construction of all active sets (Mitze and M¨onnigmann, 2020). Finally, symmetries of the solution to the OCP can be found in the set of active sets (Mitze et al., 2023). All these results are essentially based on geometric relations of the regions defined by the active sets without requiring geometric calculations. In the present paper, we focus on dynamic relations of active sets for a particular nonlinear problem class. Specifically, we show that the successor active set can be found with very simple operations on the current active set (such as index shifts of index sets). In particular, no Symbolic dynamics for active sets of a class of constrained nonlinear optimal control and MPC problems 1 M. M¨onnigmann ∗ R. Hill ∗∗ A. Bemporad ∗∗∗ G. Pannocchia ∗∗∗∗ ∗Automatic Control and Systems Theory, Ruhr-Universit¨at Bochum, Germany ∗∗ Electrical and Electronic Engineering, University of Melbourne, Australia ∗∗∗ IMT School for Advanced Studies Lucca, Italy ∗∗∗∗ Civil and Industrial Engineering, University of Pisa, Italy Abstract: Solutions to optimal control problems are usually understood to provide optimal trajectories. In this paper, we show that the optimal state-space system dynamics induce a dynamics of the active sets. More specifically, given the optimal active set at the solution obtained at the current time, its successor optimal active set (which, in turn, defines the successor solution) can be found with index set operations. These operations do not involve any optimal control (or other optimization or integration) problem, but they can be described with simple rules. These rules constitute the symbolic dynamics for active sets. The present paper treats a particular constrained nonlinear problem class, extending earlier results for the constrained linear-quadratic case. Keywords: optimal control, nonlinear model predictive control 1. INTRODUCTION Constrained optimal control problems are more demanding than their unconstrained counterparts. For example, discrete-time finite-horizon constrained linear optimal control problems, such as those that arise in linear model predictive control (MPC) formulations, admit a simple analytical linear state-feedback solution in the absence of constraints, while they require more substantial online or offline computation effort in the presence of linear constraints. It has proven to be useful to characterize the solution to constrained optimal control problems with the set of active sets, where we call a subset of the indices to all constraints active set if this combination of constraints is active for at least one feasible initial state. The set of active sets then is the set of all active sets that may appear when solving the optimal control problem (OCP). Constructing the set of active sets is often associated with constructing explicit solutions (Gupta et al., 2011; Herceg et al., 2013; Mitze and M¨onnigmann, 2020; Oberdieck et al., 2017; Herceg et al., 2015; Feller et al., 2013), specifically for the constrained linear-quadratic regulator (Bemporad et al., 2002; Tøndel et al., 2003; Seron et al., 2002). Even if no explicit feedback law is ultimately constructed, the set of active sets of an OCP is still useful, as it defines and characterizes its solution. We claim that this characterization is not only interesting per se but also 1MM and GP gratefully acknowledge funding by the European Commission under grant no. 101079342 (FrontSeat). in practice. If an explicit solution is not computable, either because it is too expensive to store and evaluate (even for moderately complex linear-quadratic problems), or not computable at all (as in the general nonlinear case), knowing the optimal active set can greatly simplify online optimization. For example in the simple case of upper and lower bounds only, the OCP becomes unconstrained and with a smaller or equal number of optimization variables to determine. Even in case an explicit solution is predetermined offline, knowing the optimal active set can greatly simplify the solution of the point-location problem online. The characterization with active sets has led to several interesting insights for the linear-quadratic case. Neighboring regions of the piecewise solution to the OCP can be identified from analyzing the active sets (AhmadiMoshkenani et al., 2018). Similarly, it has been shown that dynamic programming can be carried out with the active sets (M¨onnigmann, 2019), which helps to accelerate the construction of all active sets (Mitze and M¨onnigmann, 2020). Finally, symmetries of the solution to the OCP can be found in the set of active sets (Mitze et al., 2023). All these results are essentially based on geometric relations of the regions defined by the active sets without requiring geometric calculations. In the present paper, we focus on dynamic relations of active sets for a particular nonlinear problem class. Specifically, we show that the successor active set can be found with very simple operations on the current active set (such as index shifts of index sets). In particular, no Symbolic dynamics for active sets of a class of constrained nonlinear optimal control and MPC problems 1 M. M¨onnigmann ∗R. Hill ∗∗ A. Bemporad ∗∗∗ G. Pannocchia ∗∗∗∗ ∗Automatic Control and Systems Theory, Ruhr-Universit¨at Bochum, Germany ∗∗ Electrical and Electronic Engineering, University of Melbourne, Australia ∗∗∗ IMT School for Advanced Studies Lucca, Italy ∗∗∗∗ Civil and Industrial Engineering, University of Pisa, Italy Abstract: Solutions to optimal control problems are usually understood to provide optimal trajectories. In this paper, we show that the optimal state-space system dynamics induce a dynamics of the active sets. More specifically, given the optimal active set at the solution obtained at the current time, its successor optimal active set (which, in turn, defines the successor solution) can be found with index set operations. These operations do not involve any optimal control (or other optimization or integration) problem, but they can be described with simple rules. These rules constitute the symbolic dynamics for active sets. The present paper treats a particular constrained nonlinear problem class, extending earlier results for the constrained linear-quadratic case. Keywords: optimal control, nonlinear model predictive control 1. INTRODUCTION Constrained optimal control problems are more demanding than their unconstrained counterparts. For example, discrete-time finite-horizon constrained linear optimal control problems, such as those that arise in linear model predictive control (MPC) formulations, admit a simple analytical linear state-feedback solution in the absence of constraints, while they require more substantial online or offline computation effort in the presence of linear constraints. It has proven to be useful to characterize the solution to constrained optimal control problems with the set of active sets, where we call a subset of the indices to all constraints active set if this combination of constraints is active for at least one feasible initial state. The set of active sets then is the set of all active sets that may appear when solving the optimal control problem (OCP). Constructing the set of active sets is often associated with constructing explicit solutions (Gupta et al., 2011; Herceg et al., 2013; Mitze and M¨onnigmann, 2020; Oberdieck et al., 2017; Herceg et al., 2015; Feller et al., 2013), specifically for the constrained linear-quadratic regulator (Bemporad et al., 2002; Tøndel et al., 2003; Seron et al., 2002). Even if no explicit feedback law is ultimately constructed, the set of active sets of an OCP is still useful, as it defines and characterizes its solution. We claim that this characterization is not only interesting per se but also 1MM and GP gratefully acknowledge funding by the European Commission under grant no. 101079342 (FrontSeat). in practice. If an explicit solution is not computable, either because it is too expensive to store and evaluate (even for moderately complex linear-quadratic problems), or not computable at all (as in the general nonlinear case), knowing the optimal active set can greatly simplify online optimization. For example in the simple case of upper and lower bounds only, the OCP becomes unconstrained and with a smaller or equal number of optimization variables to determine. Even in case an explicit solution is predetermined offline, knowing the optimal active set can greatly simplify the solution of the point-location problem online. The characterization with active sets has led to several interesting insights for the linear-quadratic case. Neighboring regions of the piecewise solution to the OCP can be identified from analyzing the active sets (AhmadiMoshkenani et al., 2018). Similarly, it has been shown that dynamic programming can be carried out with the active sets (M¨onnigmann, 2019), which helps to accelerate the construction of all active sets (Mitze and M¨onnigmann, 2020). Finally, symmetries of the solution to the OCP can be found in the set of active sets (Mitze et al., 2023). All these results are essentially based on geometric relations of the regions defined by the active sets without requiring geometric calculations. In the present paper, we focus on dynamic relations of active sets for a particular nonlinear problem class. Specifically, we show that the successor active set can be found with very simple operations on the current active set (such as index shifts of index sets). In particular, no Copyright © 2024 The Authors. This is an open access article under the CC BY-NC-ND license ( https://creativecommons.org/licenses/by-nc-nd/4.0/ ) 182 M. Mönnigmann et al. / IFAC PapersOnLine 58-18 (2024) 181–187 optimal control problems (or other optimization problems) need to be solved to obtain successor active sets. Successor active sets, which define the successor optimal solution, can be constructed both for open-loop optimal and closedloop optimal solutions, where “closed-loop optimal” refers to the usual MPC use of the OCP solution on a receding horizon. We note that dynamic relations of active sets have been used to determine robust MPC solutions for the linear-quadratic case (M¨onnigmann and Pannocchia, 2020) and a shrinking horizon nonlinear case (Dyrska and M¨onnigmann, 2024) before. Section 2 introduces the problem class. Section 3 states the main results. It first introduces the symbolic dynamics informally (see (I), (II), (III) in subsection 3.3), illustrates these ideas with a sample problem, and states formal results. Brief conclusions and an outlook are stated in Section 4. 2. PROBLEM STATEMENT We consider discrete-time, nonlinear systems of the form x(k+ 1) = f(x(k),u(k)),k=0,1,... (1a) with state x(k)∈Rn, input u(k)∈Rm, and a nonlinear state-update function f:Rn×Rm→Rn. We assume states and inputs are subject to constraints x(k)∈X⊂Rn, u(k)∈U⊂Rm(1b) for all time steps k, where Xand Uare compact sets that contain the origin in their interior and that can be described as the intersection of a finite number of sublevel sets. Furthermore, we assume fis twice continuously differentiable on an open superset of X×U, and f(0,0) = 0. We are interested in the infinite-horizon nonlinear optimal control problem for (1) min u(k),x(k+1),k=0,1,... ∞  k=0 ℓ(x(k),u(k)) (2a) subject to x(k+ 1) = f(x(k),u(k)),k=0,1,... x(k)∈X,k=0,1,... u(k)∈U,k=0,1,... (2b) for given current state x(0), and the stage cost ℓ(x, u), which is specified later. The finite-horizon problem over Nsteps min u(k),x(k+1),k=0,...N−1ℓT(x(N)) + N−1  k=0 ℓ(x(k),u(k)) (3a) subject to x(k+ 1) = f(x(k),u(k)),k=0, ..., N −1 x(k)∈X,k=0, ..., N −1 u(k)∈U,k=0, ..., N −1 x(N)∈T. (3b) is used as an auxiliary problem, where ℓT(x) and T ⊆X with 0 ∈int Tare a terminal cost and constraint, respectively, which are described in more detail in Assumption 1. Let FNrefer to the set of initial states x(0) for which (3) with horizon Nhas a solution. The following Assumption 1 allows to relate solutions of (2) and (3). The assumption is mild for linear systems but strong for nonlinear systems. It therefore deserves some comments, which are stated below. Assumption 1. Assume there exist a set T ⊆X,a feedback law κ:T →Uand a terminal cost ℓT:T→R such that int Tis positive invariant for the closed-loop system and such that, for any x(0) ∈T, evaluating u(k)=κ(x(k)), x(k+ 1) = f(x(k),κ(x(k))) (4) for k=0,1,... yields a minimum for (2) for initial condition x(0) with cost ∞ k=0 ℓ(x(k),u(k)) = ℓT(x(0)). Assumption 1 is strong because it essentially states we know an optimal solution to the infinite-horizon problem for all initial conditions from Tand know the corresponding infinite-horizon cost. This assumption can easily be fulfilled for linear-quadratic problems under mild additional conditions (Chmielewski and Manousiouthakis, 1996; Scokaert and Rawlings, 1998), (Bemporad et al., 2002, Sect. 3). A nonlinear class that respects Assumption 1 results for switching cost functions of the form ℓ(x, u)=˜ ℓ(x, u) if x∈T ˆ ℓ(x, u) otherwise. This switching cost function class yields the following relation of the infinite-horizon cost (2a) to the finitehorizon cost (3a): ∞  k=0 ℓ(x(k),u(k)= ∞  k=N ˜ ℓ(x(k),u(k))   ℓT(x(N)) + N−1  k=0 ℓ(x(k),u(k)) where only ˜ ℓappears in ℓTbecause x(N+k)∈T for all k≥0 if int Tis positive invariant. Also note that ℓT(x(N)) = ∞ k=N˜ ℓ(x(k),u(k)) can be expressed in terms of only x(N), because x+=f(x, κ∞(x)) and u(x)=κ(x) uniquely determine the sequences u(N),u(N+ 1),... and x(N+ 1),x(N+ 2),... for a given x(N). The required dual-mode controller results if we determine a control law u=κ(x) that results in the desired properties on some set Tand then treat x+=f(x, κ(x)+u) by setting u= 0 on T. The following example illustrates Assumption 1. The example is used for all illustrations in the paper. Example 1. Consider the system (1) with f(x, u)=Ax +bu +1 40 x2 1,A=1 2−11 −1−1,b=0 1 constraint sets X=x∈R2|−1≤xi≤1,i=1,2 U={u∈R|−1≤u≤1} stage cost ℓ(x, u)=1 2x⊤Qx +1 2Ru2,Q=10 01 ,R=1/10 terminal cost ℓT(x) = 0, and terminal set Tand controller κT:T→R T=x∈R2|∥x∥2 2≤1,κ T(x)=0. It is easy to show that Tis positive invariant for x(k+ 1) = f(x(k),κ T(x(k)). The proof is given in Appendix A for completeness. M. Mönnigmann et al. / IFAC PapersOnLine 58-18 (2024) 181–187 183 optimal control problems (or other optimization problems) need to be solved to obtain successor active sets. Successor active sets, which define the successor optimal solution, can be constructed both for open-loop optimal and closedloop optimal solutions, where “closed-loop optimal” refers to the usual MPC use of the OCP solution on a receding horizon. We note that dynamic relations of active sets have been used to determine robust MPC solutions for the linear-quadratic case (M¨onnigmann and Pannocchia, 2020) and a shrinking horizon nonlinear case (Dyrska and M¨onnigmann, 2024) before. Section 2 introduces the problem class. Section 3 states the main results. It first introduces the symbolic dynamics informally (see (I), (II), (III) in subsection 3.3), illustrates these ideas with a sample problem, and states formal results. Brief conclusions and an outlook are stated in Section 4. 2. PROBLEM STATEMENT We consider discrete-time, nonlinear systems of the form x(k+ 1) = f(x(k),u(k)),k=0,1,... (1a) with state x(k)∈Rn, input u(k)∈Rm, and a nonlinear state-update function f:Rn×Rm→Rn. We assume states and inputs are subject to constraints x(k)∈X⊂Rn, u(k)∈U⊂Rm(1b) for all time steps k, where Xand Uare compact sets that contain the origin in their interior and that can be described as the intersection of a finite number of sublevel sets. Furthermore, we assume fis twice continuously differentiable on an open superset of X×U, and f(0,0) = 0. We are interested in the infinite-horizon nonlinear optimal control problem for (1) min u(k),x(k+1),k=0,1,... ∞  k=0 ℓ(x(k),u(k)) (2a) subject to x(k+ 1) = f(x(k),u(k)),k=0,1,... x(k)∈X,k=0,1,... u(k)∈U,k=0,1,... (2b) for given current state x(0), and the stage cost ℓ(x, u), which is specified later. The finite-horizon problem over Nsteps min u(k),x(k+1),k=0,...N−1ℓT(x(N)) + N−1  k=0 ℓ(x(k),u(k)) (3a) subject to x(k+ 1) = f(x(k),u(k)),k=0, ..., N −1 x(k)∈X,k=0, ..., N −1 u(k)∈U,k=0, ..., N −1 x(N)∈T. (3b) is used as an auxiliary problem, where ℓT(x) and T ⊆X with 0 ∈int Tare a terminal cost and constraint, respectively, which are described in more detail in Assumption 1. Let FNrefer to the set of initial states x(0) for which (3) with horizon Nhas a solution. The following Assumption 1 allows to relate solutions of (2) and (3). The assumption is mild for linear systems but strong for nonlinear systems. It therefore deserves some comments, which are stated below. Assumption 1. Assume there exist a set T ⊆X,a feedback law κ:T →Uand a terminal cost ℓT:T→R such that int Tis positive invariant for the closed-loop system and such that, for any x(0) ∈T, evaluating u(k)=κ(x(k)), x(k+ 1) = f(x(k),κ(x(k))) (4) for k=0,1,... yields a minimum for (2) for initial condition x(0) with cost ∞ k=0 ℓ(x(k),u(k)) = ℓT(x(0)). Assumption 1 is strong because it essentially states we know an optimal solution to the infinite-horizon problem for all initial conditions from Tand know the corresponding infinite-horizon cost. This assumption can easily be fulfilled for linear-quadratic problems under mild additional conditions (Chmielewski and Manousiouthakis, 1996; Scokaert and Rawlings, 1998), (Bemporad et al., 2002, Sect. 3). A nonlinear class that respects Assumption 1 results for switching cost functions of the form ℓ(x, u)=˜ ℓ(x, u) if x∈T ˆ ℓ(x, u) otherwise. This switching cost function class yields the following relation of the infinite-horizon cost (2a) to the finitehorizon cost (3a): ∞  k=0 ℓ(x(k),u(k)= ∞  k=N ˜ ℓ(x(k),u(k))    ℓT(x(N)) + N−1  k=0 ℓ(x(k),u(k)) where only ˜ ℓappears in ℓTbecause x(N+k)∈T for all k≥0 if int Tis positive invariant. Also note that ℓT(x(N)) = ∞ k=N˜ ℓ(x(k),u(k)) can be expressed in terms of only x(N), because x+=f(x, κ∞(x)) and u(x)=κ(x) uniquely determine the sequences u(N),u(N+ 1),... and x(N+ 1),x(N+ 2),... for a given x(N). The required dual-mode controller results if we determine a control law u=κ(x) that results in the desired properties on some set Tand then treat x+=f(x, κ(x)+u) by setting u= 0 on T. The following example illustrates Assumption 1. The example is used for all illustrations in the paper. Example 1. Consider the system (1) with f(x, u)=Ax +bu +1 40 x2 1,A=1 2−11 −1−1,b=0 1 constraint sets X=x∈R2|−1≤xi≤1,i=1,2 U={u∈R|−1≤u≤1} stage cost ℓ(x, u)=1 2x⊤Qx +1 2Ru2,Q=10 01 ,R=1/10 terminal cost ℓT(x) = 0, and terminal set Tand controller κT:T→R T=x∈R2|∥x∥2 2≤1,κ T(x)=0. It is easy to show that Tis positive invariant for x(k+ 1) = f(x(k),κ T(x(k)). The proof is given in Appendix A for completeness. 3. SYMBOLIC DYNAMICS FOR ACTIVE SETS 3.1 Preliminaries We need to state a clear relation between solutions of the problems with finite and infinite horizons. Lemma 1. Consider a constrained system (1) and suppose Assumption 1 holds. (a) Let x(0) be an arbitrary initial condition such that the horizon-Nproblem (3) has an optimal solution, which we denote (u(k),x(k+ 1))N−1 k=0 .(5) If x(N)∈int T, then (5) extended by (4) for all k≥N is an optimal solution for the infinite-horizon problem (2) with initial condition x(0). (b) Conversely, let x(0) be an arbitrary initial condition such that the infinite-horizon problem (2) has an optimal solution, which we denote (u(k),x(k+ 1))∞ k=0 .(6) If there exists an Nsuch that x(N)∈int T, then (6) truncated after Nsteps is an optimal solution for (3) with horizon Nand initial condition x(0). The proof of Lemma 1 is stated in Appendix B. Note that Lemma 1 cannot be stated as an equivalence. Problems (2) and (3) are not equivalent because the set of admissible initial conditions is in general larger for (2) than for (3). Remark 1. The condition x(N)∈int Tcan neither be omitted nor replaced by x(N)∈T in part (a) of Lemma 1. An example where all conditions of Lemma 1 but x(N)∈ int Thold and the implication of Lemma 1 does not hold is given in (M¨onnigmann, 2019, Example 2 and Fig. 3) for a linear example to which the lemma applies. We stress this counterexample is not a pathological or otherwise artificial case. We must expect full-dimensional regions of initial conditions to exist such that (3) has solutions with x(N)∈int Tthat cannot be extended to solutions for the infinite-horizon problem (2) even if Assumption 1 holds. 3.2 Ordering the constraints We assume without restriction the constraints are ordered stage by stage, i.e., in the order x(0) ∈X,u(0) ∈U,(qstage constraints) x(1) ∈X,u(1) ∈U,(qstage constraints) . . . x(N−1) ∈X,u(N−1) ∈U,(qstage constraints) x(N)∈T (qTconstraints) (7) where the number of constraints per line is given in parentheses. We refer to the stages evident from (7) as stage 0, stage 1,..., stage N−1, and the terminal stage, respectively. It turns out to be convenient to denote sets of active constraints with bit sequences. For example, consider a problem with horizon N= 2, qstage = 5, qT= 3, q=Nqstage +qT= 13 constraints in the order (7) and assume the active set A={1,3,12}appears. Let qdenote the total number of constraints q=Nq stage +qT. We identify Awith 10100  α0 .00000  α1 .010  α2 (8) where dots are introduced to separate stages and the αi refer to the bit tupels of the stages. We call (8) an active set to avoid phrases like ’the bit sequence identified with the active set’. Recall Ais an active set of (3) if there exists an x(0) ∈F Nwith active set Aat the optimal solution. 3.3 Informal summary We intend to characterize the solution of the horizon-N+1 problem (3) by carrying over as much information from the horizon-Nproblem as possible. We stress that the solution for horizon Nis in general not contained in the solution for horizon N+ 1. This can easily be illustrated with explicit solutions in the linear-quadratic case, where the explicit control law for horizon N+ 1 does not coincide with the law for N(wherever they both exist, i.e., on the feasible set for N; see M¨onnigmann (2019), Fig. 1 for an example). In fact, the solution for an initial condition x(0) and horizon Ndoes remain the same for N+ 1 if x(N)∈ int T. Solutions for which x(N)∈Tis fulfilled with x(N)∈∂T, where ∂Trefers to the boundary of T, do not have this property. It may appear pedantic to even pay attention to solutions with x(N)∈∂T, since ∂Tis a set with measure zero. Solutions with this property do in general exist, however, for full-dimensional regions of initial conditions (see M¨onnigmann, 2019, Fig. 3, for an example again) and therefore are not negligible, because they constitute parts of FNwith nonzero measure. Rather than analyzing the effect of an increasing horizon point-by-point, i.e., x(0) by x(0), it proved useful to carry out this analysis with the active sets and the regional optimal feedback laws they define. Essentially, we need three simple operations on active sets, which are referred to as I, II and III below. Let ”x” refer to an unspecified bit in an active set. Color is used as guide to the eye. In (I) and (III) (but not in (II)) the terminal constraints are assumed to be inactive as evident from the trailing zeros: (I) Extending an Awith an inactive stage An active set for (3) with horizon Nmay be extended to the right with a zero stage to obtain an active set for (3) with horizon N+ 1: AN=α0.α1.···.αN−1.0...0 ↓ AN+1 =α0.α1.....α N−1.0...0.0...0 If ANis an active set for horizon N, then AN+1 is an active set for horizon N+1. Specifically, AN+1 defines the same region as ANor a superset thereof, and the optimal solution is equal on the common region. (See Prop. 1 and Example 2 below for a concise statement of I and an example, respectively.) (II) Deleting the first stage of an A Deleting a stage on the left in an active set for (3) with horizon Nresults in an active set for (3) with horizon N−1: AN=x...x.x...x.···.x...x.0...0 ↓ AN−1=x...x.···.x...x.0...0 184 M. Mönnigmann et al. / IFAC PapersOnLine 58-18 (2024) 181–187 If ANis an active set for horizon N, then AN−1is an active set for horizon N−1. (See Prop. 2 and Example 3.) While (I) and (II) relate active sets for different horizons, combining the two results in a simple relation between active sets for the same horizon. (III) Symbolic dynamics for active sets Applying (I) and (II) to an active set for horizon N results in a new active set for horizon Nthat is part of the solution: AN=x...x.x...x.···.x...x.0...0 ↓ A′ N=x...x.···.x...x.0...0.0...0 Moreover, A′ Ndefines the successor region for the region defined by AN. In other words, A′ Ndefines the region to which the nominal system is driven when the first optimal control signal is applied. (See Prop. 3 and Example 4.) 3.4 Precise statements and illustrations Proposition 1 states claim (I) more precisely. The proposition 1 extends Lemma 3 from M¨onnigmann (2019) for linear-quadratic problems to the nonlinear system class treated here. Proposition 1. (a) Consider (3) with constraint order (7). If α0.··· .αN−1.0···0  qT (9) is an active set of (3) with horizon N, then α0.··· .αN−1.0···0  l(qX+qU) .0···0  qT (10) is an active set for horizon N+lfor all l≥0. (b) The set defined by (10) is equal to or a superset of the set defined by (9). Both active sets yield the same solution on the set defined by (9). Proof. (a) According to Lemma 1 part (a), the active set (9) can be extended with (4) to a solution for the infinite-horizon problem. Since int Tis positive invariant for the system subject to u(k)=κ(x(k)) from (4) by assumption, all constraints on u(k), x(k), k≥Nare inactive. According to part (b) of Lemma 1, the infinitehorizon solution can be truncated to any length N+l, l≥0. Since the constraints are inactive for all stages l≥0, the active set (10) exists for all l≥0. (b) Let x(0) ∈Rnbe an arbitrary point such that there exists a minimum for (3) with horizon Nand with active set AN. Let (5) refer to this solution. According to Prop. 1 this solution can be extended to a solution (6) for the infinite-horizon problem. The positive invariance of intTimplies x(N+l)∈int T for all l≥0. Therefore (6) can be truncated for any l≥0 according to part (b) of Lemma 1. Since this truncated solution yields the same active constraints for the first N stages as the horizon-Nproblem and solution, and since all additional stages N+l,l≥0 are inactive, the active set (10) results for horizon N+lfor any l≥0. We showed that any x(0) ∈Rnthat is a solution to (3) with horizon Nand active set (9) also is a solution for (3) with horizon N+land active set (10) for any l≥0.  We illustrate claim (I) and Prop. 1 with Example 2. The results shown in Figs. 1 to 4 are obtained by solving (3) on a grid of 100 ×100 points and recording all solutions including the active sets. Example 2. Figure 1 shows all initial states x(0) that result in the active sets 000001.000000.0(N= 2) (11a) 000001.000000.000000.0(N= 3) (11b) for (3) with Example 1 and N= 2 and N= 3, respectively. It is evident from the figures that the set defined by (11b) and N= 3 is a superset of the set defined by (11a). Moreover, it is evident the optimal signal u(0) = −1 results in both cases. The remaining optimal input signals are also equal, which we claim without showing them. The active constraint in both active sets corresponds to u(0) = −1. As a side-effect, Example 2 shows that sets of points defined by an active set may not be connected in the nonlinear case. Proposition 2 and Example 3 belong to claim (II). Note that the terminal constraints are not required to be inactive in Prop. 2. Furthermore, note that claim (II) and Proposition 2 essentially state the principle of optimality for active sets. Proposition 2. Consider (3) with constraint order (7). If AN=α0.α1··· .αN−1.αN(12) is an active set for (3) with horizon N, then AN−1=α1··· .αN−1.αN(13) is an active set for (3) with horizon N−1. Moreover, any x(0) from the set defined by ANis mapped to a successor state in the set defined by AN−1for the closedloop nominal system. Proof. Let x(0) be any initial condition such that (3) for horizon Nresults in an optimal solution with active set (12). Let the optimal solution be denoted as in (5). Then the sequence that results from (5) after removing u(0) and x(1), i.e., (u(k),x(k+ 1))N−1 k=1 (14) is an optimal solution for (3) with horizon N−1 and initial condition x(1) by the principle of optimality. Since the same constraints are active for (14) as for (5) the active set (13) results, which proves the first part of the claim. Since x(0) was an arbitrary initial condition from the set defined by (12), and since x(1) belongs to the set defined by (13), the second part of the claim holds.  Example 3. Figure 2 shows all initial states x(0) for which (3) with Example 1 results in the active sets 000001.000001.000000.0(N= 3) 000001.000000.0(N= 2) for N= 2 and N= 3, respectively. The yellow region in the figure for N= 2 results from the yellow region for N= 3 with the principle of optimality. Finally, Prop. 3 and Example 4 state respectively illustrate the main result, i.e., the symbolic dynamics for active sets stated in claim (III). It is the very point of the paper to show that sequences of active sets (e.g., (15)→(16) in Prop. 3 or (18a)→(18b)→(18c) and (19a)→(19b)→(19c) in Example 4) can be inferred from an active set with M. Mönnigmann et al. / IFAC PapersOnLine 58-18 (2024) 181–187 185 If ANis an active set for horizon N, then AN−1is an active set for horizon N−1. (See Prop. 2 and Example 3.) While (I) and (II) relate active sets for different horizons, combining the two results in a simple relation between active sets for the same horizon. (III) Symbolic dynamics for active sets Applying (I) and (II) to an active set for horizon N results in a new active set for horizon Nthat is part of the solution: AN=x...x.x...x.···.x...x.0...0 ↓ A′ N=x...x.···.x...x.0...0.0...0 Moreover, A′ Ndefines the successor region for the region defined by AN. In other words, A′ Ndefines the region to which the nominal system is driven when the first optimal control signal is applied. (See Prop. 3 and Example 4.) 3.4 Precise statements and illustrations Proposition 1 states claim (I) more precisely. The proposition 1 extends Lemma 3 from M¨onnigmann (2019) for linear-quadratic problems to the nonlinear system class treated here. Proposition 1. (a) Consider (3) with constraint order (7). If α0.··· .αN−1.0···0  qT (9) is an active set of (3) with horizon N, then α0.··· .αN−1.0···0  l(qX+qU) .0···0  qT (10) is an active set for horizon N+lfor all l≥0. (b) The set defined by (10) is equal to or a superset of the set defined by (9). Both active sets yield the same solution on the set defined by (9). Proof. (a) According to Lemma 1 part (a), the active set (9) can be extended with (4) to a solution for the infinite-horizon problem. Since int Tis positive invariant for the system subject to u(k)=κ(x(k)) from (4) by assumption, all constraints on u(k), x(k), k≥Nare inactive. According to part (b) of Lemma 1, the infinitehorizon solution can be truncated to any length N+l, l≥0. Since the constraints are inactive for all stages l≥0, the active set (10) exists for all l≥0. (b) Let x(0) ∈Rnbe an arbitrary point such that there exists a minimum for (3) with horizon Nand with active set AN. Let (5) refer to this solution. According to Prop. 1 this solution can be extended to a solution (6) for the infinite-horizon problem. The positive invariance of intTimplies x(N+l)∈int T for all l≥0. Therefore (6) can be truncated for any l≥0 according to part (b) of Lemma 1. Since this truncated solution yields the same active constraints for the first N stages as the horizon-Nproblem and solution, and since all additional stages N+l,l≥0 are inactive, the active set (10) results for horizon N+lfor any l≥0. We showed that any x(0) ∈Rnthat is a solution to (3) with horizon Nand active set (9) also is a solution for (3) with horizon N+land active set (10) for any l≥0.  We illustrate claim (I) and Prop. 1 with Example 2. The results shown in Figs. 1 to 4 are obtained by solving (3) on a grid of 100 ×100 points and recording all solutions including the active sets. Example 2. Figure 1 shows all initial states x(0) that result in the active sets 000001.000000.0(N= 2) (11a) 000001.000000.000000.0(N= 3) (11b) for (3) with Example 1 and N= 2 and N= 3, respectively. It is evident from the figures that the set defined by (11b) and N= 3 is a superset of the set defined by (11a). Moreover, it is evident the optimal signal u(0) = −1 results in both cases. The remaining optimal input signals are also equal, which we claim without showing them. The active constraint in both active sets corresponds to u(0) = −1. As a side-effect, Example 2 shows that sets of points defined by an active set may not be connected in the nonlinear case. Proposition 2 and Example 3 belong to claim (II). Note that the terminal constraints are not required to be inactive in Prop. 2. Furthermore, note that claim (II) and Proposition 2 essentially state the principle of optimality for active sets. Proposition 2. Consider (3) with constraint order (7). If AN=α0.α1··· .αN−1.αN(12) is an active set for (3) with horizon N, then AN−1=α1··· .αN−1.αN(13) is an active set for (3) with horizon N−1. Moreover, any x(0) from the set defined by ANis mapped to a successor state in the set defined by AN−1for the closedloop nominal system. Proof. Let x(0) be any initial condition such that (3) for horizon Nresults in an optimal solution with active set (12). Let the optimal solution be denoted as in (5). Then the sequence that results from (5) after removing u(0) and x(1), i.e., (u(k),x(k+ 1))N−1 k=1 (14) is an optimal solution for (3) with horizon N−1 and initial condition x(1) by the principle of optimality. Since the same constraints are active for (14) as for (5) the active set (13) results, which proves the first part of the claim. Since x(0) was an arbitrary initial condition from the set defined by (12), and since x(1) belongs to the set defined by (13), the second part of the claim holds.  Example 3. Figure 2 shows all initial states x(0) for which (3) with Example 1 results in the active sets 000001.000001.000000.0(N= 3) 000001.000000.0(N= 2) for N= 2 and N= 3, respectively. The yellow region in the figure for N= 2 results from the yellow region for N= 3 with the principle of optimality. Finally, Prop. 3 and Example 4 state respectively illustrate the main result, i.e., the symbolic dynamics for active sets stated in claim (III). It is the very point of the paper to show that sequences of active sets (e.g., (15)→(16) in Prop. 3 or (18a)→(18b)→(18c) and (19a)→(19b)→(19c) in Example 4) can be inferred from an active set with Fig. 1. Illustration of claim (I) and Prop. 1. The region defined by (11a) for N= 2 (yellow, top diagrams) is a subset of the region defined by (11b) for N= 3 (green and yellow, bottom diagrams, yellow used to highlight the region from N= 2). Grey area delineates FN. inactive terminal constraints, where these sequences of active sets define sequences of regions through which the systems evolves under MPC. Obtaining these does not require solving optimal control problems, but the successor active sets can simply be constructed by deleting the first Fig. 2. Illustration of claim (II) and Prop. 2. Initial states from the region defined by (12) for N= 3 propagate to the region defined by (13) for N= 2. stage of the given active set and appending it by an inactive stage. Proposition 3. Consider (3) with constraint order (7). If (15) is an active set, then (16) is an active set, where (16) results from deleting α0and inserting an inactive penultimate stage in (15). 186 M. Mönnigmann et al. / IFAC PapersOnLine 58-18 (2024) 181–187 Fig. 3. Illustration of claim (III) and Prop. 3. The regions belong to the active sets (18). Any initial point x(0) located in the red region passes through the cyan and green region and subsequently enters the blue region. The sequence of these active sets can be found from the first active set (18a) with claim (III) and Prop. 3 without solving any optimal control problem. α0.α1.α2.··· .αN−1.0···0  qT (15) α1.α2.··· .αN−1.0···0.0···0  qT (16) Moreover, (16) defines the successor set to the set defined by (15) or a superset thereof. In other words, for any x(0) that belongs to the set defined by (15), the successor state belongs to the set defined by (16). Proof. If (15) is an active set for horizon N, then α1.α2.··· .αN−1.0···0 (17) is an active set for horizon Naccording to Prop. 2. Inserting an inactive penultimate inactive stage in (17) results in (16), which is an active set for horizon N according to Prop. 1.  Example 4. Consider the optimal control problem (3) for Example 1 and N= 3. Figure 3 shows the regions defined by active sets 000001.000010.000000.0 (red) (18a) 000010.000000.000000.0 (cyan) (18b) 000000.000000.000000.0 (green) (18c) which result from applying claim (III) or Prop. 3 to (18a) once and twice. The colors stated in parentheses correspond to the colors of the regions in Fig. 3. To show another example, Fig. 4 shows the regions defined by active sets Fig. 4. Illustration of claim (III) and Prop. 3 with another example. The regions belong to the active sets (19). See the caption of Fig. 3 for further explanations. 000001.000001.000000.0 (red) (19a) 000001.000000.000000.0 (cyan) (19b) 000000.000000.000000.0 (green) (19c) which result from applying claim (III) or Prop. 3 to (19a) once and twice. 4. CONCLUSIONS AND OUTLOOK We showed how to infer active sets that characterize the optimal successor solution given the active set of the current optimal solution. It was the purpose of the paper to establish the operations that need to be carried out with the active sets. Because these rules do not involve optimal control (or other optimization) problems but are based on simple operations like index shifts, we coined the term symbolic dynamics for active sets for them. Future work will focus on extending the problem class. Extensions may either attempt to drop some of the assumptions, or to combine the two-stage cost function with an advanced terminal controller such as an economic model predictive controller. Appendix A. PROPERTIES OF EXAMPLE 1 The linear autonomous part of the dynamical system is locally asymptotically stable at x= 0, since its eigenvalues are λ1,2=−1 2±i1 2. Furthermore, it is easy to show that ∥ξ(k+ 1)∥2=∥Aξ(k)∥2=1 2∥ξ(k)∥2for the linear autonomous part of the example. This implies ∥x(k+ 1)∥2=∥Ax(k)+1 40 x2 1∥2≤1 2∥x(k)∥2+1 42x4 1. Since the M. Mönnigmann et al. / IFAC PapersOnLine 58-18 (2024) 181–187 187 Fig. 3. Illustration of claim (III) and Prop. 3. The regions belong to the active sets (18). Any initial point x(0) located in the red region passes through the cyan and green region and subsequently enters the blue region. The sequence of these active sets can be found from the first active set (18a) with claim (III) and Prop. 3 without solving any optimal control problem. α0.α1.α2.··· .αN−1.0···0  qT (15) α1.α2.··· .αN−1.0···0.0···0  qT (16) Moreover, (16) defines the successor set to the set defined by (15) or a superset thereof. In other words, for any x(0) that belongs to the set defined by (15), the successor state belongs to the set defined by (16). Proof. If (15) is an active set for horizon N, then α1.α2.··· .αN−1.0···0 (17) is an active set for horizon Naccording to Prop. 2. Inserting an inactive penultimate inactive stage in (17) results in (16), which is an active set for horizon N according to Prop. 1.  Example 4. Consider the optimal control problem (3) for Example 1 and N= 3. Figure 3 shows the regions defined by active sets 000001.000010.000000.0 (red) (18a) 000010.000000.000000.0 (cyan) (18b) 000000.000000.000000.0 (green) (18c) which result from applying claim (III) or Prop. 3 to (18a) once and twice. The colors stated in parentheses correspond to the colors of the regions in Fig. 3. To show another example, Fig. 4 shows the regions defined by active sets Fig. 4. Illustration of claim (III) and Prop. 3 with another example. The regions belong to the active sets (19). See the caption of Fig. 3 for further explanations. 000001.000001.000000.0 (red) (19a) 000001.000000.000000.0 (cyan) (19b) 000000.000000.000000.0 (green) (19c) which result from applying claim (III) or Prop. 3 to (19a) once and twice. 4. CONCLUSIONS AND OUTLOOK We showed how to infer active sets that characterize the optimal successor solution given the active set of the current optimal solution. It was the purpose of the paper to establish the operations that need to be carried out with the active sets. Because these rules do not involve optimal control (or other optimization) problems but are based on simple operations like index shifts, we coined the term symbolic dynamics for active sets for them. Future work will focus on extending the problem class. Extensions may either attempt to drop some of the assumptions, or to combine the two-stage cost function with an advanced terminal controller such as an economic model predictive controller. Appendix A. PROPERTIES OF EXAMPLE 1 The linear autonomous part of the dynamical system is locally asymptotically stable at x= 0, since its eigenvalues are λ1,2=−1 2±i1 2. Furthermore, it is easy to show that ∥ξ(k+ 1)∥2=∥Aξ(k)∥2=1 2∥ξ(k)∥2for the linear autonomous part of the example. This implies ∥x(k+ 1)∥2=∥Ax(k)+1 40 x2 1∥2≤1 2∥x(k)∥2+1 42x4 1. Since the last expression is not larger than 1 2+1 16 for all x(k) the closed unit disk, the example is positive invariant on Tfor u=κT(x). It can be shown to be positive invariant on the interior of Tby the same arguments. Appendix B. PROOF OF LEMMA 1 Part (a): Consider the infinite-horizon problem (2) for x(0), assume (5) extended by (4) is not an optimal solution and show a contradiction results. If (5) extended by (4) is not an optimal solution, then there exists, in any neighborhood of (5) extended by (4), a different sequence that respects the constraints of (2) and yields a lower cost function value for (2). Let (˜u(k),˜x(k+ 1))∞ k=0 refer to this sequence and assume it is from a neighborhood of (4, 5) sufficiently small for x(N)∈int Tto imply ˜x(N)∈int T.(B.1) This implies at least one of the terms N−1  k=0 ℓ(˜x(k),˜u(k)) + ∞  k=N ℓ(˜x(k),˜u(k)) evaluates to a lower value than its counterpart in N−1  k=0 ℓ(x(k),u(k)) + ∞  k=N ℓ(x(k),u(k)). If this is the case for the second term, this contradicts the optimality of (4). If this is the case for the first term, this contradicts the optimality of (5), where we used the fact that (˜u(k),˜x(k+ 1))N−1 k=0 is admissible for (3) because it respects (B.1) and the remaining constraints of (3) are fulfilled because (3) has them in common with (2). Thus, the desired contradiction results in any case. Part (b): The truncated sequence (6) is feasible for the horizon-Nproblem (3), since problems (2) and (3) have the constraints for stages k=0,...,N −1 in common, and the only remaining constraint of (3), i.e., x(N)∈T, is fulfilled by assumption. Now assume the truncated sequence is feasible but not optimal for (3). This implies there exists (in any, arbitrarily small, neighborhood N⊂ RmN ×RnN of the truncated sequence) a different sequence (¯u(k),¯x(k+ 1))N−1 k=0 (B.2) that results in a lower cost function value, with ¯x(N)∈T (and, in general, ¯x(N)=x(N)). By part (a) we can extend (B.2) to a solution for the infinite-horizon problem, which we denote (¯u(k),¯x(k))∞ k=0. Since (¯u(k),¯x(k))N−1 k=0 =(u(k),x(k))N−1 k=0 , we also have (¯u(k),¯x(k))∞ k=0 =(u(k),x(k))∞ k=0 ,(B.3) and the optimality of the former does not contradict the optimality of the latter. Since Ncan be chosen to be arbitrarily small, we can make the difference between the l.h.s. and r.h.s. in (B.3) arbitrarily small (e.g., in the obvious 2-norm). This implies there exists a solution (¯u(k),¯x(k+ 1))∞ k=0 in any neighborhood of (u(k),x(k+ 1))∞ k=0 such that the former results in a lower cost function value than the latter, which is the desired contradiction. REFERENCES Ahmadi-Moshkenani, P., Johansen, T.A., and Olaru, S. (2018). Combinatorial approach toward multiparametric quadratic programming based on characterizing adjacent critical regions. IEEE Transactions on Automatic Control, 63(10), 3221–3231. Bemporad, A., Morari, M., Dua, V., and Pistikopoulos, E.N. (2002). The explicit linear quadratic regulator for constrained systems. Automatica, 38(1), 3–20. Chmielewski, D. and Manousiouthakis, V. (1996). On constrained infinite-horizon linear quadratic optimal control. Systems and Control Letters, 121–129. Dyrska, R. and M¨onnigmann, M. (2024). Active set prediction for nonlinear model predictive control on a shrinking horizon based on the principle of optimality. Int. J. Robust and Nonlinear Control, 34(4), 2768–2780. Feller, C., Johansen, T., and Olaru, S. (2013). An improved algorithm for combinatorial multi-parametric quadratic programming. Automatica, 45(5), 1370–1376. Gupta, A., Bhartiya, S., and Nataraj, P. (2011). A novel approach to multiparametric quadratic programming. Automatica, 47(9), 2112–2117. Herceg, M., Jones, C., Kvasnica, M., and Morari, M. (2015). Enumeration-based approach to solving parametric linear complementarity problems. Automatica, 62, 243–248. Herceg, M., Kvasnica, M., Jones, C., and Morari, M. (2013). Multi-parametric toolbox 3.0. In Proc. 2013 European Control Conference (ECC), 502–510. Mitze, R., Kvasnica, M., and M¨onnigmann, M. (2023). Exploiting symmetries in active set enumeration for constrained linear-quadratic optimal control. Automatica, 151, 110900. Mitze, R. and M¨onnigmann, M. (2020). A dynamic programming approach to solving constrained linearquadratic optimal control problems. Automatica, 120, 109132. M¨onnigmann, M. (2019). On the structure of the set of active sets in constrained linear quadratic regulation. Automatica, 106, 61–69. M¨onnigmann, M. and Pannocchia, G. (2020). Reducing the computational effort of MPC with closed-loop optimal sequences of affine laws. In 21st IFAC Worldcongress 2020, IFAC PapersOnline, volume 53, 11344– 11349. Oberdieck, R., Diangelakis, N., and Pistikopoulos, E. (2017). Explicit model predictive control: A connectedgraph approach. Automatica, 76, 103–112. Scokaert, P. and Rawlings, J. (1998). Constrained linear quadratic regulation. IEEE Transactions on Automatic Control, 43(8), 1163–1169. Seron, M., Goodwin, G., and DeDona, J. (2002). Finitely parametrised implementation of receding horizon control for constrained linear systems. In Proc. 2002 American Control Conf., 4481–4486. Tøndel, P., Johansen, T.A., and Bemporad, A. (2003). An algorithm for multi-parametric quadratic programming and explicit MPC solutions. Automatica, 39(3), 489– 497.