{'fraction_non_alphanumeric': 0.05508646998982706, 'fraction_numerical': 0.019786368260427265, 'mean_word_length': 4.101453035806954, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Low-complexity stabilizing PWA controllers for linear systems with parametric uncertainties

Explicit MPC often results in a large number of irregular partitions in the feasible region as the dimension of the system increases and the storage requirement for the control and region parameters often limit its applications. In this paper, we consider a class of discretetime linear systems with polytopic parametric uncertainties and provide a robust control Lyapunov based synthesis method to obtain robust low-complexity PWA controllers on regular partitionings. By implementing a refinement procedure, we can fit the PWA feedback control law in each regular partitioning based on feasibility of linear programming problems, which preserves stability, constraint satisfaction, and certain performance requirement. Numerical examples will demonstrate the effectiveness of the approach.


INTRODUCTION
Since its inception, explicit MPC (Bemporad et al., 2002) has become a standard way of achieving a simple and cheap implementation of optimization-based controllers. The popularity of the framework is due its ability to shift the majority of the computational effort off-line where the analytical solution to a given MPC problem is precomputed as a PWA function defined over polytopic regions. The on-line implementation then reduces to an evaluation of such a function for current values of measurements, a task that only requires modest computational resources. However, the storage complexity of such PWAbased controllers (driven mainly by the number of regions) often exceeds storage limits provided by typical control hardware. Therefore a significant research effort is devoted to developing ways of reducing the memory complexity of explicit MPC controllers even at the expense of suboptimal performance. Typical approaches either rely on relaxation of optimality conditions (Bemporad and Filippi, 2003), post-processing of the PWA function (Christophersen et al., 2007), or approximation of the optimal PWA solutions by nonlinear functions (Summers et al., 2011;Kvasnica et al., 2011). However, the majority of existing approaches can only provide feasibility and stability guarantees if the prediction model is perfect, i.e., not affected by any disturbances or uncertainties. The only notable extension is the approach of Grieder et al. (2003) which, on the one hand, supports systems with uncertainties, but, on the other hand, can not provide apriori guarantees of closed-loop stability. This paper proposes a novel way of synthesizing PWA controllers of low storage complexity for linear systems with parametric uncertainties and therefore can provide safety guarantees for a broader class of systems. Linear systems with polytopic parametric uncertainties, which are represented by a convex combination of a finite number of linear dynamics, is one of the most fundamental models in robust optimization (Ben-Tal and Nemirovski, 2002;Löfberg, 2012). To provide feasibility and stability guarantees, the papers employs the inherent freedom of control Lyapunov functions (CLF) to find a PWA function of low complexity that enforces a prescribed decay rate of the CLF while maintaining positive invariance of the domain of the control function. Therefore the presented procedure can be viewed at as an extension of methods proposed in Nguyen et al. (2014);Di Cairano et al. (2014);Nguyen et al. (2017);  with one notable improvement: while the aforementioned approaches shift some of the effort off-line, they still require an optimization problem to be solved onthe-fly to find the stabilizing control actions. The novelty of this paper lies in abolishing the need for on-line optimization completely by constructing, off-line, a regular partitioning of the state space over which the suboptimal controller is defined. Note that the underlying ideas have been proposed earlier in our conference paper (Lu et al., 2011), which, however, only covered the nominal case, i.e., only systems without uncertainties.
The idea of using a regular partitioning is not new in the context of explicit MPC and has been employed, successfully, to synthesize low-complexity PWA controllers for linear time-invariant systems either without uncertainties, or with additive disturbances only, see, e.g. Bemporad et al. (2011);Rubagotti et al. (2014) where the space was partitioned into simplices, or Johansen and Grancharova (2003); Genuit et al. (2012); Lu et al. (2011) where hyper-rectangular regions were used. In this paper, hyperrectangular partitioning of the feasible state space is used starting from a coarse partition and refining it further by orthogonal splits if required to achieve recursive feasibility and closed-loop stability. Therefore, feasibility and stability of our suboptimal PWA controller is achieved by construction. The only pre-requisites for the construction of a simple PWA feedback law that provides feasibility and stability guarantees for uncertain linear systems is the availability of a polytopic robustly positive invariant set and a convex PWA control Lyapunov function. Both of these ingredients can be constructed, off-line, by employing standard reachability analysis tools (Blanchini and Miani, 2008;. Therefore a further advantage of the presented approach is that the original (complex) explicit MPC solution is not required for constructing the simple stabilizing PWA feedback law and its costly construction need not take place. In this paper, optimal explicit MPC controllers are only considered to judge the resulting reduction of complexity.

PRELIMINARIES
Let R, R + , Z and Z + denote the set of real numbers, nonnegative real numbers, integers and non-negative integers, respectively. For a vector x ∈ R n , x p is its Hölder pnorm given by ( n i=1 |x i | p ) 1 p , 1 ≤ p < ∞, and x ∞ := max i=1,··· ,n |x i |. A set P is called a polyhedral set or polyhedron if it can be written as the intersection of a finite number of half-spaces. A compact polyhedron is called a polytope. A finite setP = {P i } is called a polytopic partitioning of a polytope P if ∪ iPi = P and int(P i ) ∩ int(P j ) = ∅, for all i = j where int(·) is the interior of a set. A function φ : R + → R + belongs to class K (φ ∈ K) if it is continuous, strictly increasing and φ(0) = 0. A function φ : and for each fixed s ∈ R + , β(s, ·) is non-increasing and lim t→∞ β(s, t) = 0.

Consider a system
x(t + 1) = Γ(x(t), w(t), u(t)), (1) where x(t) ∈ X ⊆ R n and w(t) ∈ W ⊆ R q are the state and the parametric uncertainties at time t ∈ Z + and u(t) ∈ U ⊆ R m (2) is the control input at time t ∈ Z + . The set U represents input constraints and Γ : X × W × U → R n is a given function. Definition 1. (Blanchini and Miani, 2008) Let λ ∈ R [0,1] . A set P ⊆ R n is called a controlled robustly λ-contractive invariant set for system (1)-(2) with disturbance set W, if P ⊆ X and for all x ∈ P there is a u ∈ U such that Γ(x, u, w) ∈ λP and λP ⊆ P for all w ∈ W. In case this property holds for λ = 1, we call P a controlled robustly positively invariant (CRPI) set for disturbance set W. Definition 2. (Jiang and Wang, 2001;Lazar et al., 2008) and Γ(x, u, w) ∈ X.
Note that robust control Lyapunov functions are convenient for finding robustly stabilizing feedback laws. Indeed, if V is a RCLF for (1)-(2) with disturbance set W, then any feedback law K : X → U satisfying for all x ∈ X K(x) ∈ {u ∈ U | (4) and (5) hold for all w ∈ W}, results in a closed-loop system x(t + 1) = Γ(x(t), w(t), K(x(t))), which is robustly assymptotically stable.

PROBLEM FORMULATION
In this section, we consider an extension of the previous results towards the case of discrete-time linear systems with parametric uncertainties given by where x(t) ∈ X ⊆ R n , u(t) ∈ U ⊆ R m and w(t) ∈ W ⊆ R q are, respectively, the state, the input and the parametric uncertainties at time t ∈ Z + . We assume X and U as for matrices E x ∈ R nx×n , E u ∈ R nu×m and vectors e x ∈ R nx e u ∈ R nu of appropriate dimensions. As customary in the literature on LPV systems Daafouz and Bernussou (2001), we assume that which can capture many situations of interest.
To address the problem of robust stabilization of systems of the form (6) subject to input and state constraints, the min-max MPC setup proposed in Lee and Yu (1997) can be used. In particular the following so-called closed-loop constrained robust optimal control (CL-CROC) problem is suitable in this context. This CL-CROC problem is based on the following recursion: (12) Above, Q ∈ R r Q ×n , R ∈ R r R ×m and P ∈ R r P ×n are fullcolumn rank matrices, p = 1 or p = ∞, X T ⊆ X is a polytopic terminal set with 0 ∈ int(X T ), and X j f denotes the set of states x ∈ X such that (11) is feasible for j = 0, . . . , N − 1. We define X f := X 0 f and we assume it is given as Solving this min-max feedback MPC problem, (possibly non-unique) optimal PWA state feedbacks u * j : X j f → R m , j = 0, 1, · · · , N −1 can be obtained. The min-max feedback MPC control law is set to To guarantee that the MPC state feedback u(t) = µ * (x(t)) robustly asymptotically stabilizes (6) in X f , we adopt the following assumption: Assumption 3.1 (Lazar et al., 2008) There exists a feedback gain K such that (ii) X T is a robustly positively invariant set for system (6) with disturbance set W in closed loop with Under Assumption 3.1 we obtain that (6) and (14) is robustly asymptotically stable (RAS), and V : X f → R + given by V (x) := V 0 (x) is a robust CLF for (6) and (14) and disturbance set W, see Lazar et al. (2008) for the details. Note that to satisfy (iii), we have to enforce (iii) only for the vertices of W. Then by the method presented in Lazar et al. (2006), P , K and X T can be computed using the Matlab command fmincon.
Problem 1: Consider system (6) with (9), and W as in (10). Given a regular polyhedral partitioning {P i | i ∈ FP } of X f ⊆ X, where FP ⊂ Z ≥1 is a finite set of indices, find a PWA state feedback controller given byμ : where F i ∈ R m×n , g i ∈ R m , for all i ∈ FP are chosen, such that the closed-loop system (6) and (16) has the following design properties: The set X f is robustly positively invariant for the system (6) and (16) with disturbance set W, i.e.
x ∈ X f and w ∈ W implies A(w)x + B(w)μ(x) ∈ X f , and hence, for any x(0) ∈ X f and w(t) ∈ W, t ∈ Z + , the corresponding solution to (6) and (16) satisfies the state constraints x(t) ∈ X f ⊆ X, t ∈ Z + . (iii) The system (6) and (16) with disturbance set W is robustly asymptotically stable in X f .
In , it is proven that V N −1 in (11) is a convex and PWA function of x N −1 , that a corresponding optimal controller u * N −1 can be chosen that is PWA and continuous, and the feasible set X N −1 f is a polytope. Similarly, the convexity and PWA nature of V j and the existence of continuous PWA optimal control laws u * j can be shown to hold for j = 0, . . . , N − 1. From the equivalence of the representations of PWA convex functions (Schechter, 1987), the optimal cost V = V 0 , which we get from the optimization problem (11), can be written in a convex PWA form as As mentioned, V : X f → R + is a robust CLF for system (6) and (2) on the set X f . Based on (17) we can get the partitioning of X f related to V as P l := {x ∈ R n | H l x + h l ≥ H x + h , ∈ F P , = l} (18) with l ∈ F P , i.e. ∪ l∈F P P l = X f and int(P l ) ∩ int(P ) = ∅, ∀l, ∈ F P , l = .
Next, we will derive a CLF-based approach to solve Problem 1.

MAIN RESULTS
The main approach will be based on the availability of a robust control Lyapunov function V : X f → R + for system (6) for the feasible set X f . These two ingredients can be obtained in two principal ways: (1) by solving the min-max CL-CROC problem (11) parametrically with respect to x using multiparametric programming as in  with the boundary conditions on X T and P satisfying Assumption 3.1; or (2) by first computing X f as the λ-contractive RPI set for the uncertain system (6), followed by taking V either as the gauge function (Blanchini and Miani, 2008) of the set X f , or by constructing V using convex-liftings (Nguyen et al., 2017).
All results of this paper hold regardless of which way to construct V and X f was employed.
Then we can state the first main result: Theorem 1. Given a regular polyhedral partitioningP = {P i | i ∈ FP }, and a scalar 0 ≤ λ < 1, if there exist matrices F i , g i , i ∈ FP , and a function V : X f → R + that satisfy (3)-(4) for all x ∈P i , and for all i ∈ FP Then, Problem 1 is solved for the closed-loop system (6)-(9) and (16) for the given partitioningP.
Proof. The condition (19a) enforces input constraints satisfaction and the condition (19b) is the robust positive invariance condition, meaning that the updated state A(w)x + B(w)F i x + B(w)g i = q r=1 w r (A r x + B r F i x + B r g i ) remains inside the convex set X f as given by (13) for all w ∈ W and all x ∈ X f . In addition, noting that ≤ λV (x). Hence, since the conditions of Definition 2 are met, this gives together with the robust positive invariance of X f that the closed-loop system (6)- (9) and (16) satisfies all the properties in Problem 1. 2 The difficulty for searching for the parameters F i and g i of the sub-optimal PWA controller defined over a regular polyhedral partition stems from the fact that constraints (19) need to hold for all points x ∈P i , i.e., for an infinite number of points. However, since each regionP i is assumed a polytope, it admits a vertex representatioñ where M i is the number of vertices of the i-th polytope. Moreover, let the CLF function V be a convex PWA function, thus representable by (17). Then the following result is a direct extension of Theorem 1 by arguments of convexity and robust optimization (Ben-Tal and Nemirovski, 2002;Löfberg, 2012): , and all r = 1, . . . , q, for all v ∈ extr(P i ∩ P l ), k ∈ F P , r=1, . . . , q, l ∈ I(P i , P l ), and 0 ≤ λ i < 1, where g i = 0 for all i ∈ F 0 P , and extr(P i ) enumerates the vertices of a given polytopic set.
Notice that all constraints in (20a)-(20c) are linear in F i and g i , therefore they can be searched for by solving (20) as a feasibility linear program (LP) for each region of the regular partitionP i . Remark 1. In case one would like to guarantee a certain worst case decay factor 0 ≤λ < 1, one can set for (20) the condition 0 ≤ λ i ≤λ instead of 0 ≤ λ i < 1. Remark 2. If the CLF function V is the optimal cost function of the CL-CROC problem (11), conditions (19c) and (20c) represent a bound on the performance decay.
If the LP (20) is infeasible, the regular regionsP i inside X f needs to be refined. We propose to do this by splitting the regionP i into smaller regular subregions. For instance, in case hypercubic regions are used one can perform a dyadic discretization (Gao and Yan, 2010) and get 2 n hypercubes, where n is the dimension of the space. A dyadic discretization of a hypercube splits the hypercube into 2 n equal hypercubes by inserting hyperplanes perpendicular to each of the coordinate axes exactly in the middle of each edge of the hypercube (see Gao and Yan (2010) for more details on dyadic discretization). Based on the smaller subregions, new local problems of the form (20) are generated and solved via LP techniques.
As already mentioned under same conditions, one can guarantee that only a finite number of refinement steps are needed to fulfill the LP conditions (20) and thus solve Problem 1. However, a priori it is hard to establish a bound on the number of necessary refinements. To avoid that the refinement procedure does not terminate or that the number of regular regions becomes too large due to too many refinement steps, a maximum number of regions n max and/or a maximum level of refinement h max is added as a stopping criterium to the refinement procedure.
Hence, the refinement procedure provides the means to synthesize the partitioning automatically as instead of fixing a regular partitioningP = {P i | i ∈ FP } of X f ⊆ X a priori, one can start from a very rough initial partitioningP init , e.g., consisting of only X f , which is refined only where necessary to eventually satisfy (20) (or reach the maximum n max or h max ).

Algorithm I: Automatic Refinement Procedure
Given: A robust CLF for system (6) V : X f → R + of the form (17) for input constraint set U as in (8) is given with X f as in (13). The partitioning P is given according to (18). In addition, an initial (rough) regular partitioning P init , the maximum refinement level h max ≥ 1 and the maximal number of cells n max ≥ 1 are available. In Section 5, we will give an example to illustrate the implementation of this algorithm. In particular, in the example we will use hypercubic regions for the regular regions and use dyadic discretization to refine regions when necessary.

NUMERICAL EXAMPLES
In this section we provide numerical examples to highlight the main features of the approach. All computations were done in MATLAB R2017a on an Intel 3.70 GHz Xeon workstation, using GUROBI 7.0.2, the Hybrid Toolbox (Bemporad, 2004), and the MPT Toolbox 3 (Herceg et al., 2013).
Consider the uncertain linear system (6) taken from Kothare et al. (1996); Lee and Kouvaritakis (2006) (11) results in a RAS closed-loop system (6) and (14). The partition P corresponding to the optimal cost V : X f → R + , which is a robust CLF for (6) with disturbance set W, have been computed using the method in , resulting in an optimal solution composed over 160 irregular regions, shown in Fig. 1(a). Next, we have applied Algorithm I to construct a simple PWA controller defined over a rectangular partition by employing the dyadic discretization (Gao and Yan, 2010). Specifically, Algorithm I led to a stabilizing controller defined over 16 hypercubes, which are shown in Fig. 1(b). Therefore the complexity could be reduced by a factor of 10 while maintaining feasibility and stability guarantees. These findings are supported by the closed-loop profiles of state and input variables in Fig. 2 for the two vertices of the parametric uncertainty, i.e., (A 1 , B 1 ) and (A 2 , B 2 ) starting from the initial condition x = −7.3754 11.3193 that is located in the upper-left corner of the feasible space. As can be observed, the state profiles under the simple suboptimal controller are asymptotically stable.
To compare the proposed low-complexity control design procedure to other alternatives, we have post-processed the optimal CL-CROC solution using the optimal region merging (ORM) procedure of Geyer et al. (2008), and by the clipping-based approach of Kvasnica and Fikar (2012). We remark that both approaches reduce the complexity without sacrificing performance. The ORM procedure was able to simplify the solution from 160 regions to 94 while the clipping procedure resulted in 98 regions. As can be seen, the proposed PWA controller is still superior in terms of complexity (16 regions). Finally, the suboptimal simplification scheme of Grieder et al. (2003) was applied, resulting in 32 regions, double of that achieved by Algorithm I.

CONCLUSIONS
This paper presented a robust control Lyapunov function (CLF) approach to synthesize low-complexity stabilizing PWA controllers for constrained linear systems with polytopic parametric uncertainties. When a robust CLF is available, a linear programming (LP) feasibility problem was formulated with a refining splitting procedure on a given regular paratitionings (e.g. regular simplices or hypercubes) in order to synthesis a low-complexity controller that guarantees a prerequisite stability, constraints satisfaction and performance properties. It will become an