A Tuner that Accelerates Parameters

Felipe M Pait^{1} and Paulo A Atkinson^{2}

pait,atk@lac.usp.br

Universidade de São Paulo – pee Laboratório de Automação e Controle

Av. Prof. Gualberto trav 3–158 São Paulo SP 05508–900 Brasil

Abstract

We propose a tuner, suitable for adaptive control and (in its discrete-time version) adaptive filtering applications, that sets the second derivative of the parameter estimates rather than the first derivative as is done in the overwhelming majority of the literature. Comparative stability and performance analyses are presented.

Key Words: Adaptive Control; Parameter Estimation; Adaptive Filtering; Covariance Analysis.

1 Parameter Adjustment

In adaptive control and recursive parameter estimation one often needs to adjust recursively an estimate p̂ of a vector p, which comprises n constant but unknown parameters, using measurements of a quantity

y = x^{⊤}p + w.  (1)

Here x : [0, t̄) → ℝ^{n} is a vector of known data, often called the regressor, and w is a measurement error signal. The goal of tuning is to keep both the estimation error x^{⊤}p̂ − y and the parameter error p̂ − p as small as possible.

There are several popular methods for dealing with the problem above, for instance least-squares. Maybe the most straightforward involve minimizing the prediction error via gradient-type algorithms of the form:

˙p̂ = −Mx(x^{⊤}p̂ − y),  (2)

where M is a constant, symmetric, positive-definite gain matrix. Let us define q = p̂− p and analyze differential equations (1) and (2), which under the assumption that w(t) is identically zero read:

q̇ = −Mxx^{⊤}q.  (3)

The nonnegative function V = \frac{1}{2}q^{⊤}M^{−1}q has time derivative V̇ = q^{⊤}M^{−1}q̇ = −q^{⊤}xx^{⊤}q, hence

∫_{0}^{t} V̇ = V (t) − V (0) = − ∫_{0}^{t}(x^{⊤}q)^{2}.

Inspection of the equation above reveals that V is limited in time, thus q ∈ L^{∞}, and also that the error x^{⊤}q ∈ L^{2} (norms are taken on the interval [0, t̄) where all signals are defined). These are the main properties an algorithm needs in order to be considered a suitable candidate for the role of a tuner in an adaptive control system. Often q̇ ∈ L^{2} or something similar is also a desirable property. To obtain the latter, normalized algorithms can be used; however, the relative merits of normalized versus unnormalized tuners are still somewhat controversial. Another alternative is to use a time-varying M, as is done in least-squares tuning.

In §2 we present a tuner that sets the second derivative of p̂, and in §3 the effects of a white noise w on the performance of the two algorithms are compared. Then we show some simulations and make concluding remarks.

2 The Accelerating Algorithm

Classical tuners are such that the velocity of adaptation (the first derivative of the parameters) is set proportional to the regressor and to the prediction error x^{⊤}p̂ − y = x^{⊤}q. We propose to set the acceleration of the parameters:

q̈ = −xx^{⊤}q − 2(I + xx^{⊤})q̇.  (4)

Notice that the the formula above is implementable (using 2n integrators) if measurement error is absent, because the unknown q appears only in scalar product with x. Choose another function of Lyapunovian inspiration:

1Research supported by cnpq – Brazilian Research Council, grant 523949/95-2.

2Research supported by fapesp – São Paulo Research Agency, scholarship 97/00582-5.

V = q^{⊤}q + q^{⊤}q̇ + q̇^{⊤}q̇

= [q^{⊤} q̇^{⊤}] [\begin{matrix}I & I/2 \\ I/2 & I \end{matrix}] [q ; q̇] ≥ 0.

Taking derivatives and using the accelerating tuner (4) gives

V̇ = 2q^{⊤}q̇ + q̇^{⊤}q̇ − (q^{⊤} + 2q̇^{⊤})(2q̇ + xx^{⊤}q + 2xx^{⊤}q̇)
= −3q̇^{⊤}q̇ − (q + 2q̇)^{⊤}xx^{⊤}(q + 2q̇) ≤ 0.

Integrating V̇ we obtain

V (t) = V (0) − ∫_{0}^{t} q̇^{⊤}q̇ − ∫_{0}^{t}(x^{⊤}(q + 2q̇))^{2},

which leads immediately to the desired properties:

