Rodolphe Jenatton
email: jenatton@amazon.com

Jim Huang
email: huangjim@amazon.com

Cédric Archambeau
email: cedrica@amazon.com

Adaptive Algorithms for Online Convex Optimization with Long-term Constraints

We present an adaptive online gradient descent algorithm to solve online convex optimization problems with long-term constraints, which are constraints that need to be satisfied when accumulated over a finite number of rounds T , but can be violated in intermediate rounds. For some user-defined trade-off parameter β ∈ (0, 1), the proposed algorithm achieves cumulative regret bounds of O(T max{β,1-β} ) and O(T 1-β/2 ) for the loss and the constraint violations respectively. Our results hold for convex losses and can handle arbitrary convex constraints without requiring knowledge of the number of rounds in advance. Our contributions improve over the best known cumulative regret bounds by Mahdavi, et al. (2012) that are respectively O(T 1/2 ) and O(T 3/4 ) for general convex domains, and respectively O(T 2/3 ) and O(T 2/3 ) when further restricting to polyhedral domains. We supplement the analysis with experiments validating the performance of our algorithm in practice.

Introduction

Online convex optimization (OCO) plays a key role in machine learning applications, such as adaptive routing in networks [START_REF] Awerbuch | Online linear optimization and adaptive routing[END_REF] and online display advertising [START_REF] Agrawal | Fast algorithms for online stochastic convex programming[END_REF]. In general, an OCO problem can be formulated as a sequential and repeated game between a learner and an adversary. In each round t, the learner first plays a vector x t ∈ X ⊆ R p , where X is a compact convex set corresponding to the set of possible solutions. The learner then incurs a loss f t (x t ) for playing vector x t . The function f t (x) : X → R + is defined by the adversary and can vary in each round, but it is assumed to be convex. We say that a function f t : R d → R + is strongly convex with modulus σ > 0 if

f t (x) ≤ f t (y) + ∇f t (x) (x -y) - σ 2 x -y 2 .
for any x, y ∈ R d . We use the notation ∇f t (x) to refer to any (sub-)gradient of f t at x. Furthermore, we say that f t is convex if σ = 0.

The learner's objective is to generate a sequence of vectors x t ∈ X for t = 1, 2, • • • , T that minimizes the cumulative regret over T rounds relative to the optimal vector x :

Regret T (x * ) T t=1 f t (x t ) - T t=1 f t (x ). (1)
The latter measures the difference between the cumulative loss of the learner's sequence of vectors {x t } T t=1 and the accumulated loss that would be incurred if the sequence of loss functions f t would be known in advance and the learner could choose the best vector x in hindsight.

Several algorithms have been developed over the past decade that achieve sub-linear cumulative regret in the OCO setting. The problem was formalized in the seminal work of [START_REF] Zinkevich | Online convex programming and generalized infinitesimal gradient ascent[END_REF], which presents an online algorithm based on projected gradient descent [START_REF] Bertsekas | Parallel and Distributed Computation: Numerical Methods[END_REF] that guarantees a cumulative regret of O(T 1/2 ) when the set X is convex and the loss functions are Lipschitz-continuous over X . In [START_REF] Hazan | Logarithmic regret algorithms for online convex optimization[END_REF] and [START_REF] Shalev-Shwartz | Mind the duality gap: Logarithmic regret algorithms for online optimization[END_REF], algorithms with logarithmic regret bounds were proposed for strongly convex loss functions. Notably, online gradient descent achieves an O(log T ) regret bound for strongly convex loss functions for appropriate choices of step size.

In the aforementioned work, the constraint on vector x t is assumed to hold in round t, such that a projection step is applied in every round to enforce the feasibility of each x t . For general convex sets X , the projection step may require solving an auxiliary optimization problem, which can be computationally expensive (e.g., projections onto the semi-definite cone). More importantly, in practical applications, the learner may in fact only be concerned with satisfying long-term constraints, that is, the cumulative constraint violations resulting from the sequence of vectors {x t } T t=1 should not exceed a certain amount by the final round T . An example of such an application is in online display advertising, where x t corresponds to a vector of ad budget allocations and the learner is primarily concerned in enforcing the long-term constraint that each ad consumes its budget in full over the lifetime of the ad. Another example is from wireless communications [START_REF] Mannor | Online learning with constraints[END_REF], where x t is a vector of power allocations across multiple devices, and the learner must satisfy average power consumption constraints per device.

In this work, we consider OCO problems where the learner is required to satisfy long-term constraints. For such problems, we will be concerned both with a) the learner's cumulative regret as defined by ( 1) and b) the learner's ability to satisfy long-term constraintsthe notion of long-term shall be made more formal in Section 2.2. This class of problems was studied previously in [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF][START_REF] Mahdavi | Efficient constrained regret minimization[END_REF]. In particular, [START_REF] Mahdavi | Efficient constrained regret minimization[END_REF] considered online exponentially-weighted average in the case where the loss and constraints are linear, while [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF] presented online algorithms based on projected subgradients and the mirror prox method [START_REF] Nemirovski | Prox-method with rate of convergence o (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems[END_REF]. The authors derived cumulative regret bounds for the cumulative loss and cumulative constraint violations respectively of O(T 1/2 ) and O(T 3/4 ) in the case of online projected subgradients, and respectively of O(T 2/3 ) and O(T 2/3 ) in the case of mirror prox. To our knowledge, these are the best-known regret bounds for OCO with long-term constraints. The analysis of [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF] assumes the number of rounds is known ahead of time, which enables the authors to set the various constants in the algorithm that lead to the desired regret bounds. For the mirror prox method, it is additionally required that the constraint set X is fully specified by a finite number of linear constraints.

The concept of long-term constraints also enables us to avoid the computation of potentially expensive projections onto the domain X of x in each round. This is closely related to recent work in stochastic optimization that aims to minimize the number of expensive projection steps [START_REF] Mahdavi | Stochastic gradient descent with only one projection[END_REF]. The guarantees sought in our analysis have also similarities with the results obtained in the context of the online alternating direction method [START_REF] Wang | Online alternating direction method[END_REF], where regret bounds are provided for the violation of equality constraints.

Contributions: Building on the work of [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF], we propose an algorithm based on a saddle-point formulation of the OCO problem with long-term constraints, which is adaptive (i.e., the step sizes and the regularisation parameter depend on the round t). We show that the algorithm satisfies cumulative regret bounds of O(T 2/3 ) for both the cumulative loss and the cumulative constraint violations without requiring us to know the number of rounds T in advance to set the algorithmic hyperparameters. Unlike mirror prox, our method can deal with any convex constraint set X , making it amenable to a wider range of OCO problems. Also, the algorithm we derive allows us to interpolate between the regret bounds of O(T 1/2 ) and O(T 3/4 ) from [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF] and the above bound of O(T 2/3 ), depending on how we wish to trade off between the cumulative regret associated to the loss and the long-term constraints. In addition to our analysis of regret bounds, we empirically validate our algorithm by comparing it to the methods of [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF] on a) the online estimation of doubly stochastic matrices and b) the online learning of sparse logistic regression based on the elastic net penalty [START_REF] Zou | Regularization and variable selection via the elastic net[END_REF].

2 Online Convex Optimization with Long-term Constraints

Preliminaries

Consider m convex functions g j : R d → R which induce a convex constraint set

X x ∈ R d : max j∈{1,••• ,m} g j (x) ≤ 0 .
We assume that the set X is bounded so that it is included in some Euclidean ball B with radius R > 0 (to be further discussed in Section 5):

X ⊆ B x ∈ R d : x 2 ≤ R .
Along with the functions g j , we consider a sequence of convex functions f t :

R d → R + such that max t∈{1,••• ,T } max x,x ∈B |f t (x) -f t (x )| ≤ F for some F > 0.
As is typically assumed in online learning [START_REF] Cesa | Prediction, learning, and games[END_REF], the functions g j and f t shall be taken to be Lipschitz continuous. We do not generally assume g j and f t to be differentiable. We further assume that for some finite G > 0 the (sub-)gradients of f and g j are bounded max

j∈{1,••• ,m} max x∈B ∇g j (x) 2 ≤ G, max t∈{1,••• ,T } max x∈B ∇f t (x) 2 ≤ G.
We take the same constant G for, both, g j and f t for simplicity as we can always take the maximum between that of g j and that of f t . Finally, we assume that there exists a finite D > 0 such that the constraint functions are bounded over B:

max j∈{1,••• ,m} max x∈B |g j (x)| ≤ D.
Finally, we note that the set of assumptions enumerated in this section are equivalent to the ones in [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF].

Problem Statement

Let {x t } T t=1 be the sequence of vectors played by the learner and {f t (x t )} T t=1 the corresponding sequence of incurred losses. We aim at efficiently solving the following optimization problem in online fashion:

min x T ∈B f T (x T ) + . . . + min x2∈B f 2 (x 2 ) + min x1∈B f 1 (x 1 ) -min x∈X T t=1 f t (x)
subject to the following long-term constraint:

max j∈{1,••• ,m} T t=1 g j (x t ) ≤ 0.
3 Adaptive Online Algorithms based on a Saddle-point Formulation

Following [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF], we consider a saddle-point formulation of the optimization problem. For any λ ∈ R + , x ∈ B we define the following function:

L t (x, λ) f t (x) + λg(x) - θ t 2 λ 2
where g(x) max j∈{1,••• ,m} g j (x) and {θ t } T t=1 is a sequence of positive numbers to be specified later. The role of g is to aggregate the m constraints into a single function. It otherwise preserves the same properties as those of individual g j 's (sub-differentiability, bounded (sub-)gradients and bounded values; see Proposition 6 in [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF] or Section 2.3 in [START_REF] Borwein | Convex Analysis and Nonlinear Optimization: Theory and Examples[END_REF] for a proof). In the saddle-point formulation (2), we will alternate between minimizing with respect to the primal variable x and maximizing with respect to the dual parameter λ. A closer look at the function λ → L t (x, λ) indicates that we penalize the violation of the constraint g(x) ≤ 0 through, using [u] + max{0, u},

1 2θ t [g(x)] 2 + = sup λ∈R+ λg(x) - θ t 2 λ 2 , (2)
which is a penalty commonly used when going from constrained to unconstrained problems (e.g., Section 17.1 in [START_REF] Nocedal | Numerical Optimization[END_REF]). Also, we can see from (2) that θ t acts as a regularization parameter. We note at this point that in contrast to our method, [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF] make use of a single θ that is constant in all rounds. 1In the sequel, we study the following online algorithm where we alternate between primal-descent and dualascent steps:

• Initialize x 1 = 0 and λ 1 = 0

• For t ∈ {1, • • • , T -1}: x t+1 = Π B (x t -η t ∇ x L t (x t , λ t )) λ t+1 = Π R + (λ t + µ t ∇ λ L t (x t , λ t )),
where Π C stands for the Euclidean projection onto the set C, while {η t } T t=1 and {µ t } T t=1 are sequences of nonnegative step sizes that respectively drive the update of x and λ. The algorithm is in the same vein as the ones proposed in [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF][START_REF] Koppel | A saddle point algorithm for networked online convex optimization[END_REF], but it is adaptive. The step sizes, which are different for the updates of x and λ, are listed in Table 1. They result from the analysis we provide in the next section. We also derive sub-linear regret bounds associated to these instantiations of the sequences {θ t } T t=1 , {η t } T t=1 and {µ t } T t=1 .

Main Results

We begin by listing three sufficient conditions for obtaining sub-linear regret bounds for the proposed algorithm:

(C1): For any t ≥ 2, 1 µt -1 µt-1 -θ t ≤ 0. (C2): For any t ≥ 2, η t G 2 + µ t θ 2 t -1 2 θ t ≤ 0. (C3): For some finite U η > 0, T t=2 1 ηt -1 ηt-1 -σ ≤ U η .
Conditions C1 and C3 impose constraints on the decreasing speed of the step sizes. We note that there is an asymmetry between µ t and η t : while we will always be able to control the norm of the variables x t (by design, they must lie in B), the sequence {λ t } T t=1 is not directly upper-bounded in the absence of further assumptions on the gradient of g, hence the most stringent condition C1 is to avoid any dependencies on λ t . Condition C2 couples the behaviour of the three sequences to guarantee their validity. Finally, C1, C2 and C3 are expressed for t ≥ 2 because of our choice for the initial conditions x 1 = 0 and λ 1 = 0.

