Distributed model predictive control—Recursive feasibility under inexact dual optimization

doi:10.1016/j.automatica.2018.12.037

Automatica

Volume 102, April 2019, Pages 1-9

https://doi.org/10.1016/j.automatica.2018.12.037 Get rights and content

Abstract

We propose a novel model predictive control (MPC) formulation, that ensures recursive feasibility, stability and performance under inexact dual optimization. Dual optimization algorithms offer a scalable solution and can thus be applied to large distributed systems. Due to constraints on communication or limited computational power, most real-time applications of MPC have to deal with inexact minimization. We propose a modified optimization problem inspired by robust MPC which offers theoretical guarantees despite inexact dual minimization. The approach is not tied to any particular optimization algorithm, but assumes that the feasible optimization problem can be solved with a bounded suboptimality and constraint violation. In combination with a distributed dual gradient method, we obtain a priori upper bounds on the number of required online iterations. The design and practicality of this method are demonstrated with a benchmark numerical example.

Keywords

Predictive control

Control of constrained systems

Large scale systems

Distributed dual optimization

1. Introduction

Model predictive control (MPC) is a well-established control method, that can be used to control complex dynamical systems and guarantee constraint satisfaction (Rawlings & Mayne, 2009). One of the main limitations to control a system with MPC comes from computational issues, since in each time step an optimization problem has to be solved. In order to apply MPC to large-scale systems, we have to consider distributed approaches, which fall in the domain of distributed MPC (DMPC) (Maestre et al., 2014, Müller and Allgöwer, 2017). If we want to facilitate DMPC applications to fast (physically) interconnected networks, we typically need scalable distributed optimization algorithms with bounds on the number of required iterations.

Dual optimization algorithms such as the alternating direction method of multipliers (ADMM), dual gradient methods and proximal decomposition have been studied to solve DMPC optimization problems online (Kögel and Findeisen, 2012, Necoara and Nedelcu, 2015, Necoara and Suykens, 2008). While these algorithms enable a fully distributed implementation and asymptotically converge to the optimal central solution, real-time requirements lead to early termination and an inexact solution. Contrary to primal decomposition methods (Stewart, Venkat, Rawlings, Wright, & Pannocchia, 2010), these inexact solutions based on dual optimization do not necessarily satisfy the posed constraints (dynamic, state and input constraints) in the MPC optimization problem. This necessitates additional modifications to ensure recursive feasibility and stability of the resulting MPC scheme.

Related work

In Giselsson and Rantzer (2014) DMPC without terminal constraints is investigated and a sufficient stopping condition for the distributed iteration based on a candidate solution is presented. For this approach no prior bound on the number of required iterations can be given.

In Kögel and Findeisen (2014) a primal optimization algorithm with constraint violations in the dynamic equality constraints is investigated. Recursive feasibility is ensured with an appropriate state and input constraint tightening.

In Necoara, Ferranti, and Keviczky (2015) and Rubagotti, Patrinos, and Bemporad (2014) constraint violations in the inequality constraints due to inexact dual optimization are addressed with an appropriate (constant or adaptive) constraint tightening. Constraint violations in the posed dynamic equality constraints are avoided by using a condensed formulation (Necoara et al., 2015) or projecting the intermediate solution to the set of dynamically feasible trajectories (Rubagotti et al., 2014). Both approaches are, however, unsuited for distributed large-scale systems.

In Ferranti and Keviczky (2015) constraint violations in inequality constraints and dynamic equality constraints are considered by using an appropriate constraint tightening. Recursive feasibility is ensured by choosing the tolerance and thus the constraint tightening adaptively. As a consequence, the number of iterations can vary and global communication is required to enable this adaptation. In Doan, Keviczky, and Schutter (2011) a similar constraint tightening is used for a distributed hierarchical MPC scheme.

Contribution

We propose a new framework to ensure recursive feasibility of inexact DMPC resulting from finite dual iterations. This consists of a constant constraint tightening and a stabilizing controller, motivated by robust MPC (Chisci, Rossiter, & Zappa, 2001). To avoid an overly conservative constraint tightening, we propose a modified optimization problem and employ a different candidate solution, that explicitly takes the inexactness into account. This presents a general procedure which is applicable to different MPC setups. By combining this framework with a dual distributed gradient algorithm, we obtain an a priori upper bound for the number of dual iterations to ensure recursive feasibility. Compared to Ferranti and Keviczky (2015), Giselsson and Rantzer (2014) and Necoara et al. (2015), no adaptive constraint tightening is required. Furthermore, compared to Doan et al. (2011), Ferranti and Keviczky (2015), Kögel and Findeisen (2014) and Rubagotti et al. (2014), no centralized operations are necessary, thus allowing a fully distributed implementation for large-scale systems.

Outline

The remainder of this paper is structured as follows: Section 2 presents the nominal distributed MPC formulation and explains the problem inherent in inexact dual optimization. Section 3 presents the modified formulation, derives closed-loop properties under inexact minimization and presents a corresponding distributed dual iteration scheme. Section 4 illustrates the practicality and simplicity of the proposed framework with a numerical example. Section 5 concludes the paper.

In the extended version (Köhler, Müller, & Allgöwer, 2018a), these results are generalized to MPC without terminal ingredients, unreachable setpoints, multi-step MPC and the distributed offline computation of the terminal ingredients is detailed.

2. Distributed model predictive control

Notation

The real numbers are

R

, the positive real numbers are

R_{> 0} = {r \in R | r > 0}

and the natural numbers are

N

. Given vectors

a_{i} \in R^{n_{i}}

, we abbreviate the column vector

{[a_{1}^{⊤}, \dots, a_{n}^{⊤}]}^{⊤} = (a_{1}, \dots, a_{n})

. The quadratic norm with respect to a positive definite matrix

Q = Q^{⊤}

is denoted by

{‖ x ‖}_{Q}^{2} = x^{⊤} Q x

and the minimal and the maximal eigenvalue of

Q

are denoted by

λ_{min} (Q)

and

λ_{max} (Q)

, respectively. For a polytopic constraint

A y \leq b

, we define an

ϵ

-feasible solution as any vector

y

that satisfies

A y \leq b + ϵ 1

, with

ϵ \in R_{> 0}

and the vector of ones

1 = {[1, \dots, 1]}^{⊤}

. We call a vector

ϵ

-strictly feasible if it satisfies

A y \leq b - ϵ 1

. The Minkowski sum of two sets

S, T \subset R^{n}

is denoted by

S \oplus T = {x | \exists s \in S, t \in T : x = s + t} .

A distributed system is represented as a graph

G = (N, E)

with nodes

N

and edges

E

. Each node

i \in N

corresponds to a subsystem with local state

x_{i} \in R^{n_{i}}

and local input

u_{i} \in R^{m_{i}}

. The neighborhood of a subsystem

i

is given by

N_{i} = {j | (i, j) \in E} \cup {i}

, with

x_{N_{i}} \in R^{n_{N_{i}}}

n_{N_{i}} = \sum_{j \in N_{i}} n_{j}

2.1. Problem setup

The distributed linear discrete-time system is given by (1)

x_{i} (t + 1) = A_{N_{i}} x_{N_{i}} (t) + B_{i} u_{i} (t), i \in N,

with polytopic state and input constraints of the form (2)

x_{N_{i}} \in X_{N_{i}} = {x_{N_{i}} | H_{N_{i}} x_{N_{i}} \leq h_{N_{i}}},

(3)

u_{i} \in U_{i} = {u_{i} | L_{i} u_{i} \leq l_{i}},

where

h_{N_{i}} \in R_{> 0}^{p_{i}}

and

l_{i} \in R_{> 0}^{q_{i}}

. We consider the general case, where the control input is given by (4)

u_{i} (t) = K_{N_{i}} x_{N_{i}} (t) + v_{i} (t),

where

K

is some existing distributed controller and

v

is the input calculated using distributed MPC. If no such feedback is known, we can always set

K = 0

. However, including this feedback can reduce the conservatism and mitigate the deteriorating effects of suboptimality on closed-loop stability. The overall system is given by (5)

x (t + 1) = A x (t) + B u (t) = \underset{≕ A_{K}}{\underset{︸}{(A + B K)}} x (t) + B v (t),

with the polytopic constraints

X = {x | x_{N_{i}} \in X_{N_{i}} \forall i \in N} = {x | H x \leq h} \subseteq R^{n},

U = U_{1} \times \dots U_{| N |} = {u | L u \leq l} \subseteq R^{m},

where

l \in R_{> 0}^{q}

and

h \in R_{> 0}^{p}

. We consider a structured quadratic stage cost

ℓ (x, v) = {‖ x ‖}_{Q}^{2} + {‖ v ‖}_{R}^{2}

, with block diagonal positive definite matrices

Q

and

R

. We consider an MPC framework including a terminal cost and terminal set. To this end, we make the following assumption.

Assumption 1

There exists a terminal cost

