# A Reference Governor for Overshoot Mitigation of Tracking Control Systems

C. Freiheit, D. M. Anand, H. R. Ossareh C. Freiheit and H. R. Ossareh are with
the University of Vermont, Burlington, VT, 05405 USA, e-mail:
{collin.freiheit<EMAIL_ADDRESS>M. Anand is with the National
Institute of Standards and Technology, USA, e-mail<EMAIL_ADDRESS>
(August 2019)

###### Abstract

This paper presents a novel reference governor scheme for overshoot mitigation
in tracking control systems. Our proposed scheme, referred to as the Reference
Governor with Dynamic Constraint (RG-DC), recasts the overshoot mitigation
problem as a constraint management problem. The outcome of this reformulation
is a dynamic Maximal Admissible Set (MAS), which varies in real-time as a
function of the reference signal and the tracking output. The RG-DC employs
the dynamic MAS to modify the reference signal to mitigate or, if possible,
prevent overshoot. We present several properties of the dynamic MAS and the
algorithms required to compute it. We also investigate the stability and
recursive feasibility of the RG-DC, and present an interesting property of RG-
DC regarding its effect on the governed system’s frequency response.
Simulation results demonstrate the efficacy of the approach, and also
highlight its limitations. This paper serves as an extension of our earlier
paper on this topic.

###### Index Terms:

Overshoot mitigation, Reference governor, Constraint management, Maximal
admissible set, Linear systems

##  I Introduction

Overshoot in closed-loop control systems is often an undesired phenomenon. For
example, position overshoot in servo controlled robots may result in
collisions, and in regulated electronic power converters, overshoot may cause
overload currents. Surprisingly, there are very few methods available in the
literature of control systems dedicated to overshoot mitigation. One obvious
solution is feedforward plant inversion [1, 2], wherein a pre-filter is used
to eliminate the overshoot resulting from the underdamped and/or zero dynamics
of the closed-loop system. However this strategy requires an exact model of
the plant, which is not always available. Additionally, a stable non-minimum
phase system poses the problem of system destabilization upon plant inversion.
Another strategy is to use a detuned or a more complex controller within the
loop; however, this approach has the downside of slowing down the system,
increasing its complexity, or not being able to handle variability in the
plant dynamics. Furthermore, this approach may not be applicable to off-the-
shelf products or systems with legacy controllers. Other overshoot mitigation
solutions in the literature include a cascade control scheme coupled with a
sliding mode controller [3], and a feedback gain design method based on
quantifier elimination [4]. These solutions either require an accurate model
of the plant or increase the complexity of the inner loop. In this paper, we
propose a novel overshoot mitigation strategy using the Reference Governor
(RG) framework. Unlike the existing methods in the literature, the proposed
strategy does not require modifications to the controller within the closed-
loop system, does not require model inversion, and can be made robust to
modeling errors.

To provide a brief background, RG [5, 6, 7, 8, 9, 10, 11, 12, 13] is a
predictive control strategy that, similar to Model Predictive Control (MPC)
[14], employs a prediction of the evolution of the system state to enforce
pre-specified constraints on the inputs, states, or the outputs. Unlike MPC,
however, RG modifies the reference to a pre-stabilized closed-loop control
system and is primarily intended for constraint management. Moreover, RG is
more numerically efficient than MPC, which makes it attractive for real-time
control of fast processes. A block diagram of a closed-loop system controlled
by a RG is depicted in Fig. 1. RG employs the so-called Maximal Admissible Set
(MAS) [15], which characterizes the set of all initial conditions and inputs
that satisfy the constraints for all time. The MAS is computed offline,
allowing the RG to enforce the constraints in real-time by solving a linear
program subject to state and input values belonging to the MAS.

Reference Governor Closed-Loop System $r(t)$$v(t)$$y(t)$$x(t)$ Figure 1:
Reference governor block diagram.

Traditional RG theory can only handle static constraints (i.e., constraints
that do not vary with time). In this paper, we cast overshoot as a dynamic
(i.e., time-varying) constraint on the tracking output (denoted by $y_{tr}$
hereafter) of the system. Specifically, if $y_{tr}(t)$ is above $r(t)$, we
wish to maintain $y_{tr}$ above $r(t)$ for all future time. Similarly, if
$y_{tr}(t)$ is below $r(t)$, we wish to hold $y_{tr}$ below $r(t)$ for all
future time. To accomplish this in the framework of the reference governor, we
define the constraint set $\\{y\mathrel{\mathop{\mathchar 58\relax}}y\leq
r(t)\\}$ whenever $y_{tr}(t)\leq r(t)$, and by the set
$\\{y\mathrel{\mathop{\mathchar 58\relax}}y\geq r(t)\\}$ whenever
$y_{tr}(t)>r(t)$. This dynamically-varying constraint leads to a novel,
dynamically-varying MAS. We present a unique modification of the RG theory to
allow it to handle such dynamic MAS. We call this RG solution the Reference
Governor with Dynamic Constraint (RG-DC).

The dynamic nature of the MAS and our RG-DC formulation raise the following
questions:

  1. 1.

Does the number of inequalities required to describe the dynamic MAS change as
the reference varies in real-time?

  2. 2.

What is the geometric and algebraic relationship between the instances of the
dynamic MAS at different times?

  3. 3.

Does the RG-DC guarantee constraint satisfaction for all time?

  4. 4.

Can the RG-DC destabilize the control loop?

  5. 5.

How much additional computational complexity does the RG-DC introduce compared
to the standard RG?

  6. 6.

How can the RG-DC be made robust to model uncertainty and unknown
disturbances?

All of these questions will be addressed in this paper. To summarize, the
original contributions of this paper are a new approach (RG-DC) to mitigate
overshoot in closed-loop control systems, and the analysis and demonstration
of the six questions raised above. Additionally, we reveal an interesting
property of RG-DC regarding its effect on the governed system’s frequency
response. Specifically, the RG-DC can act as a novel nonlinear filter to
eliminate resonance in closed-loop systems caused by underdamped poles and/or
zero dynamics.

Note that reference [16] investigates a RG solution for systems with slowly-
varying constraints. However, the results of [16] are not applicable to our
problem because the dynamic constraint considered in our paper may vary
rapidly. Furthermore, similar to our paper, reference [17] briefly considers
overshoot mitigation in the framework of RG, but it does not provide a
rigorous answer to the questions raised above.

This paper is an extended version of our earlier IEEE L-CSS publication [18].
Furthermore, this paper corrects a small error in the L-CSS publication which
is explained in the footnote of page $3$.

##  II Review of Reference Governors

Consider Fig. 1, in which the “closed-loop system” is described by the single-
input multi-output discrete-time, stable linear system:

$\displaystyle x(t+1)=Ax(t)+Bv(t)$ $\displaystyle y(t)=Cx(t)+Dv(t)$

where the output $y$ is subject to the following polyhedral constraints:

$y(t)\in\mathbb{Y}\triangleq\\{y\mathrel{\mathop{\mathchar 58\relax}}Sy\leq
s\\}$ (1)

Vector inequalities here and throughout the paper are to be interpreted
element-wise. In general, the set in (1) may be unbounded. The RG employs the
so-called maximal admissible set (MAS), denoted by $O_{\infty}$, which is the
set of all states and control inputs that satisfy (1) for all time:

$O_{\infty}=\big{\\{}(x,v)\mathrel{\mathop{\mathchar 58\relax}}x(0)=x,\
v(t)=v,\ y(t)\in\mathbb{Y},\ \forall t\in\mathbb{Z}^{+}\big{\\}}$ (2)

As seen in (2), to construct MAS, $v(t)=v$ is held constant for all $t$. Using
this assumption, the evolution of the output $y(t)$ can be expressed
explicitly as a function of $x(0)=x$ and $v$:

$y(t)=CA^{t}x+\left(C(I-A^{t})(I-A)^{-1}B+D\right)v$ (3)

Therefore, MAS in (2) can be characterized by a polyhedron defined by an
infinite number of inequalities:

$\displaystyle O_{\infty}=\Big{\\{}(x,v)\mathrel{\mathop{\mathchar 58\relax}}$
(4) $\displaystyle SCA^{t}x+S\left(C(I-A^{t})(I-A)^{-1}B+D\right)v\leq s,\
\forall t\in\mathbb{Z}^{+}\Big{\\}}$

It is shown in [15] that, under mild assumptions on $C$ and $A$, it is
possible to make this set finitely determined (i.e., be described by a finite
number of inequalities) by constraining the steady-state value of $y$, denoted
by $y(\infty)$, to the interior of the constraint set:

$y(\infty)\triangleq\left(C(I-A)^{-1}B+D\right)v\in(1-\epsilon)\mathbb{Y}$ (5)

where $\epsilon\in\mathbb{R}^{+}$ is a small number. As shown in [15], after
introducing (5) in the MAS, there exists a finite prediction time $j^{*}$,
where the inequalities corresponding to all future prediction times
($t>j^{*}$) are redundant. The smallest such $j^{*}$ is referred to as the
admissibility index of the MAS.

Combining (4) and (5), we obtain an inner approximation of $O_{\infty}$,
denoted by $\widetilde{O}_{\infty}$, which can be represented by:

$\widetilde{O}_{\infty}=\Big{\\{}(x,v)\mathrel{\mathop{\mathchar
58\relax}}H_{x}x+H_{v}v\leq h\Big{\\}}$ (6)

where the matrices $H_{x}$, $H_{v}$, and $h$ are finite dimensional. Note that
$h$ is a vector with all elements equal to $s$, except the first block of
rows, which is $(1-\epsilon)s$. To numerically construct $H_{x},\ H_{v}$ and
$h$, we begin with the steady-state inequality in (5) and iteratively add the
inequalities in (4) starting with $t=0$. After each $t$, we check if the newly
added rows are all redundant. If this is so, $j^{*}$ has been reached and the
construction of $\widetilde{O}_{\infty}$ is complete.

We now review the algorithm provided in [15] to check for redundancy. This
algorithm is leveraged in Section III for the analysis of our dynamic MAS.
Given any polyhedron defined by $Mz\leq N$ and a scalar inequality given by
$c^{T}z\leq d$, to determine if the inequality is redundant with respect to
the polyhedron, it is common practice to solve the following linear program
(LP) [15]:

$f=\max\ c^{T}z\quad\mathrm{subject\ to}\quad Mz\leq N$ (7)

If $f\leq d$, the new inequality is redundant. To apply this idea to MAS,
suppose MAS has been partially constructed with the inequalities in (5) and
(4) from $t=0$ up to $t=j$, for some $j$. Let $H_{x}$, $H_{v}$, $h$ represent
the matrices of this partially constructed MAS. We wish to test whether an
inequality in (4) with $t=j+1$ is redundant. The LP above can be used for this
purpose, with $M=[H_{x},H_{v}]$, $N=h$, $z=(x,v)$, and $c^{T}$ and $d$
representing the inequality being tested for redundancy.

The final step in the RG is to select an optimal control input that will not
cause a constraint violation. The RG update law that achieves this is:

$v(t)=v(t-1)+\kappa\left(r(t)-v(t-1)\right)$ (8)

where $\kappa\in[0,1]$. To select $\kappa$, we solve the following linear
program:

$\displaystyle\underset{\kappa\in[0,1]}{\text{maximize}}$
$\displaystyle\mathrm{\kappa}$ (9) s.t. $\displaystyle
v(t)=v(t-1)+\kappa\left(r(t)-v(t-1)\right)$ $\displaystyle\left(x(t),\
v(t)\right)\in\widetilde{O}_{\infty}$

where $x(t)$, $r(t)$, and $v(t-1)$ are known parameters at time $t$. If
$\kappa=0$, the control command from the previous timestep is maintained to
avoid constraint violation, and if $\kappa=1$, the reference $r(t)$ is
feasible and, therefore, $v(t)=r(t)$.

##  III Reference Governor with Dynamic Constraint (RG-DC)

Consider the asymptotically stable system

$\displaystyle x(t+1)$ $\displaystyle=Ax(t)+Bv(t)$ (10) $\displaystyle
y_{tr}(t)$ $\displaystyle=C_{tr}x(t)+D_{tr}v(t)$ $\displaystyle y_{st}(t)$
$\displaystyle=C_{st}x(t)+D_{st}v(t)$

with DC gain from $v$ to $y_{tr}$ equal to $1$, where $y_{tr}\in\mathbb{R}$ is
the tracking output on which we wish to enforce the dynamic overshoot
constraint (as explained below). Additionally, $y_{st}\in\mathbb{R}^{p}$
refers to constrained outputs, on which we wish to enforce standard static
constraints:

$\displaystyle
y_{st}(t)\in\mathbb{Y}_{st}\triangleq\\{y\mathrel{\mathop{\mathchar
58\relax}}S_{st}y\leq s_{st}\\}$ (11)

It should be noted that, because $y_{tr}$ is the output of the plant within
the closed-loop system, there is no feedforward from $v$ to $y_{tr}$ in
practice. Thus, for the remainder of the paper, we assume that $D_{tr}=0$.
Note however that $D_{st}$ is allowed to be non-zero because static
constraints could be imposed on controller states or the controller output,
which may require feedthrough.

For overshoot mitigation, we impose that $y_{tr}$ be constrained by the
reference $r$, which may vary with time. To do so, two cases must be
considered: the first case is where $y_{tr}(t)\leq r(t)$ at the current time
$t$, for which we define overshoot by the following condition: $\exists k>t$
such that $y_{tr}(k)>r(t)$. Thus, to prevent overshoot, we must enforce the
following constraint: $y_{tr}(k)\in\\{y\mathrel{\mathop{\mathchar
58\relax}}y\leq r(t)\\}$ for all $k>t$. In the second case, $y_{tr}(t)>r(t)$
at the current time $t$, for which we define overshoot by $\exists k>t$ such
that $y_{tr}(k)<r(t)$ and the constraint by
$y_{tr}(k)\in\\{y\mathrel{\mathop{\mathchar 58\relax}}y\geq r(t)\\}$ for all
$k>t$. Note that we have chosen the constraint sets to be closed (i.e., the
inequalities are not strict), which is necessary to ensure that the linear
programs that arise in RG-DC are well-posed. The above leads to a time-varying
constraint set that depends on both $y_{tr}(t)$ and $r(t)$:

$\displaystyle\mathbb{Y}_{tr}(r(t),\
y_{tr}(t))\triangleq\begin{cases}\\{y\mathrel{\mathop{\mathchar
58\relax}}y\leq r(t)\\}&y_{tr}(t)\leq r(t)\\\ \\{y\mathrel{\mathop{\mathchar
58\relax}}y\geq r(t)\\}&y_{tr}(t)>r(t)\\\ \end{cases}$ (12)

The goal is to enforce $y_{tr}(k)\in\mathbb{Y}_{tr}(r(t),\ y_{tr}(t))$ for all
$k>t$.

We now define the maximal admissible sets for this system. For the static
constraint in (11), we create MAS as discussed previously in Section II. We
denote this MAS by $O_{\infty,st}$. For the dynamic MAS, note that the second
constraint in (12) can be re-written as $\\{y\mathrel{\mathop{\mathchar
58\relax}}-y\leq-r(t)\\}$, which implies that both constraints in (12) can be
cast in the form (1), where $S$ takes on the values of $1$ or $-1$ and $s$
takes on the values of $r(t)$ or $-r(t)$. Therefore, the definition of MAS
remains the same as (2), with the exception that, since $\mathbb{Y}_{tr}$
depends on $r(t)$ and $y_{tr}(t)$, so does the MAS. We thus denote this
dynamic MAS by $O_{\infty,tr}\left(r(t),y_{tr}(t)\right)$. In Subsection
III-A, we analyze the properties and computation of this dynamic MAS.

The proposed reference governor scheme (RG-DC) employs the intersection of the
static MAS (for constraints on $y_{st}$) and the dynamic MAS (for constraints
on $y_{tr}$) to compute $\kappa$ from (9) and $v(t)$ from (8). We will discuss
the stability and recursive feasibility of the system with RG-DC, as well as
the implementation aspects, in Subsection III-B. We also discuss a robust
formulation of RG-DC to handle plant-model mismatch and unknown disturbances.

For simplicity, we assume that all states of the system are available for
feedback. If not, a set-based observer can be designed as is done in [19].

###  III-A Computational aspects and properties of the dynamic MAS

We first address the computation of the dynamic MAS defined above (the
computation of the static MAS is standard and will not be addressed). For this
investigation, we seek to develop a polyhedral characterization of the dynamic
MAS, parameterized on ${r(t)=r}$ and $y_{tr}(t)$.

First suppose that $r>0$ denoted $r^{+}$. We will relax this assumption later.
Now consider the inequalities in (4). Recall from above that $S$ takes on the
value of $1$ (in which case $s=r^{+}$), or $-1$ (in which case $s=-r^{+}$). If
$S=1$, the steady-state halfspace should be shrunk to:
$v\leq(1-\epsilon)r^{+}$ and the inequalities in (4) become:

$C_{tr}A^{t}x+C_{tr}(I-A^{t})(I-A)^{-1}Bv\leq r^{+}$ (13)

If $S=-1$, the steady-state halfspace should be shrunk to:
$v\geq(1+\epsilon)r^{+}$ and the inequalities in (4) become:

$C_{tr}A^{t}x+C_{tr}(I-A^{t})(I-A)^{-1}Bv\geq r^{+}$ (14)

A polyhedral representation of MAS constructed from the tightened steady-state
constraint $v\leq(1-\epsilon)r^{+}$ and the inequalities in (13) for all
$t\geq 0$ is given by:

$O_{\infty}^{-}(r^{+})=\Big{\\{}(x,v)\mathrel{\mathop{\mathchar
58\relax}}H_{x}x+H_{v}v\leq r^{+}h^{-}\Big{\\}}$ (15)

Similarly, a representation of MAS using (14) with the tightened steady-state
constraint $v\geq(1+\epsilon)r^{+}$ is:

$O_{\infty}^{+}(r^{+})=\Big{\\{}(x,v)\mathrel{\mathop{\mathchar
58\relax}}H_{x}x+H_{v}v\geq r^{+}h^{+}\Big{\\}}$ (16)

where $h^{-}$ and $h^{+}$ are vectors of all $1$s except the first block of
rows, which are $1-\epsilon$ and $1+\epsilon$, respectively111As mentioned in
the Introduction, this paper corrects a small error in the L-CSS publication
[18] involving the steady-state halfspaces of the dynamic MASs. In the L-CSS
publication, the steady state halfspace constraint for all dynamic MASs was
$(1-\epsilon)r$. This is problematic because $O^{+}_{\infty}(r)$ and
$O^{-}_{\infty}(r)$ from Cases $2$ and $3$ from Table III-A of [18] would not
necessarily be finitely determined because the steady-state halfspaces are not
being shrunk. In this paper we fix this problem by letting the steady-state
halfspaces of $O^{+}_{\infty}(r)$ and $O^{-}_{\infty}(r)$ from Cases $2$ and
$3$ from Table III-A of [18] have constraints of $(1+\epsilon)r$, making the
sets finitely determined. Note that all of the results (Lemmas, Propositions,
Theorem, and example) of the L-CSS publication still hold, we simply modify
the notation in this paper to distinguish between the cases of $(1-\epsilon)r$
and $(1+\epsilon)r$ for the steady-state halfspaces of the dynamic MAS.. Note
that in order to explicitly show the dependence of the sets on $r^{+}$, we
have formulated (15)-(16) with $r^{+}h^{-}$ and $r^{+}h^{+}$ on the right hand
sides (instead of simply $h$ as in (6)). For now, we consider
$H_{x},H_{v},h^{-},h^{+}$ as being infinite dimensional matrices (i.e., a
redundancy check was not performed when forming $O_{\infty}^{-}$ and
$O_{\infty}^{+}$). Since we know, from Section II, that both (15) and (16)
must be finitely determined for a fixed $r^{+}$, our goal now is to study the
admissibility index of these sets as functions of $r^{+}$.

Recall from Section II that to find the admissibility index of a MAS, we
construct it row by row and stop when redundancy is detected. Furthermore, to
detect redundancy, we use the linear program (LP) in (7). While redundancy can
be checked for $O_{\infty}^{-}(r^{+})$ using the same approach,
$O_{\infty}^{+}(r^{+})$ requires a LP of a different form. To formulate a LP
for $O_{\infty}^{+}(r^{+})$, we represent (16) in the form of (15), yielding
$-(H_{x}x+H_{v}v)\leq-r^{+}h^{+}$. Upon applying (7) to this inequality and
simplifying the resulting LP, we obtain the following adaptation of (7):

$f=\min\ c^{T}z\quad\mathrm{subject\ to}\quad Mz\geq N$ (17)

To proceed with our analysis of admissibility index, we first show, with
support of Lemma 1, that the individual admissibility indices of
$O_{\infty}^{-}(r^{+})$ and $O_{\infty}^{+}(r^{+})$ are unchanged for any
$r^{+}$.

######  Lemma 1.

Suppose the unique maximizer of

$\displaystyle\mathrm{max}\ c^{T}z\quad\mathrm{subject\ to}\quad Mz\leq N$
(18)

is given by $z^{*}$. Then, for any $\gamma\in\mathbb{R^{+}}$, the maximizer of

$\displaystyle\mathrm{max}\ c^{T}z\quad\mathrm{subject\ to}\quad Mz\leq\gamma
N$ (19)

is given by $\gamma z^{*}$. Furthermore, the optimal values of the objective
functions in (18) and (19) are given by $c^{T}z^{*}$ and $c^{T}\gamma z^{*}$.
That is, the optimal value of (19) is $\gamma$ times larger than that of (18).

###### Proof.

Given (18), we rewrite the constraint by multiplying both sides by $\gamma$:
$M(\gamma z)\leq\gamma N$. Furthermore, we can multiply the cost function by
$\gamma$, which is permitted because a positive scaling on the objective
function of a linear programming problem does not change the optimizer. We
thus obtain the equivalent linear program:

$\displaystyle\mathrm{max}\ c^{T}(\gamma z)\quad\mathrm{subject\ to}\quad
M(\gamma z)\leq\gamma N$

which has the same optimizer as (18) but a different objective function value.
Finally, we can perform a change of variable $\gamma z\rightarrow z$ to
transform this optimization into (19). It can be concluded that, if the
optimizer of (18) is $z^{*}$, the optimizer of (19) must be $\gamma z^{*}$.

∎

Noting that (7) and (18) are the same linear program, we can now apply the
results of Lemma 1 to the LP in (7) to show that admissibility index of
$O_{\infty}^{-}(r^{+})$ in (15) is unaffected by a positive scaling on $r^{+}$
(the same argument holds true for $O_{\infty}^{+}(r^{+})$ as well).
Specifically, suppose the redundancy of a new inequality $c^{T}z\leq r^{+}$ is
tested against the partially constructed MAS given by $Mz\leq N$, where
$M=[H_{x},\ H_{v}]$, $N=r^{+}h^{-}$, and $z=(x,\ v)$. From Lemma 1, scaling
$r^{+}$ by $\gamma\in\mathbb{R}^{+}$ (i.e., replacing $r^{+}$ with $\gamma
r^{+}$) scales the optimal solution of the LP by $\gamma$. However, the
constraint being tested for redundancy is also scaled by $\gamma$, which
implies that the redundancy of $c^{T}z\leq\gamma r^{+}$ is unaffected by
$\gamma$. Therefore, we conclude that the admissibility index of
$O_{\infty}^{-}(r^{+})$ is unaffected by a positive scaling on $r^{+}$.

Now assume $r<0$, denoted $r^{-}$. A polyhedral representation of MAS for the
case of $S=1$ is given by

$O_{\infty}^{-}(r^{-})=\Big{\\{}(x,v)\mathrel{\mathop{\mathchar
58\relax}}H_{x}x+H_{v}v\leq r^{-}h^{+}\Big{\\}}$ (20)

Note that we choose $h^{+}$ in (20) to ensure that the steady-state constraint
is indeed contracted. Similarly, a representation of MAS for the case of
$S=-1$ is:

$O_{\infty}^{+}(r^{-})=\Big{\\{}(x,v)\mathrel{\mathop{\mathchar
58\relax}}H_{x}x+H_{v}v\geq r^{-}h^{-}\Big{\\}}$ (21)

Using Lemma 1, we can conclude that the admissibility index of
$O_{\infty}^{-}(r^{-})$ in (20) is also unaffected by a positive scaling on
$r^{-}$ and that the same argument holds true for $O_{\infty}^{+}(r^{-})$ in
(21).

Now suppose that $r$ is allowed to be any non-zero real number. If $r$ changes
sign, the geometric properties of the MAS change (graphical argument presented
in Fig. 2), which in turn changes the linear programs in (7) and (17).

Figure 2: Two systems of linear inequalities in $\mathbb{R}^{2}$: constraints
are positive in the left plot and negative in the right plot.

However, with the help of Lemma 2 below, we prove that the admissibility index
of (15), is equivalent to the admissibility index of (21), and similarly that
the admissibility index of (16), is equivalent to the admissibility index of
(20).

######  Lemma 2.

suppose the maximizer of

$\displaystyle\mathrm{max}\ c^{T}z\quad\mathrm{subject\ to}\quad Mz\leq N$
(22)

is given by $z^{*}$. Then, the minimizer of

$\displaystyle\mathrm{min}\ c^{T}z\quad\mathrm{subject\ to}\quad Mz\geq-N$
(23)

is given by $-z^{*}$.

The proof for Lemma 2 is simple and follows similarly to Lemma 1, we thus omit
the proof. From Lemma 2, we can conclude that if the maximum value of the
objective function in (22) is $c^{T}z^{*}$, then the minimum of (23) is
$c^{T}(-z^{*})$. Applying this result to (15), we see that we will obtain the
same admissibility index as for (21). The same can be said between (16) and
(20).

If we combine the information presented in Lemmas 1 and 2, it follows that,
for a given $r$, $O_{\infty}^{+}$ and $O_{\infty}^{-}$ can both be uniquely
defined by only two representations of $H_{x},\ H_{v},$ and $h$, which is the
novel result of this subsection. This is summarized in Table III-A, where
superscripts + and - are used to denote the two possible representations. This
table also highlights the relationship between the dynamic MAS,
$O_{\infty,tr}\left(r(t),\ y_{tr}(t)\right)$, and the sets
$O_{\infty}^{-}(r^{+})$, $O_{\infty}^{+}(r^{+})$, $O_{\infty}^{-}(r^{-})$, and
$O_{\infty}^{+}(r^{-})$ in (15), (16), (20) , and (21) respectively.

| $\\{y_{tr}\leq r\\}$ | $\\{y_{tr}>r\\}$
---|---|---
$r=r^{+}>0$ | Case 1: $O_{\infty,tr}=O_{\infty}^{-}(r^{+})$ | Case 2: $O_{\infty,tr}=O_{\infty}^{+}(r^{+})$
Minimal representation: $\big{\\{}H_{x}^{-}x+H_{v}^{-}v\leq rh^{-}\big{\\}}$ |  Minimal representation: $\big{\\{}H_{x}^{+}x+H_{v}^{+}v\geq rh^{+}\big{\\}}$
$r=r^{-}<0$ | Case 3: $O_{\infty,tr}=O_{\infty}^{-}(r^{-})$ | Case 4: $O_{\infty,tr}=O_{\infty}^{+}(r^{-})$
Minimal representation: $\big{\\{}H_{x}^{+}x+H_{v}^{+}v\leq rh^{+}\big{\\}}$ |  Minimal representation: $\big{\\{}H_{x}^{-}x+H_{v}^{-}v\geq rh^{-}\big{\\}}$

TABLE I: The representation of the dynamic maximal admissible set.

Note that the MASs in Cases $1$ and $4$ share the same matrices
$H_{x}^{-},H_{v}^{-},h^{-}$. Similarly, the MASs in Cases $2$ and $3$ share
the same matrices $H_{x}^{+},H_{v}^{+},h^{+}$. Furthermore, these matrices are
constant and do not depend on the magnitude of $r$. Therefore, to construct
these matrices, we can make simplifying assumptions on $r$. Specifically, to
compute $H_{x}^{-},H_{v}^{-},h^{-}$, we can assume that $r=1$ and leverage the
standard methods presented in Section II. Similarly, to compute
$H_{x}^{+},H_{v}^{+},h^{+}$, we can assume that $r=-1$ and use the standard
methods.

Note that the only remaining case to consider is $r=0$. In this case, the
constraint on the steady state cannot be shrunk (because
$(1-\epsilon)r=(1+\epsilon)r=r$ when $r=0$), resulting in a MAS that may not
necessarily be finitely determined. We resolve this by approximating it by the
representation with the higher number of rows. This completes the answer to
the first question raised in the Introduction around the admissibility index
of the dynamic MAS.

We next study the geometric properties of the dynamic MAS as a function of $r$
using Propositions 1 and 2 below.

######  Proposition 1.

Let $O_{\infty}^{-}(r^{+})$, $O_{\infty}^{+}(r^{+})$, $O_{\infty}^{-}(r^{-})$
and $O_{\infty}^{+}(r^{-})$ be defined by (15), (16), (20), and (21)
respectively; and let $r_{1},\ r_{2}\in\mathbb{R}\setminus\\{0\\}$. Then, the
following holds. i) If $\frac{r_{1}}{r_{2}}>0$, then
$O_{\infty}^{-}(r_{1})=\frac{r_{1}}{r_{2}}O_{\infty}^{-}(r_{2})$ and
$O_{\infty}^{+}(r_{1})=\frac{r_{1}}{r_{2}}O_{\infty}^{+}(r_{2})$ ii) If
$\frac{r_{1}}{r_{2}}<0$, then
$O_{\infty}^{-}(r_{1})=\frac{r_{1}}{r_{2}}O_{\infty}^{+}(r_{2})$ and
$O_{\infty}^{+}(r_{1})=\frac{r_{1}}{r_{2}}O_{\infty}^{-}(r_{2})$