Our main result is described in the following theorem, whose proof is in Section 3.2:

Theorem 1. Consider the convex case (σ = 0) and the corresponding instantiations of the sequences µ t , η t and θ t for some β ∈ (0, 1), as summarized in Table 1.

It holds for any T ≥ 1 that

T t=1 ∆f t ≤ R f T RG + D 2 6βRG T β + 2RG 1 -β T 1-β
where ∆f t f t (x t ) -f t (x ), and

T t=1 g(x t ) ≤ 24RG 1 -β R f T + F T T 1-β . Convex (σ = 0) Strongly convex (σ > 0) θ t 6RG t β 6G 2 σt β η t R Gt β 1 σt µ t 1 θt(t+1) 1 θt(t+1) S θ 6RG 1-β T 1-β 6G 2 σ(1-β) T 1-β S η R G(1-β) T 1-β 1 σ (1 + log(T )) S µ 1 6βRG T β σ 6βG 2 T β U η G R T β 0 1 µ1 -θ 1 6RG 6G 2 σ 1 η1 -σ G R 0 Table 1:
Parameter instantiations in different regimes (β denotes some number in (0, 1)).

For the strongly convex case (σ > 0), we also have valid instantiations of η t , µ t , θ t (see Table 1), whose resulting cumulative regret bounds are tighter than those given in Theorem 1, but with the same leading terms. Theorem 1 can be stated in a simplified form, forgetting momentarily about the dependencies on {D, G, R, F }:

T t=1 ∆f t ≤ O(max{T β , T 1-β }), T t=1 g(x t ) ≤ O(T 1-β/2 ).
In particular, by setting β = 2/3, we obtain T t=1 ∆f t ≤ O(T 2/3 ) and T t=1 g(x t ) ≤ O(T 2/3 ), which matches the mirror prox guarantees of [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF] while being valid for general convex constraint sets X as opposed to just polyhedral constraint sets. Similarly, taking β = 1/2, we recover the regret bounds [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF]. We can, of course, also define novel trade-offs between loss and constraint violations, e.g., β = 3/4 with regret bounds of O(T 3/4 ) and O(T 5/8 ) respectively.

T t=1 ∆f t ≤ O(T 1/2 ) and T t=1 g(x t ) ≤ O(T 3/4 ), of Section 3.1 in

Analysis and Proofs

To analyze the above algorithm, we first introduce a series of lemmas. The analysis is analogous to that developed in [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF], which we provide below for selfcontainedness. We begin by upper-bounding the variations of L t with respect to its two arguments. In particular, the following lemma takes advantage of the fact that the partial function λ → L t (x t , λ) is not only concave as considered in [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF], but strongly concave with parameter θ t . This observation is at the origin of our improved regret bounds.

Lemma 1 (Upper bound of L t (x t , λ)-L t (x t , λ t )). For L t (x, λ) as defined above and for non-negative η t , θ t and µ t , we have

L t (x t , λ) -L t (x t , λ t ) ≤ 1 2µt b t -b t+1 -θt 2 b t + µt 2 [∇ λ L t (x t , λ t )] 2
where b t (λ -λ t ) 2 .

Proof.

Expanding (λ -λ t+1 ) 2 yields (λ -λ t+1 ) 2 = λ -Π R + (λ t + µ t ∇ λ L t (x t , λ t )) 2 ≤ λ -(λ t + µ t ∇ λ L t (x t , λ t )) 2 = (λ -λ t ) 2 -2µ t (λ -λ t )∇ λ L t (x t , λ t ) + µ 2 t (∇ λ L t (x t , λ t )) 2 By strong concavity of L t (x t , λ) with respect to λ, L t (x t , λ t ) -L t (x t , λ) ≤ (λ -λ t )∇ λ L t (x t , λ t ) - θ t 2 b t .
Substituting the inequality for µ t (λ -λ t )∇ λ L t (x t , λ t ) completes the proof.

We omit the derivation for x → L t (x, λ t ) that follows similar arguments. We now turn to a lower-bound of the variations of

L t . Lemma 2. Let x = arg min x∈X T t=1 f t (x). Then T t=1 L t (x t , λ) -L t (x , λ t ) ≥ T t=1 ∆f t + λ T t=1 g(x t ) - λ 2 2 T t=1 θ t + 1 2 T t=1 θ t λ 2 t .
Proof. We have L t (x t , λ) -L t (x , λ t ) equal to

f t (x t ) -f t (x ) + λg(x t ) -λ t g(x ) - θ t 2 (λ 2 -λ 2 t ).
We simply notice that g(x ) ≤ 0 to obtain a lower bound -g(x )

T t=1 λ t to complete the proof after summing both sides over rounds t

= 1, • • • , T . Lemma 3. Let a t x t -x 2 . For any σ, θ t ≥ 0, T t=1 1 2η t a t -a t+1 - σ 2 a t ≤ R 2 2 δ η + 1 2 T t=2 a t 1 η t - 1 η t-1 -σ , T t=1 1 2µ t b t -b t+1 - θ t 2 b t ≤ λ 2 2 δ µ + 1 2 T t=2 b t 1 µ t - 1 µ t-1 -θ t
where we have used δ η 1 η1 -σ and δ µ 1 µ1 -θ 1 .

Proof. Shifting indices in the sums for terms that depend on a t+1 /η t , b t+1 /µ t and collecting terms that depend on a t , b t , we then use

a 1 = x 1 -x 2 2 = x 2 2 ≤ R 2 and b 1 = (λ -λ 1 ) 2 = λ 2 to conclude.
We now present the key lemma of the analysis.

T t=1 ∆f t ≤ R f
T , and

T t=1 g(x t ) ≤ 2(S θ + δ µ )(R f T + F T ).
Proof. By the triangle inequality, we have

∇ x L t (x, λ) 2 2 ≤ 2G 2 (1 + λ 2 ) and ∇ λ L t (x, λ) 2 ≤ 2(D 2 + θ 2 t λ 2 ). We then combine Lemmas 1-3, starting from L t (x t , λ) -L t (x * , λ t ) = L t (x t , λ) -L t (x t , λ t ) + L t (x t , λ t ) -L t (x * , λ t ), yielding T t=1 ∆f t + λ T t=1 g(x t ) -λ 2 2 S θ + δ µ ≤ R f T + T t=1 λ 2 t η t G 2 + µ t θ 2 t -1 2 θ t .
Maximizing the left-hand side with respect to λ ∈ R + , we obtain:

T t=1 ∆f t + T t=1 g(xt) 2 + 2 S θ +δµ ≤ R f T + T t=1 λ 2 t η t G 2 + µ t θ 2 t -1 2 θ t .
The regret bound on the loss is obtained by using C2 and [

T t=1 g(x t )] 2 + /(2[S θ + δ µ ]) ≥ 0.
The bound on constraint violations is obtained as above, but by substituting the lower bound t ∆f t ≥ -F T .

In order to discuss the scaling of our regret bounds, we state the next simple lemma without proof Lemma 5. Let β ∈ (0, 1). Then T t=1

1 t β ≤ T 1-β 1-β .
With the above lemmas, we now prove Theorem 1:

Proof of Theorem 1. For the proposed choices of θ t , µ t and η t , we can verify that C1, C2 and C3 hold. Here we focus on the convex case, the strongly convex one following along the same lines. First, we can easily see that C1 is true as long as θ t is non-increasing. Then, we can notice that, given the choice of µ t , condition C2 is implied by the stronger condition η t ≤ θt 6G 2 (satisfied by the choice of η t and θ t in Table 1). This results in

S µ = T t=1 1 θ t (t + 1) ≤ T t=1 t β 6RGt ≤ T β 6βRG . S η = T t=1 η t ≤ R G T 1-β 1 -β , S θ = T t=1 6RG t β ≤ 6RG 1 -β T 1-β , along with 1/µ 1 -θ 1 = 6RG and 1/η 1 -σ = G/R.
The term U η can be obtained by summing the series 1/η t -1/η t-1 = (G/R)(t β -(t -1) β ) over t, which directly simplifies by telescoping for the σ = 0 case, and is identically equal to zero for σ > 0. As a result, we obtain from Lemma 4

T t=1 ∆f t ≤ R f T RG + D 2 6βRG T β + RG 1 -β T 1-β + RG 2
and for the constraint

T t=1 g(x t ) ≤ 2(R f T + F T ) 6RG 1 -β T 1-β + 6RG .
We obtain the desired conclusion by noticing that for any T ≥ 1 and β ∈ (0, 1), we have T 1-β 1-β ≥ 1.

Towards No Violation of Constraints

We next show that our extension also applies to the more specific setting developed in Section 3.2 from [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF], where additional assumptions on the gradient of g can translate into no constraint violations. For the sake of self-containedness, we briefly recall it. Assume that there exist γ ≥ 0 and r > 0 such that the variations of g are lower bounded as min

x∈R d :g(x)+γ=0 ∇g(x) 2 ≥ r. (3) Denote X γ {x ∈ R d : g(x) + γ ≤ 0} ⊂ X .
It can then be shown that (see Theorem 7 in [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF]):

T t=1 f t (x ) - T t=1 f t (x γ ) ≤ G r T γ, (4)
where x and x γ are solutions of min x∈X T t=1 f t (x) and min x∈Xγ T t=1 f t (x) respectively. In words, the gap between the optimal value of the original optimization problem and that of the problem over X γ is well-controlled as a function of (γ, r). Examples where (3) holds include the positive semi-definite cone, as described in Section 4 of [START_REF] Mahdavi | Stochastic gradient descent with only one projection[END_REF]. For space limitation reasons, we state our result in a simplified form, only briefly sketching its proof that follows the same logic as that of the previous section.

Corollary 1. Assume (3) holds. Consider the convex case (σ = 0) and some instantiations of the sequences µ t , η t and θ t for some β ∈ (0, 1), differing from Table 1 only up to numerical constants. There exist c 0 and c 1 depending on {D, G, R, F, r} such that setting γ c 1 T -β/2 , we have for any

T ≥ c 0 T t=1 ∆f t ≤ O(max{T β , T 1-β , T 1-β/2 }),
and no constraint violations T t=1 g(x t ) ≤ 0.

Sketch of proof.

We can apply the same analysis as before to the function g γ (x) g(x) + γ, replacing D by D + γ and adapting the constants in both C2 (i.e., η t G 2 + 3 2 µ t θ 2 t -1 2 θ t ) as well as for the instantiations of µ t , η t and θ t . The regret bound on T t=1 ∆f t is identical as earlier, with additional additive terms 3γ 2 S µ /2 and GT γ/r introduced as a result of (4). As for

T t=1 g(x t ), the term [ T t=1 g(x t )] 2 + becomes here [ T t=1 g(x t ) + γT ] 2
+ , which in turn leads to the same regret bound as previously stated, minus the contribution -γT . We cancel out the constraint violationsscaling in O(T 1-β/2 ) according to Theorem 1-by setting γ = c 1 T -β/2 . Note that c 0 is determined by examining when the extra term 3γ 2 S µ /2 can be upper bounded by those in R f T .

The regret bound presented in Corollary 1 is minimized for β = 2/3, leading to a regret of O(T 2/3 ) with no constraint violations. This result extends Theorem 8 and Corollary 13 from [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF] in that it holds for general convex domains X (as opposed to only polyhedral ones).

Experiments

We ran two sets of experiments to validate the regret bounds obtained for our adaptive algorithms for OCO with long-term constraints and compare to the algorithms proposed in [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF]. First, we examine the online estimation of doubly-stochastic matrices where the convex domain of interest X is polyhedral but whose projection operator is difficult to compute [START_REF] Helmbold | Learning permutations with exponential weights[END_REF][START_REF] Fogel | Aspremont. Convex relaxations for permutation problems[END_REF]. Second, we consider sparse online binary classification based on the elastic net penalty [START_REF] Zou | Regularization and variable selection via the elastic net[END_REF].