V_{f} (x) = \sum_{i \in N} {‖ x_{i} ‖}_{P_{i}}^{2} = {‖ x ‖}_{P}^{2}

with a block diagonal matrix

P

, a distributed terminal controller

u_{i} = K_{f, N_{i}} x_{N_{i}}

, and a distributed compact polytopic set

X_{f} = {x | F x \leq f}

, such that the following conditions hold for each

x_{f} \in X_{f}

(6a)

V_{f} ((A + B K_{f}) x_{f}) \leq V_{f} (x) - ℓ (x_{f}, (K_{f} - K) x_{f}),

(6b)

x_{f} \in X, u_{f} = K_{f} x_{f} \in U,

(6c)

(A + B K_{f}) x_{f} \in X_{f} .

Remark 2

In Conte, Jones, Morari, and Zeilinger (2016) distributed linear matrix inequalities (LMIs) are presented that can be used to compute a distributed terminal cost and an ellipsoidal terminal set

X_{f}

. Ellipsoidal terminal constraints lead to a (distributed) quadratically constrained quadratic program (QCQP), which makes the online optimization more complex. Methods to obtain a distributed polytopic terminal set

X_{f}

are for example given in Kögel and Findeisen (2012) and Trodden (2016). The offline computation of the distributed terminal ingredients is discussed in more detail in the extended version (Köhler et al., 2018a A.1). The proposed framework can also be used without such terminal ingredients, which is discussed in Köhler et al. (2018a, A.2, A.3).

The open-loop cost of a state sequence

x (\cdot | t) \in R^{n \times N + 1}

and an input sequence

v (\cdot | t) \in R^{m \times N}

with the prediction horizon

N \in N

is defined as

J_{N} (x (\cdot | t), v (\cdot | t)) ≔ \sum_{k = 0}^{N - 1} ℓ (x (k | t), v (k | t)) + V_{f} (x (N | t)) .

The standard MPC optimization problem is given by (7)

V_{N} (x (t)) = min_{v (\cdot | t), x (\cdot | t)} J_{N} (x (\cdot | t), v (\cdot | t))

s.t. x (k + 1 | t) = A_{K} x (k | t) + B v (k | t), x (0 | t) = x (t), x (N | t) \in X_{f}, x (k | t) \in X, u (k | t) = v (k | t) + K x (k | t) \in U .

The solution to this optimization problem is the value function

V_{N}

and optimal state and input trajectories

(x^{*} (\cdot | t), v^{*} (\cdot | t))

that satisfy the dynamic equality constraint and the state and input constraints. Problem (7) is a distributed quadratic program, the solution of which is discussed in Sections 2.2, 3.5.

For the closed-loop operation the first step of the optimal input

v^{*} (\cdot | t)

is applied to the system (5), resulting in the following closed-loop system dynamics: (8)

x (t + 1) = A_{K} x (t) + v^{*} (0 | t) = x^{*} (1 | t) .

The following theorem is a standard result in MPC and establishes the desired properties.

Theorem 3

Rawlings & Mayne, 2009

Let Assumption 1 hold and assume that Problem (7) is feasible at

t = 0

. Then Problem (7) is recursively feasible and the origin

x = 0

is asymptotically stable for the resulting closed-loop system (8).

2.2. Distributed (dual) optimization

In the following, we motivate why we consider inexact dual optimization and explain why it necessitates modifications to Problem (7). Most theoretical results for MPC (such as Theorem 3) assume that the optimal solution to (7) is obtained in real time, which is rarely achievable in practice.

If primal optimization methods are used, Theorem 3 remains valid with inexact optimization assuming a suitable initialization (Scokaert et al., 1999, Stewart et al., 2010). However, an application of primal optimization methods to large-scale distributed systems suffers from various difficulties, including initialization and scalability.

Thus, we consider dual optimization algorithms (Kögel and Findeisen, 2012, Necoara and Nedelcu, 2015, Necoara and Suykens, 2008), which only require neighbor-to-neighbor communication and can be implemented in a fully distributed manner. The main drawback of dual optimization is that the constraints (dynamic, state and input) are not necessarily satisfied after finite iterations. This necessitates additional modifications to enable theoretical guarantees after finite iterations, compare (Ferranti and Keviczky, 2015, Rubagotti et al., 2014). In the following, we provide a novel MPC formulation which is suitable for distributed computation and explicitly takes the inexact dynamics of approximate solutions into account.

3. Inexact distributed MPC

In the following, we consider bounds on the accuracy

ϵ

, interpret them as disturbances and use tools from robust MPC (Chisci et al., 2001) to compensate the effects of inexact minimization. The proposed modifications are inspired by Ferranti and Keviczky (2015) and directly take the inexactness of the solver into account. By making use of an inexact candidate solution, we obtain a formulation that requires no adaptation and thus no global communication.

3.1. Inexact MPC and constraint tightening

Define an accuracy for the dynamic, state, input and terminal constraints and strict feasibility

ϵ_{z}, ϵ_{x}, ϵ_{u}, ϵ_{f}, ϵ_{λ} \in R_{> 0}

, given by the user. Consider relaxation parameters (9)

ϵ_{z, k} ≔ ϵ_{λ} + (N - 1 - k) (ϵ_{λ} + ϵ_{z}), k = 0, \dots, N - 1,

and the sets

W_{k} = {w \in R^{n} | {‖ w ‖}_{\infty} \leq ϵ_{z, k} + ϵ_{z}}

. We tighten the constraints using the

k

-step support function (Conte, Zeilinger, Morari, & Jones, 2013), which for some

a \in R^{n}

and

k \in N

is defined as (10)

σ_{W} (a, k) = sup_{w \in W_{0}^{k}} a^{⊤} y (k),

s.t. y (l + 1) = A_{K} y (l) + w (l), y (0) = 0 .

The tightened state and input constraints are given by

{\bar{X}}_{k} = {x | H x \leq {\bar{h}}_{k}}, {\bar{U}}_{k} = {u | L u \leq {\bar{l}}_{k}},

with (11)

{\bar{h}}_{j, k} = h_{j} - σ_{W} (H_{j}^{⊤}, k) - ϵ_{x} - k (ϵ_{x} + ϵ_{λ}),

(12)

{\bar{l}}_{j, k} = l_{j} - σ_{W} (K^{⊤} L_{j}^{⊤}, k) - ϵ_{u} - k (ϵ_{u} + ϵ_{λ}) .

Here,

{\bar{h}}_{j, k}

denotes the

j

th component of

{\bar{h}}_{k}

h_{j}

the

j

th component of

h

and

H_{j}

the

j

th row of

H

j \leq p

. The evaluation of the

k

-step support function amounts to solving a distributed linear program (LP) offline. The resulting tightened constraints preserve the distributed structure and can equally be represented with the local polytopic sets

{\bar{X}}_{N_{i}, k}, {\bar{U}}_{i, k}

Assumption 4

Consider the terminal cost and controller from Assumption 1. There exists a compact tightened terminal set

{\bar{X}}_{f} = {x | F x \leq \bar{f}}

, such that the following conditions hold (13a)

{\bar{X}}_{f, ϵ} ⨁_{k = 0}^{N - 1} A_{K}^{N - 1 - k} W_{k} \subseteq X_{f},

(13b)

{\bar{X}}_{f, ϵ} \oplus A_{K}^{N - 1} W_{0} \subseteq {x | H x \leq {\bar{h}}_{N - 1} - 1_{p} ϵ_{λ}},

(13c)

K_{f} ({\bar{X}}_{f, ϵ} \oplus A_{K}^{N - 1} W_{0}) \subseteq {u | L u \leq {\bar{l}}_{N - 1} - 1_{q} ϵ_{λ}},

(13d)

(A + B K_{f}) ({\bar{X}}_{f, ϵ} \oplus A_{K}^{N - 1} W_{0}) \subseteq {\bar{X}}_{f, λ}, {\bar{X}}_{f, ϵ} ≔ {x | F x \leq \bar{f} + 1_{r} ϵ_{f}}, {\bar{X}}_{f, λ} ≔ {x | F x \leq \bar{f} - 1_{r} ϵ_{λ}} .

The sets

{\bar{X}}_{f, ϵ}, {\bar{X}}_{f, λ}

are needed to study strict recursive feasibility (

ϵ_{λ}

) under inexact minimization (

ϵ_{f}

). A sufficient condition for (13b) is

{\bar{X}}_{f, ϵ} \subseteq {\bar{X}}_{N}

. In case

K_{f} = K

K_{f} {\bar{X}}_{f, ϵ} \subseteq {\bar{U}}_{N}

is a sufficient condition for (13c). Condition (13d) requires contractivity of the terminal set, despite the additive disturbance

w_{0}

If the terminal set in Assumption 1 is contractive, Assumption 4 can be satisfied with the following design procedure: for a fixed accuracy

ϵ

and prediction horizon

N

, compute the tightened constraints (11). Then scale the terminal set

X_{f}