###### Proof.

For clarity throughout the proof, let superscripts + (positive) and -
(negative) denote the signs of $r_{1}$ and $r_{2}$. We prove case $i$) and
$ii$) for $O_{\infty}^{-}(r_{1}^{+})$; the rest of the cases can be proven
similarly. $i$) Let $(x,v)\in O_{\infty}^{-}(r_{1}^{+})$. Then, it follows
from (15) that $\displaystyle H_{x}x+H_{v}v\leq r_{1}^{+}h^{-}\quad$
$\displaystyle\Longleftrightarrow$
$\displaystyle\frac{r_{2}^{+}}{r_{1}^{+}}\left(H_{x}x+H_{v}v\right)\leq\frac{r_{2}^{+}}{r_{1}^{+}}\left(r_{1}^{+}h^{-}\right)$
$\displaystyle\Longleftrightarrow$ $\displaystyle
H_{x}\left(\frac{r_{2}^{+}}{r_{1}^{+}}x\right)+H_{v}\left(\frac{r_{2}^{+}}{r_{1}^{+}}v\right)\leq
r_{2}^{+}h^{-}\quad$ $\displaystyle\Longleftrightarrow$
$\displaystyle\frac{r_{2}^{+}}{r_{1}^{+}}\left(x,v\right)\in
O_{\infty}^{-}(r_{2}^{+})$ $\displaystyle\Longleftrightarrow$
$\displaystyle(x,v)\in\frac{r_{1}^{+}}{r_{2}^{+}}O_{\infty}^{-}(r_{2}^{+})$