We shall refer to our adaptive online gradient descent (A-OGD) for convex f t (i.e., σ = 0) as Convex A-OGD and for strongly convex f t (i.e., σ > 0) as Strongly convex A-OGD, which enjoy the same regret guarantees of O(T 2/3 ) for the loss and constraint. The method of [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF] that handles general convex domains X will be referred to as Convex OGD, while the mirror prox method analyzed in [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF], which is only applicable to polyhedral domains, will be denoted by Convex mirror prox. The parameters of Convex OGD and Convex mirror prox are instantiated according to [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF].

Although we generate the sequence of losses {f t } T t=1 stochastically in the experiments, we would like to emphasize that the regret bounds we obtain are also valid for adversarially-generated sequences, so that it is not required that {f t } T t=1 are generated in i.i.d. fashion. 4.1 Doubly-Stochastic Matrices Doubly-stochastic matrices appear in many machine learning and optimization problems, such as clustering applications [START_REF] Zass | Doubly stochastic normalization for spectral clustering[END_REF] or learning permutations [START_REF] Helmbold | Learning permutations with exponential weights[END_REF][START_REF] Fogel | Aspremont. Convex relaxations for permutation problems[END_REF]. Briefly, for a sequence of matrices {Y t } T t=1 in R p×p , we solve the following optimization problem in an online fashion:

min X∈R p×p T t=1 1 2 Y t -X 2 F ( 5
)
subject to the (linear) convex constraints

X ≥ 0, X1 = 1 and X 1 = 1.
This problem can easily be mapped to OCO setting by assuming that the sequence {Y} T t=1 is generated by random permutation matrices which are known to constitute the extreme points of the set of doublystochastic matrices [START_REF] Birkhoff | Tres observaciones sobre el algebra lineal[END_REF]. We have

d = p 2 , f t (X) = 1 2 Y t -X 2
F and m = p 2 + 4p to describe all the linear constraints, more specifically there are p 2 nonnegativity constraints, along with 4p inequalities to model the 2p equality constraints. This leads to the following instantiations of the parameters controlling f t and g: R = √ p, G = 2R and D = R. Note that we can apply a) Strongly convex A-OGD (since f t is by construction strongly convex with parameter σ = 1), and b) Convex mirror prox since X is polyhedral.

The cumulative regret for the loss and the long-term constraint are shown in Figures 1 and2. They are computed over T = 1000 iterations with d = 64, and are averaged over 10 random sequences {Y t } T t=1 (the standard deviations are not shown since they are negligible). The offline solutions of (5) required for various t ∈ {1, • • • , T } to compute the regret are obtained using CVXPY [START_REF] Diamond | CVXPY: A Python-embedded modeling language for convex optimization[END_REF].

The results shown in Figure 1 and 2 indicate that although the cumulative regret bounds for Strongly convex A-OGD were not demonstrated to be tighter in our analysis than those for Convex A-OGD, they achieve a better cumulative regret for this problem, especially with respect to the long-term constraint. Also, while Convex mirror prox and Convex A-OGD should theoretically exhibit the same behavior, the results suggest that mirror prox is not able to decrease cumulative regret at the same rate as our proposed method. We surmise that this may be due to the fact that the guarantees of Convex mirror prox proved in [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF] only hold for very large T . 2

Sparse Online Binary Classification

Next, we examine the application of sparse online binary classification. Our goal will be to minimize the log-loss subject to a constrained elastic-net penalty: 3 min

x∈R d : x 1+ 1 2 x 2 2 ≤ρ T t=1 log(1 + e -ytx ut ), (6)
where {y t , u t } T t=1 denotes a sequence of label/featurevector pairs and ρ > 0 is a parameter that measures the degree of the sparsity of the solutions of ( 6). This problem is mapped to our formulation by setting

f t (x) = log(1 + e -ytx ut ) with m = 1, g(x) = x 1 + 1 2 x 2 2 -ρ, R = √ 1 + 2ρ -1, 4 G = max{ √ d + R, max t u t 2 } and D = √ dR + R 2 /2.
The sequences {y t , u t } T t=1 are generated by drawing pairs at random with replacement. We solve the above problem using the datasets ijcnn1 and covtype, consisting respectively of 49, 990 and 581, 012 samples of dimension d = 22 and d = 54

2 Theorem 12 from [START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF] requires T ≥ 164(m + 1) 2 , which translates into T > 10 7 in our setting. 3 Constraint formulations with sparsity-inducing terms are sometimes preferred over their penalized counterparts when they express some concrete physical budget, e.g., in the context of learning predictors with low-latency [START_REF] Xu | The greedy miser: Learning under test-time budgets[END_REF]. 4 The value for R is found by noticing that

x 1 + 1 2 x 2 2 ≥ x 2 + 1 2 x 2 2
and solving the resulting secondorder polynomial inequality. We display the mean computed over 10 random sequences {y t , u t } T t=1 .

each 5 . The parameter ρ is set to obtain approximately 30% of non-zero variables. Moreover, and in order to best display cumulative regret, we compute offline solutions of (6) for various t ∈ {1, • • • , T } thanks to an implementation of [START_REF] Defazio | Saga: A fast incremental gradient method with support for non-strongly convex composite objectives[END_REF].

The results are summarized in Figures 3 and4 and represent an average over 10 random sequences {y t , u t } T t=1 (the standard deviations are not shown since they are negligible). The number of iterations T is equal to the number of samples in each dataset. Interestingly, we observe that the constraint is not violated on average (i.e., via a negative cumulative regret) and the iterates x t remain feasible within the domain x 1 + 1 2 x 2 2 ≤ ρ. This tendency is more pronounced for Convex OGD since a closer inspection of the sequence {η t } T t=1 shows numerical values smaller than those of our approach Convex A-OGD (by 2 to 3 orders of magnitude). As a result, starting from x 1 = 0, we found that the iterates generated by Convex OGD do not approach the boundary of the domain, hence increasing regret on cumulative loss. We also note that the offline solutions of (6) always saturate the constraint. Although our analysis predicts that the cumulative regret of Convex OGD associated to the loss (i.e., O(T 1/2 )) should be smaller than that associated to Convex A-OGD (i.e., O(T 2/3 )), Convex A-OGD achieves here a lower cumulative regret. This observation may be explained by the same argument as that described previously, namely that the larger step sizes {η t } T t=1 of Convex A-OGD enables us to make faster progress.

Discussion

In this section, we discuss several generalizations.

Broader families of step sizes. We have assumed that the updates of the primal variable x are driven by a projected gradient step controlled through a single step size η t . Following the ideas developed in [START_REF] Mcmahan | Adaptive bound optimization for online convex optimization[END_REF][START_REF] Duchi | Adaptive subgradient methods for online learning and stochastic optimization[END_REF], we could analyze the regret guarantees of our algorithm when there is a vector of step sizes η t that is given by a diagonal matrix Diag(η t ) ∈ R d×d , updating adaptively and separately each coordinate of x.

Can we identify a better penalty? In the light of (2), it is tempting to ask whether we can find a penalty function that will lead to lower cumulative regret guarantees. To this end, we could for example introduce a smooth, 1-strongly-convex function φ with domain Ω. The saddle-point formulation of the new problem is then given by L t (x, λ) f t (x) + λg(x) -θ t φ(λ), where {θ t } T t=1 is, as earlier, a sequence of non-negative numbers to be specified subsequently for any λ ∈ Ω, x ∈ B. Interestingly, it can be shown that condition C2 becomes a first-order nonlinear ordinary differential inequality in this setting, leading to η t G 2 λ 2 + µ t θ 2 t dφ dλ 2 -θ t φ(λ) ≤ 0, for all λ ∈ Ω. Hence, the above differential inequality suggests a family of penalty functions which we could use. In particular, we see that φ must grow at least quadratically and stay greater than its squared first derivative, which rules out a softmax penalty like λ → log(1+e λ ). Moreover, the maximization with respect to λ in the last step of Lemma 4 introduces the Moreau envelope [START_REF] Lemaréchal | Practical aspects of the moreau-yosida regularization: Theoretical preliminaries[END_REF] of the Fenchel conjugate of φ, namely

φ * S θ (u) sup λ∈Ω λu -S θ φ(λ) -δ µ λ 2 2 .
The goal is then to find a feasible penalty φ of which the inverse mapping u → [φ * S θ ] -1 (u) would minimize the regret bound. For instance, the inverse mapping would scale as u → √ u when using the squared 2 norm over Ω = R + . We defer to future work the study of this admissible family of penalties.

Which enclosing set for X ? Our current analysis relies on the idea that instead of having to perform a projection on X in each update (which could be computationally costly and perhaps intractable in some cases), we restrict the iterates x t to remain within a simpler convex set B ⊇ X . While we assumed de facto an Euclidean ball for B, we could consider sets enclosing X more tightly, while preserving the appealing computational properties. Having a principled methodology to choose B and carefully assessing its impact on the regret bounds is an interesting avenue for future research.

Lemma 4 . 2 2

 42 [Cumulative regret bound] Let x = arg min x∈X T t=1 f t (x) and assume C1, C2 and C3 hold. Define R f T R δ η +G 2 S η +D 2 S µ +R 2 U η , where we have introduced S η T t=1 η t , S µ T t=1 µ t and S θ T t=1 θ t . Then, it holds that

Figure 1 :

 1 Figure 1: Cumulative regret of the loss function for the online estimation of doubly-stochastic matrices. We display the mean computed over 10 random sequences {Y t } T t=1 . (Best viewed in colour.)

Figure 2 :Figure 3 :

 23 Figure 2: Cumulative regret of the long-term constraint for the estimation of doubly-stochastic matrices. We display the mean computed over 10 random sequences {Y t } T t=1 . The embedded graph is a zoom of the area of interest in the original figure. (Best viewed in colour.)

Figure 4 :

 4 Figure 4: Cumulative regret of the constraint for the sparse online binary classification (left: ijcnn1, right: covtype). We display the mean computed over 10 random sequences {y t , u t } T t=1 .

More precisely, in[START_REF] Mahdavi | Trading regret for efficiency: online convex optimization with long term constraints[END_REF], θ is equal to the product of a constant step size times a constant scaling factor.

www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/binary.html


J Le Coz

B Camenen

X Peyrard

G Dramais

Erratum -Uncertainty in open-channel discharges measured with the velocity-area method (2012)

Several formal mistakes can be found in the research paper published by Le Coz et al. [START_REF] Le Coz | Uncertainty in open-channel discharges measured with the velocity-area method[END_REF] in Flow Measurement and Instrumentation. Their conclusions on the introduced method are still valid but the following errors may be detrimental to its correct implementation by others.

As stated in the original paper, uncertainty components written u(X) are relative standard uncertainties (in % of measurand X). Therefore, the right-hand terms of Eqs. 12, 14, 15 and Eq. 16 should be divided by D i and V i , respectively. In Eqs. 14 and 15, the 'mid-section' and 'mean-section' mentions should be inverted. The presented results were not affected by these typos.

Two additional mistakes were actually included in our computations. The uncertainty component, u s , accounting for systematic errors remaining after the best calibration of velocity, width and depth measuring devices was neglected in the application of Eq. 11, instead of being set to 1% as announced. This slightly affected the lowest uncertainty estimates, that typically cannot be lower than 2%. The main mistake lies in Eq. 15 where 8 should be replaced by 4, which means that the uncertainty components u m (D) were systematically underestimated in the presented results. Whereas it was previously obtained to be equivalent to u m (V), it is actually now twice bigger than u m (V), on average. This seems realistic since the transverse velocity profile is usually smoother than the bed profile.

The correct expressions for Eq. 14 and Eq. 15 are:

u m (D i ) = b i 4 √ 3D i tan α (mean -section) (14) u m (D i ) = b 2 i+1 + b 2 i 4 √ 3D i (b i+1 + b i ) tan α (mid -section) (15)
The corrected values of Table 2 in the original paper are presented in Tab. 2. Additional columns for u 2 s and u 2 c,e were included since these terms are no longer negligible for several cases. Typically, u 2 s contributes for almost half of the variance for the measurements in the artificial canals (Gignac and Laboratory flume).