q, q̇ ∈ L^{∞}; q̇ ∈ L^{2}; x^{⊤}(q + 2q̇) ∈ L^{2}.

The slow variation property q̇ ∈ L^{2} follows without the need for normalization, and now we obtain x^{⊤}(q + 2q̇) ∈ L^{2} instead of x^{⊤}q ∈ L^{2} as before. We might regard x^{⊤}(q + 2q̇) as a modified error, which can be used in the stability analysis of a detectable or “tunable” adaptive system via an output-injection argument; see [3]. A generalization of (4) is

q̈ = −M_{1}(x(x^{⊤}p̂ − y) + 2(M_{2} + xx^{⊤}M_{1}M_{3})q̇), (5)

with M_{1}, M_{2} and M_{3} constant, symmetric, positivedefinite n × n matrices such that M_{2}^{−1} < 4M_{1}M_{3}M_{1} and M_{2}M_{1}M_{3} + M_{3}M_{1}M_{2} > M_{1}^{−1}/2. The properties of tuner (5), which can be obtained using the positivedefinite function

[q^{⊤} q̇^{⊤}] [\begin{matrix}M_{2} & M_{1}^{−1}/2 \\ M_{1}^{−1}/2 & M_{3} \end{matrix}] [q ; q̇]

in the same manner as before, are

q, q̇ ∈ L^{∞}; q̇ ∈ L^{2}; x^{⊤}(q + 2M_{1}M_{3}q̇) ∈ L^{2}.

3 Covariance Analysis

We now consider the effects on the expected value and covariance of q(t) of the presence of a measurement error. The assumptions are that w(t) is a white noise with zero average and covariance σ_{w}^{2}δ(t − τ) and that x(t) are given, deterministic data. For comparison purposes, first consider what happens when the conventional tuner (2) is applied to (1) in the presence of measurement error w:

q̇ = −Mxx^{⊤}q + Mxw.  (3′)

The solution to the equation above can be written in terms of (−Mxx^{⊤})’s state transition matrix ϕ(t, τ) as follows

q(t) = ϕ(t, 0)q(0) + ∫_{0}^{t} dτ ϕ(t, τ)Mx(τ)w(τ),

hence E_{w}{q(t)} = ϕ(t, 0)q(0) because E{w(τ)} = 0 by assumption. Here the notation E_{w}{·}, denoting the expectation with respect to the random variable w, is used to emphasize that the stochastic properties of x are not under consideration. The conclusion is that q(t) will converge to zero in average as fast as ϕ(t, 0) does. The well-known persistency of excitation conditions on x(·) are sufficient for the latter to happen.

To study the second moment of the parameter error, write

qq^{⊤}(t) = ϕ(t, 0)qq^{⊤}(0)ϕ^{⊤}(t, 0)
+ ϕ(t, 0)q(0) ∫_{0}^{t} dτ w(τ)x^{⊤}(τ)Mϕ^{⊤}(t, τ)

+ (∫_{0}^{t} dτ ϕ(t, τ)Mx(τ)w(τ)) q^{⊤}(0)ϕ^{⊤}(t, 0)

+ (∫_{0}^{t} dτ ϕ(t, τ)Mx(τ)w(τ)) ·
(∫_{0}^{t} dτ w(τ)x^{⊤}(τ)Mϕ^{⊤}(t, τ)) .

The covariance of q(t) can be written as the sum of four terms. The first is deterministic. The second term

E_{w}{ϕ(t, 0)q(0) ∫_{0}^{t} dτ w(τ)x^{⊤}(τ)Mϕ^{⊤}(t, τ)}

= ϕ(t, 0)q(0) ∫_{0}^{t} dτ E{w(τ)}x^{⊤}(τ)Mϕ^{⊤}(t, τ) = 0

because w(t) has zero mean, and the third term is likewise zero. The fourth term

E_{w} {∫_{0}^{t} dτ_{1} ϕ(t, τ_{1})Mx(τ_{1})w(τ_{1})

∫_{0}^{t} dτ_{2} w(τ_{2})x^{⊤}(τ_{2})Mϕ^{⊤}(t, τ_{2})}
= ∫_{0}^{t} dτ_{1} ∫_{0}^{t} dτ_{2} ϕ(t, τ_{1})Mx(τ_{1})

