{'fraction_non_alphanumeric': 0.06357300696923339, 'fraction_numerical': 0.026177120516743157, 'mean_word_length': 3.31025641025641, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Forward Euler Scheme for Nonconvex Lipschitz Differential Inclusions Converges with Rate One

In a previous paper it was shown that the Forward Euler method applied to differential inclusions where the right-hand side is a Lipschitz continuous set-valued function with uniformly bounded, compact values, converges with rate one. The convergence, which was there in the sense of reachable sets, is in this paper strengthened to the sense of convergence of solution paths. An improvement of the error constant is given for the case when the set-valued function consists of a small number of smooth ordinary functions.


Introduction
In this paper we extend the convergence result from [4]. The following differential inclusion is considered: x ′ (t) ∈ F x(t) , where x 0 ∈ R d , and F is a function from R d to the compact subsets of R d .
In [4], it is shown that if F is uniformly bounded in the sense that and Lipschitz continuous with respect to Hausdorff distance, then the Forward Euler method converges with rate one. For the definition of the Hausdorff distance we need the following notation (as in [4]). We denote by B the closed unit ball in R d . The Minkowski sum of two nonempty sets C, D ⊂ R d is defined by the multiplication by a scalar, λ > 0, by λC = λc | c ∈ C , and the sum of an element c ∈ R d and a set C by The Hausdorff distance is given by H(C, D) = inf λ ≥ 0 | C ⊂ D + λB and D ⊂ C + λB .
We will denote by |·| the Euclidean norm, when applied to a vector, and the Euclidean operator norm, when applied to a matrix. We consider solutions The convergence result in [4] concerns the reachable sets This was an extension of the previous first order convergence result in [2] in the sense that the set-valued function F did not need to be convex. In [3], the non-convex case was presented, although in a different form (see [4]), but there only half-order convergence was proved. Although the convergence of the reachable sets in (1.5) is what is needed in many situations, e.g. in optimal control (see [4]), it is weaker than the convergence of solution paths, the type of convergence used in e.g. [2] and [3]. In section 2 we show that the first-order convergence result for non-convex differential inclusions can be extended so that it gives convergence of solution paths. The proof is actually only a minor change of the proof in [4]. Another weakness with the convergence result in (1.5) is that the constant depends quadratically on the dimension. In [4] it was shown that this constant can not be expected to be smaller than of order √ d in general. In section 2 a partial improvement is given for the case where the differential inclusion is a control problem with few control parameters. In section 3 two results which are needed in the proof of the theorem involving few control parameters are presented.

The Results
We introduce the same set-valued maps that was used in [4]. Let ϕ and ψ be functions from R d into the non-empty compact subsets of R d , defined by where co denotes the convex hull. If A is a subset of R d we define and similarly for the set-valued maps ψ and F We will use the following result for convex differential inclusions. It is taken from [2], where it is formulated in a slightly more general setting than the one presented here. The convergence of solution paths to non-convex differential inclusions is given next. Proof. Let {η n } N n=0 be a solution to the scheme η n+1 ∈ ψ(η n ), for 0 ≤ n ≤ N − 1, which satisfies (2.1). By lemma 2.1 in [4] it follows that the set-valued function co F (x) is Lipschitz continuous in the Hausdorff distance with the same constant as F (x). Therefore Theorem 2.1 guarantees the existence of such a solution {η n }.
Let ε be any positive number, n an integer such that d ≤ n ≤ N , and ξ n−d a point in R d such that Similarly as in the proof of Theorem 3.4 in [4] we have the following inclusion: By the proof of Theorem 3.5 in [4] it holds that Let us extend the solution {ξ n } up to n = N , by letting {ξ n } N n=N −d+1 be any solution to (2.3) Hence (2.4) holds for all 0 ≤ n ≤ N . This together with (2.1) gives (2.2) Let us now consider the situation where the set-valued function F is given by and where we have smoothness, in the sense that there exists a constant S > 0, such that Let us assume that we also have the following bound on the Jacobians: Proof. This proof follows the same basic lines as the proof of Theorem 2.2.
Hence we assume that we have a solution {η n } N n=0 to the scheme η n+1 ∈ ψ(η n ), for 0 ≤ n ≤ N − 1, which satisfies (2.1). Let ε be any positive number, n an integer such that Similarly as in the proof of Theorem 3.4 in [4] we have the following inclusion:

By Theorems 3.3 and 3.2 we have
Therefore, there must exist a ξ n−M +2 ∈ ϕ(ξ n−M +1 ), such that From this we have that Hence As in the proof of Theorem 2.2 we can extend {ξ n } up to N and have This together with (2.1) gives us (2.9).

The fully discrete case
We present here two results, Theorems 3.2 and 3.3, that are useful for the proof of Theorem 2.3. We will use the following well-known result, the Carathéodory Theorem: Theorem 3.1. The convex hull of an arbitrary subset A of R d is given by For a proof, see [1].
Proof. We start by introducing the notation To begin with, we will make the assumption that the functions f i are given by 2) Afterwards, we will consider the general case. For simplicity, we will prove (3.1) for the case where M = d + 1. The general result follows directly from this. We will also assume that x 0 = 0, to simplify the presentation.
Since we now assume that the functions f i are given by (3.2), we have When we sum the terms in (3.3) under the consideration of (3.4), we see that Letx be the approximation of x, where all terms of power three or larger in ∆t have been dropped, i.e.
With the bounds on A i and b i from (2.7)and (2.8), we have that With a Taylor expansion of the function f (x) = (1 + x) d+1 around x = 0, we establish that Step 2. We now consider the convex combination where x 1 and x 2 are two elements in ϕ d+1 (x 0 ), such that in the expression in (3.3) for x 1 , none of the indices i n equals one, while for x 2 , N of the indices equal one. We will see how well the convex combination in (3.6) can be represented by another convex combination, wherex 1 andx 2 both have precisely one index i n equal to one in the expression in (3.3). Pick any n ∈ {1, 2, . . . , d + 1}. Assume that we definex 1 by changing the index i n (denote i n = k) in the expression (3.3) for x 1 to one. Theñ Simiarly, we definex 2 by exchanging all the indices for which i n = 1 to i n = k. Then the first order term in (3.7) is the same as in (3.6). The second order term in the differencex 1 − x 1 in (3.8) is bounded in magnitude by 2KLd∆t 2 . Since this bound holds independently of which of the indices was changed, it follows that the second order term in the differencex 2 − x 2 is bounded in magnitude by 2N KLd∆t 2 . Hence the difference in the second order term between the convex combinations in (3.6) and in (3.7) is bounded by In step 1, we established that the sum of all terms of order higher than or equal to three in ∆t for every element in ϕ d+1 (x 0 ) is bounded as in (3.5). We thereby have (3.9) Step 3. Let z be any element in co ϕ d+1 (x 0 ) . By the Carathéodory Theorem (Theorem 3.1), we have that there exists a G ≤ d + 1 and points and constants x i ∈ ϕ d+1 (x 0 ) and α i > 0, for 1 ≤ i ≤ G, such that and G i=1 α i = 1. We can then write where γ i ≥ 0 for 1 ≤ i ≤ d + 1 and d+1 i=1 γ i = d + 1. It must hold that at least one of the coefficients γ i ≥ 1. For simplicity, let us assume that γ 1 ≥ 1. We will now present an algorithm which gives us an approximation of z in the form of a convex combination of points in ϕ d+1 (x 0 ) which all have one index i n = 1 in the formula (3.3). We also give an error bound of this approximation.
Let I ⊂ {1, 2, . . . , G} be the index set of all the points x i in (3.10) for which none of the indices i 1 in the formula for the points in ϕ d+1 (x 0 ) equals one. Let J be a set which consists of the weights α i corresponding to elements in I, i.e. i ∈ I if and only if α i ∈ J.
If I = ∅, we already have what we are aiming for. Let us therefore assume that I is nonempty, and for simplicity that i = 1 is one of the elements therein. Take one element in {1, 2, . . . , d + 1} \ I, such that the corresponding element x i in the convex combination (3.10) is of the form x i = x 0 + ∆t(N b 1 + · · · ) + higher order terms, with N ≥ 2. Such an element must exist, since γ 1 ≥ 1. For simplicity, let us assume that x 2 is one such element. We may write 1 α 1 + α 2 (α 1 x 1 + α 2 x 2 ) = x 0 + ∆t(kb 1 + · · · ) + higher order terms.
One of the two following cases must hold: (1) k > 1. When this is the case we rewrite as follows: Since k > 1 we have that α 2 − α 1 /(N − 1) is positive. By the result from step 2, we have the approximation result in (3.9), with some pointsx 1 andx 2 , both being of the form x 0 + ∆t(b 1 + · · · ) + higher order terms.
Together with (3.11), this implies that (2) k ≤ 1. In this case we rewrite as follows: Since k ≤ 1 we have that α 1 − (N − 1)α 2 is nonnegative. Similarly as in case (1), we have If case (1) holds we let and remove i = 1 from I and α 1 from J. If case (2) holds we let and replace α 1 with (N − 1)α 2 in J. We then iterate the process above with z replaced byẑ, and the new sets I and J. We continue this process until the sets I and J are empty, and we have an approximationz of z of the form where everyx i is of the form x i = x 0 + ∆t(mb 1 + · · · ) + higher order terms, with m an integer greater than or equal to one. We note that the factor N α 2 , appearing in the error estimate in (3.15) is the same as the weights of the new pointsx 1 andx 2 in (3.14). The same holds also for case (1), with (3.13) and (3.12). Since the total weight of the points that have been changed can not be larger than one, we have that Step 4. We now approximate the pointz in (3.16) by a point in ϕ d (x 0 + ∆tf 1 (x 0 )). Consider any pointx i in the convex combination in (3.16). Wheñ x i is computed by equation (3.3) we know that at least one of the indices must equal one. Let us assume that i n = 1. We denote byx i the element in ϕ d (x 0 + ∆tf 1 (x 0 )) we obtain by switching the indices i 1 and i n = 1 in the expression forx i in (3.3). We then have the differencē We may get a bound for the magnitude of the differencex i −x i by using the bounds on |A i | and |b i | from (2.7) and (2.8) and the bound on the higher order terms ofx i andx i in (3.5). We get the largest possible difference if n = d + 1: Since iα i = 1, we therefore have that Step 5. We now consider the contribution to the error from the fact that we may not have (3.2), but instead the functions f i satisfy (2.6). Denote by P the set co ϕ d+1 (x 0 ) when it is computed using (3.2). The set co ϕ d+1 (x 0 ) in the general case satisfies the inclusion An error of size r is made also when is approximated using ( Proof. To begin with, let us assume that (3.20) We will show that this implies that ψ co(ϕ M −1 (z)) ⊂ co ϕ M (z) . Let v be any unit vector in R d and consider the function over the set x, α 1 , . . . , α M : x ∈ co(ϕ M −1 (z)), α i ∈ R, α i ≥ 0, The function is continuous, and the set is compact, and hence there is a maximizer x * , α * 1 , . . . , α * M . We note two things: (1) Since the function is linear, its maximum over co ϕ M −1 (z) is attained at a point in ϕ M −1 (z). (2) Since the function is linear, its maximum over is attained at a point where one of the α i :s are one.
Since v can be any element in R d , these facts imply that co ψ co(ϕ M −1 (z)) = co ϕ N (z) , Similarly, P ⊂ co ϕ M (z) + rB.