B/D/m max. α U(Q) u 2 s u 2 c,e u 2 m (V, D) u 2 p u 2 ed U(Q) u 2 m slope (

Table 2 :

 2 Results of the uncertainty analysis of the stream discharge measurements test cases (after correction).

					new)	(ratio) (ratio)	(ratio)	(ratio) (ratio) (ISO748) (ratio)
	Arc	5.0	15 •	15 • 10.4%	0%	0%	95%	5%	0%	5.2%	77%
	Ardèche	0.5	41 •	40 •	5.0%	16%	5%	74%	6%	0%	5.1%	82%
	Gignac	0.2	0 •	10 •	2.9%	48%	12%	2%	23%	12%	13%	98%
	Laboratory	0.6	3 •	5 •	3.0%	44%	0%	2%	34%	17%	3.5%	60%
	Doller	1.7	14 •	15 •	7.7%	7%	15%	74%	2%	1%	9.8%	90%

Author-produced version of the article published in Flow Measurement and Instrumentation (2015), vol.46, p. 193-194 The original publication is available at http://www.sciencedirect.com DOI : 10.1016/j.flowmeasinst.2014.07.004

Acknowledgements

We are grateful to Aurélien Despax (LTHE, EDF) and Pierre-Marie Bechon (DREAL Rhône-Alpes) who contributed to the identification of errors in the published article.


Frederic Mazenc
email: frederic.mazenc@l2s.centralesupelec.fr

Michael Malisoff
email: malisoff@lsu.edu.

Silviu-Iulian Niculescu
email: niculescu@lss.supelec.fr

Stability Analysis for Systems with Time-Varying Delay: Trajectory Based Approach

Keywords: delay, time-varying, stability I. INTRODUCTION

Recent work by Mazenc and Malisoff provided a trajectory-based approach to proving stability of time-varying systems with time-varying delay. It uses a contraction lemma, instead of Lyapunov-Krasovskii or Razumikhin functions. Here, we use their lemma, and a Lyapunov function for an undelayed system, to provide a new method to prove stability of linear continuous-time time-varying systems with time-varying bounded delays. No constraint on the upper bound of delay is imposed, nor do we need any differentiability of the delay. Instead, we use an upper bound on an integral average of the delay. We prove input-to-state stability under disturbances.

are time-varying when the delay is zero [START_REF] Gu | Stability of Time-Delay Systems[END_REF]. The motivation for studying time-varying control systems is strong, since tracking problems for nonlinear control systems generally lead to time-varying systems with time-varying linear approximations [START_REF] Mazenc | Reduction model approach for linear time-varying systems with delays[END_REF]. Many contributions require that the largest value of the delay be sufficiently small, or that the matrices of the vector field belong to special compact sets [START_REF] Gu | Stability of Time-Delay Systems[END_REF]Chapt. 6]. Another classical assumption is that the delay h(t) is such that the function φ(t) = t -h(t) is invertible [START_REF] Krstic | Lyapunov stability of linear predictor feedback for time-varying input delay[END_REF]. The contribution [START_REF] Bresch-Pietri | Robust compensation of a chattering time-varying input delay[END_REF] is an exception. In [START_REF] Bresch-Pietri | Robust compensation of a chattering time-varying input delay[END_REF], the function φ(t) = t -h(t) is not assumed to be invertible; instead, an averaging assumption on an integral of |h | 2 is imposed.

The present paper owes a great deal to [START_REF] Bresch-Pietri | Robust compensation of a chattering time-varying input delay[END_REF], because we also use an assumption on an integral involving h. However, we do not require differentiability of h, and [START_REF] Bresch-Pietri | Robust compensation of a chattering time-varying input delay[END_REF] is restricted to constant coefficient linear systems with predictive controls. We establish our results by applying the trajectory-based approach from [START_REF] Mazenc | Trajectory based approach for the stability analysis of nonlinear systems with time delays[END_REF]. The approach from [START_REF] Mazenc | Trajectory based approach for the stability analysis of nonlinear systems with time delays[END_REF] has the potential advantages that (i) it does not require the Lyapunov or small gain conditions that are prevalent in the literature and (ii) it applies to many classes of time-varying systems with timevarying delay. We are not aware of any other technique that can establish the results that we provide in the present paper.

The restrictions on the size of the delay in [START_REF] Gao | A new delay system approach to network-based control[END_REF] and [START_REF] Mazenc | Robustness of nonlinear systems with respect to delay and sampling of the controls[END_REF] are not in general satisfied by the systems we consider here. Moreover, we do not require the time-varying matrices involving the vector fields to belong to specific compact sets, as was imposed in [START_REF] Gu | Stability of Time-Delay Systems[END_REF]Chapt. 6]. Unlike [START_REF] Bresch-Pietri | Robust compensation of a chattering time-varying input delay[END_REF], we consider linear time-varying systems with a time-varying piecewise continuous delay h(t). The requirements from [START_REF] Krstic | Lyapunov stability of linear predictor feedback for time-varying input delay[END_REF] may be violated by our systems, and our results ensure exponential stability in cases where the existing Razumikhin and Lyapunov-Krasovskii methods do not seem to apply.

In Section II, we explain our notation and our key lemma from [START_REF] Mazenc | Trajectory based approach for the stability analysis of nonlinear systems with time delays[END_REF] that we use to prove our main results in Sections III-IV. Section V has illustrating examples. In Section VI, we summarize our findings and suggest future research topics. Sections III-V consist of previously unpublished, original results which are not being submitted elsewhere. [START_REF] Mazenc | Trajectory based approach for the stability analysis of nonlinear systems with time delays[END_REF] In what follows, all dimensions are arbitrary. The usual Euclidean norm of vectors, and the induced norm of matrices, are denoted by | • |. For any measurable essentially bounded R n valued function φ having an interval I in its domain, let |φ| I be its essential supremum over I. Let C 1 denote the set of all continuously differentiable functions, where the domains and ranges will be clear from the context. Given any constant τ > 0, we let C([-τ, 0], R n ) denote the set of all continuous R n -valued functions that are defined on [-τ, 0]. We abbreviate this set as C in , and call it the set of all initial functions. By input-to-state stability (or ISS) of a system of the form ẋ(t) = f (t, x t , u) with respect to functions u : [0, ∞) → D that are valued in some set D, we mean that there are β ∈ KL and γ ∈ K ∞ such that for all initial functions x 0 and all locally bounded piecewise continuous functions u : [0, ∞) → D, the corresponding unique solution x(t) of the system with initial function

II. NOTATION AND KEY LEMMA FROM

x 0 satisfies |x(t)| ≤ β(|x 0 | [-τ,0] , t) + γ(|u| [0,t]
) for all t ≥ 0, where KL and K ∞ are the standard classes of comparison functions [START_REF] Khalil | Nonlinear Systems, Third Edition[END_REF] and for simplicity we always take the initial times to be 0. By piecewise continuous (resp., C 1 ), we mean continuous (resp., C 1 ) except at finitely many points on each bounded interval; this includes the classes of all continuous and C 1 functions when the finite sets are empty. Also, for any continuous function ϕ : [-τ, ∞) → R n and all t ≥ 0, we define ϕ t by ϕ t (m) = ϕ(t + m) for all m ∈ [-τ, 0], i.e., ϕ t ∈ C in is the translation operator. The special case of ISS where u is zero and β(s, t) = c1 se -c2t for some constants c1 > 0 and c2 > 0 is global exponential stability (GES). We use this trajectory-based stability result from [START_REF] Mazenc | Trajectory based approach for the stability analysis of nonlinear systems with time delays[END_REF]:

Lemma 1: Let T * > 0 be a constant. Let a function w : [-T * , ∞) → [0, ∞) admit a sequence {v i } and positive constants v a and v b such that v 0 = 0, v i+i -v i ∈ [v a , v b ] for all i ≥ 0, w is continuous on [v i , v i+1
) for all i ≥ 0, and the left limit lim v→v i -w(v) exists and is finite for each i ∈ N. Let d : [0, ∞) → [0, ∞) be any piecewise continuous function. Assume that there is a constant ρ ∈ (0, 1) such that

w(t) ≤ ρ|w| [t-T * ,t] + d(t) (1)
holds for all t ≥ 0. Then

w(t) ≤ |w| [-T * ,0] e ln(ρ) T * t + 1 (1-ρ) 2 |d| [0,t] (2)
holds for all t ≥ 0. See Section IV-C for more comparisons with [START_REF] Mazenc | Trajectory based approach for the stability analysis of nonlinear systems with time delays[END_REF].

III. PRELIMINARY RESULT A. Statement and Proof of Result

We first study systems

ẋ(t) = A(t)x(t) + B(t)x(t -h(t)) + u(t) (3)
whose stabilizing part A(t)x(t) consists of a term without delay (but see the next section below for other cases). In (3), we assume that the state x is valued in R n , the initial conditions are in C in , h : [0, ∞) → [0, ∞) is a piecewise continuous function, and A : [0, ∞) → R n×n , B : [0, ∞) → R n×n , and u : [0, ∞) → R n are piecewise continuous functions that are bounded in norm over [0, ∞).

The functions u represent uncertainty. We show that even when the term B(t)x(t-h(t)) does not help stabilize the system, we can establish robust stability in cases where the classical stability analysis techniques do not seem to apply; see our example in Section V-A. We introduce

ż(t) = A(t)z(t) (4)
with z valued in R n and the following two assumptions: Assumption 1: There exist a continuous function p 1 : [0, ∞) → R, a C 1 function P : [0, ∞) → R n×n such that P (t) is symmetric and positive definite for all t ≥ 0, and positive constants p 2 , p 3 , and p 4 such that

|p 1 (t)| ≤ p 4 (5)
and

p 2 |z| 2 ≤ V (t, z) ≤ p 3 |z| 2 (6)
hold for all t ≥ 0 and z ∈ R n , where

V (t, z) = z P (t)z, (7)
and such that along all trajectories of (4), we have

V (t, z) ≤ -p 1 (t)V (t, z) (8)
for all t ≥ 0. Assumption 2: There is a constant h * ≥ 0 such that

0 ≤ h(t) ≤ h * for all t ≥ 0 . (9)
Also, there are constants T > 0 and δ ∈ (0, 1) such that

t t-T 2 p2 (|P (m)B(m)| + p 3 |u(m)|)e -t m p1( )d dm + e -t t-T p1(m)dm ≤ δ holds for all t ≥ T, (10)
where P and the p i 's are from Assumption 1.

Our first result for (3) is as follows (but see Remark 1 for a way to convert the conclusion of the following theorem into an ISS estimate with respect to u that holds for all t ≥ 0):

Theorem 1: If Assumptions 1-2 hold, then all solutions x(t) of (3) satisfy

|x(t)| ≤ p3 p2 e ln(δ) T +h * (t-T -h * ) |x| [0,T +h * ] + 2T p3e T p 4 |u| [h * ,t] p2(1-δ) 2 (11)
for all t ≥ T + h * .

Proof: From Assumption 1, it follows that the time derivative of V along all trajectories of (3) satisfies

V (t) ≤ -p 1 (t)V (t, x(t)) + 2x(t) P (t)u(t) + 2x(t) P (t)B(t)x(t -h(t)) (12)
for all t ≥ 0. Using ( 6) and considering the possibilities

