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
卷 102，2019 年 4 月，页码 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.
我们提出了一种新颖的模型预测控制（MPC）公式，确保在不精确的对偶优化下的递归可行性、稳定性和性能。对偶优化算法提供了一种可扩展的解决方案，因此可以应用于大型分布式系统。由于通信限制或计算能力有限，大多数实时 MPC 应用必须处理不精确的最小化问题。我们提出了一种受鲁棒 MPC 启发的修改优化问题，尽管存在不精确的对偶最小化，但仍提供理论保证。该方法不依赖于任何特定的优化算法，而是假设可行的优化问题可以在有界的次优性和约束违反下得到解决。结合分布式对偶梯度方法，我们获得了所需在线迭代次数的先验上界。通过基准数值示例展示了该方法的设计和实用性。

Keywords 关键词

Predictive control

Control of constrained systems

Large scale systems

Distributed dual optimization

预测控制受限系统的控制大规模系统分布式双重优化

1. Introduction 1. 引言

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.
模型预测控制（MPC）是一种成熟的控制方法，可用于控制复杂的动态系统并保证约束满足（Rawlings & Mayne, 2009）。使用 MPC 控制系统的主要限制之一来自计算问题，因为在每个时间步都必须解决一个优化问题。为了将 MPC 应用于大规模系统，我们必须考虑分布式方法，这属于分布式 MPC（DMPC）的范畴（Maestre et al., 2014，Müller 和 Allgöwer，2017）。如果我们希望促进 DMPC 在快速（物理上）互联网络中的应用，通常需要具有可扩展性的分布式优化算法，并对所需迭代次数进行限制。

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.
双重优化算法，如交替方向乘子法（ADMM）、双重梯度方法和近端分解，已被研究用于在线解决 DMPC 优化问题（Kögel 和 Findeisen，2012 年；Necoara 和 Nedelcu，2015 年；Necoara 和 Suykens，2008 年）。虽然这些算法实现了完全分布式的实施并渐近收敛到最优中心解，但实时要求导致了提前终止和不精确解。与原始分解方法（Stewart、Venkat、Rawlings、Wright 和 Pannocchia，2010 年）相反，这些基于双重优化的不精确解不一定满足 MPC 优化问题中提出的约束（动态、状态和输入约束）。这需要额外的修改以确保所得到的 MPC 方案的递归可行性和稳定性。

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.
在 Giselsson 和 Rantzer（2014）中，研究了没有终端约束的 DMPC，并提出了一种基于候选解的分布式迭代的充分停止条件。对于这种方法，无法给出所需迭代次数的先验界限。

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.
在 Kögel 和 Findeisen（2014）中，研究了一种在动态等式约束中存在约束违反的原始优化算法。通过适当的状态和输入约束收紧，确保了递归可行性。

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.
在 Necoara、Ferranti 和 Keviczky（2015）以及 Rubagotti、Patrinos 和 Bemporad（2014）中，由于不精确的对偶优化导致的不等式约束的约束违反通过适当的（常量或自适应）约束收紧来解决。通过使用浓缩形式（Necoara 等，2015）或将中间解投影到动态可行轨迹集（Rubagotti 等，2014），避免了所提出的动态等式约束中的约束违反。然而，这两种方法都不适合分布式大规模系统。

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.
在 Ferranti 和 Keviczky（2015）中，通过使用适当的约束收紧来考虑不等式约束和动态等式约束中的约束违反。通过自适应选择容差，从而确保递归可行性。因此，迭代次数可能会有所不同，并且需要全球通信以实现这种适应。在 Doan、Keviczky 和 Schutter（2011）中，类似的约束收紧被用于分布式层次模型预测控制方案。

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.
我们提出了一个新的框架，以确保由于有限的对偶迭代而导致的不精确分布式模型预测控制（DMPC）的递归可行性。该框架包括一个恒定的约束收紧和一个稳定控制器，受到鲁棒模型预测控制（MPC）（Chisci, Rossiter, & Zappa, 2001）的启发。为了避免过于保守的约束收紧，我们提出了一个修改后的优化问题，并采用了一个不同的候选解，明确考虑了不精确性。这提供了一种适用于不同 MPC 设置的一般程序。通过将该框架与对偶分布式梯度算法相结合，我们获得了确保递归可行性的对偶迭代次数的先验上界。与 Ferranti 和 Keviczky（2015）、Giselsson 和 Rantzer（2014）以及 Necoara 等（2015）相比，不需要自适应约束收紧。此外，与 Doan 等（2011）、Ferranti 和 Keviczky（2015）、Kögel 和 Findeisen（2014）以及 Rubagotti 等（2014）相比，不需要集中操作，从而允许对大规模系统进行完全分布式的实现。

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))

Outline 大纲

Cited by (22) 引用自 (22)

Figures (6) 图（6）

Automatica 自动化

Abstract 摘要

Keywords 关键词

1. Introduction 1. 引言

Related work 相关工作

Contribution 贡献

Outline

2. Distributed model predictive control

Notation

2.1. Problem setup

Rawlings & Mayne, 2009

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

Automatica 自动化

Brief paper 简短论文Distributed model predictive control—Recursive feasibility under inexact dual optimization☆分布式模型预测控制——不精确对偶优化下的递归可行性☆

Abstract 摘要

Keywords 关键词

1. Introduction 1. 引言

Related work 相关工作

Contribution 贡献

Outline

2. Distributed model predictive control

Notation

2.1. Problem setup

Rawlings & Mayne, 2009

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

Brief paper 简短论文
Distributed model predictive control—Recursive feasibility under inexact dual optimization☆
分布式模型预测控制——不精确对偶优化下的递归可行性☆