such that conditions (13a)–(13c) are satisfied. Finally, verify that condition (13d) is satisfied. If this is not the case, decrease

ϵ

and start over. In Köhler et al. (2018a), we show that the proposed framework can also be used without constructing a terminal set.

With this, we define the modified optimization problem (14a)

min_{v (\cdot | t), z (\cdot | t)} J_{N} (z (\cdot | t), v (\cdot | t))

(14b)

s.t. {‖ A_{K} z (k | t) + B v (k | t) - z (k + 1 | t) ‖}_{\infty} \leq ϵ_{z, k},

(14c)

z (k | t) \in {\bar{X}}_{k}, v (k | t) + K z (k | t) \in {\bar{U}}_{k}, k = 0, \dots, N - 1,

(14d)

z (N | t) \in {\bar{X}}_{f},

(14e)

z (0 | t) = x (t) .

Compared to the original optimization Problem (7), the state and input constraints are tightened and the dynamic equality constraints are relaxed to inequality constraints. We do not try to find a solution that exactly satisfies the dynamic constraints, but only consider a relaxed dynamic constraint with the parameter

ϵ_{z, k}

. This relaxation will allow us to construct a feasible candidate solution which again does not exactly satisfy the dynamic constraints. This is the key insight and novelty in order to prove recursive feasibility and stability under inexact minimization. The resulting Problem (14) is a distributed quadratic program with linear inequality constraints.

To study recursive feasibility of (14) under the inexact DMPC we introduce the notion of

ϵ

-feasible solutions.

Definition 5

ϵ

-feasible solution to (14) is any pair

(z_{ϵ} (\cdot | t), v_{ϵ} (\cdot | t))

, that satisfies (15)

{‖ A_{K} z_{ϵ} (k | t) + B v_{ϵ} (k | t) - z_{ϵ} (k + 1 | t) ‖}_{\infty} \leq ϵ_{z, k} + ϵ_{z}, H z_{ϵ} (k | t) \leq {\bar{h}}_{k} + 1_{p} ϵ_{x}, L (v_{ϵ} (k | t) + K z_{ϵ} (k | t)) \leq {\bar{l}}_{k} + 1_{q} ϵ_{u}, F z_{ϵ} (N | t) \leq \bar{f} + 1_{r} ϵ_{f}, z_{ϵ} (0 | t) = x (t) .

This formulation allows a constraint violation for the posed constraints (14b)–(14d) by

ϵ_{z}, ϵ_{x}, ϵ_{u},

and

ϵ_{f}

, respectively. A corresponding algorithm to ensure an

ϵ

-feasible solution with finite iterations is presented in Section 3.5.

3.2. Feasible consolidated trajectory

In order to characterize the feasibility of on an

ϵ

-feasible solution, we consider the consolidated¹ trajectory (Ferranti & Keviczky, 2015).

Proposition 6

Let Assumption 1, Assumption 4 hold. Given an

ϵ

-feasible solution (15)

z_{ϵ} (\cdot | t), v_{ϵ} (\cdot | t)

at time

t

, the consolidated state and input trajectories

{\bar{x}}_{ϵ} (\cdot | t), {\bar{u}}_{ϵ} (\cdot | t)

{\bar{x}}_{ϵ} (k + 1 | t) ≔ A_{K} {\bar{x}}_{ϵ} (k | t) + B v_{ϵ} (k | t), {\bar{x}}_{ϵ} (0 | t) ≔ x (t),

(16)

{\bar{u}}_{ϵ} (k | t) ≔ K {\bar{x}}_{ϵ} (k | t) + v_{ϵ} (k | t),

satisfy

{\bar{x}}_{ϵ} (k | t) \in X, {\bar{u}}_{ϵ} (k | t) = v_{ϵ} (k | t) + K {\bar{x}}_{ϵ} (k | t) \in U,

{\bar{x}}_{ϵ} (N | t) \in X_{f} .

Proof

The inexact relaxed dynamic constraint (15) can be equivalently written as a dynamic equality constraint with an additive disturbance (17)

z_{ϵ} (k + 1 | t) = A_{K} z_{ϵ} (k | t) + B v_{ϵ} (k | t) + w_{k}, w_{k} \in W_{k} .

The consolidated trajectory (16) satisfies (18)

{\bar{x}}_{ϵ} (k | t) \in {z_{ϵ} (k | t)} ⨁_{l = 0}^{k - 1} A_{K}^{k - l - 1} W_{l} \overset{(9)}{\subseteq} {z_{ϵ} (k | t)} ⨁_{l = 0}^{k - 1} A_{K}^{l} W_{0},

which implies

H_{j} {\bar{x}}_{ϵ} (k | t) \overset{(10)}{\leq} H_{j} z_{ϵ} (k | t) + σ_{W} (H_{j}^{⊤}, k)

\overset{Def. 5}{\leq} {\bar{h}}_{j, k} + ϵ_{x} + σ_{W} (H_{j}^{⊤}, k) \overset{(11)}{\leq} h_{j},

L_{j} {\bar{u}}_{ϵ} (k | t) \overset{(10)}{\leq} L_{j} (v_{ϵ} (k | t) + K z_{ϵ} (k | t)) + σ_{W} (K^{⊤} L_{j}^{⊤}, k)

\overset{Def. 5}{\leq} {\bar{l}}_{j, k} + ϵ_{u} + σ_{W} (K^{⊤} L_{j}^{⊤}, k) \overset{(12)}{\leq} l_{j} .

Terminal constraint satisfaction follows by condition (13a) in combination with the characterization (18) for

k = N

. □

Proposition 6 shows that the consolidated trajectory based on the inexact optimization has all the desirable properties of the standard optimal solution

x^{*} (\cdot | t), u^{*} (\cdot | t)

to Problem (7). The closed-loop system resulting from an inexact DMPC is given by (19)

u (t) = K x (t) + v_{ϵ} (0 | t) = {\bar{u}}_{ϵ} (0 | t),

x (t + 1) = A_{K} x (t) + v_{ϵ} (0 | t) = {\bar{x}}_{ϵ} (1 | t) .

Thus, Proposition 6 implies that the closed loop based on an

ϵ

-feasible solution satisfies the state and input constraints.

Remark 7

In order to show feasibility of the consolidated trajectory, the constraint tightening (11), (12) could be formulated without the term

k (ϵ_{x} + ϵ_{λ})

and the support function could be defined based on the smaller set

W_{0} \times \dots \times W_{k}

, compare (Ferranti & Keviczky, 2015). The more restrictive constraint tightening will be crucial in order to establish recursive feasibility of Problem (14) for the closed-loop system (19) based on an

ϵ

-feasible solution. The issue of using a more conservative constraint tightening to establish recursive feasibility is also addressed in Kögel and Findeisen (2014) and Rubagotti et al. (2014).

3.3. Recursive feasibility under inexact minimization

The following Theorem is the main contribution of this paper. It establishes recursive feasibility of Problem (14) under the inexact MPC control law with a suitable candidate solution.

Theorem 8

Let Assumption 1, Assumption 4 hold. Given an

ϵ

-feasible solution (15)

z_{ϵ} (\cdot | t), v_{ϵ} (\cdot | t)

at time

t

, the candidate sequence (20)

\tilde{v} (k | t + 1) = v_{ϵ} (k + 1 | t), k = 0, \dots, N - 2,

\tilde{v} (N - 1 | t + 1) = (K_{f} - K) \tilde{z} (N - 1 | t + 1),

\tilde{z} (0 | t + 1) = x (t + 1) = z_{ϵ} (1 | t) + w_{0}, w_{0} \in W_{0},

\tilde{z} (k | t + 1) = z_{ϵ} (k + 1 | t) + A_{K}^{k} w_{0}, k = 0, \dots, N - 1,

\tilde{z} (N | t + 1) = (A + B K_{f}) \tilde{z} (N - 1 | t + 1),

is an

ϵ_{λ}

-strictly feasible solution to the optimization Problem (14) at time

t + 1

. Problem (14) is recursively feasible for the closed-loop system (19).

Proof

The proof is composed of three parts. First, we show strict satisfaction of the relaxed dynamic constraints. Then we show strict satisfaction of the tightened state and input constraints. Finally, we show strict satisfaction of the terminal constraint and thus establish recursive feasibility.

Part I: Show that the candidate sequence

\tilde{z} (\cdot | t + 1), \tilde{v} (\cdot | t + 1)

in (20) strictly satisfies the relaxed dynamic constraint (14b): The candidate input

\tilde{v} (\cdot | t + 1)

(20) is constructed by shifting the previous input sequence

v_{ϵ} (\cdot | t)

by one time step and appending the terminal controller

K_{f}

. The state sequence

z_{ϵ} (\cdot | t)

is shifted with an additional error term

w_{0}

propagated through the system dynamics to ensure satisfaction of the initial state constraint (14e). Substituting (17) in

\tilde{z} (\cdot | t + 1)

yields