V (t, x(t))/p 2 ≤ 1 and V (t, x(t))/p 2 > 1, we get V (t) ≤ -p 1 (t)V (t, x(t)) + 2|P (t)||x(t)||u(t)| + 2|P (t)B(t)||x(t)||x(t -h(t))| ≤ -p 1 (t)V (t, x(t)) + 2|P (t)B(t)| × V (t,x(t)) p2 V (t-h(t),x(t-h(t)) p2 + 2p 3 V (t,x(t)) p2 |u(t)| (13)
and therefore also

V (t) ≤ -p 1 (t)V (t, x(t)) + 2|P (t)B(t)| p2 sup s∈[t-h * ,t] V (s, x(s)) + 2p 3 1 p2 |u(t)|V (t, x(t)) + |u(t)| (14)
for all t ≥ h * , where we also used the fact that |P (t)| ≤ p 3 holds for all t ≥ 0, which follows because (6) gives | P (t)z| ≤ √ p 3 |z| and therefore also

|P (t)z| = P (t) P (t)z ≤ p 3 |z| (15)
for all z ∈ R n and t ≥ 0. Consequently,

V (t) ≤ -p 1 (t)V (t, x(t)) + 2p 3 |u(t)| + 2(|P (t)B(t)|+p3|u(t)|) p2 sup s∈[t-h * ,t] V (s, x(s)) (16)
for all t ≥ h * . Lemma A.1 in the appendix below applied with a(t

) = p 1 (t), a s = p 4 , λ(t) = 2p 3 |u(t)|, g = h * and X(t) = V (t, x(t))
and Assumption 2 allow us to conclude that

V (t, x(t)) ≤ sup s∈[0,T +h * ] V (s, x(s))e ln(δ) T +h * (t-T -h * ) + 2T p3e T p 4 |u| [h * ,t] (1-δ) 2 (17)
holds for all t ≥ h * + T . From ( 6), it follows that

p 2 |x(t)| 2 ≤ p 3 |x| 2 [0,T +h * ] e ln(δ) T +h * (t-T -h * ) + 2T p3e T p 4 |u| [h * ,t] (1-δ) 2 (18)
for all t ≥ h * + T . This allows us to conclude. Remark 1: Our conclusion [START_REF] Haidar | Further remarks on Markus-Yamabe instability for time-varying delay differential equations[END_REF] differs from an ISS estimate because it only holds for t ≥ T + h * , and the usual procedure for using an integrating factor to extend the ISS estimate to [0, ∞) does not apply, because of the time delay. However, we can use the following simple Gronwall inequality argument to extend the ISS estimate [START_REF] Haidar | Further remarks on Markus-Yamabe instability for time-varying delay differential equations[END_REF] to all of [0, ∞).

Set Ā = max{sup t∈[0,T +h * ] |A(t)|, sup t∈[0,T +h * ] |B(t)|}. Then the dynamics (3) gives | ẋ(t)| ≤ 2 Ā|x| [t-h * ,t] + |u| [0,T +h * ] (for all t ∈ [0, T + h * ]
where the corresponding solution is defined). Applying the Fundamental Theorem of Calculus to x(s) on [0, t] for any such t ∈ [0, T + h * ], and then suping on the left side over [0, t], we get

|x| [t-h * ,t] ≤ |x| [-h * ,0] + 2 Ā t 0 |x| [s-h * ,s] ds + (T + h * )|u| [0,T +h * ] . (19)
Next we apply Gronwall's inequality to φ(s) = |x| [s-h * ,s] on [0, t] and use the fact that trajectory values on [0, t] do not depend on future values of u (i.e., causality) to get

|x| [t-h * ,t] ≤ |x| [-h * ,0] e T +h * -t + (T +h * )|u| [0,t] e 2 Ā(T +h * ) (20)
for all t ∈ [0, T + h * ] and therefore also

|x(t)| ≤ e 2 Ā(T +h * ) |x| [-h * ,0] e T +h * -t + (T + h * )e 2 Ā(T +h * ) |u| [0,t] (21)
for all t ∈ [0, T + h * ]. Substituting ( 21) into [START_REF] Haidar | Further remarks on Markus-Yamabe instability for time-varying delay differential equations[END_REF] gives

|x(t)| ≤ p3 p2 e ln(δ) T +h * (t-T-h * ) e (2 Ā+1)(T +h * ) |x| [-h * ,0] + p 3 /p 2 (T + h * )e 2 Ā(T +h * ) |u| [0,t] + 2T p3e T p 4 |u| [0,t] p2(1-δ) 2 (22)
for all t ≥ T + h * . The final ISS estimate is obtained by adding ( 21) and ( 22) and then dividing both sides of the result by 2 to get an ISS estimate that holds for all t ≥ 0.

B. Notable Features of Theorem 1

Before turning to our main result of this paper, we discuss several features of Theorem 1. We do not require p 1 to be nonnegative valued, but Assumptions 1-2 imply that (4) is exponentially stable to zero (GES), by taking B = 0. Since we do not require p 1 to be periodic, it is unclear whether V can be transformed into a strict Lyapunov function for [START_REF] Bresch-Pietri | Robust compensation of a chattering time-varying input delay[END_REF].

Theorem 1 leads to a bound on B such that (3) is GES if (4) is GES. Moreover, we can find a bound on B that is independent of the bound h * on h(t). To see how this can be done, assume that ( 4) is GES and that A is bounded and continuous. For simplicity, we assume that the perturbation u in (3) is the zero function. Then standard results (e.g., [START_REF] Khalil | Nonlinear Systems, Third Edition[END_REF]Theorem 4.14]) allow us to satisfy Assumption 1 with a constant positive value of p 1 (t) = p1 . Then [START_REF] Gu | Stability of Time-Delay Systems[END_REF] holds if there are constants T > 0 and δ ∈ (0, 1) such that

e -T p1 + 2p3|B| [0,∞) p2 T 0 e -p1m dm < δ, (23)
or equivalently, if

|B| [0,∞) < p1 p 2 /(2p 3 ) is satisfied.
Here is an analog where p 1 takes both positive and negative values. Assume that we are given a GES system

ż(t) = N z(t) (24)
for some constant matrix N , and any bounded continuous function q : R → R that admits constants q 0 > 0 and T > 0 such that for all t ∈ R, we have t t-T q( )d ≥ q 0 . For instance, q can be a persistency of excitation function like q( ) = sin 2 ( ). Then solving a Riccati equation provides a positive definite symmetric matrix P and positive constants α, α, and α * such that the time derivative of V (z) = z P z along all trajectories of (24) satisfies V (z) = z (N P + P N )z ≤ -α * V (z) and such that α|z| 2 ≤ V (z) ≤ α|z| 2 for all t ≥ 0 and z ∈ R n . Set A(t) = q(t)N . Then Assumption 1 holds with the choices p 1 (t) = α * q(t), p 2 = α, p 3 = α, and p 4 = |p 1 | [0,∞) . Then we can argue as in the preceding paragraph to conclude that

ẋ(t) = q(t)N x(t) + B(t)x(t -h(t)) (25)
is GES for all piecewise continuous functions h : [0, ∞) → [0, ∞), and for all choices of B : R → R n×n such that

sup t≥T exp -α * t t-T q( )d + t t-T 2p3 p2 |B(m)|exp -α * t m q( )d dm < 1, which is satisfied if |B| [0,∞) < inf t≥0 p2 2p3 t t-T exp -α * t m q( )d dm -1
(1-e -α * q0 ) holds.

Similar reasoning applies if N is time varying, as long as ż = N (t)z admits a time invariant Lyapunov function of the form V (z) = z P z. In summary, Theorem 1 can be viewed as a robustness result for GES of the stable system (4) with respect to the potentially destabilizing added terms B(t)x(t -h(t)) + u(t) with time-varying delays h(t).

IV. MAIN RESULT

A. Statement and Proof of Main Result

We consider systems (3) in situations where (4) is not necessarily exponentially stable. For the sake of simplicity, we do not the consider the case where an additive disturbance u is present (but additive disturbances can also be handled, by a variant of the arguments used in the previous section). Let us introduce the system

ż(t) = H(t)z(t) (26)
where H(t) = A(t) + B(t), and the following assumptions: Assumption 3: The matrices A and B and the delay h are piecewise continuous. Also, there exist a bounded piecewise continuous function p 1 : [0, ∞) → R, positive constants p 2 and p 3 , and a C 1 function P : [0, ∞) → R n×n such that P (t) is symmetric and positive definite for all t ≥ 0, for which: For all t ≥ 0 and z ∈ R n , we have

p 2 |z| 2 ≤ V (t, z) ≤ p 3 |z| 2 , ( 27
)
where V (t, z) = z P (t)z and the time derivative of V along all trajectories of (26) satisfies

V (t, z) ≤ -p 1 (t)V (t, z) (28)
for all t ≥ 0. Assumption 4: There is a constant h * ≥ 0 such that

0 ≤ h(t) ≤ h * ( 29
)
hold for all t ≥ 0. Also, there exist constants T > 0 and δ ∈ (0, 1) such that with the choice

r(t) = 2|P (t)B(t)| p 2 t t-h(t) [|A(m)| + |B(m)|] dm, (30)
we have

e -t t-T p1(m)dm + t t-T r(m)e -t m p1( )d dm ≤ δ (31)
for all t ≥ 2(T + h * ). Also, A and B are bounded. We prove: Theorem 2: If the system (3) satisfies Assumptions 3-4, then (3) satisfies GES.

Proof: For all t ≥ h * , we have

ẋ(t) = H(t)x(t) -B(t)[x(t) -x(t -h(t))] = H(t)x(t) -B(t) t t-h(t) ẋ(m)dm (32)
Using the expression for ẋ(m), we obtain ẋ(t) = H(t)x(t)-B(t)L(t) for all t ≥ 2h * , where

L(t) = t t-h(t) [A(m)x(m)+B(m)x(m-h(m))]dm. ( 33
)
From Assumption 3, we deduce that for all t ≥ 2h * , we have

V (t) ≤ -p 1 (t)V (t, x(t)) -2x(t) P (t)B(t)L(t). ( 34
)
As an immediate consequence, we get

V (t) ≤ -p 1 (t)V (t, x(t)) + 2|P (t)B(t)||x(t)||L(t)| ≤ -p 1 (t)V (t, x(t)) + 2|P (t)B(t)| V c /p 2 [t-2h * ,t] × t t-h(t) A (m) V c /p 2 [t-2h * ,t] dm = -p 1 (t)V (t, x(t)) + r(t)|V c | [t-2h * ,t] ,
where V c (m) = V (m, x(m)) and

A (m) = |A(m)| + |B(m)|. ( 35
)
Lemma A.1 in the appendix below and Assumption 4 allow us to conclude that V (t, x(t)) converges exponentially to zero. Then (27) implies that x(t) converges exponentially to the origin. This proves Theorem 2.

B. Notable Features of Theorem 2

Remark 2: Since A and B are piecewise continuous and bounded, all solutions of (3) are well-defined and defined over [0, ∞) and the function r in (30) is well-defined.

Remark 3: We do not require p 1 to be nonnegative valued. Assumptions 3-4 imply that the system (26) is globally exponentially stable.

Remark 4: Theorem 2 is not covered by the results of [START_REF] Gu | Stability of Time-Delay Systems[END_REF]Chapt. 6]. Also, Theorem 2 can be extended to systems with several time-varying delays. Through Assumption 3, Theorem 2 takes into account the case where the term B(t)x(t -h(t)) has a stabilizing effect.

Remark 5: To motivate Assumption 4, consider the case where p 1 , P , A and B are all constant, and where p 1 is nonnegative. Then (31) simplifies to

e -T p1 + 2|P B|(|A|+|B|) p2 t t-T h(m)e (m-t)p1 dm ≤ δ. (36)
This inequality is satisfied if

1 T t t-T h(m)dm ≤ p 2 2|P B| (|A| + |B|) δ -e -T p1 T (37)
is satisfied, which pertains to an average value of h.

C. More Comparisons with [20]

The main strategy in [START_REF] Mazenc | Trajectory based approach for the stability analysis of nonlinear systems with time delays[END_REF] is to prove ISS of systems of the form

ẋ(t) = f (t, x(t), ζ(t, τ ), ∆(t)) (38)
with respect to disturbances ∆, where ζ(t, τ ) = (x 1 (tτ 1 (t)), x 2 (t -τ 2 (t)), . . . , x n (t -τ n (t))) for piecewise continuous delay functions τ i , by assuming ISS of the system

ẋ(t) = f (t, x(t), u(t)) (39)
with respect to the combined disturbance u(t) = (ξ(t, τ ), ∆(t)). While our key Lemma 1 is from [START_REF] Mazenc | Trajectory based approach for the stability analysis of nonlinear systems with time delays[END_REF], neither theorem in the present work is covered by [START_REF] Mazenc | Trajectory based approach for the stability analysis of nonlinear systems with time delays[END_REF], e.g., because Assumption 1 does not imply ISS of ẋ(t) = A(t)x(t) + u(t), and because the function p 1 in Assumption 1 is not necessarily positive valued.

V. ILLUSTRATIONS

A. Illustration of Theorem 1

