{'fraction_non_alphanumeric': 0.05367339170156071, 'fraction_numerical': 0.02199382481072622, 'mean_word_length': 3.80960130187144, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Convexity of reachable sets of nonlinear ordinary differential equations

We present a necessary and sufficient condition for the reachable set, i.e., the set of states reachable from a ball of initial states at some time, of an ordinary differential equation to be convex. In particular, convexity is guaranteed if the ball of initial states is sufficiently small, and we provide an upper bound on the radius of that ball, which can be directly obtained from the right hand side of the differential equation. In finite dimensions, our results cover the case of ellipsoids of initial states. A potential application of our results is inner and outer polyhedral approximation of reachable sets, which becomes extremely simple and almost universally applicable if these sets are known to be convex. We demonstrate by means of an example that the balls of initial states for which the latter property follows from our results are large enough to be used in actual computations.


Introduction
Reachability problems play a central part in a wide range of control related problems, including safety and liveness verification, diagnosis, controller synthesis, optimization and others [1,2,3,4,5,6,7]. The vast majority of methods developed in that context compute approximations of reachable sets in an intermediate step [8,3,5], which may simplify considerably if the reachable set is known to be convex. Consider, for example, an autonomous ordinary differential equationẋ = f (x) with smooth flow ϕ : U ⊆ R×R n → R n , a subset Ω ⊆ R n of initial states and some t 1 ∈ R with {t 1 }×Ω ⊆ U, and assume Ω is closed with nonempty interior and smooth boundary ∂Ω. Inner and outer polyhedral approximations to the reachable set ϕ(t 1 , Ω) from Ω at time t 1 where f : U ⊆ R×R n ×R m → R n and u is from a set U of admissible controls, and denote the reachable set of (1) from Ω ⊆ R n at time t 1 by R(t 1 , Ω), R(t 1 , Ω) = {ϕ(t 1 ) | ϕ(0) ∈ Ω and ϕ : [0, t 1 ] → R n is a solution of (1) for some u ∈ U} .
A result of Pliś implies that, under suitable assumptions, which include convexity conditions on Ω and on images of f (t, x, ·), the reachable set R(t 1 , Ω) is convex for sufficiently small t 1 > 0 [22]. Lojasiewicz improved upon that result by giving an explicit upper bound on t 1 [23]. For prescribed t 1 > 0 and Ω a singleton, Polyak has shown under different hypotheses that R(t 1 , Ω) is convex if U is a ball of sufficiently small radius in the space of square integrable functions [0, t 1 ] → R m [24]. Recently, Azhmyakov, Flockerzi and Raisch [25] have presented a related result for a closed-loop variant of (1) to which we give a counterexample in section 4. Further sufficient conditions for convexity of the reachable set of (1) are known for rather special classes of right hand sides of (1), e.g. [26,27,28].
When applied to the problem described at the beginning of this section, the results from [22,18,19] cited above ensure that the reachable set ϕ(t 1 , Ω) is convex if Ω is a Euclidean ball of radius r, and t 1 [22,23] or r [23,18,19] does not exceed some bound. However, that bound could be extremely small and of no practical value, as is the case with the reachability problem studied by Polyak [24, p. 262].
In this paper, we present a necessary and sufficient condition for the convexity of the reachable set of the ordinary differential equation (ODE) from a ball Ω of initial values. (Note that the uncertainty comes from a set of initial values only. In contrast to the control system (1) investigated in [22,23,24], there are no inputs to (2).) In particular, convexity is guaranteed if Ω is sufficiently small, and we provide an upper bound on the radius of Ω, which can be directly obtained from the right hand side f of (2). We also demonstrate by means of an example that the balls of initial states for which our results imply the convexity of the reachable set are large enough to be used in actual computations, such as in local programming techniques [19] and polyhedral approximation of reachable sets discussed at the beginning of this section. Our results extend those in [29,30,31]. The remaining of this paper is structured as follows. After having introduced basic terminology in section 2, we establish a criterion for the convexity of a sublevel set Ω, in terms of generalized second-order directional derivatives of g in section 3, where g : U ⊆ X → R is of class C 1,1 and X is a real Banach space. We also present a criterion, rather than a sufficient condition, for the image F (Ω) of Ω under a C 1,1 -diffeomorphism F to be convex. In section 4 we investigate reachable sets from a ball Ω of initial states through solutions of the ordinary differential equation (ODE) (2), where f : U ⊆ R × X → X is continuous and X is a real Hilbert space. We establish a sharp upper bound on the radius of Ω that ensures convexity of the reachable set under the assumption that f is of class C 1,1 with respect to its second argument and also present a necessary and sufficient condition for convexity under the assumption that f is of class C 2 with respect to its second argument. In section 5 we apply our results to the equations of the damped mathematical pendulum. The reader will notice that stronger smoothness assumptions than those adopted in this paper would have simplified both notation and arguments considerably. However, such simplification would have come at the expense of narrowing applicability of our results since many commonly used models of physical systems involve C 1,1 -functions that are not of class C 2 , e.g. [32,Sec. 9.1]. On the other hand, if we had weakened smoothness requirements further, beyond C 1,1 , certain geometric properties of the boundary of Ω and F (Ω), respectively, that are related to curvature, would have become lost. See also the short discussion at the end of section 3. To conclude, we believe that for the problems investigated in this paper, C 1,1 -smoothness of both maps and sets is a rather natural assumption.

Preliminaries
Throughout this paper, "iff" abbreviates "if and only if", and X and Y denote real Banach spaces with norm · unless specified otherwise. B(x, r) andB(x, r) denote the open and closed, respectively, ball of radius r centered at x, and the space of continuous linear operators X → Y is denoted by L(X, Y ).
R and R + denote the field of real numbers and its subset of nonnegative real numbers, respectively, and [a, b], ]a, b[, [a, b[, and ]a, b] denote the closed, open and halfopen, respectively, intervals with end points a and b, a < b.
sign denotes the signum function. We write y ≥ x and x ≤ y for x, y ∈ R n if y − x ∈ R n + . The domain of a map f is denoted by dom f , f •g denotes the composition of f and g, (f • g)(x) = f (g(x)), id denotes the identity map, f −1 is used for the inverse of f as well as for preimages, and ker f denotes the nullspace of f if f is linear. If L is k-linear, we set Lh k := L(h, . . . , h).
Arithmetic operations involving subsets of a linear space are defined pointwise, e.g. αM := {αy | y ∈ M}, M + N := {y + z | y ∈ M, z ∈ N} if α ∈ R and M, N ⊆ X. ∂M denotes the boundary of M ⊆ X, and dim M denotes the dimension of a linear subspace M ⊆ X. D j f denotes the derivative of order j of f , and D j i f , the partial derivative of order j with respect to the ith argument of f , and D i f := D 1 i f , f ′ := Df := D 1 f , and f ′′ := D 2 f . C k denotes the class of k times continuously differentiable maps, and C k,1 , the class of maps in C k with (locally) Lipschitz- A K-submersion is a submersion of class K whenever K is one of the classes of maps defined above.
For f : U ⊆ X → R of class C 1 with U open, we define the four generalized second-order directional derivatives D 2 ± f and D 2 ± f , for all x ∈ U and all h, k ∈ X. If D 2 is any of the operators defined above, we note that D 2 f is positively homogeneous in both its second and its third argument and define For these and related concepts and results, see [33,34] and the references given there.
Let I ⊆ R be an interval, U ⊆ I × X be relatively open in I × X, the map f : U → X be (locally) Lipschitz-continuous with respect to its second argument and continuous, and is the maximal solution of the initial value problem composed of (2) and the initial condition x(t 0 ) = x 0 [9]. The map (t, x) → ϕ(t, 0, x) is called the flow of (2) if ϕ is the general solution of (2) and (2) is autonomous.
Let now X be a Hilbert space with inner product ·|· . Two vectors x and y are perpendicular, x ⊥ y, if x|y = 0. x and L * denote the norm of x and the adjoint of the linear map L, respectively, with respect to ·|· . We define continuous maps µ ± : L(X, X) → R by The following result is sometimes referred to as Ważewski's inequality. Its proof given in [35] carries over to the Hilbert space setting.
2.2 Proposition. Let I ⊆ R be an interval, A : I → L(X, X) be continuous, and x : I → X be a solution ofẋ = A(t)x. Then for all t, t 0 ∈ I with t ≥ t 0 .

Convexity of images of sublevel sets under diffeomorphisms
In this section, we present a necessary and sufficient condition for the convexity of the image F (Ω) of a sublevel set Ω from (3) under a diffeomorphism F . We assume that both the map g from (3) and the diffeomorphism F are of class C 1,1 ; see our remarks at the end of section 1. We therefore use the generalized derivatives defined in (4)-(5); the corresponding differentiation operators are denoted D throughout this section. We first present a characterization of the convexity of sublevel sets on which our subsequent results are based. Note that the requirement that Ω be closed is automatically met if U = X.
3.1 Theorem. Let U ⊆ X be open, g : U → R be continuous and a C 1,1submersion on its zero set, and let Ω defined by (3) be closed and connected. Let further D 2 be one of the four operators defined in (4)- (5).
Proof. Assume ∂Ω = ∅ without loss and observe that our hypotheses imply is a convex open neighborhood of the origin, and there is an open interval V containing the origin such that Z = x + W + V v and µ(h) ∈ V for all h ∈ W , and An application of the implicit function theorem to the equation for all h ∈ dom µ and all ξ ∈ ker g ′ (x), where dom µ denotes the domain of µ and Let µ be such a representation. It follows from (6) that Z ∩ Ω is convex iff µ is; see [36] for a proof of an analogous result on epigraphs. Further, (6) yields g ′ (x)v < 0, and (7) implies that µ is actually of class C 1,1 . We prove for all h ∈ dom µ and all ξ ∈ ker g ′ (x), which is the key relation.
since µ and g ′ are continuous, g ′ (x)v < 0, and g ′ (x)ξ = 0. As g ′ is uniformly Lipschitz-continuous in a neighborhood of x and µ ′ (0) = 0 we obtain which implies (9). Therefore, for D = D 2 + , for all representations κ of ∂Ω about y with respect to the direction v and all ζ ∈ ker g ′ (y). For the other three operators defined in (4)-(5), (10) is obtained in exactly the same way. Let now h ∈ dom µ be arbitrary, let P be the projection operator along v onto ker g ′ (x), let y = x + h + vµ(h), and define κ on a neighborhood of the origin in ker for all ζ ∈ ker g ′ (y). Choose convex open neighborhoods of the origin (11) and (10) for ζ = p ′ (h)ξ give (8). With (8) at our disposal, we are now in a position to prove the theorem. It follows from (8) for all h ∈ dom µ and all ξ ∈ ker g ′ (x). By Prop. 2.1, the latter condition is equivalent to the convexity of µ, which in turn is equivalent to the convexity of Z ∩ Ω for some neighborhood Z ⊆ X of x. As Ω is closed and connected, application of a (generalization of a) theorem of Tietze-Nakajima [37] completes the proof.
The criterion for the convexity of the set Ω presented in Theorem 3.1 takes the form of a condition on the map g that defines Ω. In finite dimensions, i.e., if X = R n , the oriented distance function of Ω is a C 1,1 -submersion on its zero set under our assumptions [38], and hence, is a natural choice for the map g in Theorem 3.1. However, the condition presented in Theorem 3.1 actually describes metric properties of the boundary of Ω rather than properties of maps defining Ω. In particular, if X = R n and the map g is of class C 2 , then D 2 g(x, h 2 ) = g ′′ (x)h 2 , and the restriction of g ′′ (x) to ker g ′ (x) coincides with the second fundamental form [39] of ∂Ω at x up to a positive scalar factor. Hence, Theorem 3.1 implies the following well-known result: A closed, connected set of class C 2 is convex iff the second fundamental form of its boundary is positive semi-definite everywhere.
Next we present a criterion for the convexity of the image of a sublevel set Ω under a diffeomorphism. Note that the requirement that F (Ω) be closed is automatically met if Ω is compact or V = Y . We do not assume that Ω itself is convex.
3.2 Theorem. Let U ⊆ X and V ⊆ Y be open, g : U → R be continuous and a C 1,1 -submersion on its zero set, let Ω defined by (3) be closed and connected, F : U → V be a C 1,1 -diffeomorphism, and F (Ω) be closed. Let further D 2 be one of the four operators defined in (4)- (5).
for all x ∈ ∂Ω and all h ∈ ker g ′ (x).
3.3 Corollary. Let X, Y be real Hilbert spaces, U ⊆ X and V ⊆ Y be open, F : U → V be a C 1,1 -diffeomorphism, Ω ⊆ U be a closed ball centered at x 0 , F (Ω) be closed, and D 2 be one of the four operators defined in (4)-(5).
for all x ∈ ∂Ω and all h ⊥ (x − x 0 ) with h = 1.
where r is the radius of Ω, and apply Theorem 3.2.
In contrast to related results in [18,40,20], the conditions in Theorem 3.2 and in Corollary 3.3 are to be checked on the boundary of Ω and for tangent vectors only. Further, as with Theorem 3.1, the criteria in Theorem 3.2 and Corollary 3.3 take particularly simple forms if the maps F and g are smooth. If F is of class C 2 , the left hand side of (12) and (22) The following is an immediate consequence of Corollary 3.3: The image of a ball centered at the origin under a C 1,1 -diffeomorphism defined on a neighborhood of the origin in a Hilbert space is convex provided the radius of the ball is sufficiently small [18,40]. The assumption that the diffeomorphism be of class C 1,1 rather than merely C 1 is essential [18]. For C 2 -diffeomorphisms the result is obvious [18] and can also be concluded from a well-known result on the existence of geodetically convex neighborhoods in Riemannian manifolds; see [41] and also [18,Sec. 6]. Polyak has raised the question of whether the result extends to uniformly convex Banach spaces [42]. It does not, as the following example shows.
We finally remark that the assumption in Theorem 3.2 and Corollary 3.3 that F be a global diffeomorphism on a neighborhood of Ω could easily be relaxed.

Convexity of reachable sets
In this section, we investigate reachable sets from a set Ω of initial states through solutions of the ordinary differential equation (ODE) (2), where the right hand side f : U ⊆ R × X → X of (2) is of class C 1,1 or C 2 with respect to its second argument and continuous. We also give a counterexample to a related result for control systems recently presented by Azhmyakov, Flockerzi and Raisch [25]. For the sake of simplicity, we restrict ourselves to the case where Ω is a ball and X is a real Hilbert space, so that Corollary 3.3 applies.
The general solution of (2) is denoted ϕ throughout this section. In order to avoid confusion of ideas, we would like to remind the reader that according to the notation adopted in section 2, operators D 2 and D 3 refer to the partial derivative of a map with respect to its second and third, respectively, argument, whereas D 2 refers to the second order derivative, and D 2 2 and D 2 3 , to the second order partial derivative with respect to the second and third, respectively, argument.
Our first result is a sufficient condition for the set of states reachable from a ball of initial values to be convex. That condition takes the form of an upper bound on the radius of the ball of initial values, which will be shown to be sharp later in Corollary 4.4.
The following is an immediate consequence of Theorem 4.1.
The main advantage of Theorem 4.1 over the results from section 3 is that the bound on the radius can be determined directly from properties of the right hand side of (2). Note that Theorem 4.1 cannot be obtained from applying any of the estimates from the literature [18,40,20] to the map F := ϕ(t 1 , t 0 , ·). In fact, separately estimating F ′ (x) −1 and F ′′ (x) gives a larger bound in general.
We would like to comment on our hypotheses. First note that µ − (A) and µ + (A) equal the minimum and maximum, respectively, eigenvalues of the self-adjoint part of A if X = R n . Hence, (23) and (33) reduce to bounds on eigenvalues of (35). If the ballB(x 0 , r) of initial values in Theorem 4.1 and Corollary 4.2 is an Euclidean ball, or equivalently, if the inner product ·|· equals the Euclidean inner product (·|·) given by then A * is just the transpose A T of A. If the ballB(x 0 , r) is an ellipsoid rather than Euclidean, then there is a symmetric positive definite matrix Q such that x|y = (x|Qy), from which A * = Q −1 A T Q follows. This shows conditions (23) and (33) can be readily verified. Second, note that in the Euclidean case, the result of Lojasiewicz [23] for the control system (1) applied to the special case investigated in this section would result in a similar bound on radii. In fact, apart from some technical hypotheses, the sufficient condition (26) for the convexity of the reachable set is obtained from [23], with M 1 defined by M 1 ≥ 3 D 2 f (τ, x) rather than by (23) or (34). This gives a bound on the radius r that is never larger and in general smaller than the bounds presented in Theorem 4.1 and Corollary 4.2 since 2µ Third, note that if U = I ×R n in Theorem 4.1 or in Corollary 4.2, then the condition {t 1 } × {t 0 } ×B(x 0 , r) ⊆ dom ϕ is automatically fulfilled. Indeed, it is straightforward to obtain dom ϕ = I × I × R n from condition (23) in this case.
Finally, note that condition (24) is just a bound on D 2 2 f (τ, x) in case f is of class C 2 with respect to its second argument. For this case the proof of Theorem 4.1 can be specialized to obtain a necessary and sufficient condition: Let U, f , x 0 , r, t 0 and t 1 as in Theorem 4.1 and assume in addition that f is of class C 2 with respect to its second argument. Then Proof. Pick arbitrary x ∈ ∂B(x 0 , r) and h ⊥ (x − x 0 ) with h = 1. We show that the left hand sides of (37) and (22) As F is of class In contrast to the hypotheses of Theorem 4.1 and Corollary 4.2, which may be verified by direct inspection of the right hand side f of (2), the necessary and sufficient condition for convexity of the image ϕ(t 1 , t 0 ,B(x 0 , r)) of the diffeomorphism ϕ(t 1 , t 0 , ·) that is established in Theorem 4.3 contains the diffeomorphism itself. The advantage of the latter result over a direct application of (the C 2 -version of) Corollary 3.3 is that the second derivative of that diffeomorphism does not appear in condition (37). Hence, in order to estimate the left hand side of (37) for a particular example of (2), one has to study the variational equation of (2) and its adjoint only. That way one may obtain bounds on the radius strictly greater than the one given in Theorem 4.1. This is demonstrated in section 5.
With the criterion from Theorem 4.3 at our disposal, we are now able to prove that the bound on the radius given in Corollary 4.2 is sharp, from which the sharpness of the bound in Theorem 4.1 easily follows.
Recently, Azhmyakov, Flockerzi and Raisch have investigated the closedloop variantẋ of the control system (1), where the control set U ⊆ R m is compact and convex, solutions to (38) are assumed to exist on [0, t 1 ] for any U-valued measurable feedback u and to be uniformly bounded, the right hand side f : R n × R m → R n is merely Lipschitz-continuous, and admissible controls are U-valued and Lipschitz-continuous [25]. It has been claimed that the reachable set x is a solution of (38) for some admissible feedback u} is convex provided t 1 is small enough [25]. It follows from geometric ideas employed in [22,23,24] and the present paper, in particular from Example 3.4 and Corollary 4.4, that such a claim must be wrong. We provide a simple counterexample below.