\tilde{z} (k | t + 1) = z_{ϵ} (k + 1 | t) + A_{K}^{k} w_{0}

= A_{K} z_{ϵ} (k | t) + B v_{ϵ} (k | t) + A_{K}^{k} w_{0} + w_{k}

= A_{K} \tilde{z} (k - 1 | t + 1) + B \tilde{v} (k - 1 | t + 1) + w_{k},

for

k = 1, \dots, N - 1

, with

{‖ w_{k} ‖}_{\infty} \leq ϵ_{z, k} + ϵ_{z} = ϵ_{z, k - 1} - ϵ_{λ}

. Similarly, the last dynamic constraint (

k = N

) is satisfied with equality, which implies that all relaxed dynamic constraints are strictly satisfied with

ϵ_{z, N - 1} = ϵ_{λ}

Part II: Show that the candidate sequence (20) strictly satisfies the state and input constraints (14c): Due to the definition of the support function² and linear superposition we have

σ_{W} (H_{j}^{⊤}, k + 1) \geq σ_{W} (H_{j}^{⊤}, k) + H_{j} A_{K}^{k} w_{0}, \forall w_{0} \in W_{0},

which implies

{\bar{h}}_{j, k + 1} + H_{j} A_{K}^{k} w_{0} \leq {\bar{h}}_{j, k} - (ϵ_{x} + ϵ_{λ}) .

The candidate sequence satisfies

H_{j} \tilde{z} (k | t + 1) = H_{j} z_{ϵ} (k + 1 | t) + H_{j} A_{K}^{k} w_{0}

\leq {\bar{h}}_{j, k + 1} + H_{j} A_{K}^{k} w_{0} + ϵ_{x} \leq {\bar{h}}_{j, k} - ϵ_{λ}, k = 0, \dots, N - 2 .

and hence the state constraints are strictly satisfied. For the input constraints the same argument holds with

L_{j} (\tilde{v} (k | t + 1) + K \tilde{z} (k | t + 1))

= L_{j} (v_{ϵ} (k + 1 | t) + K z_{ϵ} (k + 1 | t) + K A_{K}^{k} w_{0})

\leq {\bar{l}}_{j, k + 1} + ϵ_{u} + L_{j} K A_{K}^{k} w_{0} \leq {\bar{l}}_{j, k} - ϵ_{λ}, k = 0, \dots, N - 2 .

Given

z_{ϵ} (N | t) \in {\bar{X}}_{f, ϵ}

, conditions (13b) and (13c) imply strict satisfaction of the state and input constraints at

k = N - 1

Part III: Show that the terminal state of the candidate sequence (20) strictly satisfies the terminal constraint (14d): Condition (13d) ensures

\tilde{z} (N | t + 1)

= (A + B K_{f}) \tilde{z} (N - 1 | t + 1)

= (A + B K_{f}) (z_{ϵ} (N | t) + A_{K}^{N - 1} w_{0})

\in (A + B K_{f}) ({\bar{X}}_{f, ϵ} \oplus A_{K}^{N - 1} W_{0}) \subseteq {\bar{X}}_{f, λ} \subset {\bar{X}}_{f} . □

This theorem ensures recursive feasibility under inexact dual optimization with bounded constraint violation. The candidate solution

\tilde{z}

with the corresponding tightened (and shifted) constraint set

{\bar{X}}_{k}

is sketched in Fig. 1. The tightened constraint set

{\bar{X}}_{k}

is constructed, such that

ϵ

-feasibility of

z_{ϵ} (\cdot | t)

implies

ϵ_{λ}

-strict feasibility of

\tilde{z} (\cdot | t + 1)

w.r.t. the shifted constraint set

{\bar{X}}_{k}

, despite the error

w_{0}

3.4. Closed-loop stability

To study stability properties of the closed-loop system, we use the following definition regarding the suboptimality of the inexact solution.

Definition 9

Given an

ϵ

-feasible solution (Definition 5), the suboptimality

η

w.r.t. the optimal solution is defined as (21)

J_{N} ({\bar{x}}_{ϵ} (\cdot | t), v_{ϵ} (\cdot | t)) \leq V_{N} (x (t)) + η .

The inexact optimal solution is given by (22)

V_{N, ϵ} (x (t)) ≔ min_{z (\cdot | t), v (\cdot | t)} J_{N} (z (\cdot | t), v (\cdot | t))

s.t. z (\cdot | t), v (\cdot | t) satisfy (15) .

The suboptimality

η_{ϵ}

with respect to this inexact optimal solution is given by (23)

J_{N} (z_{ϵ} (\cdot | t), v_{ϵ} (\cdot | t)) \leq V_{N, ϵ} (x (t)) + η_{ϵ} .

Solutions satisfying (15), (21), (23) are called

(ϵ, η, η_{ϵ})

-approximate solutions.

Corresponding bounds on the suboptimality for inexact dual optimization will be established in Proposition 12. The following proposition shows that the proposed inexact DMPC approximately preserves the stability properties of nominal MPC based on exact optimization.

Proposition 10

Let Assumption 1, Assumption 4 hold. Given an

(ϵ, η, η_{ϵ})

-approximate solution

z_{ϵ} (\cdot | t), v_{ϵ} (\cdot | t)

(Definition 9) at time

t

, the candidate sequence

\tilde{z} (\cdot | t + 1), \tilde{v} (\cdot | t + 1)

in Theorem 8 implies (24)

V_{N} (x (t + 1)) \leq V_{N} (x (t)) - ℓ (x (t), v (t)) + η .

Hence the origin

x = 0

is practically asymptotically stable (Grüne & Pannek, 2017 Def. 2.15) for the closed-loop system (19) based on

(ϵ, η, η_{ϵ})

-approximate solutions at each time

t

. Given a sufficiently small

ϵ, η_{ϵ}

, the additional bound (25)

V_{N, ϵ} (x (t + 1)) \leq V_{N, ϵ} (x (t)) - ℓ (x (t), v (t)) + η_{ϵ} + β_{1}

holds with

β_{1}

according to (26).

Proof

Part I: Consolidated cost

V_{N}

: The candidate input sequence

\tilde{v} (\cdot | t + 1)

from Theorem 8 with the corresponding consolidated state trajectory

\bar{x} (\cdot | t + 1)

is a feasible solution to (7) (Proposition 6). Using suboptimality

η

according to Definition 9, this implies

V_{N} (x (t + 1)) \leq J_{N} (\bar{x} (\cdot | t + 1), v (\cdot | t + 1))

\overset{(6a)}{\leq} J_{N} ({\bar{x}}_{ϵ} (\cdot | t), v_{ϵ} (\cdot | t)) - ℓ (x (t), v (t))

\overset{(21)}{\leq} V_{N} (x (t)) + η - ℓ (x (t), v (t)) .

Practical asymptotic stability follows from standard Lyapunov arguments.

Part II: Inexact optimal cost

V_{N, ϵ}

: There exist constants

\underset{̲}{α}, \bar{α}

, such that

z_{ϵ} \in {\bar{X}}_{f}

implies

V_{f} (z_{ϵ}) \leq \bar{α}

, and

V_{f} (z_{ϵ}) \leq \underset{̲}{α}

implies

z_{ϵ} \in {\bar{X}}_{f}

. In the following we consider a bound

V_{N, ϵ} (x (t)) \leq {\bar{V}}_{ϵ} - η_{ϵ}

, with some

{\bar{V}}_{ϵ} \geq \underset{̲}{α} + η_{ϵ}

, which is recursively established in the end. This bound in combination with the suboptimality implies

J_{N} (z_{ϵ} (\cdot | t), v_{ϵ} (\cdot | t)) \leq {\bar{V}}_{ϵ}

. The stage cost and terminal cost of the candidate solution satisfy

ℓ (\tilde{z} (k | t + 1), \tilde{v} (k | t + 1)) - ℓ (z_{ϵ} (k + 1 | t), v_{ϵ} (k + 1 | t))

\leq {‖ A_{K}^{k} w_{0} ‖}_{Q}^{2} + 2 \sqrt{{\bar{V}}_{ϵ}} {‖ A_{K}^{k} w_{0} ‖}_{Q}, k = 0, \dots, N - 1, V_{f} (\tilde{z} (N - 1 | t)) - V_{f} (z_{ϵ} (N - 1 | t))

\leq {‖ A_{K}^{N - 1} w_{0} ‖}_{P}^{2} + 2 \sqrt{\bar{α}} {‖ A_{K}^{N - 1} w_{0} ‖}_{P} .

The cost of the candidate trajectory satisfies

J_{N} (\tilde{z} (\cdot | t + 1), \tilde{v} (\cdot | t + 1)) - J_{N} (z_{ϵ} (\cdot | t), v_{ϵ} (\cdot | t))

\overset{(6a)}{\leq} - ℓ (x (t), v (t)) + V_{f} (\tilde{z} (N - 1 | t + 1)) - V_{f} (z_{ϵ} (N | t))