$ii$) Let $(x,v)\in O_{\infty}^{-}(r_{1}^{+})$. Then, it follows from (15)
that

$\displaystyle H_{x}x+H_{v}v\leq r_{1}^{+}h^{-}\quad$
$\displaystyle\Longleftrightarrow$
$\displaystyle\frac{r_{2}^{-}}{r_{1}^{+}}\left(H_{x}x+H_{v}v\right)\geq\frac{r_{2}^{-}}{r_{1}^{+}}\left(r_{1}^{+}h^{-}\right)$
$\displaystyle\Longleftrightarrow$ $\displaystyle
H_{x}\left(\frac{r_{2}^{-}}{r_{1}^{+}}x\right)+H_{v}\left(\frac{r_{2}^{-}}{r_{1}^{+}}v\right)\geq
r_{2}^{-}h^{-}\quad$ $\displaystyle\Longleftrightarrow$
$\displaystyle\frac{r_{2}^{-}}{r_{1}^{+}}\left(x,v\right)\in
O_{\infty}^{+}(r_{2}^{-})$ $\displaystyle\Longleftrightarrow$
$\displaystyle(x,v)\in\frac{r_{1}^{+}}{r_{2}^{-}}O_{\infty}^{+}(r_{2}^{-})$

The remaining $6$ cases O_∞^-(r_1^-), O_∞^+(r_1^+), O_∞^+(r_1^-) for both i)
and ii) can be proven similarly. Furthermore, the reverse direction of each
case can be proven. ∎ Proposition 1 sheds light on the geometric relationship
between $O_{\infty}^{+}$ and $O_{\infty}^{-}$. For example, for positive
values of $r$, $O_{\infty}^{-}(r)$ is scaled radially from the origin as $r$
varies.