Let d > 0 and c ∈ (0, 1) be any constants such that

(1 -c)d < 1-e -1 2 . ( 40
)
Let b be the periodic function of period 1 defined by

(i) b(t) = 0 when t ∈ [0, c) and (ii) b(t) = d when t ∈ [c, 1]. Consider the system ẋ(t) = -x(t) + b(t)x(t -1), (41)
where x is valued in R.

+ t t-T 2|P (m)B(m)| p2 e -t m p1( )d dm (42)
satisfies

Ξ(t) = e -T + 2 t t-T b(m)e m-t dm (43)
for all t ≥ 0. Choosing T = 1, we obtain

Ξ(t) ≤ e -1 + 2(1 -c)d < 1 , (44)
by (40). Theorem 1 allows us to conclude.

B. Illustration of Theorem 2

Let l > 0 be a constant, and k ∈ N be an odd integer. We consider the system

ẋ(t) = -x(t -h(t)) , (45)
where x is valued in R, and the time-varying delay

h(t) = max{0, l sin k (t)}. (46)
To the best of our knowledge, Razumikhin's theorem does not apply to (45), and no Lyapunov-Krasovskii functional construction technique in the literature applies to this system. With the notation of Section IV, we choose

P (t) = 1, p 1 (t) = 2, p 2 = p 3 = 1, H = -1, A = 0, B = -
Pick any constant T > 0. Then, by the Lebesgue Dominated Convergence Theorem, there exists a constant k > 0 (which is sufficiently large, and which depends on l and T ) such that there is a constant δ ∈ (0, 1) satisfying (31) for all t ≥ 0. Thus, Assumptions 3-4 hold. Theorem 2 allows us to conclude that (45) is globally exponentially stable to 0. Since l > 0 is arbitrarily large, we have exponential stability without any constraint on sup m h(m). To our knowledge, such a result cannot be established by any other technique.

VI. CONCLUSIONS AND OPEN PROBLEMS

Time-varying delays model many important effects, such as increasing latencies in rehabilitation as a muscle becomes fatigued. Also, sampling in controllers can be modeled using piecewise C 1 time-varying delays h(t) where h (t) = 1 almost everywhere, resulting in a sawtooth shaped delay function. We developed new stability analysis techniques for piecewise continuous time-varying linear systems with timevarying delays. Our results can be used when stabilizing control laws must be designed under delays. Since we do not require the standard condition h (t) < 1, our results are quite general. One of our main tools was a trajectorybased approach from [START_REF] Mazenc | Trajectory based approach for the stability analysis of nonlinear systems with time delays[END_REF], whose advantages are that (a) it circumvents the need for Lyapunov-Krasovskii functionals or to check small-gain conditions and (b) it applies to many classes of time-varying systems with time-varying delay, and therefore is a versatile alternative to traditional methods.

The results we presented here are beyond the scope of [START_REF] Mazenc | Trajectory based approach for the stability analysis of nonlinear systems with time delays[END_REF], e.g., because here we allow sup t h(t) to be arbitrarily large, and because we introduced a useful new integral condition that allows us to establish the exponential stability. We hope to extend the present paper in several directions. We conjecture that our results can be extended to cases that have distributed delays and to nonlinear systems, including applications to networked systems with uncertainty. It would also be interesting to seek generalizations to adaptive control problems, where the objectives include both tracking and identification of unknown model parameters, as well as to cases where there are also state dependent or rapidly varying delays [START_REF] Bekiaris-Liberis | Compensation of state-dependent input delay for nonlinear systems[END_REF], [START_REF] Bekiaris-Liberis | Robustness of nonlinear predictor feedback laws to time-and state-dependent delay perturbations[END_REF], [START_REF] Fridman | On complete Lyapunov-Krasovskii functional techniques for uncertain systems with fast-varying delays[END_REF] or sampling [START_REF] Mirkin | Some remarks on the use of time-varying delay to model sample-and-hold circuits[END_REF].

APPENDIX

The following is a time-varying version of Halanay's lemma [START_REF] Halanay | Differential Equations: Stability, Oscillations, Time Lags[END_REF], and was used to prove Theorems 1-2:

Lemma A.1: Let X : [0, ∞) → [0, ∞) be a piecewise C 1 function that admits constants g ≥ 0 and a s ≥ 0 and piecewise continuous functions a holds for all t ≥ g, and assume that the left limit lim t→p -X(t) exists and is finite at each p ≥ 0. Assume that there exist two constants T > 0 and δ ∈ (0, 1) such that e

: [0, ∞) → [-a s , ∞), b : [0, ∞) → [0, ∞),

  1, andr(t) = 2h(t) = 2 max{0, l sin k (t)}. e -t m p1( )d dm = e -2T + t t-T2max{0, l sin k (m)}e 2(m-t) dm .

  and λ : [0, ∞) → [0, ∞) such that Ẋ(t) ≤ -a(t)X(t) + b(t) sup s∈[t-g,t] X(s) + λ(t) (A.1)

  It follows that for all t ≥ T + g, we haveζ(t) -ζ(t -T ) ≤ T +g t + 1 (1-δ) 2 |κ| [T +g,t+T +g] (A.11) for all t ≥ 0. Hence, for all t ≥ T + g, the inequalityX(t) ≤ |X| [0,T +g] e

	Proof: Let
			ζ(t) = e	t 0 a(m)dm X(t).	(A.4)
	Then, we can use (A.1) to get
	ζ(t) = e	t 0 a(m)dm	Ẋ(t) + a(t)X(t)
						(A.5)
	≤ e	t 0 a(m)dm b(t) sup	X(s) + λ(t)
						s∈[t-g,t]
	e for all t ≥ g. t 0 a(s)ds b(m) sup m	X(s) + λ(m) dm.	(A.6)
	t-T			s∈[m-g,m]
	From the definition of ζ, we deduce that
	X(t) ≤ e -t t-T a(m)dm X(t -T )
		+	t	b(m)e -t m a( )d	sup	X(s)dm
			t-T			s∈[m-g,m]
		+	t	λ(m)e -t m a( )d dm
			t-T
	≤	t-T a(m)dm + e -t	t
						t-T
			t
		+
			t-T
				s∈[t-T -g,t]	X(s) + κ(t),	(A.7)
	where					t
		κ(t) = e T as	λ(m)dm .	(A.8)
						t-T
	We now apply Lemma 1 with
	T (A.9)
	Since (A.7) implies that
	w(t) ≤ δ	sup s∈[t-T -g,t]	w(s) + κ(t + T + g)	(A.10)
	for all t ≥ 0, we deduce from Lemma 1 that
				ln(δ)
	w(t) ≤ |w| [-T -g,0] e

-t t-T a(m)dm + t t-T b(m)e -t m a( )d dm ≤ δ (A.2)

holds for all t ≥ T + g. Then, the inequality

X(t) ≤ |X| [0,T +g] e ln(δ) T +g (t-T -g) + T e T as |λ| [g,t] (1-δ) 2 (A.3) holds for all t ≥ T + g. b(m)e -t m a( )d dm × sup s∈[t-T -g,t] X(s) λ(m)e -t m a( )d dm .

From (A.2), it follows that, for all t ≥ T + g, the inequality

X(t) ≤ δ sup * = T + g, w(t) = X(t + T + g),

and

d(t) = κ(t + T + g). ln(δ) T +g (t-T -g) + |κ| [T +g,t+T +g] (1 -δ) 2 (A.12)

is satisfied for all t ≥ T + g, which proves the lemma, since X(t) has no dependence on values κ(s) for values of s on the interval [t, t + T + g].

Supported by NSF-ECCS Grants 1102348 and 1408295 and Roy P. Daniels Professorship #3 in LSU College of Science.


Frederic Mazenc

Michael Malisoff

Reduction Model Approach for Systems with a Time-Varying Delay

Keywords: delay, time-varying, stabilization

We provide a reduction model approach for achieving global exponential stabilization of linear systems with a time-varying pointwise delay in the input. We allow the delay to be discontinuous and uncertain. We also provide a stability result based on a different dynamic extension that ensures input-to-state stability with respect to additive uncertainties on the dynamics. Instead of the usual Lyapunov-Krasovskii or Razumikhin methods, we use a trajectory based approach.

I. INTRODUCTION

This note continues our search (begun in [START_REF] Mazenc | Trajectory based approach for the stability analysis of nonlinear systems with time delays[END_REF], [START_REF] Mazenc | New technique for stability analysis for time-varying systems with delay[END_REF], and [START_REF] Mazenc | Reduction model approach for linear time-varying systems with delays[END_REF]) for novel methods to prove global stabilization for systems with time delays. Our search is motivated by the ubiquity of input delays in engineering applications with feedback [START_REF] Dieulot | Tracking control of a nonlinear system with input-dependent delay[END_REF], [START_REF] Downey | Compensating for fatigue-induced time-varying delayed muscle response in neuromuscular electrical stimulation control[END_REF], [START_REF] Gu | Stability of Time-Delay Systems[END_REF], [START_REF] Gu | Survey on recent results in the stability and control of time-delay systems[END_REF], [START_REF] Marquez | Analysis and Control of Oilwell Drilling Vibrations: A Time-Delay Systems Approach[END_REF], [START_REF] Mazenc | Generating positive and stable solutions through delayed state feedback[END_REF], [START_REF] Mondié | Finite spectrum assignment of unstable time-delay system with a safe implementation[END_REF], [START_REF] Petit | Motion planning for two classes of nonlinear systems with delays depending on the control[END_REF] and the fact that classical methods for undelayed systems can rarely cope with the more complicated systems that result from allowing input delays [START_REF] Richard | Time-delay systems: an overview of some recent advances and open problems[END_REF]. For instance, while classical Lyapunov functions are suited for proving stability of systems without delays, one often replaces Lyapunov functions by Lyapunov-Krasovskii functionals [START_REF] Fridman | On complete Lyapunov-Krasovskii functional techniques for uncertain systems with fast-varying delays[END_REF] or Ruzumikhin functions to cope with stability problems for delayed systems.

It is often useful to prove stabilizability of time delay systems using the following two step process. First, one solves the stabilization problem with the input delays set to zero, often by building a Lyapunov function for the closed loop undelayed system and then finding decay estimates for the Lyapunov function. Then, one reintroduces the input delay and converts the Lyapunov function into a Lyapunov-Krasovskii functional for the corresponding input delayed systems, to find upper bounds on the input delays that the system can tolerate without destroying the stability. One advantage of this so-called emulation approach is that it can allow the use of relatively simple controllers. However, emulation cannot always cope with communications and other engineering applications that can have long delays [START_REF] Gao | A new delay system approach to network-based control[END_REF].

Reduction is a useful alternative to emulation, where the control uses a dynamic extension and can compensate for arbitrarily long input delays [START_REF] Artstein | Linear systems with delayed controls: a reduction[END_REF], [START_REF] Bresch-Pietri | Adaptive control scheme for uncertain time-delay systems[END_REF], [START_REF] Figueredo | Robust stability criteria for uncertain systems with delay and its derivative varying within intervals[END_REF], [START_REF] Kwon | Feedback stabilization of linear systems with delayed control[END_REF], [START_REF] Mazenc | Lyapunov-Krasovskii functionals and application to input delay compensation for linear timeinvariant systems[END_REF]. It has its origins in the classical Smith predictor [START_REF] Smith | A controller to overcome dead time[END_REF] for linear systems and so is also called prediction [START_REF] Jankovic | Recursive predictor design for linear systems with time delay[END_REF], [START_REF] Krstic | Lyapunov stability of linear predictor feedback for time-varying input delay[END_REF],

Mazenc is with EPI DISCO INRIA-Saclay, the Laboratoire des Signaux et Systèmes (L2S, UMR CNRS 8506), CNRS, Centrale-Supélec, Université Paris-Sud, 3 rue Joliot Curie, 91192, Gif-sur-Yvette, France. frederic.mazenc@l2s.centralesupelec.fr. Supported by l'Institut pour le Contrôle et la Décision de l'Idex Paris-Saclay (iCODE).