Application
In this section, we demonstrate the application of the results from section 4 to the equations of the damped mathematical pendulum, where ω > 0 and γ ≥ 0 [35]. Note that the investigation of the convexity of reachable sets of more general systems, such as a cart-pole system with a piecewise constant control, can be reduced to the autonomous system (39) [30]. The results of sections 3 and 4 cover the case of images of ellipsoids as we have allowed for arbitrary inner products. In this section, we restrict ourselves to the case of images of Euclidean balls for the sake of simplicity.
The above ODE is of the formẋ where f : R 2 → R 2 is given by We first demonstrate a straightforward application of Corollary 4.2: 5.1 Theorem. Assume ω > 0, γ ≥ 0 and t 1 = 0, let M 1 and R be given by and let ϕ be the flow of the pendulum equation (39). Then the image of any ball with radius not exceeding R under the map ϕ(t 1 , ·) is convex.
Proof. From we obtain the minimum and maximum eigenvalues λ ± = −γ± γ 2 + (1 + ω 2 ) 2 /4 of the symmetric part 1 The following larger bound on the radius is obtained from Theorem 4.3.
and let ϕ be the flow of the pendulum equation (39). Then the image of any ball with radius not exceeding R under the map ϕ(t 1 , ·) is convex.
As we have already remarked in section 4, the bound (42) on radii is never smaller and in general larger than the bound from [23]. For the pendulum equations (39) one can show that these bounds coincide iff ω = 1 and γ = 0. In particular, in the undamped case, γ = 0, (41) reads M 1 = 3 2 (1 + ω 2 ), whereas [23] would give the bound (42) with M 1 = 3 max{1, ω 2 }. Fig. 2(a) and Fig. 2(b) show the bounds obtained from Theorems 5.1 and 5.2 and from [23] in comparison to a bound obtained numerically for two sets of parameters, ω = 1 and γ = 0, and ω = 6.1 and γ = 0.2. The latter parameters are obtained from a model of an experimental cart-pole system when time is measured in seconds [44]. The results show that in both cases, the balls of initial states for which Theorem 5.2 proves the reachable sets are convex are large enough to be used in actual computations, such as in local programming techniques [19] and polyhedral approximation of reachable sets discussed in section 1. For the second set of parameters, the bounds obtained from Theorem 5.1 and [23] seem to be less useful.

Conclusions
We have presented a novel necessary and sufficient condition for the image of a sublevel set under a diffeomorphism to be convex. That result has been applied to reachable sets from a ball of initial states through solutions of an ordinary differential equation, which has resulted in a necessary and sufficient condition for the convexity of those reachable sets. We have also established an upper bound on the radius of the ball of initial states that ensures the reachable set is convex. That bound is sharp and can be directly obtained from the right hand side of the differential equation. In finite dimensions, our results cover the case of ellipsoids of initial states. We have also demonstrated by means of an example that the balls of initial states that result in convex reachable sets are large enough to be used in actual computations, for example in local programming techniques [19] and polyhedral approximation of reachable sets discussed in section 1.