+ \sum_{k = 0}^{N - 2} ℓ (\tilde{z} (k | t + 1), v_{ϵ} (k + 1 | t)) - ℓ (z_{ϵ} (k + 1 | t), v_{ϵ} (k + 1 | t))

\leq - ℓ (x (t), v (t)) + β_{1},

with (26)

β_{1} ≔ \sum_{k = 0}^{N - 2} {‖ A_{K}^{k} w_{0} ‖}_{Q}^{2} + 2 \sqrt{{\bar{V}}_{ϵ}} {‖ A_{K}^{k} w_{0} ‖}_{Q}

+ {‖ A_{K}^{N - 1} w_{0} ‖}_{P}^{2} + 2 \sqrt{\bar{α}} {‖ A_{K}^{N - 1} w_{0} ‖}_{P}^{2} .

Using feasibility based on Theorem 8 and suboptimality

η_{ϵ}

according to Definition 9, this implies

V_{N, ϵ} (x (t + 1)) \leq J_{N} (\tilde{z} (\cdot | t + 1), \tilde{v} (\cdot | t + 1))

\leq J_{N} (z_{ϵ} (\cdot | t), v_{ϵ} (\cdot | t)) - ℓ (x (t), v (t)) + β_{1}

\overset{(23)}{\leq} V_{N, ϵ} (x (t)) + η_{ϵ} + β_{1} - ℓ (x (t), v (t)) .

The upper bound

{\bar{V}}_{ϵ}

is valid recursively, if

ϵ, η_{ϵ}

are sufficiently small, such that the following inequality holds

{\bar{V}}_{ϵ} - η_{ϵ} \geq \underset{̲}{α} \geq λ_{max} (P ∕ Q) (β_{1} + η_{ϵ})

, compare (Köhler, Müller, & Allgöwer, 2018b Lemma 7, Thm. 8). □

Theorem 8 in combination with Proposition 10 ensures recursive feasibility and practical asymptotic stability under inexact dual optimization with bounded constraint violation and suboptimality. Both inequalities (24), (25) are each independently sufficient for practical asymptotic stability with the corresponding value functions

V_{N}, V_{N, ϵ}

as practical Lyapunov functions. The stability analysis based on

V_{N, ϵ}

tends to be less conservative (compare Proposition 12) and is only possible since we explicitly refrain from adapting the accuracy

ϵ

online, contrary to Ferranti and Keviczky (2015), Giselsson and Rantzer (2014) and Necoara et al. (2015). This is why we also prove the technically more difficult, but potentially less conservative, bounds on the inexact valuefunction (25).

Remark 11

Due to the inexact dynamic constraint (14b), the input

v_{ϵ} = 0

is the optimal solution to Problem (14) if

‖ x (t) ‖

is small enough. This property is another reason why the additional feedback in (4) can be advantageous.

3.5. Dual distributed optimization

In the following, we describe how to obtain an approximate solution to Problem (14) with finite dual distributed iterations. Problem (14) can be formulated³ as

min_{y} \frac{1}{2} \sum_{i \in N} {‖ y_{i} ‖}_{{\bar{Q}}_{i}}^{2}

s.t. \sum_{j \in N_{i}} C_{i j} y_{j} \leq c_{i}, i \in N, y_{i} = (v_{i} (0 | t), z_{i} (1 | t), \dots, v_{i} (N - 1 | t), z_{i} (N | t)), c \in R^{n_{c}} .

The local dual gradient is Lipschitz with

L_{d_{i}} = \frac{{‖ {[C_{j i}]}_{j \in N_{i}} ‖}^{2}}{λ_{min} ({\bar{Q}}_{i})}

. We consider the distributed dual gradient algorithm (Necoara & Nedelcu, 2015), with the local step size

W_{μ, i} = \sum_{j \in N_{i}} L_{d_{j}}

Here

{[]}_{+}

denotes the projection on the nonnegative orthant. This is an iterative synchronous algorithm, which consists of small-scale multiplications and requires only local communication. The following proposition summarizes the theoretical properties of this algorithm based on (Necoara & Nedelcu, 2015 Thm. 4.2–4.4) and strict feasibility (Ferranti & Keviczky, 2015 Thm. 1).

Proposition 12

Suppose there exists an

ϵ_{λ}

-strictly feasible solution

\tilde{y}

to Problem (14) and consider the initialization⁴

μ^{0} = 0

. For all

p \geq \bar{p}

y^{p}

is an

(ϵ, η, η_{ϵ})

-approximate solution (Definitions 5, 9) with (27a)

\bar{p} = 2 + {log}_{d} [ϵ_{λ} \underset{̲}{ϵ} ‖ W_{μ}^{- 1} ‖ ∕ {\bar{V}}_{ϵ}], d < 1,

(27b)

η_{ϵ} = \sqrt{n_{c}} {\bar{V}}_{ϵ} \bar{ϵ} ∕ ϵ_{λ} + \frac{1}{2} {\underset{̲}{ϵ}}^{2} ‖ W_{μ}^{- 1} ‖,

(27c)

η = \sqrt{n_{c}} {\bar{V}}_{ϵ} {\bar{ϵ}}_{N} ∕ ϵ_{λ} + \frac{1}{2} {\underset{̲}{ϵ}}^{2} ‖ W_{μ}^{- 1} ‖,

{\bar{ϵ}}_{N} = max {\bar{ϵ}, ϵ_{z, 0}, {\bar{h}}_{j, N} - h_{j}, {\bar{l}}_{j, N} - l_{j}}

\underset{̲}{ϵ} = min {ϵ_{z}, ϵ_{x}, ϵ_{u}, ϵ_{f}}

\bar{ϵ} = max {ϵ_{z}, ϵ_{x}, ϵ_{u}, ϵ_{f}}

{\bar{V}}_{ϵ} = {‖ \tilde{y} ‖}_{\bar{Q}}^{2}

Proof

Part I: Given the

ϵ_{λ}

-strictly feasible solution

\tilde{y}

, the following upper bound holds for the optimal dual variable

μ^{*}

(compare Ferranti & Keviczky, 2015, Lemma 1)

‖ μ^{*} ‖ \leq \frac{{‖ \tilde{y} ‖}_{\bar{Q}}^{2} - {‖ y^{*} ‖}_{\bar{Q}}^{2}}{ϵ_{λ}} \leq \frac{{‖ \tilde{y} ‖}_{{\bar{Q}}^{2}}}{ϵ_{λ}} \leq {\bar{V}}_{ϵ} ∕ ϵ_{λ} .

Based on (Necoara & Nedelcu, 2015 Thm. 4.2) the constraint violation satisfies

‖ {[C y^{p} - c]}_{+} ‖ \leq d^{p - 2} {\bar{V}}_{ϵ} ∕ ϵ_{λ} ‖ W_{μ} ‖,

with the fixed constant

d < 1

according to Necoara and Nedelcu (2015, Thm. 3.2, Thm. 4.2). Correspondingly, for

p \geq \bar{p}

y^{p}

is an

ϵ

-feasible solution, with

\bar{p}

according to (27a).

Part II: Analogous to Ferranti and Keviczky (2015, Thm. 1), we can derive the following bound based on the dual variables and the relaxation

V_{N, ϵ} (x (t)) \leq J_{N} (z^{*} (\cdot | t), v^{*} (\cdot | t)) + \sqrt{n_{c}} {\bar{V}}_{ϵ} \bar{ϵ} ∕ ϵ_{λ},

where

z^{*}, v^{*}

is the optimal solution to (14). By combining this result with the relative suboptimality

η_{y}

y^{p}

(Necoara & Nedelcu, 2015 Thm. 4.4), we can establish the following bound

η_{ϵ} \leq {‖ μ^{*} ‖}_{1} \bar{ϵ} + η_{y} \leq \sqrt{n_{c}} {\bar{V}}_{ϵ} \bar{ϵ} ∕ ϵ_{λ} + η_{y},

η_{y} ≔ \frac{1}{2} {(d^{\bar{p} - 1} {\bar{V}}_{ϵ} ∕ ϵ_{λ})}^{2} ‖ W_{μ} ‖ \leq \frac{1}{2} {\underset{̲}{ϵ}}^{2} ‖ W_{μ}^{- 1} ‖ .

The same derivations hold for

η

, using the maximal size of the constraint tightening

{\bar{ϵ}}_{N}

instead of

\bar{ϵ}

. □

Remark 13

Given a user specified accuracy

ϵ

, this proposition gives an a priori upper bound on the number of iterations

\bar{p}

for a given sublevel set of

V_{N, ϵ}

. In combination with Theorem 8 and Proposition 10, this property holds recursively under the approximate DMPC. In closed-loop operation the value of

{\bar{V}}_{N, ϵ}

decreases (Proposition 10) and thus the number of necessary iterations

\bar{p}

based on (27a) decreases. Using a larger tolerance

ϵ

leads to fewer iterations

p

and a larger suboptimality

