Andrea Boccia
email: a.boccia@imperial.ac.uk

Lars Grüne
email: lars.gruene@uni-bayreuth.de

Karl Worthmann
email: karl.worthmann@uni-bayreuth.de

Stability and Feasibility of State Constrained MPC without Stabilizing Terminal Constraints

Keywords: predictive control, optimal control, nonlinear control, linear systems, stability, state constraints, feasibility, optimal value functions

  L'archive ouverte pluridisciplinaire

Introduction

Model predictive control (MPC) is a controller design technique relying on the iterative solution of optimal control problems. In this paper we study stability and recursive feasibility of nonlinear MPC schemes without stabilizing terminal constraints or costs. For such schemes, it is known that stability for sufficiently large optimization horizons can be deduced from controllability assumptions or -alternatively and almost equivalently -bounds on the optimal value functions, see [START_REF] Jadbabaie | On the stability of receding horizon control with a general terminal cost[END_REF]; [START_REF] Grimm | Model predictive control: for want of a local control Lyapunov function, all is not lost[END_REF]; [START_REF] Tuna | Shorter horizons for model predictive control[END_REF]; [START_REF] Grüne | Analysis and design of unconstrained nonlinear MPC schemes for finite and infinite dimensional systems[END_REF]; [START_REF] Grüne | Analysis of unconstrained nonlinear MPC schemes with varying control horizon[END_REF]; [START_REF] Grüne | Nonlinear Model Predictive Control: Theory and Algorithms[END_REF]; [START_REF] Worthmann | Stability Analysis of unconstrained Receding Horizon Control[END_REF].

The present paper extends this body of literature by taking into account state constraints without assuming viability of the state constraint set or boundedness of the optimal value function on this set or its viability kernel. In the first part of the paper we consider general nonlinear systems and assume a local controllability assumption in a neighbourhood of the equilibrium to be stabilized. Under this condition, we first analyse the behaviour of the closed loop on level sets V -1 ∞ [0,C] of the infinite horizon optimal value function. Using a technique similar to [START_REF] Primbs | Feasibility and stability of constrained finite receding horizon control[END_REF] we obtain recursive feasibility and an adaptation of an argument from [START_REF] Grimm | Model predictive control: for want of a local control Lyapunov function, all is not lost[END_REF] yields asymptotic stability with V -1 ∞ [0,C]c o n t a i n e di nt h eb a s i no f attraction, provided the optimization horizon N is suffiently large. Moreover, quantitative estimates on the necessary length of N are given. This result is then extended to compact sets lying in the domain of V ∞ and avoiding suitable defined exceptional regions O.O v e r a l l ,t h i sp a r to ft h ep a p e rc a n be seen as a (discrete time) extension of [START_REF] Jadbabaie | On the stability of receding horizon control with a general terminal cost[END_REF] to the state constrained case and with additional quantitative estimates for N .

In the second part of the paper we specialize the results to the linear quadratic case with convex constraints. We show that in this setting any compact subset K in the interior of the viability kernel is contained in the basin of attraction for sufficiently large N and give an estimate of N in terms of the distance of K to the boundary of the viability kernel. These quantitative results rely on an estimate of the growth of the optimal value function V ∞ at the boundary of the viability kernel which we obtained adapting a technique from [START_REF] Gondhalekar | Controlled invariant feasibility -A general approach to enforcing strong feasibility in MPC applied to move-blocking[END_REF]. A particularly nice case appears when V ∞ is bounded on the viability kernel and we show that this property implies stationarity of the feasible sets in the sense of (Kerrigan, 2000, Chapter 5).

The paper is organized as follows. After describing the setting in Section 2, Section 3 contains the nonlinear asymptotic stability and feasibility results. The specialization to linear systems is presented in Section 4 and conclusions are given in Section 5.

Model Predictive Control

We consider discrete time systems governed by the system dynamics

x + = f (x, u)( 1 )
where f : R n ⇥R m ! R n is a map which determines the successor state x + in dependence of the current state x 2 R n and the control input u 2 R m .T h e state trajectory emanating from initial state x 0 and generated by the control sequence u =(u(k)) k∈N 0 is denoted by x u (k; x 0 ), k 2 N 0 . Here, the trajectory x u (•)=x u (•; x 0 )i sd e fi n e di t e r a t i v e l yb yx u (k +1;x 0 )=f (x u (k; x 0 ),u(k)) and x u (0,x 0 )=x 0 .C o n s t r a i n t sf o rt h es t a t ex and the control u are modeled by a suitably chosen subset E✓R n ⇥ R m ,i . e . ,w er e q u i r e (x, u) 2E.

(2)

Hence, for a given set E,thesetofadmissiblestatesisgivenbytheprojection of the set E on the state space R n ,i . e .

X := proj R n (E)={x 2 R n : 9 u 2 R m s.t. (x, u) 2E}. (3)
Furthermore, for a given admissible state x 2 X,t h ec o n t r o lc o n s t r a i n t sc a n be represented by U (x): ={u 2 R m :( x, u) 2E} . Using these definitions the concept of an admissible control sequence can be defined as follows.

Definition 1