Another important result, which ties into recursive feasibility of the RG-DC
as addressed in Subsection III-B, is as follows.

######  Proposition 2.

Suppose $r_{2}\geq r_{1}$, then $O_{\infty}^{-}(r_{1})\subseteq
O_{\infty}^{-}(r_{2})$. Similarly, if $r_{2}\leq r_{1}$, then
$O_{\infty}^{+}(r_{1})\subseteq O_{\infty}^{+}(r_{2})$.

###### Proof.

We prove the first statement of Proposition 2. The second statement follows
similarly. Let $r_{2}\geq r_{1}$, and $(x,v)\in O_{\infty}^{-}(r_{1})$. We
first consider the case where $r_{1}\geq 0$, denoted $r_{1}^{+}$, and where
$r_{2}\geq 0$, denoted $r_{2}^{+}$. From (15), it is true that
$H_{x}x+H_{v}v\leq r_{1}^{+}h^{-}$. Therefore, because $r_{2}^{+}h^{-}\geq
r_{1}^{+}h^{-}$, $H_{x}x+H_{v}v\leq r_{2}^{+}h^{-}$. From here it can be
concluded that any $(x,v)\in O_{\infty}^{-}(r_{1}^{+})$ also belongs to
$O_{\infty}^{-}(r_{2}^{+})$. Therefore, $O_{\infty}^{-}(r_{1}^{+})\subseteq
O_{\infty}^{-}(r_{2}^{+})$. Now let us consider the case where $r_{1}\leq 0$,
denoted $r_{1}^{-}$, and where $r_{2}\geq 0$, denoted $r_{2}^{+}$. Clearly,
$r_{2}^{+}\geq r_{1}^{-}$. Let $(x,v)\in O_{\infty}^{-}(r_{1}^{-})$. From
(20), it is true that $H_{x}x+H_{v}v\leq r_{1}^{-}h^{+}$. Therefore, because
$r_{2}^{+}h^{-}\geq r_{1}^{-}h^{+}$, $H_{x}x+H_{v}v\leq r_{2}^{+}h^{-}$. From
here it can be concluded that any $(x,v)\in O_{\infty}^{-}(r_{1}^{-})$ also
belongs to $O_{\infty}^{-}(r_{2}^{+})$. Therefore,
$O_{\infty}^{-}(r_{1}^{-})\subseteq O_{\infty}^{-}(r_{2}^{+})$. Finally, we
consider the case where $r_{1}\leq 0$, denoted $r_{1}^{-}$, and where
$r_{2}\leq 0$, denoted $r_{2}^{-}$. From (20), it is true that
$H_{x}x+H_{v}v\leq r_{1}^{-}h^{+}$. Therefore, because $r_{2}^{-}h^{+}\geq
r_{1}^{-}h^{+}$, $H_{x}x+H_{v}v\leq r_{2}^{-}h^{+}$. From here it can be
concluded that any $(x,v)\in O_{\infty}^{-}(r_{1}^{-})$ also belongs to
$O_{\infty}^{-}(r_{2}^{-})$. Therefore, $O_{\infty}^{-}(r_{1}^{-})\subseteq
O_{\infty}^{-}(r_{2}^{-})$. The three cases for the second statement of
Proposition 2, regarding $r_{2}\leq r_{1}$, can be proven similarly.