η, η_{ϵ}

. The bound for

η_{ϵ}

is (typically) significantly smaller than

η

, which is crucial for the stability analysis (Proposition 10). Instead of choosing a desired accuracy

ϵ

, a user can also specify an upper bound on the number of iterations

\bar{p}

and choose a sufficiently small accuracy

ϵ

using (27a). There exists a variety of distributed dual algorithms for which similar complexity bounds can be obtained. If an alternating minimization algorithm such as Kögel and Findeisen (2012) and Ferranti and Keviczky (2015) is used, the relationship between the inexactness of the optimization

ϵ

and the resulting inexactness in the dynamic constraint changes, see Ferranti and Keviczky (2015) and Köhler, Müller, Li, and Allgöwer (2017).

The initialization and closed-loop operation of the MPC scheme is summarized in the following two algorithms.

Instead of using the (possibly conservative) a priori bound

\bar{p}

, a stopping condition ensuring an

ϵ

-feasible solution (Definition 5) can be used, which can be efficiently and distributedly checked online, compare Section 4. All the necessary offline and online computations can be accomplished in a fully distributed and scalable fashion.

3.6. Comments

By combining Theorem 8 and Proposition 10, Proposition 12, we can ensure recursive feasibility and practical asymptotic stability with finite distributed dual iterations. While parts of the proof might be technical, the application of the proposed method is straightforward. The bounds on the suboptimality

η_{ϵ}, η

and the resulting closed-loop stability guarantees (Propositions 10, 12) tend to be conservative and should rather be interpreted as a conceptual result of how the inexact minimization affects stability.

We prove the theoretical properties of the proposed framework within the standard MPC setup including a terminal cost and a polytopic terminal set. In various applications and setups, different variations of MPC can be advantageous (such as MPC without terminal ingredients or economic MPC). The extended version (Köhler et al., 2018a) shows in detail under which conditions similar results can be derived for these different setups.

The following remark discusses similarities of the proposed framework to existing schemes and highlights the novelty based on the inexact candidate solution.

Remark 14

In Rubagotti et al. (2014) violations in the inequality constraints (state and input constraints

ϵ_{x}, ϵ_{u}

) are considered. The corresponding constraint tightening can be viewed as a special case (

ϵ_{z} = 0

) of the proposed method.

In Kögel and Findeisen (2014) a constraint tightening is proposed to ensure recursive feasibility of the consolidated trajectory despite inexact dynamic constraints. The a priori complexity bounds (Proposition 12) do not hold for this formulation due to the usage of equality constraints and lack of strict feasibility.

In Giselsson and Rantzer (2014) the stopping condition is based on an explicit candidate solution for the next time step, which needs to be computed online. This requires additional online computations and bounds on the number of iterations cannot be given (in contrast to

ϵ

-feasibility as used in Ferranti and Keviczky, 2015, Necoara et al., 2015, Rubagotti et al., 2014).

In Ferranti and Keviczky (2015) and Necoara et al. (2015) the constraints are tightened, such that the consolidated trajectory is (strictly) feasible (Proposition 6). Recursive feasibility is ensured be adapting the accuracy

ϵ

and constraint tightening online. This adaptation requires global communication, is complex, and it is a priori unclear whether the number of online iterations increases or decreases in closed-loop operation. One of the main benefits of the proposed framework is that such an adaptation is not needed (although incorporating an optional adaptation, if possible, could be beneficial).

To the best of our knowledge, the proposed result is the first MPC result based on a dynamic inexact candidate solution. As discussed above, the use of such an inexact candidate solution is possible through relaxing the dynamic constraint (14b) and is the key ingredient for establishing recursive feasibility with a fixed constraint tightening, allowing for a fully distributed implementation of the proposed scheme with finite dual iterations.

4. Numerical example

In the following, we show the practicality of the proposed approach with the example⁵ of a chain of masses (Conte et al., 2016). We consider

M = 20

subsystems with randomly sampled mass

m \in [0.5, 1.5]

, spring constant

k \in [1.5, 4.5]

, damping constant

d \in [1.5, 4.5]

and use an Euler discretization with

h = 0.1

s. The cost is

Q = I

R = I

and the constraints are

{‖ u_{i} ‖}_{\infty} \leq 10

| [1, 0] x_{i} | \leq 10

| [0, 1] x_{i} | \leq 1

{‖ x_{i} - x_{j} ‖}_{\infty} \leq 3, j \in N_{i}

. The resulting system has

40

states,

20

inputs, and coupled dynamics and constraints.

Offline computation

In the following we detail the offline computations. We consider no additional feedback, i.e.,

K = 0

. We choose a prediction horizon of

N = 4

and the tolerance is chosen as

ϵ = 2.5 \cdot 1 0^{- 3} = ϵ_{z} = ϵ_{x} = ϵ_{u} = ϵ_{λ} = ϵ_{f}

. The constraints are tightened with the

k

-step support function (11), (12). We compute a distributed terminal cost

P

that satisfies (6a) with distributed LMIs as in Conte et al. (2016). For the terminal set, we consider decoupled local terminal sets

{\bar{X}}_{f} = {\bar{X}}_{f, 1} \times \dots {\bar{X}}_{f, M}

, with symmetric local sets