E{w(τ_{1})w(τ_{2})}x^{⊤}(τ_{2})Mϕ^{⊤}(t, τ_{2})

= σ_{w}^{2} ∫_{0}^{t} dτ_{1} ϕ(t, τ_{1})Mx(τ_{1})x^{⊤}(τ_{1})Mϕ^{⊤}(t, τ_{1}),

where Fubini’s Theorem and the fact E{w(τ_{1})w(τ_{2})} = σ_{w}^{2}δ(τ_{1} − τ_{2}) were used. Adding the first and fourth terms and performing the integration results in

E_{w}{qq^{⊤}(t)} = ϕ(t, 0)qq^{⊤}(0)ϕ^{⊤}(t, 0)

+ \frac{σ_{w}^{2}}{2} (M − ϕ(t, 0)Mϕ^{⊤}(t, 0)).

This equation can be given the following interpretation: for small t, when ϕ(t, 0) is close to the identity, the covariance of q(t) remains close to qq^{⊤}(0), the outer product of the error in the initial guess of the parameters with itself. As ϕ(t, 0) → 0, which will happen if x(·) is persistently exciting, E_{w}{qq^{⊤}(t)} tends to σ_{w}^{2}M/2. This points to a compromise between higher convergence speeds and lower steady-state parameter error, which require respectively larger and smaller values of the gain M. Algorithms that try for the best of both worlds — parameter convergence in the mean-square sense — often utilize time-varying, decreasing gains; an example is the least-squares algorithm.

We shall now attempt a similar analysis for the acceleration tuner (5) applied to (1), which results in the differential equation

[q̇ ; q̈] = [ 0 I_{−M_{1}xx^{⊤} −2M_{1}(M_{2}+xx^{⊤}M_{1}M_{3})}] [q ; q̇] + [ 0_{M_{1}xw}] .

Let

[\begin{matrix}ϕ̇_{11} & ϕ̇_{12} \\ ϕ̇_{21} & ϕ̇_{22} \end{matrix}] = [ 0 I_{−M_{1}xx^{⊤} −2M_{1}(M_{2}+xx^{⊤}M_{1}M_{3})}] [\begin{matrix}ϕ_{11} & ϕ_{12} \\ ϕ_{21} & ϕ_{22} \end{matrix}] ,

where ϕ_{11}(t, t) = ϕ_{22}(t, t) = I, ϕ_{12}(t, t) = ϕ_{21}(t, t) = 0, each ϕ_{ii} is a function of (t, τ) unless otherwise noted, and the dot signifies derivative with respect to the first argument. If q̇(0) = 0,

q(t) = ϕ_{11}(t, 0)q(0) + ∫_{0}^{t} dτ ϕ_{12}(t, τ)M_{1}x(τ)w(τ).

Following the same reasoning used for the velocity tuner, one concludes that E_{w}{q(t)} = ϕ_{11}(t, 0)q(0) and that

E_{w}{qq^{⊤}(t)} = ϕ_{11}(t, 0)qq^{⊤}(0)ϕ_{11}^{⊤}(t, 0) +

σ_{w}^{2} ∫_{0}^{t} dτ ϕ_{12}(t, τ)M_{1}xx^{⊤}(τ)M_{1}ϕ_{12}^{⊤}(t, τ), (6)

however the properties of the acceleration and velocity tuners are not yet directly comparable because the right-hand side of (6) does not lend itself to immediate integration. To obtain comparable results, we employ the ungainly but easily verifiable formula (7), valid for arbitrary scalars μ_{1} and μ_{2}, and make the

Simplifying Assumption: For i = 1, 2, and 3, M_{i} = m_{i}I, where m_{i} are scalars and I is the n × n identity matrix.

Premultiplying (7) by [I 0], postmultiplying by [I 0]^{⊤}, integrating from 0 to t, and using the simplifying assumption gives formula (8). Taking μ_{1} = μ_{2} = 0 in (8), M̄_{2} results positive-semidefinite, therefore

∫_{0}^{t} dτ ϕ_{12}(t, τ)M_{1}xx^{⊤}(τ)M_{1}ϕ_{12}^{⊤}(t, τ)

≤ \frac{1}{4m_{1}^{2}m_{2}m_{3} − 1} (m_{1}^{2}m_{3}I

− [ϕ_{11}(t, 0) ϕ_{12}(t, 0)] M̄_{1} [\begin{matrix}ϕ_{11}^{⊤}(t, 0) \\ ϕ_{12}^{⊤}(t, 0) \end{matrix}]) . (9)