∎

Note that $O_{\infty}^{-}(r_{1})\not\subseteq O_{\infty}^{-}(r_{2})$ if
$r_{2}<r_{1}$, and $O_{\infty}^{+}(r_{1})\not\subseteq O_{\infty}^{+}(r_{2})$
if $r_{2}>r_{1}$. This result implies that, while the dynamic MAS is
positively invariant for a fixed $r$, it may not be positively invariant if
$r$ varies over time (conditions for positive invariance under time-varying
$r$ are given in Proposition 2). The implication of this in terms of
constraint management will be discussed in the next subsection. The above two
propositions provide the answer to the second question raised in the
Introduction around the geometric properties of the dynamic MAS.

###  III-B Computational aspects and properties of RG-DC

To implement the RG-DC, the values of $y_{tr}(t)$ and $r(t)$ are used at every
timestep to determine the appropriate MAS from Table III-A. This MAS is then
employed in (9) to calculate $\kappa$. We denote the resulting solution by
$\kappa_{tr}$. If static constraints are also imposed on the system, we
compute (9) separately with $O_{\infty,st}$, yielding $\kappa_{st}$. The RG-DC
then chooses the minimum of $\\{\kappa_{tr},\kappa_{st}\\}$ and applies the
solution to (8) to compute $v(t)$.

As discussed in the previous subsection, the dynamic MAS may or may not be
positively invariant if $r$ changes in real-time (conditions for positive
invariance were provided in Proposition 2). This implies that the LP in (9)
may be infeasible, which means that $\kappa_{tr}$ may not exist. The
traditional reference governor handles this situation by forcing $\kappa$ to
be 0 (i.e., $v(t)=v(t-1)$). RG-DC handles infeasibilities in the same manner.
Specifically, if at the current timestep the LP in (9) is infeasible, we set
$\kappa=0$. In such cases, overshoot is not preventable. However, we maintain
$\kappa_{tr}\in[0,1]$ in our RG-DC formulation to assure stability at the
expense of overshoot mitigation performance. We demonstrate a scenario where
the RG-DG forces $\kappa=0$ in Section IV.

We discuss the stability of RG-DC in Theorem 1 below.

######  Theorem 1.

The RG-DC loop is BIBO stable, and for a constant $r$, $v$ converges to a
constant.

###### Proof.

From (8), and with $\kappa\in[0,1]$, it follows that $v(t)$ is a convex
combination of $r(t)$ and $v(t-1)$, both of which are bounded. Therefore,
$v(t)$ is bounded. Boundedness of $v(t)$ and asymptotic stability of (10)
imply BIBO stability of the system. Furthermore, $v(t)$ forms a monotonic
sequence bounded by $r$, which implies convergence. ∎

Note that this result is similar to the stability result of the standard RG.
However, we present it formally to reinforce the claim that, like the RG, the
RG-DC is BIBO stable.

The computational complexity of the RG-DC is similar to that of the standard
RG with an additional constraint on the tracking output. Note that the
additional logic introduced to determine the MAS characterization from Table
III-A is negligible when compared to the processing times associated with the
calculation of $\kappa$ in (9). The RG-DC is also comparable to the RG in
terms of memory requirements.

Finally, note that external disturbances, model uncertainty, and plant
variability can be naturally incorporated in the RG-DC framework. This is
done, similar to standard RG, by “robustifying” (i.e., shrinking) the MAS
using the ideas from Pontryagin subtraction (P-subtraction) [6] and polytopic
uncertainties [20]. We will show an example of this in the next section.

The above analyses provide complete answers to questions 3 – 6 raised in the
Introduction around the properties of RG-DC.

We now present the RG-DC algorithm (see Algorithm III-B), which can be used to
enforce overshoot mitigation constraints using $O_{\infty,tr}$ and static
constraints using $O_{\infty,st}$. In preparation for Algorithm III-B, assume
that the two representations of the dynamic MAS, namely
$H_{x}^{-},H_{v}^{-},h^{-}$ and $H_{x}^{+},H_{v}^{+},h^{+}$, have been
calculated. Let $H_{x,tr},H_{v,tr},h_{tr}$ be the representation with the
larger number of rows, where $h_{tr}$ is a vector of all $1$s. Additionally,
let $H_{x,st},H_{v,st},h_{st}$ denote the matrices that define
$O_{\infty,st}$. The RG-DC algorithm is as follows:

Algorithm 1 RG-DC

Inputs:

$y(t),r(t),x(t),v(t-1),H_{x,tr},H_{v,tr},h_{tr},H_{x,st},H_{v,st},h_{st},\epsilon$
Output: $v(t)$

1: if $y_{tr}(t)\leq r(t)$ then

2: if $r(t)>0$ then

3: first row of $h_{tr}=(1-\epsilon)$

4: else

5: first row of $h_{tr}=(1+\epsilon)$

6: end if

7: for $j$ = each row in $0_{\infty,tr}$ do

8: $n=h_{tr}(j)r(t)-H_{x,tr}(j)x(t)-H_{v,tr}(j)v(t-1)$

9: $d=H_{v,tr}(j)(r(t)-v(t-1))$

10: $\kappa(j)=\mathrm{kappa}(n,d)$