{\bar{X}}_{f, i} = {x_{i} | G x_{i} \leq q_{i}, - G x_{i} \leq q_{i}}, G^{⊤} = (\begin{pmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & - 1 \end{pmatrix}) .

The vectors

q_{i}

are determined using the method in Trodden (2016), such that the set

{\bar{X}}_{f, ϵ}

is (robust) positively invariant for the dynamics

A + B K_{f}

, by solving a (distributed) LP. This terminal set is scaled, such that the conditions (13c), (13b) are satisfied. Finally, we verify that this terminal set satisfies condition (13d) and thus Assumptions 1, 4 are satisfied. The overall offline computations are accomplished in 60 s with an Intel Core i7.

Simulations — stability and dual initialization

In the following, the online optimization (Alg. 1) is stopped once an

ϵ

-feasible solution (Definition 5) is obtained. We explore the effect of the initialization

μ^{0}

(Alg. 3) on the number of dual iterations

p

. Simple initialization strategies are

μ^{0} = 0

, using the previous dual variables

μ^{0} = μ^{p}

, or shifting

μ^{p}

similar to the shifted candidate solution

\tilde{z}

in Theorem 8 (and appending zero at the end). We consider an initial condition with random positions and zero velocity. The inexact cost

J_{N} (z_{ϵ}, v_{ϵ})

and number of dual iterations

p

for the resulting closed loop can be seen in Fig. 2.

As expected, the predicted cost

J_{N}

decreases and the origin is (practically) asymptotically stable (Proposition 10). Clearly, using the previous solution

μ^{p}

can significantly reduce the number of online iterations. Since the cost

J_{N}

with different initialization

μ^{0}

only varies marginally, a suitable initialization simply reduces the number of online iterations.

In the following, we quantitatively explore the effect of the tolerance

ϵ

and the number of subsystems

M

on the closed-loop computational demand. We consider the initialization based on the shifted vector

μ^{p}

. In Fig. 3 we can see the number of online iterations

p

in each time step for different numbers of subsystems

M \in {5, 10, 15, 20}

and tolerances

ϵ \in {2.5 \cdot 1 0^{- 3}, 1 0^{- 3}, 1 0^{- 4}}

. If we increase the number of subsystems

M

, the number of dual iterations tends to increase slightly (due to the increased cost

{\bar{V}}_{ϵ}

, compare Proposition 12). In contrast, if we chose a smaller tolerance

ϵ

the number of dual iterations increases significantly. Thus, by choosing a larger tolerance

ϵ

, we can consider significantly more subsystems

M

without increasing the number of online dual iterations

p

To summarize: Compared to a nominal DMPC, the design procedure only requires the additional computation of the tightened constraints for the chosen tolerance

ϵ

. With the proposed modifications, the closed loop satisfies the constraints and the effect of inexact minimization on closed-loop stability is negligible. Thus, we can significantly reduce the online computational demand by allowing for a non-vanishing tolerance

ϵ

without any major downside. The main limitation to consider more subsystems

M

and a larger tolerance

ϵ

is the construction of the polytopic terminal set

{\bar{X}}_{f}

and the robust positive invariance condition (13d).

5. Conclusion

We have proposed a new formulation for DMPC based oninexact dual optimization. The online optimization can beaccomplished in a fully distributed manner using standard dual distributed optimization methods and only has to obtain an approximate solution. We have established recursive feasibility, constraint satisfaction and practical stability of the closed loop based on such an approximate solution. This is possible through the usage of a reformulated optimization problem and a novel candidate solution, which both explicitly consider the inexactness of the optimization. This modified formulation enables practical applications of MPC to large-scale systems with fast dynamics, for which the underlying MPC optimization problem cannot be solved inreal time.

Acknowledgments

Preliminary results of this paper have been derived during a stay of the first author in Na Li’s research group in SEAS Harvard.

References

Chisci et al., 2001
Chisci Luigi, Rossiter J Anthony, Zappa Giovanni
Systems with persistent disturbances: predictive control with restricted constraints
Automatica, 37 (2001), pp. 1019-1028
View PDF View article View in Scopus Google Scholar
Conte et al., 2016
Conte Christian, Jones Colin N, Morari Manfred, Zeilinger Melanie N
Distributed synthesis and stability of cooperative distributed model predictive control for linear systems
Automatica, 69 (2016), pp. 117-125
View PDF View article View in Scopus Google Scholar
Conte et al., 2013
Conte Christian, Zeilinger Melanie N, Morari Manfred, Jones Colin N
Robust distributed model predictive control of linear systems
Proc. European control Conf. (ECC) (2013), pp. 2764-2769
Crossref View in Scopus Google Scholar
Doan et al., 2011
Doan Minh Dang, Keviczky Tamás, Schutter Bart De
A distributed optimization-based approach for hierarchical model predictive control of large-scale systems with coupled dynamics and constraints
Proc. 50th IEEE Conf. Decision and control (CDC) (2011), pp. 5236-5241
Crossref View in Scopus Google Scholar
Ferranti and Keviczky, 2015
Ferranti Laura, Keviczky Tamás
A parallel dual fast gradient methodfor MPC applications
Proc. 54th IEEE Conf. Decision and control (CDC) (2015), pp. 2406-2413
Crossref View in Scopus Google Scholar
Giselsson and Rantzer, 2014
Giselsson Pontus, Rantzer Anders
On feasibility, stability and performance in distributed model predictive control
IEEE Transactions on Automatic Control, 59103 (2014), pp. 1-1036
Google Scholar
Grüne and Pannek, 2017
Grüne Lars, Pannek Jürgen
Nonlinear model predictive control
Springer (2017)
Google Scholar
Kögel and Findeisen, 2012
Kögel Markus, Findeisen Rolf
Cooperative distributed MPC using the alternating direction multiplier method
Proc. 8th IFAC symposium on advanced control of chemical processes (2012), pp. 445-450
View PDF View article View in Scopus Google Scholar
Kögel and Findeisen, 2014
Kögel Markus, Findeisen Rolf
Stabilization of inexact MPC schemes
Proc. 53rd IEEE Conf. Decision and control (CDC) (2014), pp. 5922-5928
Crossref View in Scopus Google Scholar
Köhler et al., 2018a
Köhler Johannes, Müller Matthias A, Allgöwer Frank
Inexact distributed model predictive control - recursive feasibility under inexact dual optimization
Tech. rep, University of Stuttgart (2018)
Google Scholar
Köhler et al., 2018b
Köhler Johannes, Müller Matthias A, Allgöwer Frank
A novel constraint tightening approach for nonlinear robust model predictive control
Proc. American control Conf. (ACC) (2018), pp. 728-734
Crossref View in Scopus Google Scholar
Köhler et al., 2017
Köhler Johannes, Müller Matthias A, Li Na, Allgöwer Frank
Real time economic dispatch for power networks: A distributed economic model predictive control approach
Proc. 56th IEEE Conf. Decision and control (CDC) (2017), pp. 6340-6345
View in Scopus Google Scholar
Maestre et al., 2014
Maestre José M, Negenborn Rudy R, et al.
Distributed model predictive control made easy
Springer (2014)
Google Scholar
Müller and Allgöwer, 2017
Müller Matthias A, Allgöwer Frank
Economic and distributed model predictive control: Recent developments in optimization-based control
SICE J. of Control, Measurement, and System Integration, 10 (2017), pp. 39-52
Crossref Google Scholar
Necoara et al., 2015
Necoara Ion, Ferranti Laura, Keviczky Tamás
An adaptive constraint tightening approach to linear model predictive control based on approximation algorithms for optimization
Optimal Control Applications & Methods, 36 (2015), pp. 648-666
Crossref View in Scopus Google Scholar
Necoara and Nedelcu, 2015
Necoara Ion, Nedelcu Valentin
On linear convergence of a distributed dual gradient algorithm for linearly constrained separable convex problems
Automatica, 55 (2015), pp. 209-216
View PDF View article View in Scopus Google Scholar
Necoara and Suykens, 2008
Necoara Ion, Suykens JohanAK
Application of a smoothing technique to decomposition in convex optimization
IEEE Transactions on Automatic Control, 53 (2008), pp. 2674-2679
View in Scopus Google Scholar
Rawlings and Mayne, 2009
Rawlings James B, Mayne David Q
Model predictive control: Theory and design
Nob Hill Pub (2009)
Google Scholar
Rubagotti et al., 2014
Rubagotti Matteo, Patrinos Panagiotis, Bemporad Alberto
Stabilizing linear model predictive control under inexact numerical optimization
IEEE Transactions on Automatic Control, 59 (2014), pp. 1660-1666
View in Scopus Google Scholar
Scokaert et al., 1999
Scokaert Pierre OM, Mayne David Q, Rawlings James B
Suboptimal model predictive control (feasibility implies stability)
IEEE Transactions on Automatic Control, 44 (1999), pp. 648-654
View in Scopus Google Scholar
Stewart et al., 2010
Stewart Brett T, Venkat Aswin N, Rawlings James B, Wright Stephen J, Pannocchia Gabriele
Cooperative distributed model predictive control
Systems & Control Letters, 59 (2010), pp. 460-469
View PDF View article View in Scopus Google Scholar
Trodden, 2016
Trodden Paul
A one-step approach to computing a polytopic robustpositively invariant set
IEEE Transactions on Automatic Control, 61 (12) (2016), pp. 4100-4105
View in Scopus Google Scholar

Cited by (22)

Analysis and design of model predictive control frameworks for dynamic operation—An overview
2024, Annual Reviews in Control
Citation Excerpt :
MPC formulations without terminal ingredients (Section 6) are simple to apply for large scale systems due to the absence of any offline designs. For example, Giselsson and Rantzer (2014) and Köhler et al. (2019a, App. A) derive closed-loop guarantees for regulation and economic performance despite inexact distributed optimization. In the following, we mention existing results that combine the nominal results in Sections 3–6 with a robust MPC formulation.
This article provides an overview of model predictive control (MPC) frameworks for dynamic operation of nonlinear constrained systems. Dynamic operation is often an integral part of the control objective, ranging from tracking of reference signals to the general economic operation of a plant under online changing time-varying operating conditions. We focus on the particular challenges that arise when dealing with such more general control goals and present methods that have emerged in the literature to address these issues. The goal of this article is to present an overview of the state-of-the-art techniques, providing a diverse toolkit to apply and further develop MPC formulations that can handle the challenges intrinsic to dynamic operation. We also critically assess the applicability of the different research directions, discussing limitations and opportunities for further research.
Distributed model predictive safety certification for learning-based control
2020, IFAC-PapersOnLine
While distributed algorithms provide advantages for the control of complex large-scale systems by requiring a lower local computational load and less local memory, it is a challenging task to design high-performance distributed control policies. Learning-based control algorithms offer promising opportunities to address this challenge, but generally cannot guarantee safety in terms of state and input constraint satisfaction. A recently proposed safety framework for centralized linear systems ensures safety by matching the learning-based input online with the initial input of a model predictive control law capable of driving the system to a terminal set known to be safe. We extend this idea to derive a distributed model predictive safety certification (DMPSC) scheme, which is able to ensure state and input constraint satisfaction when applying any learning-based control algorithm to an uncertain distributed linear system with dynamic couplings. The scheme is based on a distributed tube-based model predictive control (MPC) concept, where subsystems negotiate local tube sizes among neighbors in order to mitigate restrictiveness of the safety approach. In addition, we present a technique for generating a structured ellipsoidal robust positive invariant tube. In numerical simulations, we show that the safety framework ensures constraint satisfaction for an initially unsafe control policy and allows to improve overall control performance compared to robust distributed MPC.
Tube-Based Model Predictive Full Containment Control for Stochastic Multiagent Systems
2023, IEEE Transactions on Automatic Control
Robust-to-Early Termination Model Predictive Control
2023, IEEE Transactions on Automatic Control
Stochastic Distributed Predictive Tracking Control under Inexact Minimization
2021, IEEE Transactions on Control of Network Systems
Distributed Model Predictive Control and Optimization for Linear Systems with Global Constraints and Time-Varying Communication
2021, IEEE Transactions on Automatic Control

View all citing articles on Scopus

Johannes Köhler received his Master degree in Engineering Cybernetics from the University of Stuttgart, Germany, in 2017. During his studies, he spent 3 months at Harvard University in Na Li’s research lab. He has since been a doctoral student at the Institute for Systems Theory and Automatic Control under the supervision of Prof. Frank Allgöwer and a member of the Graduate School Soft Tissue Robotics at the University of Stuttgart. His research interests are in the area of model predictive control.

Matthias A. Müller received a Diploma degree in Engineering Cybernetics from the University of Stuttgart, Germany, and an M.S. in Electrical and Computer Engineering from the University of Illinois at Urbana-Champaign, US, both in 2009. In 2014, he obtained a Ph.D. in Mechanical Engineering, also from the University of Stuttgart, Germany, for which he received the 2015 European Ph.D. award on control for complex and heterogeneous systems. He is currently working as a senior lecturer (Akademischer Oberrat) at the Institute for Systems Theory and Automatic Control at the University of Stuttgart, Germany. His research interests include nonlinear control and estimation, model predictive control, distributed control and switched systems, with application in different fields including biomedical engineering.

Frank Allgöwer studied Engineering Cybernetics and Applied Mathematics in Stuttgart and at the University of California, Los Angeles (UCLA), respectively, and received his Ph.D. degree from the University of Stuttgart in Germany. Since 1999 he is the Director of the Institute for Systems Theory and Automatic Control and professor at the University of Stuttgart. His research interests include networked control, cooperative control, predictive control, and nonlinear control with application to a wide range of fields including systems biology. For the years 2017–2020 Frank serves as President of the International Federation of Automatic Control (IFAC) and since 2012 as Vice President of the German Research Foundation DFG.

^☆: The authors thank the German Research Foundation (DFG) for support of this work within grant AL 316/11-1 and within the Research Training Group Soft Tissue Robotics (GRK 2198/1). The material in this paper was not presented at any conference. This paper was recommended for publication in revised form by Associate Editor Giancarlo Ferrari-Trecate under the direction of Editor Ian R. Petersen.

¹: The feasibility recovery scheme described in Kögel and Findeisen (2014) to obtain a (dynamically) feasible solution is comparable to the definition of the consolidated trajectory.

²: This would not hold, if we would use $W_{0} \times \dots \times W_{k - 1}$ for the definition of the $k$ -step support function, compare Remark 7.

³: The minimization can be further decoupled along the time axis with the variables $y_{i, k} = [v_{i} (k | t), z_{i} (k | t)]$ , compare (Ferranti & Keviczky, 2015).

⁴: The following properties remain valid if the initialization $μ^{0}$ satisfies ${‖ μ^{0} - μ^{*} ‖}_{W} \leq {‖ μ^{*} ‖}_{W}$ .

⁵: To improve the numerical conditioning, we set $\tilde{u} = 10 \cdot u$ .

View Abstract

[1] Chisci et al., 2001
Chisci Luigi, Rossiter J Anthony, Zappa Giovanni
Systems with persistent disturbances: predictive control with restricted constraints
Automatica, 37 (2001), pp. 1019-1028
View PDF View article View in Scopus Google Scholar

[2] Conte et al., 2016
Conte Christian, Jones Colin N, Morari Manfred, Zeilinger Melanie N
Distributed synthesis and stability of cooperative distributed model predictive control for linear systems
Automatica, 69 (2016), pp. 117-125
View PDF View article View in Scopus Google Scholar

[3] Conte et al., 2013
Conte Christian, Zeilinger Melanie N, Morari Manfred, Jones Colin N
Robust distributed model predictive control of linear systems
Proc. European control Conf. (ECC) (2013), pp. 2764-2769
Crossref View in Scopus Google Scholar

[4] Doan et al., 2011
Doan Minh Dang, Keviczky Tamás, Schutter Bart De
A distributed optimization-based approach for hierarchical model predictive control of large-scale systems with coupled dynamics and constraints
Proc. 50th IEEE Conf. Decision and control (CDC) (2011), pp. 5236-5241
Crossref View in Scopus Google Scholar

[5] Ferranti and Keviczky, 2015
Ferranti Laura, Keviczky Tamás
A parallel dual fast gradient methodfor MPC applications
Proc. 54th IEEE Conf. Decision and control (CDC) (2015), pp. 2406-2413
Crossref View in Scopus Google Scholar

[6] Giselsson and Rantzer, 2014
Giselsson Pontus, Rantzer Anders
On feasibility, stability and performance in distributed model predictive control
IEEE Transactions on Automatic Control, 59103 (2014), pp. 1-1036
Google Scholar

[7] Grüne and Pannek, 2017
Grüne Lars, Pannek Jürgen
Nonlinear model predictive control
Springer (2017)
Google Scholar

[8] Kögel and Findeisen, 2012
Kögel Markus, Findeisen Rolf
Cooperative distributed MPC using the alternating direction multiplier method
Proc. 8th IFAC symposium on advanced control of chemical processes (2012), pp. 445-450
View PDF View article View in Scopus Google Scholar

[9] Kögel and Findeisen, 2014
Kögel Markus, Findeisen Rolf
Stabilization of inexact MPC schemes
Proc. 53rd IEEE Conf. Decision and control (CDC) (2014), pp. 5922-5928
Crossref View in Scopus Google Scholar

[10] Köhler et al., 2018a
Köhler Johannes, Müller Matthias A, Allgöwer Frank
Inexact distributed model predictive control - recursive feasibility under inexact dual optimization
Tech. rep, University of Stuttgart (2018)
Google Scholar

[11] Köhler et al., 2018b
Köhler Johannes, Müller Matthias A, Allgöwer Frank
A novel constraint tightening approach for nonlinear robust model predictive control
Proc. American control Conf. (ACC) (2018), pp. 728-734
Crossref View in Scopus Google Scholar

[12] Köhler et al., 2017
Köhler Johannes, Müller Matthias A, Li Na, Allgöwer Frank
Real time economic dispatch for power networks: A distributed economic model predictive control approach
Proc. 56th IEEE Conf. Decision and control (CDC) (2017), pp. 6340-6345
View in Scopus Google Scholar

[13] Maestre et al., 2014
Maestre José M, Negenborn Rudy R, et al.
Distributed model predictive control made easy
Springer (2014)
Google Scholar

[14] Müller and Allgöwer, 2017
Müller Matthias A, Allgöwer Frank
Economic and distributed model predictive control: Recent developments in optimization-based control
SICE J. of Control, Measurement, and System Integration, 10 (2017), pp. 39-52
Crossref Google Scholar

[15] Necoara et al., 2015
Necoara Ion, Ferranti Laura, Keviczky Tamás
An adaptive constraint tightening approach to linear model predictive control based on approximation algorithms for optimization
Optimal Control Applications & Methods, 36 (2015), pp. 648-666
Crossref View in Scopus Google Scholar

[16] Necoara and Nedelcu, 2015
Necoara Ion, Nedelcu Valentin
On linear convergence of a distributed dual gradient algorithm for linearly constrained separable convex problems
Automatica, 55 (2015), pp. 209-216
View PDF View article View in Scopus Google Scholar

[17] Necoara and Suykens, 2008
Necoara Ion, Suykens JohanAK
Application of a smoothing technique to decomposition in convex optimization
IEEE Transactions on Automatic Control, 53 (2008), pp. 2674-2679
View in Scopus Google Scholar

[18] Rawlings and Mayne, 2009
Rawlings James B, Mayne David Q
Model predictive control: Theory and design
Nob Hill Pub (2009)
Google Scholar

[19] Rubagotti et al., 2014
Rubagotti Matteo, Patrinos Panagiotis, Bemporad Alberto
Stabilizing linear model predictive control under inexact numerical optimization
IEEE Transactions on Automatic Control, 59 (2014), pp. 1660-1666
View in Scopus Google Scholar

[20] Scokaert et al., 1999
Scokaert Pierre OM, Mayne David Q, Rawlings James B
Suboptimal model predictive control (feasibility implies stability)
IEEE Transactions on Automatic Control, 44 (1999), pp. 648-654
View in Scopus Google Scholar

[21] Stewart et al., 2010
Stewart Brett T, Venkat Aswin N, Rawlings James B, Wright Stephen J, Pannocchia Gabriele
Cooperative distributed model predictive control
Systems & Control Letters, 59 (2010), pp. 460-469
View PDF View article View in Scopus Google Scholar

[22] Trodden, 2016
Trodden Paul
A one-step approach to computing a polytopic robustpositively invariant set
IEEE Transactions on Automatic Control, 61 (12) (2016), pp. 4100-4105
View in Scopus Google Scholar

Brief paperDistributed model predictive control—Recursive feasibility under inexact dual optimization☆

Abstract

Keywords

1. Introduction

Related work

Contribution

Outline

2. Distributed model predictive control

Notation

2.1. Problem setup

2.2. Distributed (dual) optimization

3. Inexact distributed MPC

3.1. Inexact MPC and constraint tightening

3.2. Feasible consolidated trajectory

3.3. Recursive feasibility under inexact minimization

3.4. Closed-loop stability

3.5. Dual distributed optimization

3.6. Comments

4. Numerical example

Offline computation

Simulations — stability and dual initialization

5. Conclusion

Acknowledgments

References

Brief paper
Distributed model predictive control—Recursive feasibility under inexact dual optimization☆