(Admissible control sequence). A sequence of control values u =( u(0),u(1),...,u(N -1)) is called admissible for x 0 2 X and N 2 N [ {1} if the conditions f (x u (k; x 0 ),u(k)) 2 X and u(k) 2 U (x u (k; x 0 ))
hold for all k 2{0, 1,...,N -1}. The set of all admissible control sequences of length N 2 N [ {1} is denoted by U N (x 0 ). Let x ? 2 X be a (controlled) equilibrium, i.e. there exists u ? 2 U (x ? ) such that f (x ? ,u ? )=x ? holds. Our goal is to find a static state feedback µ : R n ! R m and a basin of attraction S✓X such that x ? is asymptotically stable for the resulting closed loop system x + = f (x, µ(x)). This means that for any initial state x 0 2Sthe closed loop trajectory x µ (k; x 0 ), k 2 N 0 , generated by

x µ (k +1;x 0 )=f (x µ (k; x 0 ),µ(x µ (k; x 0 ))), x µ (0; x 0 )=x 0 ,( 4 ) remains feasible, i.e., (x µ (k; x 0 ),µ(x µ (k; x 0 ))) 2E holds for all k 2 N 0 ,a n d satisfies the estimate |x µ (k; x 0 ) -x ? |β(|x 0 -x ? |,k), k 2 N 0 ,f o rs o m e KL-function β.
In MPC, the feedback values µ(x) are computed by solving optimal control problems. To this end, running costs `:

R n ⇥ R m ! R ≥0 satisfying `(x ? ,u ? )=0and ⌘(|x -x ? |)  `?(x):= inf u ∈U 1 (x) `(x, u)  ⌘(|x -x ? |) 8 x 2 X (5)
for two K ∞ -functions ⌘, ⌘ are defined. The corresponding cost function

J N : R n ⇥ (R m ) N ! R ≥0 and optimal value function V N : R n ! R ≥0 [{+1} are given by J N (x, u):= N -1 X k=0 `(x u (k; x),u(k)) and V N (x):= inf u ∈U N (x) J(x, u) for N 2 N [ {1}, x 2 X and u 2U N (x)withthecon v en tionV N (x)=+1 if x/ 2 X or U N (x)=;
.I np r i n c i p l e ,t h es t a b i l i z a t i o np r o b l e mc o u l db es o l v e d by solving the optimal control problem for N = 1. However, solving optimal control problems on an infinite time horizon is, in general, computationally hard. This explains why we pursue a different approach: model predictive control (MPC), also termed receding horizon control. Fixing a finite prediction horizon (or optimization horizon) N and setting x µ (0; x 0 ):=x 0 , k := 0, the MPC loop is as follows:

1. Set x = x µ (k; x 0 ), solve the optimal control problem min u ∈U N (x) J N (x, u)
and denote a respective minimizing control sequence1 by u ? 2U N (x).

2. Define the MPC feedback value by µ N (x):=u ? (0). 3. Compute x µ (k +1;x 0 )b y( 4 )w i t hµ = µ N ,s e tk := k +1 and go to 1.

This iteration yields a closed loop trajectory for the implicitly defined MPC feedback law µ N : X ! R m . However, because of the truncation of the optimization horizon stability, feasibility, and optimality may get lost, see, e.g., [START_REF] Raff | Nonlinear model predictive control of a four tank system: An experimental stability study[END_REF].

Recursive Feasibility and Asymptotic Stability

In order to guarantee that the optimal control problem in Step 1 of the MPC loop is feasible, we need to ensure U N (x) 6 = ; for x = x µ N (k; x 0 ), k 2 N 0 . This problem can be solved by incorporating suitable terminal constraints and costs in the optimal control problem to be solved in each MPC step. However, the construction of such stabilizing constraints may be challenging and their use may considerably reduce the operating range of the MPC scheme, cf. (Grüne and Pannek, 2011, Chapter 8) or [START_REF] Mayne | An apologia for stabilising terminal conditions in model predictive control[END_REF] for a detailed discussion. Hence, we want to analyse the scheme without additional terminal constraints or costs. In particular, feasibility of the MPC algorithm in each step and asymptotic stability of the resulting closed loop has to be ensured. To this end, the following local controllability condition is employed.

Assumption 1. There exists a neighbourhood N of x ? and a positive constant γ 2 R such that

V ∞ (x)  γ • `?(x), 8 x 2N\X.
Remark 2. (i) The name controllability condition stems from the fact that the inequality V ∞ (x) <Crequires the system to be controllable to x ? sufficienty fast, since otherwise (5) implies V ∞ (x)=+ 1. For the particular form of the bound γ assumed above, for instance the exponential controllability assumption w.r.t. `used in (Grüne and Pannek, 2011, Chapter 6) would be sufficient. However, note that in contrast to [START_REF] Grüne | Nonlinear Model Predictive Control: Theory and Algorithms[END_REF] here we only require the inequality to hold locally around x ? .

(ii) The condition on V ∞ implies the analogous inequalities for V N , N 2 N. These inequalities could be replaced by inequalities in which γ depends on N , thus allowing for less conservative estimates, cf. [START_REF] Worthmann | Stability Analysis of unconstrained Receding Horizon Control[END_REF]. However, in order to keep the presentation simple, in this paper we will work with the assumption on V ∞ and a single γ.

In order to formalize recursive feasibility, some notation is needed. The feasible set for a horizon length N 2 N [ {1} is defined as

F N := {x 2 X : U N (x) 6 = ;}. (6)
The set F ∞ is also called viability kernel. Furthermore, a set C✓X is said to be (controlled) forward invariant or viable if, for each x 2C,t h e r ee x i s t s u 2 U (x)s u c ht h a tf (x, u) 2C holds. Observe that every forward invariant set C✓X satisfies the inclusion C✓F ∞ and that the set of admissible states X is, in general, much larger than the viability kernel F ∞ .M e t h o d sw h i c h can be used in order to compute invariant sets can be found in [START_REF] Blanchini | Set-Theoretic Methods in Control[END_REF]. The set C is said to be recursively feasible if it is forward invariant with respect to the feedback law µ N ,t h a ti sµ N (x) 2 U (x)a n d f (x, µ N (x)) 2C for all x 2C.

Asymptotic Stability on Level Sets

Ideally we would like the basin of attraction S to coincide with F ∞ since the viability kernel is the maximal set on which an admissible feedback can be defined. However, this is, in general, not possible. The reason for this is that the closer we get to the boundary of F ∞ ,t h em o r ec o s t l y( i nt h es e n s e of our objective J N )i tm a yb e c o m et os t e e rt h es y s t e mt ox ? and if this happens then the optimization criterion may lead the MPC closed loop to stay near the boundary of F ∞ instead of approaching x ? . Hence, a central task considered in this paper is to estimate the basin of attraction S✓F ∞ and -conversely -given a set K ✓F ∞ to estimate an optimization horizon N such that K ✓S is guaranteed.

As a first step, we consider the problem to determine a recursively feasible set. To this end, for a given horizon length N 2 N [ {1} and a positive constant C define the level set

V -1 N [0,C]:={x 2 X : V N (x)  C}.
Since the running costs are supposed to satisfy (5), existence of the lower bound

M := inf x∈X \N `?(x) > 0( 7 ) is ensured. Then, for every x 2 V -1 N [0,C]\N,t h ei n e q u a l i t y V N (x)  C M • M  C M • `?(x)
holds. The parameter C can be chosen sufficiently large such that the inequality

V N (x)  γ • `?(x)  γ • sup x ∈N∩X `?(x)  C (8)
holds for all x 2N\X.S u m m a r i z i n g , a c o n s t a n t β = β(C, M, γ)o n l y depending on Assumption 1, Condition (5), and a parameter C can be found satisfying

V N (x)  β • `?(x) 8 x 2 V -1 N [0,C]a n dN\X ✓ V -1 N [0,C]. ( 9
)
This in particular shows that Assumption 1 can be extended to arbitrary level sets

V -1 N [0,C].
This fact is exploited in order to prove Theorem 3.

Theorem 3. Let Assumption 1 and Inequality (5) be satisfied. Take any positive real number C satisfying (8) and let M be defined as in (7).I n addition, choose N 0 2 N such that the inequalities

C ✓ β -1 β ◆ N 0 -1 <M and 1 -↵ N 0 > 0( 1 0 )
are satisfied with β := max{C/M, γ} and

↵ N := β 2 ⇣ β-1 β ⌘ N .
Then, for every

N ≥ N 0 and every x 2 V -1 N [0,C], we have V N (f (x, µ N (x)))  V N (x) -(1 -↵ N )`?(x). ( 11
)
In particular V N (•) is a Lyapunov function on the recursively feasible set V -1 N [0,C] which implies recursive feasibility and asymptotic stability of the MPC closed loop.

Proof. The proof is an adaptation of the arguments developed in Grüne (2012) to our setting. In particular, Variant II from Section 3.2 of this paper is used, whose idea was taken from [START_REF] Tuna | Shorter horizons for model predictive control[END_REF]. Take any

x 2 V -1 N [0,C]. Then V N (x)  C
and by hypothesis there exists an admissible control sequence u ? 2U N (x)s u c ht h a tV N (x)=J N (x, u ? ). If we define

`k := `(x u ? (k; x),u ? (k)) for k 2{0, 1,...,N -1}, then V N (x)canbewrittenasV N (x)= P p-1 k=0 `k + V N -p (x u ? (p; x)) for any p = 0, 1,...,N-1. This implies V N -p (x u ? (p; x))  C,i.e.,x u ? (p; x) 2 V -1 N -p [0,C].
Since β only depends on C, γ,a n dM (and not on the optimization horizon) from ( 9) we obtain the inequality V N -p (x u ? (p; x))  β`p.T h e r e f o r e

V N (x)= N -1 X k=0 `k  p-1 X k=0 `k + β`p. ( 12
) If f (x, µ N (x)) is feasible, i.e., if f (x, µ N (x)) 2F N holds or, equivalently, U N (f (x, µ N (x))) 6 = ;,w eo b t a i nt h ei n e q u a l i t y V N (f (x, µ N (x)))  N -2 X k=1 `k + V 2 (x u ? (N -1; x)) = V N (x) -`0 -`N-1 + V 2 (x u ? (N -1; x)). ( 13
)
In general, however, without additional hypotheses, we cannot guarantee feasibility of f (x, µ N (x)). Still, by setting V 2 (x u? (N -1; x)) = +1 in case of infeasibility we can extend (13) to this case. We keep this in mind and show x u ? (N -1; x) 2N\X and, thus,

V 2 (x u ? (N -1; x)) < 1.I n d e e d ,b y( 1 2 ) , P N -1 k=p+1 `k  (β -1)`p holds which implies N -1 X k=p `k ≥ ✓ β β -1 ◆ N -1 X k=p+1 `k ≥ ✓ β β -1 ◆ 2 N -1 X k=p+2 `k ≥ ... ≥ ✓ β β -1 ◆ N -p-1 `N-1 for p 2{0, 1,...,N -1}. When p =0,sincex 2 V -1 N [0,C], we obtain C ≥ V N (x) ≥ ✓ β β -1 ◆ N -1 `N-1 , (14)
β • `?(x) ≥ V N (x) ≥ ✓ β β -1 ◆ N -1 `N-1 . ( 15
)
According to our choice of N Inequality ( 14) implies `?(x u ? (N -1; x))  `N-1 <M and, in view of x u? (N -1; x) 2 X and ( 7), x u ? (N -1; x) 2N\X where our local Assumption 1 can be invoked. Consequently feasibility and

V 2 (x u ? (N -1; x))  γ`N -1  β`N -1 hold.
A further appeal to ( 13) and ( 15) now gives

V N (f (x, µ N (x)))  V N (x) -`0 +(β -1)`N -1  V N (x) -(1 -↵ N )`?(x),
i.e. Inequality (11) and recursive feasibility of the level set V -1 N [0,C]. From this and the bounds on V N induced by ( 5) and ( 9), the Lyapunov function property of V N and asymptotic stability follow by standard arguments, see, e.g. (Grüne, 2009, Section 5).

and β ⇠ (C/M) as C !1 . 2
We claim that this bound can be improved under additional hypotheses. Let e N be a neighbourhood of the origin such that e N\X is controlled forward invariant. 3 Define f M := inf x∈X \ e N `?(x) and assume that the horizon N only satisfies the first inequality in (10), now with respect to the constant f M . Then feasibility of the MPC closed loop trajectory is ensured -as proved in Theorem 3-since x u? (N -1; x) 2 Ñ\X which is forward invariant. Since feasibility is now ensured, the estimates from (Grüne et al., 2010, Section 6) can be applied to get the improved value

↵ N = (β -1) N β N -1 -(β -1) N -1
which is positive when N>2+ ln(β-1) ln β-ln(β-1) . Hence, this bound for the optimization horizon N behaves asymptotically as (C/M)lnC for C ! +1.

Often more restrictive controllability conditions are assumed in order to ensure asymptotic stability, see, e.g. [START_REF] Tuna | Shorter horizons for model predictive control[END_REF] or [START_REF] Grüne | NMPC without terminal constraints[END_REF] where our local Assumption 1 was assumed on a (controlled) invariant subset of the viability kernel. We like to point out that no 'viability' conditions -such as forward invariance -nor regularity hypotheses on the dynamics f (•, •)a n d the control constraint set U (•)a r ei m po s e do nX in this section.

2 We use the notation f (x) ⇠ g(x) as x !1to indicate that the functions f (•) and g(•) have asymptotically the same behaviour, i.e., that lim x→∞ f (x) g(x) = 1 holds.

3 Such a neighborhood e N exists under the assumptions of Theorem 3 as one may define e N as the interior of a sublevel set of V N .

Global stability

Theorem 3 implies that for each compact set K ✓ X satisfying C := sup V ∞ (K) < 1 the MPC controller yields asymptotic stability for N ≥ N 0 with a basin of attraction S◆V -1 N [0,C] ◆ K.I no r d e rt oa n a l y s ew h i c h kind of sets K have this property, we consider the set

V -1 ∞ [0, +1)={x 2 X : V ∞ (x) < +1} and the decreasing family of sets V -1 ∞ [n, +1) ◆ V -1 ∞ [n + 1, +1
)w i t hv a r y i n gn 2 N.F o rt h e s es e t sw ec o n s i d e rt h es e tv a l u e dl i m i t [START_REF] Aubin | Set-valued analysis[END_REF], Section 1.1). In many cases of interest the set O has zero measure. If, for example, the value function is uniformly bounded or continuous on V -1 ∞ [0, +1), then the set V -1 ∞ [0, +1)\O is empty. Later on, conditions ensuring one of these two stipulations are investigated for linear systems, see Section 4.

O := lim n→∞ V -1 ∞ [n, +1)= \ n∈N V -1 ∞ [n, +1), cf.
The relevance of the set O for MPC stems from the following claim: take any compact set

K ⇢ V -1 ∞ [0, +1) \O.
T h e n w e c l a i m t h a t t h e r e e x i s t s

C 2 R >0 such that V -1 ∞ [0,C] ◆ K. Suppose to the contrary, it would exist a convergent sequence (x n ) n∈N 0 ⇢ K such that x n ! x 2 K and V ∞ (x n ) >n.T h u sx n 2 V -1 ∞ [n, +1
)a n dx 2O. This is not possible since x 2 K.

The following theorem shows the consequences of this claim for the MPC controller. Its proof is an immediate consequence of the facts stated so far in this section.

Theorem 5. Let Assumption 1 and Condition (5) be satisfied and K ⇢ V -1 ∞ [0, +1) \O be a compact set. Then there exists N K 2 N such that for each N ≥ N K the MPC closed loop is recursively feasible and asymptotically stable with basin of attraction S◆K.

Theorem 5 provides a nonlinear extension of the linear results shown in [START_REF] Primbs | Feasibility and stability of constrained finite receding horizon control[END_REF]. It tells us that, for a sufficiently large horizon, the MPC algorithm provides a recursively feasible and asymptotically stable closed loop on every compact set in which the value function is finite, as long as we avoid 'small' areas of bad behaviour (close to O). Note that Theorem 5 is also applicable if state constraints are present and thus extends [START_REF] Jadbabaie | On the stability of receding horizon control with a general terminal cost[END_REF]. The set O can comprise points x satisfying V ∞ (x)=+ 1,b u tm a ya l s o contain points x which are controllable to x ? in finite time with V ∞ (x) < 1. The latter situation is shown in the following example.

Example 6. Consider the one dimensional system

x + = ux 2 +(1-u)(x-3 2 ) with X =[ -1 2 , 2], U = {1}[{0} and equilibrium x ? =0 .
Here, for a cost function, say `(x, u):=|x|, the set V -1 ∞ [0, +1) is equal to X. Nevertheless, the set O is nonempty since O = {1} holds and V ∞ (1) is finite, cf. Figure 1.

Linear Systems

This section is dedicated to linear constrained systems

x + = Ax + Bu,( x, u) 2E.( L )
For this class of systems we will be able to provide more precise estimates for the constants involved in the general nonlinear results of the last section. Moreover, we will be able to characterize the "exceptional set" O in more detail and investigate the relation between the stabilizable set S and the viability kernel F ∞ .

Like for nonlinear systems, we will base our analysis on the controllability Assumption 1. It should be noted that for linear systems an alternative methodology for ensuring stability and recursive feasibility of the MPC closed loop is available, cf. [START_REF] Primbs | Feasibility and stability of constrained finite receding horizon control[END_REF]. However, this approach requires precise knowledge on the growth of the value function and can, thus, be seldomly applied if constraints are present. In contrast to that, techniques based on Assumption 1 can be applied since this condition is significantly easier to verify. Below, we prove that Assumption 1 can always be ensured for a large class of linear constrained systems. To this end, we make the folowing two assumptions.

Assumption 2. The constraint set E is convex, compact, and contains the origin (0, 0) in its interior.

Assumption 3. The linear system described by the pair (A, B) is stabilizable.

Characterization of the Viability Kernel for Linear Systems

In the next two propositions we characterize the viability kernel F ∞ in order to gain insight into the structure of the set S on which the MPC feedback law µ N stabilizes the system. Proposition 7. Consider the nonlinear system (1) and the viability kernel F ∞ defined by (6). Then, the following claims hold: Proof. Without loss of generality let F ∞ 6 = ;.W es h o wt h a tF ∞ is bounded and closed in order to prove part (a) of the proposition. Since F ∞ ✓ X, boundedness follows directly from the boundedness of E. Hence, it remains to show F ∞ = cl{F ∞ }.T a k ea n yx 2 cl{F ∞ }.T h e ni np a r t i c u l a rx 2 X. By definition of closure we can find points x i 2F ∞ such that x i ! x and by definition of F ∞ we can find admissible controls u i such that f (x i ,u i ) 2F ∞ holds for every i 2 N. Now each pair (x i ,u i )belongstothecompactsetE so that extracting a subsequence if necessary (x i ,u i ) ! (x, u) 2E.B u tt h e nb y continuity f (x, u) 2 cl{F ∞ }.T h i sp r o v e st h a tf o re v e r yx 2 cl{F ∞ },t h e r e exists u 2 U (x)s u c ht h a tf (x, u) 2 cl{F ∞ },n a m e l y ,cl{F ∞ } is a forward invariant set. Therefore cl{F ∞ }✓F ∞ which completes part (a) of the proof since the reverse inclusion is obvious.

Part (b) is a straightforward application of the respective definitions. Take x 1 ,x 2 2F ∞ and a convex combination λx 1 +(1-λ)x 2 , λ 2 [0, 1], of them. By definition there exist u 1 2U ∞ (x 1 )a n du 2 2U ∞ (x 2 )s u c ht h a t (x u 1 (k; x 1 ),u 1 (k)) 2E and (x u 2 (k; x 2 ),u 2 (k)) 2E for every k 2 N 0 .B e c a u s e of the linearity of the dynamics

λx u 1 (k; x 1 )+(1-λ)x u 2 (k; x 2 )=x λu 1 +(1-λ)u 2 (k; λx 1 +(1-λ)x 2 )
holds and the result is a consequence of the convexity assumption on E.

Proposition 7 tells us that, in our linear setting under Assumption 2, the viability kernel F ∞ is a convex and compact set. We characterize it further.

Proposition 8. Consider the viability kernel F ∞ given by (6) and linear dynamic as in (L). Let Assumption 2 be satisfied. Then, the following assertions hold.

(a) The set λF ∞ is forward invariant for any λ 2 [0, 1]. More precisely take any λ 2 [0, 1] and x 2 λF ∞ , there exists an admissible control sequence u =(u(k)) k∈N 2U ∞ (x) such that

(x u (k; x),u(k)) 2 λE✓E and x u (k; x) 2 λF ∞ 8 k 2 N 0 .
(b) If, in addition, Assumption 3 holds, the origin is contained in the interior of the viability kernel, i.e., 0 2 int F ∞ .

Proof. Fix any λ 2 (0, 1]. If λ =0t h er e s u l ti so b v i o u sb e i n g0a ne q u ilibrium. Given any x 2 λF ∞ we have that x/λ 2F ∞ and thus there is

u λ 2U ∞ (x/λ)s u c ht h a t (x u λ (k; x/λ),u λ (k)) 2E and x u λ (k; x/λ) 2F ∞ 8 k 2 N 0 .
Define the control sequence u := λu λ ,w eclaimthatu 2U ∞ (x). By linearity λx u λ (k; x/λ)=x u (k; x)h o l d sa n dp a r t( a )f o l l o w su po nm u l t i p l i c a t i o nb yλ. Part (b). Since the pair (A, B)i ss t a b i l i z a b l e ,af e e d b a c kl a wF 2 R m×n exists such that %(A + BF) < 1h o l d s ,i . e . a l le i g e n v a l u e so ft h ec l o s e dl o o p given by A+BF are contained in the interior of the unit circle, cf. [START_REF] Hinrichsen | Mathematical Systems Theory I[END_REF]. As a consequence, constants C ≥ 1andσ 2 (0, 1) exist such that, for each state

x 0 2 R n ,t h ec l o s e dl o o ps o l u t i o n( x F (k; x 0 )) k∈N 0 generated by x F (k +1;x 0 )=(A + BF)x F (k; x 0 ), x F (0; x 0 )=x 0 ,s a t i s fi e s |x F (k; x 0 )|k(A + BF) k k|x 0 |Cσ k |x 0 |8 k 2 N 0 . ( 16
)
This shows in particular that |(x

F (k; x 0 ),Fx F (k; x 0 ))|Cσ k (kF k +1)|x 0 | holds.
Recall that (0, 0) 2 int E by hypothesis. Therefore existence of an "ball "B ✓Eis ensured. Hence, (x F (k; x 0 ),Fx F (k; x 0 )), k 2 N 0 , is admissible, which implies x 0 2F ∞ for arbitrary x 0 2 δB with C(kF k +1)δ  ".T h i s completes the proof of the proposition.

According to Propositions 7 and 8, when Assumptions 2 and 3 are in force, the viability kernel F ∞ is a compact and convex set containing the origin in its interior and, for any λ 2 [0, 1], the shrunk set λF ∞ is controlled forward invariant, i.e. for any x 2 λF ∞ there exists a feasible state trajectory remaining in λF ∞ for any time. In addition, by the fact that F ∞ is the maximal forward invariant set, we have information about the behaviour of feasible trajectories on @F ∞ .

Proposition 9. Consider the discrete time system (1) and assume that the dynamics f (•) are continuous. If x 2 @F ∞ , every feasible trajectory will remain on the boundary unless it touches @X.

Proof. The result derives from the fact that F ∞ is the maximal forward invariant set. If there were a control u 2 U (x)f o rx 2 @F ∞ \ @X such that f (x, u) 2 int F ∞ ,t h e nb yc o n t i n u i t yt h i sw o u l db et r u eo nan e i g h b o u r h o o d of x making F ∞ larger. For details we refer to [START_REF] Quincampoix | Differential inclusions and target problems[END_REF].

Linear Quadratic MPC

The following Proposition provides a uniform bound for V ∞ (•)o nt h e interior of the viability kernel. This is a key ingredient in order to characterize the operating range of the MPC feedback law µ N .I np a r t i c u l a r ,t h es e tO constructed in Subsection 3.2, if nonempty, can contain only points of the boundary of the viability kernel.

Proposition 10. Let Assumptions 2 and 3 be satisfied and let quadratic running costs `: R n ⇥ R m ! R ≥0 be given by

`(x, u):=(x T u T ) ✓ QN N T R ◆✓ x u ◆ ( 17
)
with symmetric matrices Q 2 R n×n and R 2 R m×m . Then, for each λ 2 [0, 1) the optimal value function is uniformly bounded from above on λF ∞ , i.e., a constant M = M (λ) 2 R ≥0 exists such that V ∞ (x)  M holds for all x 2 λF ∞ .

Proof. We borrow techniques from (Gondhalekar et al., 2009, Lemma 12). Fix any λ 2 (0, 1) and choose x 2 λF ∞ (the result is obvious for λ = 0). As we have seen in Proposition 8(a) there exists u I 2U ∞ (x)s u c ht h a t for some C ≥ 1a n dσ 2 (0, 1) which, in particular, implies x F (k; x) ! 0a s k !1 . However, the pair (x F ,Fx F )m a yn o ts a t i s f yt h ec o n s t r a i n t s . T h e idea is to take a convex combination of these two trajectories and exploit linearity and convexity of the data to show that such a combination defines a feasible trajectory which converges to 0. When a sufficiently small neighbourhood of the origin is reached, the constraints can be neglected and the feedback law F is applied. This procedure yields a uniform bound for V ∞ (•). Analytic arguments follow.

Using the control sequence u F given by u F (k): =Fx F (k; x), k 2 N 0 ,w e have

|(x F (k; x),u F (k))|Cσ k (kF k +1)|x|Lλσ k d min 8 k 2 N 0 (18)
where

L := C(kF k +1)d max d -1 min with d min := inf x ∈ @X |x| > 0a n dd max := sup x ∈ X |x| < 1. Hence, (x F (k; x),u F (k)) 2 LλE holds for all k 2 N 0 . If λL  1, u F 2U ∞ (x)s ot h a tx F (k; x)i sf e a s i b l ef o re v e r yk 2 N 0 and a uniform bound for V ∞ (•) is given by sup x ∈ X J ∞ (x, u F )  ↵ for some ↵ 2 R ≥0 .
Otherwise, for λL > 1, the control sequence u is defined as u(k):

= µu I (k)+(1-µ)u F (k), k 2 N 0 ,w i t hµ := λL-1
λ(L-1) 2 (0, 1). Then, by linearity of the dynamics

x u (k; x)=µx u I (k; x)+(1-µ)x u F (k; x). Our choice of µ implies µλ +(1-µ)Lλ  1a n d ,t h u s ,( x u (k; x),u(k)) 2E
for all k 2 N 0 which is, in turn, equivalent to admissibility of u. Now since x F (k; x) ! 0ask !1,ifk is taken large enough, the pair (x u (k; x),u(k)) 2 "λE for some " 2 (µ, 1). More precisely, (x u (k; x),u(k)) 2 "λE holds if (recall Estimate (18))

µλ

+(1-µ)Lλσ k  "λ.
Call k * the first integer such that this condition is satisfied. If for example

" := µ + 1-µ L ,t h e nk * is such that σ k *  1 L 2 and so it is the only integer satisfying log σ ( 1 L 2 )  k * < log σ ( 1 L 2 )+1
. The point x u (k * ; x) 2 λ"F ∞ and the procedure followed so far can be iterated, say m times, until x u (mk * ; x) 2 λ" m F ∞ and λ" m L  1. We keep calling u the admissible sequence that transfers the point x 2 λF ∞ to the point x u (mk * ; x) 2 λ" m F ∞ . As soon as the condition λ" m L  1i ss a t i s fi e d , we switch to the feedback F which ensures that the system feasibly converges to the origin with uniformly bounded costs for each state contained in λ" m F ∞ .S i n c eX and the constraint set are bounded, the prior caused costs are also uniformly bounded since the number of steps needed in order to reach this set is bounded by mk * . Note that in particular

V ∞ (x)  J mk * (x, u)+J ∞ (x u (mk * ; x),u F ). (19)
This, in addition to the convergence to the origin already shown in (Gondhalekar et al., 2009, Lemma 12), provides bounds on the number of steps required in order to reach an arbitrarily small neighborhood of the originindependent of the chosen initial state x 2 λF ∞ .

We are now ready to show that for linear quadratic systems, in Theorem 5, Assumption 1 and Condition (5) can be replaced by the easily checkable Assumptions 2 and 3. Moreover, the set V -1 ∞ [0, +1) \O,s e eT h e o r e m5 , can be replaced by the interior int F ∞ of the viability kernel.

Theorem 11. Let Assumptions 2 and 3 hold. Furthermore, let the dynamics be given by (L) and the running costs by (17) such that the matrix comprised of Q, R, and N is positive definite. Let K ✓ int F ∞ be a compact set. Then, a prediction horizon N K 2 N exists such that, for each N ≥ N K , the MPC feedback law µ N asymptotically stabilizes the closed loop at x ? =0on a recursively feasible set S◆K.

Proof. Since the running costs `are positive definite there exist constants c, c such that c|x|`?(x)  c|x|,i.e.Condition(5)holds. F urthermore,sincethe origin is contained in the interior of the constraint set E and the pair (A, B) is supposed to be stabilizable, a neighborhood N of the origin exists such that an LQR can be applied neglecting the constraints. Then, the solution P of the algebraic Riccati equation fulfills V ∞ (x 0 )=x T 0 Px 0  c|x 0 | 2  ⇢`?(x 0 ) with ⇢ := cc -1 on N where c is the maximal eigenvalue of P ,i m p l y i n g Assumption 1.

Moreover, since K is compact and contained in int F ∞ ,w ec a nc o n c l u d e that K ✓ int λF ∞ for some λ 2 (0, 1). Hence, by Proposition 10, V ∞ is bounded on a neighborhood of K and consequently K ✓ V -1 ∞ [0, +1) \O. Hence, all assumptions of Theorem 5 are satisfied and the assertion follows from this theorem.

Next, under the assumptions of Theorem 11 we are going to investigate the dependence of the horizon N K on the distance of the compact set K from the boundary of the viability kernel @F ∞ . To this end, denoting the control u in (19) by u x ,w eo b t a i n

sup x ∈ λF∞ V ∞ (x)  sup x ∈ λF∞ J mk * (x, u x )+sup x∈X J ∞ (x, u F )  βmk * + ↵,
for constants ↵, β > 0o n l yd e p e n d i n go nt h ed a t ao ft h ep r o b l e m( m =0 holds for λL  1). We emphasise that m depends on λ, indeed m is the first integer which satisfies " m  1 λL .W ea l s oo b s e r v e dt h a tk * can be chosen to be the unique integer which satisfies log σ ( 1

L 2 )  k * < log σ ( 1 L 2 )+1. Consequently defining β := βk * we obtain sup x ∈ λF∞ V ∞ (x)  βm+↵.F o l l o w i n go u rc h o i c e " = µ + 1-µ
L (where we recall µ = λL-1 λ(L-1) )w eh a v et h a t" =1-1-λ λL .T h i s yields an estimate for the growth of m.M o r ep r e c i s e l ym ⇠ L ln L 1-λ as λ ! 1. When we are in a sufficiently small neighbourhood of the origin, say δB, constraints can be neglected and V ∞ (x)=x T Px where P is the solution of the algebraic Riccati equation. This in turn gives a bound for V ∞ (•)o ft h e type V ∞ (x)  ⇢|x| 2 for all x 2 δB. Away from the origin, when constraints are present this bound is no longer satisfied. We have shown, though, that it is possible to find constants β and ↵ := max{⇢, ↵/δ} such that

V ∞ (x)  βm x +↵|x| 2
with m x ! +1 when x ! @F ∞ . Note that the upper bound diverges to +1 as x ! @F ∞ .

The discussion above can be summarised in the following corollaries.

Corollary 12. Let the assumptions of Proposition 10 be satisfied. Then there exist constants ↵>0 and β>0 depending only on the data of the problem such that for any

x 2 int F ∞ V ∞ (x)  βm x +↵|x| 2
with m x ! +1 when x ! @F ∞ . Asymptotically, m x behaves like4 m x ⇠ !L ln L dist(x;@F∞) as x ! @F ∞ , where ! 2 [inf x∈@F∞ |x|, sup x∈F∞ |x| ] and L is from the proof of Proposition 10. Moreover, m x =0in a sufficiently small neighbourhood of the origin.

Proof. We only have to verify the assertion m x ⇠ !L ln L dist(x;@F∞) for some ! 2 [f -,f + ]w h e r ef -:= inf x∈@F∞ |x| and f + := sup x∈F∞ |x|.T ot h i se n d ,w e introduce a well known construct from convex analysis to compare λ and dist(x; @F ∞ )w h e nx 2 λ@F ∞ ,

g(x):=inf{γ>0:γ -1 x 2F ∞ } .
This function is Lipschitz with Lipschitz constant 1/f -.

For every x 2 λ@F ∞ , λ 2 (0, 1), we define ⇡(x)t ob eap r o j e c t i o no f x onto @F ∞ .T h e n dist(x; @F ∞ )=|x -⇡(x)|.M o r e o v e r g(x)=λ and g(⇡(x)) = 1. Therefore

1 -λ = g(⇡(x)) -g(x)  1 f -|x -⇡(x)| = 1 f -dist(x; @F ∞ ) .
On the other hand

dist(x; @F ∞ ) | x λ -x|f + 1 -λ λ .
Using this estimate we arrive at the following estimate for the optimization horizon needed in order to ensure K ✓S.

Corollary 13. Given a compact set K ✓ int F ∞ there exists a constant D only depending on the data of the problem such that

sup x∈K V ∞ (x)  D dist(K; @F ∞ ) . ( 20
)
Moreover, whenever N ≥ N K , where N K is the smallest integer satisfying

N K > 2+ ln(β -1) ln β -ln(β -1) (21)
for β =m a x {D • (M • dist(K; @F ∞ )) -1 ,γ }, then the MPC closed loop is asymptotically stable with recursively feasible basin of attraction S◆K. Asymptotically, N K behaves like

D M • dist(K; @F ∞ ) ln ✓ D dist(K; @F ∞ ) ◆ .
Proof. The bound in (20) follows directly from Corollary 12 choosing a constant D sufficiently large. Theorem 3 and Remark 4 then yield the inequalities for N K .

The following example illustrates that the required prediction horizon grows rapidly for initial values approaching the boundary of the viability kernel.

Example 14. We consider the controllable and, thus, in particular stabilizable linear system given by

x + = ✓ 11 02 ◆✓ x 1 x 2 ◆ + ✓ 10 01 ◆✓ u 1 u 2 ◆ with constraints X := [-100, 100] ⇥ [-1, 1] and U := ( u 2 R 2 : ✓ 1 -11 -1 11 -1 -1 ◆ T ✓ u 1 u 2 ◆  1111 T )
.

The quadratic stage costs are given by

`(x, u)= ✓ x 1 x 2 ◆ T ✓ 100 0 01 ◆✓ x 1 x 2 ◆ + ✓ u 1 u 2 ◆ T ✓ 10 01 0 0 ◆✓ u 1 u 2 ◆ .
Then, the minimal stabilizing horizon b N := min{N 2 N : x µ N (k; x 0 ) ! 0 for k ! 1} w.r.t. the origin (controlled equilibrium for u ? =( 00 ) T ) in dependence of given initial values are shown in the following table.5

x 1 0.5 0.5 0.5 0.5 0.5 0.5 x 2 0.9 0.99 0.999 0.9999 0.99999 0.999999 b N 6 6 7 10 13 16 4.3. Boundedness of V ∞ on the Viability Kernel F ∞ In the preceeding Subsection 4.2 we considered the stabilization task for arbitrary compact sets contained in the interior of the viability kernel F ∞ . However, it follows from Theorem 3 that for each sufficiently large N MPC will yield asymptotic stability with the basin of attraction S containing the whole viability kernel F ∞ if sup V ∞ (F ∞ )i sfi n i t e . I nt h i sfi n a ls e c t i o nw e show that this property implies stationarity of the feasible sets F N .

We say that the feasible sets F N become stationary,ifthereexistsN 0 2 N with F N = F N 0 for all N ≥ N 0 .I n( K e r r i g a n ,2 0 0 0 ,T h e o r e m5 . 3 )( s e ea l s o (Grüne, 2012, Section 5.1)), it was shown that stationarity of the feasible sets is sufficient for recursive feasibility of F ∞ for all optimization horizons N ≥ N 0 +1. In the following theorem we show that it is also necessary for V ∞ being bounded on the viability kernel F ∞ .

Theorem 15. Consider the linear system (L) with positive definite quadratic running costs `and let Assumptions 2 and 3 be satisfied. Then, if V ∞ (x)  c holds for some c 2 R >0 and all x 2F ∞ , the feasible sets F N become stationary for some N 0 2 N.

Proof. By definition F N ◆F ∞ . An adaptation of the proof of Proposition 7(b) shows that F N is convex and it is an easy excercise to prove that V N is convex. We prove the result by showing the existence of N 0 with F N 0 = F ∞ , which implies stationarity. We proceed by contradiction, i.e., we assume that F N ) F ∞ holds for every N 2 N.I fN 2 N is chosen sufficiently large, then for every x 0 2F N \F ∞ we have that V N (x 0 ) >c+ 2. Indeed, any trajectory originating at x 0 cannot reach F ∞ and in particular remains outside a ball around the origin. Fix a natural number N 2 N with such property and observe that by convexity of the set F N we may chose x 2F N \F ∞ and y 2 @F ∞ such that λy +( 1-λ)x 2F N \F ∞ for all λ 2 (0, 1). This implies the inequalities V N (λy +(1-λ)x) >c+2 for all λ 2 (0, 1) and V N (y)  V ∞ (y)  c.T h e nf o ra l lλ 2 (0, 1), convexity of V N yields c +2<V N (λy +(1-λ)x)  λV N (y)+(1-λ)V N (x)  λc +(1-λ)V N (x). Since every x 2 X =[ -1, 1] is a controlled equilibrium (u = -x) F ∞ = X and, thus, F N = F ∞ actually holds for every N 2 N. Yet, for any positive definite quadratic cost V ∞ fails to be bounded on @F ∞ and grows unboundedly for x ! @F ∞ , as the following computation shows. If x 0 =1the only admissible control sequence u is u ⌘-1 for every time instant. Indeed x u (k;1) = 1 for every k 2 N. Therefore as soon as we define a cost say `(x, u)=x 2 we have that V ∞ (1) = +1. The point x 0 = -1 has a similar behaviour. Every other initial point x 0 2 (-1, 1) = X \{1, -1}, different from 1 and -1, can be controlled to zero in finite time by u x 0 (k)=-sign(x ux 0 (k; x 0 )) min{2|x ux 0 (k; x 0 )|, 1}.

However, the closer x 0 to 1 or -1, the longer it will take before an interval of the form [-δ, δ] for δ 2 (0, 1) can be reached. Hence, as x 0 ! 1 or x 0 !-1, the value function V ∞ (x 0 ) tends to +1.

Conclusions

We investigated recursive feasibility and asymptotic stability for nonlinear MPC schemes with state and control constraints without imposing stabilizing terminal constraints or costs. Assuming a local controllability condition around the equilibrium to be stabilized, we have shown that the system can be asymptotically stabilized and that any level set V -1 [0,C]o ft h ei n fi n i t e horizon optimal value function V ∞ is contained in the domain of attraction for sufficiently large optimization horizon N .M o r e o v e r , w e e s t a b l i s h e d a quantitative relation between the level C and the proposed estimate of the horizon N .

For linear systems, this relation was made more precise by estimating the growth of V ∞ at the boundary of the viability kernel. Particularly, we have shown that any compact subset of the interior of the viability kernel F ∞ is contained in the basin of attraction S for sufficiently large N .O u ra n a l y s i s moreover shows that the whole viability kernel F ∞ is contained in S if V ∞ is bounded on F ∞ .T h i sp r o p e r t y ,i nt u r n ,i m p l i e ss t a t i o n a r i t yo ft h ef e a s i b l e sets F N .

Remark 4 .

 4 The optimization horizon N 0 guaranteeing stability in Theorem 3 grows like 2(C/M)lnC as C ! +1. Indeed the horizon N must satisfy N> 2lnβ ln βln(β -1)

Figure 1 :

 1 Figure 1: Illustration of the pointwise bounded value function V ∞ (•) for Example 6.

  (a) If E is compact and the dynamics f (•, •) are continuous, F ∞ is compact. (b) If E is convex and the dynamics f (•, •) are linear, F ∞ is a convex set.

(

  x u I (k; x),u I (k)) 2 λE and x u I (k; x) 2 λF ∞ 8 k 2 N 0 , i.e. a feasible state trajectory which remains in the interior of F ∞ .I na d d ition, since (A, B)i ss t a b i l i z a b l e ,af e e d b a c kl a wF 2 R m×n exists such that the corresponding closed loop x + F =(A + BF)x F satisfies Inequality (16), i.e. |x F (k; x)|k(A + BF) k k|x|Cσ k |x|8 k 2 N 0

For

  λ sufficiently close to 1 we obtain the desired contradiction. (Note thatV N (x)i sbo u n d e d ) .The converse is not true in general as shown in the following Example 16.Example 16. Consider the discrete time system in R given byx + =2x + u with constraint set E := [-1, 1] ⇥ [-1, 1].

Whenever U N (x) 6 = ;, existence of a minimizer u ?

2U N (x) satisfying J N (x, u ? )= V N (x)is assumed in order to avoid technical difficulties.

Given any set Ω ⇢ R n and x 2 R n , dist(x; Ω) denotes the Euclidean distance of the point x from the set Ω. Given a second set K ⇢ R n , dist(K;Ω) := min x∈K dist(x;Ω).

Note that the point (0.5, 1) T is not contained in the viability kernel F ∞ . b N was computed with the Matlab-routine mpc ExampleBGW.m which is available for download at http://num.math.uni-bayreuth.de/de/team/Gruene Lars/publications/boccia et al feasibility 2013.

Acknowledgment

This work was supported by the European Union under the 7th Framework Programme FP7-PEOPLE-2010-ITN Grant agreement number 264735-SADCO (A. Boccia and L. Grüne) and by the DFG Grant GR1569/12-2 (K. Worthmann). The research for this pap er was carried out while the first author visited the University of Bayreuth during his SADCO secondment.