11: end for

12: else

13: if $r(t)>0$ then

14: first row of $h_{tr}=(1+\epsilon)$

15: else

16: first row of $h_{tr}=(1-\epsilon)$

17: end if

18: for $j$ = each row in $0_{\infty,tr}$ do

19: $n=-h_{tr}(j)r(t)+H_{x,tr}(j)x(t)+H_{v,tr}(j)v(t-1)$

20: $d=-H_{v,tr}(j)(r(t)-v(t-1))$

21: $\kappa(j)=\mathrm{kappa}(n,d)$

22: end for

23: end if

24: $\kappa_{tr}=\mathrm{min}(\kappa)$

25: if there are any static constraints then

26: use standard RG algorithm with $O_{\infty,st}$ to obtain $\kappa_{st}$

27: else

28: $\kappa_{st}=1$

29: end if

30: $\kappa^{*}=\mathrm{min}(\kappa_{tr},\kappa_{st})$

31: $v(t)=v(t-1)+\kappa^{*}(r(t)-v(t-1))$

function $\mathrm{kappa}(n,d)$

1: if $n>0$ then

2: if $d>0$ then

3: $\kappa=\mathrm{min}(n/d,1)$

4: else

5: $\kappa=1$

6: end if

7: else

8: $\kappa=0$

9: end if

10: return $\kappa$

end function

##  IV Illustrative Examples

###  IV-A System model

Phase Comparator Loop Filter VCO $v(t)$$y(t)$ Figure 3: Simple analog PLL
system.

Consider the analog phase locked loop (PLL) system shown in Fig. 3, which is
comprised of a phase comparator, a loop filter, and a voltage controlled
oscillator (VCO). The transfer function of the closed-loop PLL system around a
nominal operating point is as follows [21]:

$\displaystyle H_{PLL}=\frac{G_{lp}G_{VCO}}{s^{2}+G_{lp}s+G_{lp}G_{VCO}}$ (24)

where $G_{lp}$ is the loop filter parameter and $G_{VCO}$ is the VCO gain.
Note that the closed-loop system has a DC gain of $1$ and perfect steady-state
tracking of step commands. For the simulation, $G_{lp}$ was chosen to be
$100$, and $G_{VCO}$ was chosen to be $2G_{lp}$ to yield an underdamped system
with damping ratio $\zeta=0.35$. By selecting states as $x_{1}=y$ and
$x_{2}=\dot{y}$, a zero order hold discretization of the system with a sample
time of $T_{s}=1\times 10^{-4}$ seconds is used to obtain the discrete state-
space model of the closed-loop system.

Constraints are imposed on both outputs of the system. The dynamic constraint
is applied to the tracking output $y_{tr}\triangleq y_{1}$ and a slew-rate
limiting constraint ($-100\leq y_{2}\leq 100$) is applied to the constrained
output $y_{st}\triangleq y_{2}$. The static and dynamic maximal admissible
sets are constructed as discussed in Sections II and III. The resulting
polyhedra, $O_{\infty}^{-}(r^{+})$ and $O_{\infty}^{-}(r^{-})$, both have
admissibility indices of $342$ (the representations happen to be the same for
this example). Additionally, the admissibility index of $O_{\infty,st}$ is
$130$.

###  IV-B Response Evaluation

Fig. 4 shows the improved response characteristics of the governed system
compared to the ungoverned system. Note that overshoot was completely
eliminated without making any modifications to the PLL. Hence, the RG-DC is
especially effective in overshoot mitigation of systems with inner loop
controllers that cannot be tuned or adjusted (i.e ‘black box’ systems), which
is true for many off-the-shelf PLLs.

Figure 4: Comparison between step responses of the governed and ungoverned
systems. No slew-rate limit is applied to the governed system in this
simulation. Figure 5: Governed system response to multiple steps inputs (slew-
rate limit = 100)

A simulation of the RG-DC operating on step signals is presented in Fig. 5.
Notice that overshoot is mitigated for all but the last step at $t=0.208$
seconds. In this case, the reference changes quickly so that $(x(t),v(t-1))$
does not belong to the new MAS, which means constraint violation is not
preventable. Hence, $\kappa$ has been set to $0$. Note that we maintain
convergence to the reference at the sacrifice of reduced overshoot mitigation
performance.

###  IV-C Robustness

To test robustness under model uncertainty, we treat the VCO gain, $G_{VCO}$,
as an unknown. We suppose, however, that $G_{VCO}$ is bounded as follows:
$160\leq G_{VCO}\leq 240$. We compute a robust MAS for this system using
Algorithm $1$ from [20]. Fig. 6 compares the robust MAS with a standard MAS
generated with the nominal model parameter $G_{VCO}=200$. From the figure, it
is evident that the introduction of model uncertainty results in a more
conservative MAS. Upon simulation of the governed system with the robust MAS,
we see in Fig. 7 that the constraints are not violated for systems at the
vertices of system uncertainty (the values of $G_{VCO}$ used for the
simulations are shown in the figure titles).

Figure 6: Slices from the robust and standard MASs at various values of $v$.
The dynamic constraint for this plot is $y_{1}\leq 1$ and the slew-rate limit
is 100. Figure 7: Governed uncertain system responses to multiple step inputs
(slew-rate limit = $100$). Note that the top two sub-figures and the bottom
two sub-figures correspond to two different realizations of the system
uncertainty shown in the plot titles.

###  IV-D RG-DC as a nonlinear filter

Finally, we present an interesting experiment, which led to a thought-
provoking observation regarding the frequency response of the governed PLL
system, which we discuss next.

In [22], it is shown that nonlinear systems can be analyzed using frequency
domain techniques if they satisfy the “convergence” property. Essentially, a
system is defined to be convergent if, akin to a linear system, its response
converges to the forced response, regardless of the initial conditions. As
argued in [22], nonlinear convergent systems can be analyzed using the
nonlinear Bode magnitude plot, which is a proper extension of the traditional
Bode magnitude plot for linear systems. However, unlike the linear Bode plot,
which is only a function of the frequency of the input sinusoid, the nonlinear
Bode plot is generally a function of both the frequency and amplitude of the
input.

In our case, it can be shown that the overall system with the RG-DC governing
the input is indeed a convergent system (see Fig. 8 for graphical argument).
Furthermore, as we prove in Theorem 2, the RG-DC is such that the nonlinear
Bode plot has no dependence on the amplitude of the input because the system
satisfies the homogeneity condition, similar to a linear system. Thus, we
adopt the methods in [22] to generate a nonlinear Bode magnitude plot of the
governed system as a function of the input frequency only. This plot is
presented in Fig. 9, which also shows the Bode magnitude plot of the
ungoverned PLL system (24) as comparison. The other plots labeled
“$2^{\mathrm{nd}}$ order system” and “$12^{\mathrm{th}}$ order system” will be
explained later. Details on how each plot was generated can be found in the
caption of Fig. 9. Upon inspection of Fig. 9, it appears that the resonant
peak inherent in the Bode magnitude plot of the underdamped closed loop PLL
system is completely eliminated with the implementation of the RG-DC.

Figure 8: Demonstration of convergence via simulation of the governed PLL
system (no slew-rate limit) at $50$ jointly uniformly distributed random
initial conditions $\left(x_{0},v_{0}\right)$. Initial condition ranges:
$x_{0_{1}}\in[-2,2],\ x_{0_{2}}\in[-200,200],\ v_{0}\in[-1,1]$. The reference
$r(t)$ is a sinusoid with frequency $100$ rad/s. Note that overshoot
mitigation constraints for some initial conditions were not satisfied because
the initial conditions did not belonged to MAS. Figure 9: Bode magnitude plot
(ungoverned PLL system) and nonlinear Bode magnitude plot (governed PLL
system, no slew-rate limit). In addition, the Bode magnitude plots of the
$2^{\mathrm{nd}}$ order and $12^{\mathrm{th}}$ order systems are shown. The
nonlinear Bode magnitude plot was generated by simulating governed system
responses with sinusoidal references of amplitude $1$ at $100$ different
frequencies that were logarithmically equally spaced ranging from $10$ rad/s
to $1,000$ rad/s. The supremum norm of the outputs were measured at steady-
state and converted to dB. The ungoverned PLL system, $2^{\mathrm{nd}}$ order
system, and $12^{\mathrm{th}}$ order system Bode magnitude plots were
generated using the standard linear systems approach applied to the respective
linear system models.