The combination of (6) and (9) shows that m_{1} can be increased without affecting q’s steady-state covariance. On the other hand, to decrease the covariance we need to increase m_{2}, which roughly speaking means increasing damping in (4). Since m_{1} and m_{2} can be increased without affecting the stability properties shown in §2, a better transient × steady-state performance compromise might be achievable with the acceleration tuner than with the velocity tuner, at least in the case when M_{1}, M_{2}, and M_{3} are “scalars.” Notice that 4m_{1}^{2}m_{2}m_{3} > 1 by construction.

Approximate Analysis: The derivation of inequality (9) does not involve any approximations, and therefore provides an upper bound on E_{w}{qq^{⊤}(t)}, valid independently of x(·). A less conservative estimate of the integral in (6) can be obtained by replacing xx^{⊤} by its average value R in the definition of M̄_{2} in (8). This approximation seems reasonable because M̄_{2} appears inside an integral, but calls for more extensive simulation studies.

To obtain a useful inequality, we require M̄_{2} ≥ 0; namely, using the Schur complement

4(1 + μ_{2})M_{1}M_{2}M_{1}M_{2}M_{1} ≥

M_{1}(μ_{1}xx^{⊤}−(2+μ_{2})M_{2})M_{1}(μ_{1}xx^{⊤}−(2+μ_{2})M_{2})M_{1},

or, using the simplifying assumption and substituting xx^{⊤} by its approximation R

4(1 + μ_{2})I ≥ ((2 + μ_{2})I − \frac{μ_{1}}{m_{2}} R)^{2}.

Suppose further that R = rI. Looking for the least conservative estimate, we pick μ_{1} = \frac{m_{2}}{r} (2+μ_{2}−2\sqrt{1 + μ_{2}}), the least value of μ_{1} that keeps M̄_{2} ≥ 0. Thus

∫_{0}^{t} dτ ϕ_{12}(t, τ)M_{1}xx^{⊤}(τ)M_{1}ϕ_{12}^{⊤}(t, τ) ≤

\frac{m_{1}^{2}m_{3}r + m_{1}m_{2}(μ_{2} + 2 − 2\sqrt{1 + μ_{2}})}{4m_{1}^{2}m_{2}m_{3}r(1 + μ_{2}) − r}I − Ξ(t) (10)

with Ξ(t) = ^{\frac{[ ϕ_{11}(t,0) ϕ_{12}(t,0) ]M̄_{1}[ \begin{matrix}ϕ_{11}^{⊤}(t,0) \\ ϕ_{12}^{⊤}(t,0) \end{matrix} ]}{4m_{1}^{2}m_{2}m_{3}r(1+μ_{2})−r}}.

Taking μ_{2} = 0 we repeat the previous, exact result. For large positive values of μ_{2} the first term of the

\frac{∂}{∂τ} [\begin{matrix}ϕ_{11} & ϕ_{12} \\ ϕ_{21} & ϕ_{22} \end{matrix}] M̄_{1} [\begin{matrix}ϕ_{11}^{⊤} & ϕ_{21}^{⊤} \\ ϕ_{12}^{⊤} & ϕ_{22}^{⊤} \end{matrix}] = [\begin{matrix}ϕ_{11} & ϕ_{12} \\ ϕ_{21} & ϕ_{22} \end{matrix}]( M̄_{2}

+ [\begin{matrix}0 & 0 \\ 0 & −M_{1}xx^{⊤}M_{1} + 2(1 + μ_{2})(M_{1}M_{2}M_{1}M_{3}M_{1}xx^{⊤}M_{1} + M_{1}xx^{⊤}M_{1}M_{3}M_{1}M_{2}M_{1}) \end{matrix}]) [\begin{matrix}ϕ_{11}^{⊤} & ϕ_{21}^{⊤} \\ ϕ_{12}^{⊤} & ϕ_{22}^{⊤} \end{matrix}] ,