Malisoff is with the Department of Mathematics, 303 Lockett Hall, Louisiana State University (LSU), Baton Rouge, LA 70803-4918, USA. malisoff@lsu.edu. Supported by NSF-ECCS Grants 1102348 and 1408295 and Roy P. Daniels Professorship #3 in LSU College of Science.

but recent prediction results apply to a much wider class of systems, including adaptive and perturbed systems [START_REF] Bekiaris-Liberis | Nonlinear Control under Nonconstant Delays[END_REF], [START_REF] Bekiaris-Liberis | Compensation of state-dependent input delay for nonlinear systems[END_REF], [START_REF] Bekiaris-Liberis | Robustness of nonlinear predictor feedback laws to time-and state-dependent delay perturbations[END_REF], [START_REF] Bresch-Pietri | Prediction-based stabilization of linear systems subject to input-dependent input delay of integral-type[END_REF], [START_REF] Krstic | Delay Compensation for Nonlinear[END_REF]. Recently, Bresch-Pietri and Petit used a transport PDE, reduction, and a generalization of an inequality due to Halanay [START_REF] Halanay | Differential Equations: Stability, Oscillations, Time Lags[END_REF], [START_REF] Ivanov | Halanay inequality, Yorke 3/2 stability criterion, and differential equations with maxima[END_REF] to prove stability of linear time invariant systems with known input delays h(t) that can satisfy ḣ(t) > 1 for some t's [START_REF] Bresch-Pietri | Robust compensation of a chattering time-varying input delay[END_REF]. This differs from the usual treatments that assume that sup t ḣ(t) ≤ 1. Thus, [START_REF] Bresch-Pietri | Robust compensation of a chattering time-varying input delay[END_REF] is a significant advance in the area of stabilization of systems with time-varying delays. A key assumption in [START_REF] Bresch-Pietri | Robust compensation of a chattering time-varying input delay[END_REF] is that | ḣ| is small on average, without requiring a bound on | ḣ|, so [START_REF] Bresch-Pietri | Robust compensation of a chattering time-varying input delay[END_REF] covers chattering phenomena in delays that occur in many engineering systems and so are of considerable interest.

Here, we pursue a related line of research involving reduction, but our results differ from [START_REF] Bresch-Pietri | Robust compensation of a chattering time-varying input delay[END_REF] in several important ways. First, we allow discontinuities, as well uncertainties, in the delays. Second, our assumptions are different, and they lead to stability proofs that are based on our trajectory approach from [START_REF] Mazenc | Trajectory based approach for the stability analysis of nonlinear systems with time delays[END_REF] instead of transport PDEs. The approach from [START_REF] Mazenc | Trajectory based approach for the stability analysis of nonlinear systems with time delays[END_REF] was not used in [START_REF] Bresch-Pietri | Robust compensation of a chattering time-varying input delay[END_REF]. Finally, we provide an alternative approach that is based on a dynamical extension from [START_REF] Manitius | Finite spectrum assignment problem for systems with delays[END_REF], [START_REF] Mondié | Finite spectrum assignment of unstable time-delay system with a safe implementation[END_REF] from the theory of spectrum assignment.

In the next section, we provide preliminaries, including a key generalization of Halanay's inequality. In Section III, we present our main result, which allows uncertain or discontinuous delays. In Section IV, we provide our alternative approach using dynamic extensions from [START_REF] Mondié | Finite spectrum assignment of unstable time-delay system with a safe implementation[END_REF]. In Section V, we illustrate our work using an unstable secondorder dynamics. We close in Section VI by summarizing the value added by our work and suggesting future research problems. This paper is a companion to [START_REF] Mazenc | Stability analysis for systems with time-varying delay: trajectory based approach[END_REF], which uses our trajectory based approach from [START_REF] Mazenc | Trajectory based approach for the stability analysis of nonlinear systems with time delays[END_REF] without using reduction, under completely different assumptions from the ones in this paper and assuming the delays are known.

II. PRELIMINARIES

In all of what follows, all dimensions are arbitrary. The standard Euclidean norm of vectors, and the induced matrix norm, are denoted by | • |, I r is the identity matrix in dimension r, and | • | I denotes the supremum over any interval I ⊆ R. Also, λ max (Q) > 0 (resp., λ min (Q) > 0) denotes the largest (resp., smallest) eigenvalue of any symmetric positive definite matrix Q. Let C 1 be the set of all continuously differentiable functions, where the domains and ranges will be clear from the context. For any constant τ > 0, let C([-τ, 0], R n ) be the set of all continuous R nvalued functions having the domain [-τ, 0]. We abbreviate this set as C in , and call it the set of all initial functions. For what follows, we take τ = sup t h(t), where h(t) is the delay. For any continuous function ϕ : [-τ, ∞) → R n and all t ≥ 0, we define ϕ t by ϕ t (m) = ϕ(t + m) for all m ∈ [-τ, 0]. A function defined on an interval I ⊆ R is called piecewise continuous provided it is continuous except at finitely many points on each bounded subinterval of I.

We use this variant of the Halanany inequality:

Lemma 1: Let X : [0, ∞) → [0, ∞) be a piecewise C 1 function that admits constants g ≥ 0 and a s ≥ 0 and piecewise continuous functions a

: [0, ∞) → [-a s , ∞), b : [0, ∞) → [0, ∞), and λ : [0, ∞) → [0, ∞) such that Ẋ(t) ≤ -a(t)X(t) + b(t) sup s∈[t-g,t] X(s) + λ(t) (1)
holds for all t ≥ g. Assume that there exist two constants T > 0 and δ ∈ (0, 1) such that

e -t t-T a( )d + t t-T b(q)e -t q a( )d dq ≤ δ (2)
holds for all t ≥ T + g. Then, the inequality

X(t) ≤ |X| [0,T +g] exp ln(δ) T +g (t -T -g) + T e T as |λ| [g,t] (1-δ) 2 (3)
holds for all t ≥ T + g.

For the proof of Lemma 1, see [START_REF] Mazenc | Stability analysis for systems with time-varying delay: trajectory based approach[END_REF]; its proof is based on the trajectory approach from [START_REF] Mazenc | Trajectory based approach for the stability analysis of nonlinear systems with time delays[END_REF]. Estimate ( 3) is a special case of input-to-state stability, which we define next.

We first let K be the set of all strictly increasing continuous functions

α : [0, ∞) → [0, ∞) such that α(0) = 0; if, in addition, α is unbounded, then we say that it is of class K ∞ . We say that a continuous function β : [0, ∞) × [0, ∞) → [0, ∞)
is of class KL provided for each s ≥ 0, the function β(•, s) belongs to class K, and for each r ≥ 0, the function β(r, •) is non-increasing and β(r, s) → 0 as s → ∞. We say that a system of the form ẋ(t) = f (x(t), u(t -h(t)), ε(t)) having a controller u (with a time delay h(t) that admits a constant g > 0 such that 0 ≤ h(t) ≤ g for all t ≥ 0) is input-to-state stable (ISS) [START_REF] Khalil | Nonlinear Systems, Third Edition[END_REF] with respect to the set of all piecewise continuous functions ε : [0, ∞) → R m provided there exist functions β ∈ KL and γ ∈ K ∞ such that

|x(t)| ≤ β(|x 0 | [-g,0] , t) + γ(|ε| [0,t] ) (4)
holds for all t ≥ 0, all continuous initial functions x 0 : [-g, 0] → R n , and all piecewise continuous functions ε : [0, ∞) → R m . This agrees with the more familiar global exponential stability condition when the perturbations ε are identically zero and β(s, t) = c 1 se -c2t for some constants c 1 > 0 and c 2 > 0.

III. MAIN RESULT

Consider the linear system

ẋ(t) = Ax(t) + Bu(t -h(t) -γ(t)) (5)
where A ∈ R n×n and B ∈ R n×m are constant, u is the control, h is a known delay, and γ represents uncertainty in the delay. We make several assumptions, but see below for results under different controllers that also provide input-tostate stability and which have several degrees of freedom in terms of parameters we can tune. First, we assume:

Assumption 1:
The function h is of class C 1 and there is a constant g > 0 such that

0 ≤ h(t) ≤ g (6)
holds for all t ≥ 0. The unknown function γ is piecewise continuous, and there are a known constant γ c ≥ 0 and a known continuous function γ b such that the inequalities

0 ≤ γ(t) ≤ γ b (t) ≤ γ c (7)
hold for all t ≥ 0. Assumption 2: The pair (A, B) is controllable. By Assumption 2, there is a matrix K ∈ R m×n such that R = A+BK is Hurwitz. This provides a constant c > 0 and a symmetric positive definite matrix Q ∈ R n×n such that

QR + R Q ≤ -cQ . ( 8
)
Choose a symmetric positive definite matrix S ∈ R n×n such that Q = SS, i.e., S = √ Q. We also define

N = SA, M = SAS -1 , B K = BK, (9)
α(t) = c -2|M || ḣ(t)| , and (10)
β(t) = 2|S||B K |e |A|h(t) 2|S -1 || ḣ(t)| + γ b (t)a 1 + a 2 t-h(t) t-h(t)-γ b (t) | ḣ( )|d (11)
where

a 1 = |R||S -1 | + 2e |A|g |B K S -1 | and a 2 = |A||S -1 | + 2e |A|g |B K S -1 | -|B K S -1 |. (12)
Our final assumption is: Assumption 3: There exists a constant δ ∈ (0, 1) such that t t-2(γc+g) β(q)exp -

t q α( )d dq + exp - t t-2(γc+g) α( )d ≤ δ (13)
holds for all t ≥ 2(γ c + g).

We prove the following result: Theorem 1: If Assumptions 1-3 hold, then the control

u(t) = K e Ah(t) x(t) + t t-h(t) e A(t-) Bu( )d (14)
renders the origin of (5) globally exponentially stable.

Proof:

In what follows, all (in)equalities are to be understood to hold for all t ≥ 0, unless otherwise noted. We set

q(t) = | ḣ(t)| 2 and ζ(t) = e Ah(t) x(t) + Γ(t), where Γ(t) = t t-h(t) e A(t-) Bu( )d . ( 15
)
Then the time derivative of ζ along all trajectories of (5) is

ζ(t) = e Ah(t) ẋ(t) + ḣ(t)Ae Ah(t) x(t) + AΓ(t) + Bu(t) -(1 -ḣ(t))e Ah(t) Bu(t -h(t)) = [1 + ḣ(t)]Aζ(t) + Bu(t) -ḣ(t)A t t-h(t) e A(t-) Bu( )d + ḣ(t)e Ah(t) Bu(t -h(t)) + e Ah(t) B[u(t-h(t)-γ(t)) -u(t-h(t))]. (16)
Our control u(t) = Kζ(t) from ( 14) and Assumption 2 give

ζ(t) = Rζ(t) + ḣ(t)Aζ(t) + ω(t, ζ t ) + κ(t, ζ t ) (17)
where

ω(t, ζ t ) = -ḣ(t)AΓ(t) + ḣ(t)e Ah(t) B K ζ(t -h(t)) (18)
and

κ(t, ζ t ) = e Ah(t) B K [ζ(t -h(t) -γ(t)) -ζ(t -h(t))] . (19)
Then, since our choice of M in [START_REF] Downey | Compensating for fatigue-induced time-varying delayed muscle response in neuromuscular electrical stimulation control[END_REF] gives SM S = QA, it follows from (8) that the time derivative of

V (ζ) = ζ Qζ = |Sζ| 2 (20)
along all trajectories of (17) satisfies

V (t) ≤ -cV (ζ(t)) + 2 ḣ(t)(ζ(t) S)M (Sζ(t)) + 2ζ(t) Q[ω(t, ζ t ) + κ(t, ζ t )] ≤ -α(t)V (ζ(t)) + 2 V (ζ(t))|Sω(t, ζ t )| + 2 V (ζ(t))|Sκ(t, ζ t )| . (21)
Next, note that our choice

q(t) = | ḣ(t)| 2 gives |Sω(t, ζ t )| ≤ q(t) -N t t-h(t) e A(t-) B K ζ( )d + Se Ah(t) B K ζ(t -h(t)) . (22)
By replacing B K by B K S -1 S in [START_REF] Manitius | Finite spectrum assignment problem for systems with delays[END_REF], it follows from our choice [START_REF] Krstic | Lyapunov stability of linear predictor feedback for time-varying input delay[END_REF]