These results suggest that RG-DC could potentially be used in conjunction with
a resonant low-pass filter, giving the ability to eliminate the resonant
behavior without greatly affecting the cutoff frequency or the attenuation
properties beyond the cutoff frequency. In other words, the RG-DC may be
thought of as a “nonlinear” filter with anti-resonance properties.

We highlight the fact that the resonant peak in the Bode plot of the
ungoverned system shown in Fig. 9 is caused by underdamped poles in (24).
Therefore, a natural solution to remove the resonant peak is by using plant
inversion, i.e., replacing the RG-DC in Fig. 1 with an inverse model that
cancels the underdamped poles of the closed-loop system with a pair of complex
conjugate zeros. Since the resulting inverse model would be improper,
additional (overdamped) poles must be added to obtain a proper transfer
function. The series connection of the inverse model and the closed-loop
system yields an equivalent transfer function with no resonance peaks. This
raises the following question: how does the nonlinear Bode plot from the
governed PLL system compare with the linear Bode plot of this equivalent
system? To have a fair comparison, we introduce two choices for the equivalent
systems, both with DC gain equal to $1$ and relative degree equal to $2$ to
maintain the $-40$ dB/decade roll-off of the governed PLL system. The first
system, of order $2$, was designed such that the $-3$ dB bandwidth was equal
to that of the governed PLL system (based off the nonlinear Bode magnitude
plot), whereas the second system, of order $12$, was designed to minimize the
root-mean-square error relative to the nonlinear Bode magnitude plot. The
results are shown in Fig. 9. Note that the frequency response of the governed
PLL system has a faster transition from $0$ to $-40$ dB/decade compared to the
frequency response of the $2^{\mathrm{nd}}$ order system. Furthermore, the
$12^{\mathrm{th}}$ order Bode magnitude plot matches the nonlinear Bode
magnitude plot except for the frequency range from $100$ rad/s to $200$ rad/s
where the magnitude of the $12^{\mathrm{th}}$ order frequency response is less
than the magnitude of the governed frequency response. We thus make the mild
conclusion that the frequency response provided by the governed PLL system is
not attainable by a low-order linear system (of degree less than $12$), which
shows that an RG-DC governed resonant low-pass filter does indeed produce a
novel frequency response.

We now prove the homogeneity property of the overall system with the RG-DC
governing the reference, as alluded to above. In preparation for Theorem 2, we
introduce the following notation. Let the governed output of system (10) be
$y_{tr}\left(t,r(t),(x_{0},v_{0})\right)$, where $r(t)$ is the reference
signal that is applied to the system depicted in Fig. 1 with initial
conditions $(x_{0},v_{0})\mathrel{\mathop{\mathchar 58\relax}}=(x(0),v(-1))$
belonging to MAS. The following theorem holds.

######  Theorem 2.

Suppose $p=0$ in system (10), so that $y_{tr}(t)$ is the only output governed
by RG-DC. Then $y_{tr}\left(t,\alpha r(t),\alpha(x_{0},v_{0})\right)=\alpha
y_{tr}\left(t,r(t),(x_{0},v_{0})\right)$, $\forall\alpha\in\mathbb{R}^{+}$.

###### Proof.

We prove the homogeneity condition of the RG-DC from $r$ to $v$ by principal
of induction. The homogeneity condition from $r$ to $y_{tr}$ then follows from
the fact that the closed-loop system (10) from $v$ to $y_{tr}$ is linear.

We first establish the base case of the inductive argument, where we prove
that scaling the initial conditions, $(x_{0},v_{0})=(x(0),v(-1))$, and the
reference, $r(0)$, by $\alpha$ (written in short by
$(x_{0},v_{0})\rightarrow\alpha(x_{0},v_{0})$, $r(0)\rightarrow\alpha r(0)$),
scales the next iterate by $\alpha$:
$(x(1),v(0))\rightarrow\alpha(x(1),v(0))$. To show this, consider the RG
algorithm from (9) at time $t=0$ with the change of variables:
$x(0)\rightarrow\alpha x(0)$, $v(-1)\rightarrow\alpha v(-1)$, and
$r(0)\rightarrow\alpha r(0)$. Finally, let $\widetilde{O}_{\infty}$ from (9)
be $O_{\infty,tr}\left(\alpha r(0),\alpha
y_{tr}(0)\right)=O_{\infty,tr}\left(\alpha r(0),\alpha C_{tr}x_{0}\right)$.
The optimization problem becomes:

$\displaystyle\underset{\kappa\in[0,1]}{\text{maximize}}$
$\displaystyle\mathrm{\kappa}$ (25) s.t. $\displaystyle v(0)=\alpha
v_{0}+\kappa\left(\alpha r(0)-\alpha v_{0}\right)$ $\displaystyle\left(\alpha
x_{0},\ v(0)\right)\in O_{\infty,tr}\left(\alpha r(0),\alpha
C_{tr}x_{0}\right)$

Recall from Table III-A, that the relationship between $y_{tr}(t)$ and $r(t)$
determines which of the four cases of dynamic MAS is used in the RG algorithm
at timestep $t$. Furthermore, note that scaling $r(t)$ and $y_{tr}(t)$ by
$\alpha$ does not change which case is appropriate. This implies that
$O_{\infty,tr}\left(r(t),C_{tr}x(t)\right)$ and $O_{\infty,tr}\left(\alpha
r(t),\alpha C_{tr}x(t)\right)$, at any instance in time, both belong to the
same case from Table III-A. By Proposition 1 $i)$, it then follows that
$O_{\infty,tr}\left(\alpha r(0),\alpha C_{tr}x_{0}\right)=\alpha
O_{\infty,tr}\left(r(0),C_{tr}x_{0}\right)$, and we can conclude that the
constraints of optimization problem (25) are unaffected by $\alpha$.
Furthermore, noting that the cost function of (25) also does not depend on
$\alpha$, it follows that optimization problem (25) results in the same
optimizer $\kappa^{*}$ at time $t=0$ regardless of $\alpha$. From here, it
follows that the modified reference from (25) is $\alpha v(0)$. Furthermore,
at time $t=1$ we can conclude that $\alpha x(1)=A\alpha x_{0}+B\alpha v(0)$.
Note that this base case also holds when there is no solution to the
optimization problem because $\kappa^{*}=0$ at time $t=0$ means that $\alpha
v(0)=\alpha v_{0}$.

We now present the induction step, where we prove that scaling the parameters,
$x(t)$, $v(t-1)$, and $r(t)$, by $\alpha$, gives the following result:
$v(t)\rightarrow\alpha v(t)$ and $x(t+1)\rightarrow\alpha x(t+1)$. Consider
the RG algorithm from (9) with the change of variables: $x(t)\rightarrow\alpha
x(t)$, $v(t-1)\rightarrow\alpha v(t-1)$, and $r(t)\rightarrow\alpha r(t)$.
Finally, let $\widetilde{O}_{\infty}$ from (9) be $O_{\infty,tr}\left(\alpha
r(t),\alpha y_{tr}(t)\right)=O_{\infty,tr}\left(\alpha r(t),\alpha
C_{tr}x(t)\right)$. The optimization problem becomes:

$\displaystyle\underset{\kappa\in[0,1]}{\text{maximize}}$
$\displaystyle\mathrm{\kappa}$ (26) s.t. $\displaystyle v(t)=\alpha
v(t-1)+\kappa\left(\alpha r(t)-\alpha v(t-1)\right)$
$\displaystyle\left(\alpha x(t),\ v(t)\right)\in O_{\infty,tr}\left(\alpha
r(t),\alpha C_{tr}x(t)\right)$

Again, note that because $O_{\infty,tr}\left(\alpha r(t),\alpha
C_{tr}x(t)\right)=\alpha O_{\infty,tr}\left(r(t),C_{tr}x(t)\right)$, the
constraints of optimization problem (26) are independent of $\alpha$.
Furthermore, noting that the cost function of (26) also does not depend on
$\alpha$, it follows that (26) results in the same optimizer $\kappa^{*}$ at
time $t$ regardless of $\alpha$. From here, it follows that the modified
reference from (26) is $\alpha v(t)$. Furthermore, at time $t+1$ we can
conclude that $\alpha x(t+1)=A\alpha x(t)+B\alpha v(t-1)$. Note that this
induction step also holds when there is no solution to the optimization
problem because $\kappa^{*}=0$ at time $t$ means that $\alpha v(t)=\alpha
v(t-1)$. Considering the above logic, by the principal of induction, the RG-DC
satisfies the homogeneity condition (from $r$ to $v$) and we can conclude
that, because the closed-loop system is linear (from $v$ to $y_{tr}$), the
entire governed system (from $r$ to $y_{tr}$) satisfies the homogeneity
condition. This completes the proof. ∎