\begin{aligned}where M̄_{1} & = [\begin{matrix}M_{1}M_{3}M_{1} + μ_{1}M_{1} & −M_{1}/2 \\ −M_{1}/2 & (1 + μ_{2})M_{1}M_{2}M_{1} \end{matrix}] , \\ M̄_{2} & = [\begin{matrix}M_{1} & μ_{1}M_{1}xx^{⊤}M_{1} − (2 + μ_{2})M_{1}M_{2}M_{1} \\ μ_{1}M_{1}xx^{⊤}M_{1} − (2 + μ_{2})M_{1}M_{2}M_{1} & 4(1 + μ_{2})M_{1}M_{2}M_{1}M_{2}M_{1} \end{matrix}] \end{aligned}  (7)

∫_{0}^{t} dτ (4(1 + μ_{2})m_{1}^{2}m_{2}m_{3} − 1)ϕ_{12}(t, τ)M_{1}xx^{⊤}(τ)M_{1}ϕ_{12}^{⊤}(t, τ) = [ϕ_{11}(t, τ) ϕ_{12}(t, τ)] M̄_{1} [\begin{matrix}ϕ_{11}^{⊤}(t, τ) \\ ϕ_{12}^{⊤}(t, τ) \end{matrix}]|_{τ=0}^{τ=t} − ∫_{0}^{t} dτ [ϕ_{11} ϕ_{12}] M̄_{2} [\begin{matrix}ϕ_{11}^{⊤} \\ ϕ_{12}^{⊤} \end{matrix}] (8)

right-hand side of (10) tends to I/4m_{1}m_{3}r, which indicates that the steady-state covariance of the parameter error decreases when the signal x increases in magnitude, and that it can be made smaller via appropriate choices of the gains m_{1} and m_{3}. The situation for the accelerating tuner is hence much more favorable than for the conventional one.

4 Simulations

The simulations in this section compare the behavior of the accelerating tuner (4) with those of the gradient tuner (3) and of a normalized gradient one. All simulations were done in open-loop, with the regressor a two-dimensional signal, and without measurement noise. Figure 1 shows the values of \sqrt{q^{⊤}q} and x^{⊤}q respectively when x is a two-dimensional step signal. In Figure 2 the regressor is a sinusoid, in Figure 3 an exponentially increasing sinusoid, and in Figure 4 a pseudorandom signal generated using matlab. No effort was made to optimize the choice of gain matrices (M_{1}, M_{2}, and M_{3} were all chosen equal to the identity), and the effect of measurement noise was not considered. The performance of the accelerating tuner is comparable, and sometimes superior, to that of the other tuners.

5 Concluding Remarks

Other ideas related to the present one are replacing the integrator in (3) with a positive-real transfer function [1, page 89], and using high-order tuning ([2, 4]). High-order tuning generates as outputs p̂ as well as its derivatives up to a given order (in this sense we might consider the present algorithm a secondorder tuner), but unlike the accelerating tuner requires derivatives of x up to that same order. We expect that accelerating tuners will find application in adaptive control of nonlinear systems and maybe in dealing with the topological incompatibility known as the “loss of stabilizability problem” in the adaptive control literature.

The stochastic analysis in §3 indicates that the performance and convergence properties of the accelerating tuner, together with its moderate computational complexity, may indeed make it a desirable tool for adaptive filtering applications. It seems that a better transient × steady-state performance compromise is achievable with the accelerating tuner than with the velocity tuner. To verify this conjecture, a study of convergence properties of the accelerating tuner and their relation with the persistence of excitation conditions is in order, as well as more extensive simulations in the presence of measurement noise.

Acknowledgements The authors are grateful to Oswaldo L V Costa and Max Gerken for useful suggestions related to this work.

References

[1] Yoan D Landau. Adaptive Control: The Model Reference Approach. Marcel Dekker, New York, 1979.

[2] A Stephen Morse. High-order parameter tuners for the adaptive control of nonlinear systems. In us-Italy Joint Seminar on Systems, Models, and Feedback: Theory and Applications, Capri, 1992.

[3] A Stephen Morse. Towards a unified theory of parameter adaptive control – Part 2: Certainty equiva-

Figure 1: Response to step data

lence and implicit tuning. ieee Trans. Automatic Control, 37(1):15–29, January 1992.

[4] Romeo Ortega. On Morse’s new adaptive controller: Parameter convergence and transient performance. ieee Trans. Automatic Control, 38(8):1191– 1202, August 1993.

Figure 2: Response to sinusoidal data Figure 3: Response to exponentially increasing sinusoid

Figure 4: Response to pseudorandom signal