of V that |Sω(t, ζ t )| ≤ q(t) |Se Ah(t) B K S -1 | V (ζ(t -h(t))) +|N | t t-h(t) e |A|(t-) |B K S -1 | V (ζ( ))d .
Using the fact that |N |/|A| ≤ |S| when A = 0 and our bound g on |h(t)| from (6), it follows that

|Sω(t, ζ t )| ≤ 2 q(t)|S||B K S -1 |e |A|h(t) sup s∈[t-g,t] V (ζ(s)) . (23)
Combining ( 21) with ( 23), we get

V (t) ≤ -α(t)V (ζ(t)) + 2 V (ζ(t))|Sκ(t, ζ t )| + 4|S||B K S -1 | q(t)e |A|h(t) sup s∈[t-g,t] V (ζ(s)). (24)
Next, observe that since Q = SS, we can use the bound

| ζ(t)| ≤ |(R + ḣ(t)A)S -1 Sζ(t)| + ḣ(t)A t t-h(t) e A(t-) B K S -1 Sζ( )d -ḣ(t)e Ah(t) B K S -1 Sζ(t -h(t)) + e Ah(t) B K [S -1 Sζ(t -h(t) -γ(t)) -S -1 Sζ(t -h(t))] (25)
and our formula [START_REF] Krstic | Lyapunov stability of linear predictor feedback for time-varying input delay[END_REF] to get

| ζ(t)| ≤ |(R + ḣ(t)A)S -1 | V (ζ(t)) + q(t)|A| × t t-h(t) e A(t-) B K S -1 V (ζ( ))d + q(t) e Ah(t) B K S -1 V (ζ(t-h(t))) +|e Ah(t) B K S -1 | V (ζ(t-h(t)-γ(t))) + |e Ah(t) B K S -1 | V (ζ(t-h(t))). ( 26
)
As an immediate consequence, we get

| ζ(t)| ≤ |(R + ḣ(t)A)S -1 | V (ζ(t)) + q(t)|A||B K S -1 | t t-h(t) e A(t-) V (ζ( ))d + e Ah(t) B K S -1 q(t) + 1 V (ζ(t -h(t))) + V (ζ(t -h(t) -γ(t))) ≤ η(t) sup s∈[t-g-γc,t] V (ζ(s)), (27)
where

η(t) = |(R + ḣ(t)A)S -1 | + 2e |A|h(t) |B K S -1 | + 2 q(t)e |A|h(t) |B K S -1 | -q(t)|B K S -1 | . ( 28
)
It readily follows from ( 12) and ( 28) that

| ζ(t)| ≤ µ(t) sup s∈[t-g-γc,t] V (ζ(s)), (29)
where µ(t) = a 1 + a 2 q(t). Next, notice that

|κ(t, ζ t )| ≤ |e Ah(t) B K | t-h(t) t-h(t)-γ(t) | ζ( )|d . ( 30
)
Consequently,

|κ(t, ζ t )| ≤ |e Ah(t) B K | t-h(t) t-h(t)-γ(t) µ( )d × sup s∈[t-2g-2γc,t-h(t)] V (ζ(s)) . (31)
From ( 24), we deduce that

V (t) ≤ -α(t)V (ζ(t)) + 4|S||B K S -1 | q(t)e |A|h(t) × sup s∈[t-g,t] V (ζ(s)) +2|S||e Ah(t) B K | t-h(t) t-h(t)-γ(t) µ( )d × sup s∈[t-2g-2γc,t] V (ζ(s)) ≤ -α(t)V (ζ(t)) + β(t) sup s∈[t-2g-2γc,t] V (ζ(s)). (32)
By Lemma 1 and Assumption 3, we conclude that V (ζ(t)) converges exponentially to zero. Since Q is positive definite, it follows that ζ(t) converges exponentially to zero. Hence, since h(t) is bounded, x(t) = e -Ah(t) (ζ(t)-Γ(t)) converges exponentially to zero, which proves the theorem.

IV. ALTERNATIVE APPROACH

We next provide an approach for systems of the form

ẋ(t) = Ax(t) + Bu(t -h(t)) + ε(t) (33)
having state space R n , where A ∈ R n×n and B ∈ R n×m are constant matrices, ε is an unknown piecewise continuous disturbance, the (nonnegative) delay h(t) is known, and: Assumption 4: The pair (A, B) is controllable, h is C 1 , and there is a constant g > 0 such that sup t h(t) ≤ g.

The stabilizability of (A, B) implies that we can construct matrices A f ∈ R m×m and B f ∈ R m×n such that

H = A B B f A f (34)
is Hurwitz; see [START_REF] Mondié | Finite spectrum assignment of unstable time-delay system with a safe implementation[END_REF] for one such construction. We can also determine a symmetric and positive definite matrix Q and a constant c > 0 such that the inequality

QH + H Q ≤ -cQ holds. For each ζ = (ρ, β) ∈ R n × R m , we redefine V by V (ζ) = ζ Qζ (35)
and we choose any constants c ρ > 0 and c β > 0 such that

|β| ≤ c β V (ζ) and |ρ| ≤ c ρ V (ζ) (36)
hold for all ζ = (ρ, β) ∈ R n × R m . For instance, we can take c β and c ρ both equal to 1/ λ min (Q). Setting S = √ Q as before, and choosing the functions a(t) = 0.9c and

b(t) = 2|S|| ḣ(t)| c ρ |A| + c β |A| h(t) 0 e A B d + c β e Ah(t) B , (37)
our final assumption is as follows:

Assumption 5: With the preceding choices of a(t) and b(t), there exist constants T > 0 and δ ∈ (0, 1) such that

e -0.9cT + t t-T b( )e -(t-)0.9c d ≤ δ (38)
holds for all t ≥ T + g. We can then prove: Theorem 2: If Assumptions 4-5 hold, then [START_REF] Richard | Time-delay systems: an overview of some recent advances and open problems[END_REF] in closed loop with u(t) = β(t), where β is any solution of

β(t) = A f β(t)+B f e Ah(t) x(t)+ t t-h(t) e A(t-) Bβ( )d , (39)
is input-to-state stable with respect to the set of all piecewise continuous functions ε : [0, ∞) → R n .

Proof: Choose any piecewise continuous function ε : [0, ∞) → R n and let Assumptions 4-5 hold. By Lemma 1 and (38), the theorem will follow once we prove that

V (t) ≤ -a(t)V (ζ(t)) + b(t) sup ∈[t-g,t] V (ζ( )) + 40 c |S| 2 e 2|A|g |ε(t)| 2 (40)
holds along all solutions of the closed loop system for all t ≥ T + g. Let ρ(t) denote the quantity in squared brackets on the right side of (39), so

β(t) = A f β(t) + B f ρ(t). Then ρ(t) = Aρ(t) + Bβ(t) + ḣ(t)A [ρ(t) - t t-h(t) e A(t-) Bβ( )d + ḣ(t)e Ah(t) Bβ(t -h(t)) + e Ah(t) ε(t). (41) Since ζ(t) = (ρ(t), β(t)) ∈ R n+m for all t ≥ 0, we get ζ(t) = Hζ(t) + ḣ(t) ψ(t) 0 + e Ah(t) ε(t) 0 , (42)
where

ψ(t) = A ρ(t) - t t-h(t) e A(t-) Bβ( )d + e Ah(t) Bβ(t -h(t)) . (43)
Hence, [START_REF] Zhou | Truncated Predictor Feedback for Time-Delay Systems[END_REF] satisfies the following along trajectories of (42):

V (t) ≤ -cV (ζ(t)) + 2 ḣ(t)ζ(t) Q ψ(t) 0 + 2ζ(t) Q e Ah(t) ε(t) 0 . (44)
Using the fact that Q = SS, we obtain |ζ (t)Q| ≤ |S| V (ζ(t)), so

V (t) ≤ -cV (ζ(t)) + 2|S|| ḣ(t)| V (ζ(t))|ψ(t)| + 2|S| V (ζ(t)) e Ah(t) ε(t) . (45)
Also, our conditions (36) on c β > 0 and c ρ > 0 give

|ψ(t)| ≤ e Ah(t) B c β V (ζ(t -h(t))) +|A| c ρ V (ζ(t)) + t t-h(t) e A(t-) B c β V (ζ( ))d . Consequently, |ψ(t)| ≤ c ρ |A| + c β |A| h(t) 0 e A B d +c β e Ah(t) B sup ∈[t-g,t] V (ζ( )). (46)
Combining ( 45) with (46), we get

V (t) ≤ -cV (ζ(t)) + b(t) sup ∈[t-g,t] V (ζ( )) +2|S| V (ζ(t)) e Ah(t) ε(t) . (47)
Also, by the triangle inequality jk ≤ 0.1j 2 + 10k 2 with j and k taken to be the corresponding terms in curly braces in (48), and our bound g on h(t) from Assumption 4, we get

2|S| V (ζ(t)) e Ah(t) ε(t) ≤ cV (ζ(t)) 2 √ c |S|e |A|g |ε(t)| ≤ c 10 V (ζ(t)) + 40 c |S| 2 e 2|A|g |ε(t)| 2 (48)
for all t. If we now use (48) to upper bound the last right side term in (47), the desired estimate (40) then follows from our choice of a(t). This proves the theorem.

V. ILLUSTRATION

We revisit the unstable second order linear dynamics from [START_REF] Bresch-Pietri | Robust compensation of a chattering time-varying input delay[END_REF], which is the special case of the following when the unknown perturbation term ε(t) is the zero function:

ż(t) = 0 1 -1 1 z(t) + 0 1 u(t -h(t)) + ε(t). (49)
In this section, we only apply Theorem 2 and therefore assume that h ∈ C 1 and bounded by some constant g > 0, but we can also apply Theorem 1 to cover cases where the delay can have discontinuities and be uncertain. Choosing

A = 0 1 -1 1 and B = 0 1 , (50)
the corresponding matrix M = A + BK is Hurwitz with the choice K = -(2, 3). In fact, we can satisfy P M + M P ≤ -cP with the choices P =

holds for all t ≥ 0, where S = √ Q, Q is defined by

Q = P + ν 2 K K -ν 2 K -ν 2 K ν 2 I m , (53)
ν > 0 is any constant, and the constants c ρ > 0 and c β > 0 satisfy (36) with V (ζ) = ζ Qζ. This provides an interesting alternative to the corresponding result in [START_REF] Bresch-Pietri | Robust compensation of a chattering time-varying input delay[END_REF] because it allows us to conclude input-to-state stability with respect to additive uncertainties ε (which were not considered in [START_REF] Bresch-Pietri | Robust compensation of a chattering time-varying input delay[END_REF]) using the alternative controller from our Theorem 2 (which is based on a dynamic extension that was also not considered in [START_REF] Bresch-Pietri | Robust compensation of a chattering time-varying input delay[END_REF]), and because we include the degree of freedom ν > 0.

VI. CONCLUSIONS

We proposed two approaches for proving stability of linear time invariant systems that apply to cases where the delay could be unknown and not necessarily C 1 , and where the system is subjected to additive uncertainties on the right side. In both cases, we allow the known C 1 part h(t) of the delay to exhibit chattering phenomena, where h(t) is bounded, but where there is a bound on an integral average of | ḣ| instead of on ḣ itself. Therefore, our work built on the significant work [START_REF] Bresch-Pietri | Robust compensation of a chattering time-varying input delay[END_REF] on chattering delays, by also allowing uncertainties in the delay or in the system that were not considered in [START_REF] Bresch-Pietri | Robust compensation of a chattering time-varying input delay[END_REF]. There are many degrees of freedom in applying our methods, such as the coefficient matrices in our dynamic extensions. In our future work, we hope to develop ways to exploit the degrees of freedom to make our work applicable to the broadest possible class of systems and chattering delays.

  and c = 0.735089.(51) Also, using the fact that |B| = 1 and relatively simple calculations, one checks that Assumptions 4-5 will hold if there are also constants δ ∈ (0, 1) and T > 0 such thatt t-T | ḣ( )|d ≤ δ-e -0.9cT2|S| cρ|A|+c β e |A|g (1+g|A|)