An additional argument can be made that further strengthens the validity of
the nonlinear Bode magnitude plot. We argue that although the input to the
linear closed-loop system ($v(t)$) is not perfectly sinusoidal (due to the
governing action of the RG-DC), the output of the system ($y_{tr}$) is
“approximately” sinusoidal (which we have observed in our simulations, see for
example Fig. 8). The reason for this phenomenon can be attributed to the fact
that the closed-loop system is of low-pass-filtering nature, which implies
that it filters out higher order harmonics of $v(t)$. This argument is similar
to the methods used for Describing Functions [23].

##  V Conclusion

In this paper, an overshoot mitigation control scheme was developed using the
reference governor framework. The solution, known as the Reference Governor
with Dynamic Constraint (RG-DC), utilizes a dynamic maximal admissible set
(MAS) to constrain the tracking output such that overshoot of step inputs is
eliminated. The RG-DC loop was proven to be BIBO stable. Additionally,
properties of the dynamic MAS were studied and theorems were proven that allow
for the RG-DC to operate without recalculation of the matrices that define the
dynamic MAS. While the RG-DC can guarantee overshoot elimination for all step
inputs with the proper initial conditions, it may not remove overshoot for a
more general time-varying reference $r$. Conditions were provided in the paper
under which elimination will be guaranteed for time-varying $r$.

Future work on the RG-DC and its effect on frequency response are of interest.
More specifically, we would like to study the settling time of the system
under RG-DC and explore the application of the RG-DC as a nonlinear filter.

## Disclaimer

Portions of this publication and research effort are made possible through the
help and support of NIST via cooperative agreement 70NANB19H133. Official
contribution of the National Institute of Standards and Technology; not
subject to copyright in the United States. Certain commercial products are
identified in order to adequately specify the procedure; this does not imply
endorsement or recommendation by NIST, nor does it imply that such products
are necessarily the best available for the purpose.

## References

  * [1] S. Devasia.  Should model-based inverse inputs be used as feedforward under plant uncertainty?  IEEE Transactions on Automatic Control, 47(11):1865–1871, Nov 2002\.
  * [2] Qingze Zou and Santosh Devasia.  Precision preview-based stable-inversion for nonlinear nonminimum-phase systems: The VTOL example.  Automatica, 43:117–127, 01 2007.
  * [3] Thanh Hung Tran, Quang Phuc Ha, and Hung T. Nguyen.  Robust non-overshoot time responses using cascade sliding mode-PID control.  Journal of Advanced Computational Intelligence and Intelligent Informatics, 11:1224–1231, 2007.
  * [4] Y. Tange, S. Kiryu, and T. Matsui.  Overshoot suppression control based on final tracking error estimation and quantifier elimination.  In Proc. Asian Control Conference, pages 1–6, May 2015.
  * [5] I. Kolmanovsky, E. Garone, and S. Di Cairano.  Reference and command governors: A tutorial on their theory and automotive applications.  In Proc. American Control Conference, pages 226–241, June 2014\.
  * [6] E. G. Gilbert and I. Kolmanovsky.  Discrete-time reference governors for systems with state and control constraints and disturbance inputs.  In Proc. IEEE Conference on Decision and Control, volume 2, pages 1189–1194, Dec 1995.
  * [7] Emanuele Garone, Stefano Di Cairano, and Ilya Kolmanovsky.  Reference and command governors for systems with constraints: A survey on theory and applications.  Automatica, 75:306–328, 2017.
  * [8] Elmer G. Gilbert and Ilya Kolmanovsky.  Fast reference governors for systems with state and control constraints and disturbance inputs.  International Journal of Robust and Nonlinear Control, 9(15):1117–1141, 1999.
  * [9] H. R. Ossareh.  Reference governors and maximal output admissible sets for linear periodic systems.  International Journal of Control, pages 1–13, 2019.
  * [10] J. Osorio and H. R. Ossareh.  A stochastic approach to maximal output admissible sets and reference governors.  In Proc. IEEE Conference on Control Technology and Applications, pages 704–709, Aug 2018.
  * [11] Aidan Laracy and Hamid Ossareh.  Constraint management for batch processes using iterative learning control and reference governors.  In Proceedings of Machine Learning Research (PMLR), 2020.
  * [12] Joycer Osorio, Mario Santillo, Julia Buckland Seeds, Mrdjan Jankovic, and Hamid R Ossareh.  A reference governor approach towards recovery from constraint violation.  In 2019 American Control Conference (ACC), pages 1779–1785. IEEE, 2019.
  * [13] Yudan Liu, Joycer Osorio, et al.  Decoupled reference governors for multi-input multi-output systems.  In 2018 IEEE Conference on Decision and Control (CDC), pages 1839–1846. IEEE, 2018.
  * [14] Jan Marian Maciejowski.  Predictive control: with constraints.  Prentice Hall, 2008.
  * [15] E. G. Gilbert and K. T. Tan.  Linear systems with state and control constraints: the theory and application of maximal output admissible sets.  IEEE Transactions on Automatic Control, 36(9):1008–1020, Sep. 1991\.
  * [16] U. Kalabić and I. Kolmanovsky.  Reference and command governors for systems with slowly time-varying references and time-dependent constraints.  In Proc. IEEE Conference on Decision and Control, Dec 2014.
  * [17] U. Kalabic, I. Kolmanovsky, J. Buckland, and E. Gilbert.  Reference and extended command governors for control of turbocharged gasoline engines based on linear models.  In 2011 IEEE International Conference on Control Applications (CCA), pages 319–325, Sep. 2011.
  * [18] C. Freiheit, D. M. Anand, and H. R. Ossareh.  Overshoot mitigation using the reference governor framework.  IEEE Control Systems Letters, 4(2):518–523, 2020.
  * [19] Uros Kalabić.  Reference governors: Theoretical Extensions and Practical Applications. PhD thesis, University of Michigan, Ann Arbor, 2015.
  * [20] B. Pluymers, J. A. Rossiter, J. A. K. Suykens, and B. De Moor.  The efficient computation of polyhedral invariant sets for linear systems with polytopic uncertainty.  In Proc. American Control Conference, volume 2, pages 804–809, June 2005.
  * [21] Wen Li and Jason Meiners.  Introduction to phase-locked loop system modeling.  Analog Applications, 2000.
  * [22] A. Pavlov, N. van de Wouw, and H. Nijmeijer.  Frequency response functions and bode plots for nonlinear convergent systems.  In Proceedings of the 45th IEEE Conference on Decision and Control, pages 3765–3770, 2006.
  * [23] H. K. Khalil.  Nonlinear Systems.  Prentice-Hall, Englewood Cliffs, NJ, 2nd edition, 1996.


komalike dash headings0 headings0 plain headings subsection

# DRIFT: A Federated Recommender System with Implicit Feedback on the Items

Theo Nommay

###### Abstract

Nowadays there are more and more items available online, this makes it hard
for users to find items that they like. Recommender systems aim to find the
item who best suits the user, using his historical interactions. Depending on
the context, these interactions may be more or less sensitive and collecting
them brings an important problem concerning the users’ privacy. Federated
systems have shown that it is possible to make accurate and efficient
recommendations without storing users’ personal information. However, these
systems use instantaneous feedback from the user. In this report, we propose
DRIFT, a federated architecture for recommender systems, using implicit
feedback. Our learning model is based on a recent algorithm for recommendation
with implicit feedbacks SAROS [ABCILM21]. We aim to make recommendations as
precise as SAROS, without compromising the users’ privacy. In this report we
show that thanks to our experiments, but also thanks to a theoretical analysis
on the convergence. We have shown also that the computation time has a linear
complexity with respect to the number of interactions made. Finally, we have
shown that our algorithm is secure, and participants in our federated system
cannot guess the interactions made by the user, except DOs that have the item
involved in the interaction.

###### Acknowledgement

I would like to express my sincere gratitude to Marta Soare, Radu Ciucanu, and
Massih-Reza Amini for their invaluable assistance throughout the internship. I
would also like to express my sincere thanks to Aleksandra Burashnikova, for
all the help she gave me in understanding her algorithm.

*