Thomas Guilmeau
email: thomas.guilmeau@inria.fr

Alain Rapaport
email: alain.rapaport@inrae.fr

Singular arcs in optimal periodic control problems with scalar dynamics and integral input constraint

Keywords: Optimal control, periodic control, integral input constraint, singular arc. 2020 Mathematics Subject Classification. 49J15, 49K15, 34C25, 49N20, 49J30

We revisit recent results about optimal periodic control for scalar dynamics with input integral constraint, under lack of convexity and concavity. We show that in this more general framework, the optimal solutions are bang-singular-bang and generalize the bang-bang solutions for the convex case and purely singular for the concave one. We introduce a non-local slope condition to characterize the singular arcs. The results are illustrated on a class of bioprocesses models.

Introduction

Periodic optimal control has received relatively few attention in the literature, apart the well-known π-criterion [START_REF] Bittanti | Periodic control: A frequency domain approach[END_REF]. This later one consists in a linear-quadratic approximation about a steady state with constant control, and studying frequencies of a sinusoidal control that could improve the average performance index over a neighboring periodic solution. Extensions to other shapes of periodic controls have also been considered. However, the global optimal periodic optimal control has been very rarely investigated, apart from [START_REF] Maffezzoni | Hamilton-jacobi theory for periodic control problems[END_REF] for the characterization of the value function under quite strong assumptions. The two boundaries condition that periodic solutions have to satisfy might explain the difficulties in extending the usual approaches. Indeed, most of the existing works deal with local necessary conditions ( [START_REF] Bittanti | Status of periodic optimization of dynamical systems[END_REF][START_REF] Gilbert | Optimal periodic control: A general theory of necessary conditions[END_REF]), second order conditions ( [START_REF] Bittanti | Second-variation methods in periodic optimization[END_REF][START_REF] Speyer | A second variation theory for optimal periodic processes[END_REF][START_REF] Gilbert | Necessary and sufficient conditions for local optimality of a periodic process[END_REF]) or approximations techniques ( [START_REF] Evans | Solution of a periodic optimal control problem by asymptotic series[END_REF][START_REF] Abulesz | Periodic impulse forcing of nonlinear systems: a new method[END_REF][START_REF] Belyakov | Constant versus periodic fishing: age structured optimal control approach[END_REF]).

Recently, a class of scalar dynamics with integral input constraint has been investigated [START_REF] Bayen | Optimal periodic control for scalar dynamics under integral constraint on the input[END_REF], and it has been shown that under convexity and monotonicity assumptions, the global optimal periodic solution is bang-bang and therefore improves the averaged criterion over constant controls. For the concave case, it has been shown that constant controls remain the best ones. These results have been in particular motivated by bioprocesses applications, for which a kind of duality has been derived [START_REF] Bayen | Improvement of performances of the chemostat used for continuous biological water treatment with periodic controls[END_REF].

However, situations for which neither the convex nor the concave conditions are fulfilled have not been yet considered, which is the purpose of the present work. This allows to solve the problem of optimal periodic operations of bioprocesses with growth functions that are neither convex nor concave, which has been an open problem up to now.

The paper is organized as follows. In Section 2, the main results of [START_REF] Bayen | Optimal periodic control for scalar dynamics under integral constraint on the input[END_REF] are recalled, and the setting of the present contribution is specified. Then, in Section 3, we propose and prove a geometric optimality necessary condition in terms of slopes, which is central to our approach. In Section 4, further results on the optimal trajectories under the eventual lack of monotonicity in our assumptions are proved. Section 5 gives then the complete synthesis of the optimal control. Finally, our results are illustrated on a bioprocess model in Section 6, which shows the quantitative benefits of having singular arcs.

Some preliminaries

Let us consider two functions f, g : R → R of class C 1 and the controlled dynamics ẋ = f (x) + ug(x) [START_REF] Abulesz | Periodic optimization of continuous microbial growth processes[END_REF] where u takes values in [-1, 1]. Let us assume the following hypotheses:

(H1) There exists (a, b) ∈ R 2 with a < b such that g is positive on the interval I := (a, b) with f (a) -g(a) = 0 and f (b) + g(b) = 0 (H2) One has f -g < 0 and f + g > 0 on I.

One can straightforwardly check that the interval I is invariant by [START_REF] Abulesz | Periodic optimization of continuous microbial growth processes[END_REF] under Hypothesis H1. Hypothesis H2 implies the controllability of (1) on I. In the following, we shall consider solutions on the interval I only. For convenience, we define the function

ψ(x) := - f (x) g(x)
, x ∈ I Hypotheses H1-H2 imply ψ(I) ⊂ [-1, 1] and then for any x ∈ I, the control ū := ψ(x), which allows the system to stay at steady-state x, is admissible i.e. ū ∈ [-1, 1]. Let us stress that we do not impose f and g to be non null on the boundary of I. Therefore ψ(I) is not necessary [-1, 1] and ψ is not necessarily non decreasing. Examples 1 and 2 below show that ψ can be non monotonic on I.

Let us fix ū ∈ ψ(I) as a nominal constant control, and consider for T > 0 solutions x(•) in I that are T -periodic with a T -periodic control u satisfying the integral constraint

1 T T 0 u(t) dt = ū (2)
We denote by U T the set of admissible controls, that is U T := {u : [0, +∞) → [-1, 1] s.t. u is meas., T -periodic and fulfills (2)}

Let us now consider a function : R → R of class C 1 and associate the criterion

J T (u) := min 1 T T 0 (x u (t)) dt ; x u is T -periodic (4)
to be minimized over controls u ∈ U T , where x u denotes the solutions of (1) in I associated to u.

In the former work [START_REF] Bayen | Optimal periodic control for scalar dynamics under integral constraint on the input[END_REF], it has been shown that convexity is playing an important role in the possibility of having J T (u) lower than the cost with constant control J T (ū) under the following additional condition on the dynamics.

(H3) The function : I → R is increasing and the function γ = ψ • -1 is strictly convex increasing over (I).

Under H3, the exists an unique x in I with ψ(x) = ū and one has the following result. Proposition 1. If H1 and H3 hold true, any non-constant T -periodic solution x of (1) with x(0) = x and u ∈ U T satisfies J T (u) < J T (ū).

In the opposite way, it has been shown in [START_REF] Bayen | Optimal periodic control for scalar dynamics under integral constraint on the input[END_REF] that concavity prevents improving the cost J T (ū) with non-constant controls, under the following condition on the dynamics: (H4) There exists a continuous function ψ such that (i) ψ ≥ ψ on I with ψ(x) = ψ(x), (ii) the function γ = ψ • -1 is concave increasing on (I).

Under H4 one has also the uniqueness of x in I with ψ(x) = ū and the following result holds. Proposition 2. If H1 and H4 hold true, any non-constant T -periodic solution x of (1) with x(0) = x and u ∈ U T satisfies J T (u) > J T (ū).

In the present work, we assume that Hypotheses H1-H2 are satisfied and aim at relaxing Hypothesis (H3) or (H4) by allowing a change of convexity as well as a change of monotonicity of the function γ := ψ • -1 on the interval I, while keeping increasing. Note that under Hypotheses H1-H2, there does not necessarily exist an unique x such that ψ(x) = ū. However, we shall assume that there is an unique stable one, which is guaranteed by the following hypothesis.

( H) The function is increasing on I, and for any ȗ ∈ int (ψ(I)), there exists an unique x ∈ I, such that

ψ(x) = ȗ, there exists a neighborhood V ⊂ I of x such that (ψ(x) -ψ(x))(x -x) > 0, ∀x ∈ V \ {x}
Then, as is increasing, the steady-state x that gives the best cost J T (ū) is clearly the smallest one. Note that Hypothesis H amounts to ψ having at most one change of monotonicity on I. Under Hypotheses H1-H2, if ψ is non monotonic on I, it must be increasing first and then decreasing. Therefore, we can define values x and x as follows. Let us first give a preliminary result about periodic solutions, in the spirit of the former work [START_REF] Bayen | Optimal periodic control for scalar dynamics under integral constraint on the input[END_REF].

Lemma 1. Under Hypotheses H1-H2-H, any T -periodic solution x of (1) in I with u ∈ U T fulfills the property

T 0 (ψ(x(t)) -ū) dt = 0 (5)
and any optimal trajectory x takes the value x.

Proof. On the interval I, the function g is positive and from equation (1), one can write

T 0 ẋ(t) g(x(t)) dt = - T 0 ψ(x(t)) dt + T 0 u(t) dt
Consider then the function t → y(t) := h(x(t)) for t ∈ [0, T ], where h is defined as follows.

h(x) := x x dξ g(ξ) , x ∈ I
For any control function u that fulfills the constraint (2), one gets

y(T ) -y(0) = - T 0 (ψ(x(t)) -ū) dt
where ū = ψ(x). Therefore, for any T -periodic solution x in I, y is also T -periodic and one obtains property [START_REF] Bayen | Optimal periodic control for scalar dynamics under integral constraint on the input[END_REF].

According to the above, for any T -periodic solution x, the map t → ψ(x(t)) -ū has to take the value 0 on [0, T ). Therefore, there exists t ∈ [0, T ) such that x( t) = x with ψ(x) = ū. If x = x, then we have proved that x takes the value x. If not, one has necessarily x > x because of Definition 1. Therefore, if the solution x does not take the value x, one should have x(t) > x for any t ∈ [0, T ). The function being increasing on I, it comes that T 0 (x(t))dt > (x) = J T (ū) which shows that x cannot be optimal. We conclude that one has x = x. This Lemma allows to look for optimal solutions with x(0) = x(T ) = x without any loss generality, as we shall do now. Note that when x = x, the single T -periodic solution of (1) with the constraint (2) is the constant solution x = x, and there is no optimization to be made. Therefore, we shall assume in the following that ū is taken in int(ψ(I)), which implies x < x.

We introduce now the Hypotheses H5a and H5b that generalize Hypotheses H3 or H4, keeping increasing.

(H5a) The function : I → R is increasing and there exists x c ∈ (a, b] such that the function γ := ψ • -1 is strictly convex over ((a, x c )) and strictly concave over ((x c , b)).

(H5b) The function : I → R is increasing and there exists x c ∈ (a, b] such that the function γ := ψ • -1 is strictly concave over ((a, x c )) and strictly convex over ((x c , b)).

Remark 2. When x c = b, Hypotheses H5a and H3 are equivalent, as well as H5b and H4. Indeed, if x c > x, then H3 or H4 are also recovered, as it will be seen later in Proposition 5 of Section 4.

We provide now examples that fulfill H5a or H5b.

Example 1. Let a = 0, b = 3 and functions f , g defined as follows

f (x) = - 3 2 x 3 + x 4 - 1 6 x 5 , g(x) = 3x -x 2
Hypotheses H1 and H2 are fulfilled (see Figure 1). We take the identify function for . One can straightforwardly check that the function ψ is given by the expression

ψ(x) = x 2 2 - x 3 6
One can then easily check that Hypotheses H and H5a are fulfilled (see also Figure 1). Example 2. Let a = 0, b = 6 and functions f , g defined as follows

f (x) = 4x 3 -24x 2 4 + x + x 2 , g(x) = 6x -x 2
Hypotheses H1 and H2 are fulfilled (see Figure 2). We take the identify function for . One can straightforwardly check that the function ψ is given by the expression

ψ(x) = 4x 4 + x + x 2
One can then easily check that Hypotheses H and H5b are fulfilled (see also Figure 2).

A slope condition

In this section, we derive as a "slope condition" a geometric necessary condition for optimality, which links the switching points of an optimal trajectory through the function ψ.

We first reformulate the constraint (2) by considering the augmented dynamics

ẋ = f (x) + ug(x) ẏ = u (6)
with the boundary conditions:

(x(0), y(0)) = (x, 0) and (x(T ), y(T )) = (x, ūT )

The optimal control problem can then be stated as

inf u∈U T 0 (x(t)) dt s.t. (x, y) satisfies (6) -(7) (8)
where U denotes the set of measurable control functions u over [0, T ] taking values in [-1, 1]. Note that Problem (8) in R 2 admits a solution by classical existence results. Indeed, the set of trajectories that satisfy the boundary conditions [START_REF] Bezanson | Julia: A fresh approach to numerical computing[END_REF] is non empty (it contains the steady state x with constant control ū), and since the system is affine w.r.t. the control and is continuous, the existence of an optimal control follows by Filippov's existence theorem [START_REF] Cesari | Optimization -Theory and Applications[END_REF]. We define the Hamiltonian H :

R 2 × R 2 × R × R → R as H = H(x, y, λ x , λ y , λ 0 , u) = λ 0 (x) + λ x f (x) + u(λ x g(x) + λ y )
where λ := (λ x , λ y ) is the adjoint vector. From the Pontryagin Maximum Principle [START_REF] Pontryagin | Mathematical theory of optimal processes[END_REF], we know that for any optimal control u ∈ U and (x, y) the associated solution of ( 6)-( 7), there exists a scalar λ 0 ≤ 0 and an absolutely continuous map λ : [0, T ] → R 2 solution of the adjoint dynamics λx = -λ 0 (x(t)) -λ x (f (x(t)) + u(t)g (x(t))) λy = 0 [START_REF] Bittanti | Second-variation methods in periodic optimization[END_REF] for a.e. t ∈ [0, T ]. Moreover one has (λ 0 , λ) = 0 and the Hamiltonian condition writes

u(t) ∈ arg max v∈[-1,1] H(x(t), λ(t), λ 0 , v) a.e. t ∈ [0, T ]. (10)
A solution x satisfying ( 6)-( 7) for a control u ∈ U and such that there exists (λ 0 , λ) = 0 verifying ( 9)-( 10) is called an extremal. Since the dynamics is affine w.r.t. u, the switching function

t → φ(t) := λ x (t)g(x(t)) + λ y ,
provides the following property of the optimal control u for almost any t ∈ [0, T ]:

   φ(t) > 0 ⇒ u(t) = 1 φ(t) < 0 ⇒ u(t) = -1 φ(t) = 0 ⇒ u(t) ∈ [-1, 1] (11)
We recall that a singular arc occurs if φ vanishes on some time interval [t 1 , t 2 ] with t 1 < t 2 , and a switching time t s ∈ (0, T ) is such that an extremal control u is non-constant in any neighborhood of t s (which implies φ(t s ) = 0). Let us mention that from Hypothesis H2, when φ > 0, resp. φ < 0, then x is increasing, resp. decreasing.

For convenience, we shall define the following numbers.

Definition 2. For a solution x(•) of (1) with x(0) = x, let us denote by x m , respectively x M , the minimum, respectively the maximum, of

x(•) on [0, T ].
Let us first analyze the case of abnormal extremals i.e. with λ 0 = 0.

Proposition 3. Assume that hypotheses H1-H2-H are fulfilled.

• If ψ is increasing on I, there is no abnormal extremal.

• If ψ is not increasing on whole I, abnormal extremals are non constant with x m ≤ x ≤ x M and switches occur only at x = x m or x = x M , without singular arc.

Proof. If λ 0 = 0, then λ x cannot vanish from the adjoint equation [START_REF] Bittanti | Second-variation methods in periodic optimization[END_REF]. Otherwise λ x would be null over [0, T ] and the switching function would be constant equal to λ y . Since λ y cannot be simultaneously equal to 0, φ would be of constant sign over [0, T ] implying that u = 1 or u = -1 over [0, T ]. This is a contradiction with the periodicity of x(•) (recall that one has f + g > 0 and f -g < 0 over I). Consequently, λ x has constant non null sign.

Since λ 0 = 0, one has from the adjoint equations ( 9)

φ(t) = λ x (t)g(x(t)) 2 ψ (x(t)), a.e. t ∈ [0, T ] (12)
If ψ is increasing on I, φ is monotonic and has at most one switching point, implying that x is either entirely above or entirely below x. But then the equality (5) of Lemma 1 cannot be verified when ψ is increasing.

Consider now the case when ψ is non increasing on I. One has then x ∈ I. For any extremal x, we know from Lemma 1 that one has x m ≤ x ≤ x M . Remind, as already mentioned in Section 2, that one has necessarily x > x. If x > x M , then ψ is increasing on [0, T ] and we conclude as previously that this is not possible. Therefore an abnormal extremal should verify x m ≤ x ≤ x M . Note that the constant solution x cannot be an abnormal extremal when x = x. The extreme values of x having necessarily to be a switching locus, one should have φ(t m ) = φ(t M ) = 0 for some t m , t M ∈ (0, T ) with x(t m ) = x m and x(t M ) = x M . Since the Hamiltonian is conserved along extremal trajectories, it comes with λ 0 = 0

H(t m ) = λ x (t m )f (x m ) = -λ y ψ(x m ) = H(t M ) = λ x (t M )f (x M ) = -λ y ψ(x M )
Since λ x is non null and φ is null lat t m and t M , λ y cannot be null. We conclude that the equality ψ(

x m ) = ψ(x M ) is necessarily satisfied. Finally if a switch occurs at x s / ∈ {x m , x M } one should have ψ(x s ) = ψ(x m ) = ψ(x M
), which is in contradiction with Hypothesis H. Finally, note from equation ( 12) that a singular arc on a time interval

[t 1 , t 2 ] with t 1 < t 2 (i.e. such that φ(t) = 0, t ∈ [t 1 , t 2 ]) could occur only for x(t) = x, t ∈ [t 1 , t 2 ] but then φ(t) = λ x (t)g(x(t)) + λ y could not be constant for t ∈ [t 1 , t2].
We focus now on regular extremals, i.e. with λ 0 = -1. We begin by a lemma that characterizes the singular arcs as constant values of x.

Lemma 2. Assume that hypotheses H1-H2-H and H5a or H5b are fulfilled, and let x be a regular extremal. If there exists a time interval [t 1 , t 2 ] with t 1 < t 2 such that φ vanishes on [t 1 , t 2 ], then there exists x ∈ I such that x(t) = x and λ -1

y = γ ( (x)) for any t ∈ [t 1 , t 2 ] with u(t) = ψ(x) for a.e. t ∈ [t 1 , t 2 ]. Proof. Assume φ(t) = 0 for t ∈ [t 1 , t 2 ], which yields λ x (t) = - λ y g(x(t)) , t ∈ [t 1 , t 2 ]
If λ y = 0, then λ x = 0 on [t 1 , t 2 ] and from [START_REF] Bittanti | Second-variation methods in periodic optimization[END_REF], it comes that λ 0 = 0. The extremal cannot be regular. So, one has λ y = 0. It comes from the adjoint equations ( 9) with

λ 0 = -1 that φ(t) = (x(t))g(x(t)) + λ x (t)g(x(t)) 2 ψ (x(t)), a.e. t ∈ [t 1 , t 2 ]
As g > 0 on I and φ = 0 on [t 1 , t 2 ], one has then

0 = 1 -λ y γ ( (x(t))), a.e. t ∈ [t 1 , t 2 ] ⇒ 1/λ y = γ ( (x(t))), a.e. t ∈ [t 1 , t 2 ]
Note that under hypothesis H5a or H5b, the function γ is almost everywhere increasing or decreasing and is increasing. Therefore, the function γ • cannot be constant on any interval of non null length. The result follows with x solution of γ ( (x)) = 1/λ y .

We give now our optimality "slope condition", that shall play an important role in the derivation of an optimal synthesis. Proposition 4. Assume that hypotheses H1-H2-H and H5a or H5b are fulfilled. Let x be a non constant regular extremal. Then λ y = 0 and the switching set

S := {x(t s ); t s ∈ [0, T ], φ(t s ) = 0} is equal to {x m , x M } or {x m , x I , x M } with x m < x I < x M , satisfying the so-called slope condition (x 1 , x 2 ) ∈ S 2 , x 1 = x 2 ⇒ γ( (x 1 )) -γ( (x 2 )) (x 1 ) -(x 2 ) = 1 λ y (13)
Moreover, if x is optimal with a singular arc at x, then S = {x m , x M }, x < x with

• x = x M under Hypothesis H5a, satisfying the slope condition

γ( (x M )) -γ( (x m )) (x M ) -(x m ) = γ ( (x M )) (14)
• x = x m under Hypothesis H5b, satisfying the slope condition

γ( (x M )) -γ( (x m )) (x M ) -(x m ) = γ ( (x m )) (15) Proof. Consider t 1 , t 2 ∈ [0, T ] and distinct x 1 , x 2 in I such that x(t i ) = x i and φ(t i ) = 0 for i = 1, 2.
Since the Hamiltonian H is conserved along any extremal, one has (for a regular extremal)

H = -l(x i ) -λ y f (x i ) g(x i ) = -(x i ) + λ y ψ(x i ) for i = 1, 2
which shows that λ y = 0, using the fact that l is increasing on I. Then it comes the following "slope condition"

1 λ y = ψ(x 1 ) -ψ(x 2 ) (x 1 ) -(x 2 ) = γ( (x 1 )) -γ( (x 2 )) (x 1 ) -(x 2 )
As extreme values of x are necessarily switching locus, one has then

1 λ y = γ( (x M )) -γ( (x m )) (x M ) -(x m )
Since γ change convexity only once on l(I) under Hypothesis H5a or H5b, there can only exist at most one other value x I ∈ (x m , x M ) such that the slope constraint ( 13) is satisfied.

Consider now the case when x admits a singular arc x under Hypothesis H5a (the proof for the case with Hypothesis H5b is similar and left to the reader). Let us first show that having x < x c cannot be optimal. Otherwise, considering any interval [t 1 , t 1 + δ] ⊂ [t 1 , t 2 ] with δ > 0, the constant solution x = x has be optimal for the periodic optimal problem (4) with period δ, initial condition x(0) = x and input constraint 1 δ δ 0 u(t)dt = ũ = ψ(x). But γ being increasing and strictly convex at x, any admissible solution on [0, δ] with x(0) = x lies on a domain where γ is increasing and strictly convex, provided that δ is small. Then, Proposition 1 applies, which proves that x = x cannot be optimal. We have thus x ≥ x c . If x = x M , then the slope condition [START_REF] Evans | Solution of a periodic optimal control problem by asymptotic series[END_REF] gives

1 λ y = ψ(x M ) -ψ(x) (x M ) -(x) = γ( (x M )) -γ( (x)) (x M ) -(x)
With 1 λy = γ ( (x)) given by Lemma 2, it comes the following equality

γ ( (x)) = γ( (x M )) -γ( (x)) (x M ) -(x)
which contradicts the function γ being strictly concave on (x, x M ). We conclude that x has to be equal to x M . Now, let us show that S = {x m , x}. Suppose by contradiction that S = {x m , x I , x M }. Using the same concavity argument as before, it comes that x I < x c . Consider now the function γ : (I) → R defined as

γ( (x)) = γ( (x)) if x ≤ x c γ ( (x c ))( (x) -(x c )) + γ( (x c )) otherwise
which implies that γ is convex and above γ on (I), with γ = γ on ([a, x c ]). Now let us consider the point

x i ∈ (x c , x) such that γ ( (x c ))( (x i ) -(x c )) + γ( (x c )) = γ ( (x))( (x i ) -(x)) + γ( (x))
implying that x m < x I < x i . By convexity of γ • , γ( (x I )) is strictly under the straight line that passes through (x m , γ( (x m ))) and (x i , γ( (x i ))) which is by construction the line x -→ γ ( (x))( (x) -(x)) + γ( (x)), hence showing that x I cannot satisfy the slope condition [START_REF] Evans | Solution of a periodic optimal control problem by asymptotic series[END_REF].

Finally, the slope condition (13) with x 1 = x M , x 2 = x m and 1 λy = γ ( (x M )) gives the condition [START_REF] Gilbert | Optimal periodic control: A general theory of necessary conditions[END_REF]. Now, let us show that one has necessarily x M < x. If x M ≥ x, then (x M ) has to be in the concave part of γ with γ ( (x M )) < 0 (and γ is necessarily concave on ( (x), (b)). This implies the inequality

γ( (x)) ≤ γ( (x M )) + γ ( (x M ))( (x) -(x M ))
Recall from Lemma 1 that one has x m < x (and x ≤ x from Remark 1). As γ is increasing on ( (a), (x)) (and is an increasing function), one gets

γ( (x m )) < γ( (x M )) + γ ( (x M ))( (x m ) -(x M ))
which contradicts the condition [START_REF] Gilbert | Optimal periodic control: A general theory of necessary conditions[END_REF].

The slope condition is a necessary condition for optimality, which states that two cases can exist : either there are two switching points (the maximum and the minimum), and one of them might correspond to a singular arc (i.e. a constant portion of the trajectory), or there are three switching points without any singular arc.

Restriction to the increasing part of the function ψ

In this section, we show that when the function ψ is not increasing on the whole interval I, an optimal trajectory remains necessarily in the domain I ∩ {x < x} where the function ψ is increasing (or equivalently that one has x M < x). The main idea of the proof of Proposition 5 below is to show that if it is not the case, one can exhibit a piece of the trajectory which is increasing up to x M and decreasing so that replacing it by a constant state remains admissible and gives a better cost (see Fig. 3). For convenience, we first introduce the following function, as in [START_REF] Bayen | Optimal periodic control for scalar dynamics under integral constraint on the input[END_REF],

η(x) := 1 f (x) + g(x) - 1 f (x) -g(x)
, x ∈ I which is positive and C 1 on I thanks to H2. This function possesses the following property related to bang-bang controls.

Lemma 3. Under H1 and H2, consider a piece of trajectory x(•) in I on an interval [t 0 , t 0 + T 0 ] (with

T 0 > 0) generated by a "bang-bang" control u(•) equal to u - BB (•) or u + BB (•) defined as u - BB (t) =    -1 t ∈ [t 0 , t 1 ) 1 t ∈ [t 1 , t 2 ) -1 t ∈ [t 2 , t 0 + T 0 ) , u + BB (t) =    1 t ∈ [t 0 , t 1 ) -1 t ∈ [t 1 , t 2 ) 1 t ∈ [t 2 , t 0 + T 0 )
for some t 1 < t 2 in [t 0 , t 0 + T 0 ], that satisfies

x(t 0 + T 0 ) = x(t 0 ) and 1 T 0 t0+T t0 u(t)dt = ψ(x(t 0 )) (16)
Then, one has

x M x m η(ξ)dξ = T 0 and x M x m η(ξ)ψ(ξ)dξ = ψ(x(t 0 ))T 0 (17)
where

x m = min t∈[t0,t0+T0] x(t), x M = max t∈[t0,t0+T0] x(t). Proof. Let us consider u(•) = u - BB (•) (the case u(•) = u + BB (•) is analogous). For t ∈ [t 0 , t 1 ) ∪ [t 2 , t 0 + T 0 ), one has ẋ = f (x) -g(x) < 0. Therefore ξ : t → x(t) defines a diffeomorphism from [t 0 , t 1 ]
to its image, and from [t 2 , t 0 + T 0 ] to its image as well. Then, one can write

t 1 -t 0 = - x(t0) x(t 1 ) dξ f (ξ) -g(ξ) , T 0 + t 0 -t 2 = - x(t 2 ) x(T +t0) dξ f (ξ) -g(ξ)
Similarly, for t ∈ [t 1 , t 2 ), one has ẋ = f (x) + g(x) > 0 and can write

t 2 -t 1 = x(t 2 ) x(t 1 ) dξ f (ξ) + g(ξ)
Then x(t 0 + T 0 ) = x(t 0 ) gives

T 0 = x(t 2 ) x(t 1 ) dξ f (ξ) + g(ξ) - x(t 2 ) x(t 1 ) dξ f (ξ) -g(ξ) = x(t 2 )
x(t 1 )

η(ξ)dξ

Proceeding with the same decomposition of the interval [t 0 , t 0 + T 0 ], one obtains

t0+T t0 u(t)dt = x(t0) x(t 1 ) dξ f (ξ) -g(ξ) + x(t 2 ) x(t 1 ) dξ f (ξ) + g(ξ) + x(t 2 ) x(T +t0) dξ f (ξ) + g(ξ)
and with conditions (16) the equality

ψ(x(t 0 ))T 0 = x(t 2 ) x(t 1 ) 1 f (ξ) + g(ξ) + 1 f (ξ) -g(ξ) dξ = x(t 2 )
x(t 1 ) η(ξ)ψ(ξ)dξ is fulfilled. Clearly, one has x m = x(t 1 ) and x M = x(t 2 ), which give the expressions [START_REF] Maffezzoni | Hamilton-jacobi theory for periodic control problems[END_REF].

Proposition 5. Suppose that hypotheses H1-H2-H and H5a or H5b are verified. A non constant optimal trajectory x(•) for Problem (8) verifies x(t) < x for any t ∈ [0, T ].

Proof. Let u(•) be an optimal solution of Problem (8) and x(•) its associated trajectory. Let us remind the notation x m , x M given by Definition 2, that we shall use below. If it is a regular extremal, the slope condition (13) of Proposition 4 gives 1

λ y = ψ(x M ) -ψ(x m ) (x M ) -(x m ) (since ψ = γ • ).
Recall that is increasing. Therefore one has ψ(x M ) = ψ(x m ). We distinguish two cases.

1. ψ(x M ) < ψ(x m ). One has λ y < 0 and a switching at x I such that x m < x I < x M imposes to have ψ(x I ) < ψ(x m ) and ψ(x I ) < ψ(x M ) from the slope condition [START_REF] Evans | Solution of a periodic optimal control problem by asymptotic series[END_REF]. Since ψ is increasing on (x m , x) and decreasing on (x, x M ), it comes that x I must satisfy x I > x M , which is a contradiction. Now suppose that x(•) admits a singular arc. The inequality ψ(x M ) < ψ(x m ) yields γ ( (x)) < 0 with x = x M under H5a and x = x m under H5b. This contradicts x < x as it was proved in Proposition 4. Therefore, x(•) has switching only at x m and x M and no singular arc.

2. ψ(x M ) > ψ(x m ). Under Hypotheses H1-H2-H, we define x m as the unique value in I different from x M such that ψ(x m ) = ψ(x M ). One has necessarily x m < x. The slope condition (13) allows the existence of intermediate switch at x I ∈ (x m , x M ) but one has x I < x m . The case of a singular arc at x = x M is ruled out as Proposition 4 states that inequality x < x is satisfied.

If it is an abnormal extremal, one has ψ(x M ) = ψ(x m ) and from Proposition 3, x(•) has switching only at x m and x M and no singular arc, as for case 1. above. Now, we posit

xm = x m if ψ(x M ) ≤ ψ(x m ) x m if ψ(x M ) > ψ(x m )
(which satisfies xm < x) and define the functions

g(x) := ψ(x) x M x η(ξ)dξ, h(x) := x M x η(ξ)ψ(ξ)dξ, x ∈ [x m , x]
Clearly, one has

h(x) = x M x η(ξ)ψ(ξ)dξ < ψ(x) x M x η(ξ)dξ = g(x)
When ψ(x M ) ≤ ψ(x m ), the trajectory x(•) has switches only at x m and x M and no singular arc, according to what has been shown previously. If it has only two switches, one can apply Lemma 3 on the interval [0, T ] and write

h(x m ) = x M xm η(ξ)ψ(ξ)dξ = ψ(x)T > ψ(x m )T = g(x m )
In the case where x(•) commutes more than once at x m or x M on the interval [0, T ], say n times, the trajectory x(•) is T /n periodic and we can apply Lemma 3 on the interval [0, T /n] to obtain the same inequality. When ψ(x M ) > ψ(x m ), one has

h(x m ) = x M x m η(ξ)ψ(ξ)dξ > ψ(x m ) x M x m η(ξ)dξ = g(x m )
Since the functions g and h are continuous, we deduce the existence of a number

x d ∈ (x m , x) such that g(x d ) = h(x d ).
From what precedes, x d is not a switching point of x(•), and by periodicity of the trajectory, x(•) has to pass by x d alternatively by increasing and by decreasing or vice-versa. We can then define

t d := inf{t > 0 ; x(t) = x d ,
T d = t d +T d t d dt = x M x d dξ f (ξ) + g(ξ) + x d x M dξ f (ξ) -g(ξ) = x M x d η(ξ)dξ = g(x d ) ψ(x d )
and

t d +T d t d u(t)dt = x M x d dξ f (ξ) + g(ξ) - x d x M dξ f (ξ) -g(ξ) = x M x d η(ξ)ψ(ξ)dξ = h(x d )
The equality g(x d ) = h(x d ) gives then

t d +T d t d u(t)dt = ψ(x d )T d
Therefore, the control u # (•) defined on [0, T ] by

u # (t) = ψ(x d ) if t ∈ [t d , t d + T d ], u(t) if t ∈ [0, T ] \ [t d , t d + T d ] verifies T 0 u # (t)dt = T 0 u(t)dt
and its associated trajectory x # (•) on [0, T ] is given by

x # (t) = x d if t ∈ [t d , t d + T d ], x(t) if t ∈ [0, T ] \ [t d , t d + T d ]
which consists in a truncation of the original trajectory x(•) (see Fig. 3). Clearly u # (•) is admissible, and its cost satisfies

J T (u # ) = 1 T t d 0 (x(t))dt + T d (x d ) + T t d +T d (x(t))dt < 1 T T 0 (x(t))dt = J T (u)
being increasing and x(•) > x d on (t d , t d + T d ), which contradicts the optimality of u(•).

From Proposition 3, one obtains immediately the following property.

Corollary 1. Under hypotheses H1-H2-H and H5a or H5b, an abnormal extremal cannot be optimal.

Optimal synthesis

Let us recall that the former results in [START_REF] Bayen | Optimal periodic control for scalar dynamics under integral constraint on the input[END_REF] do not cover the case of a change of convexity of the function γ. However, these results can still be applied when x and T are such that for any admissible solution x(t) remains in one of the subsets (a, x c ) or (x c , b), where γ does not change its convexity. Then, either bang-bang, or constant solutions are optimal (depending if γ is convex or concave on the subset, as stated in [START_REF] Bayen | Optimal periodic control for scalar dynamics under integral constraint on the input[END_REF]). However, situations for which solutions x(•) can pass from one subset to another one has not been yet treated. We consider here the class of BSB (for "bang-singular-bang") control strategies with at most one singular arc.

Definition 3. Let t ∈ [0, T ].
For the initial condition x(0) = x of system (1), we call BSB controls any time function u a ( t;

•) or u b ( t; •) such that u a ( t; t) =          -1 if t ∈ [0, t 1 ) +1 if t ∈ [t 1 , t 2 ) ψ(x(t 2 )) if t ∈ [t 2 , t 2 + t) -1 if t ∈ [t 2 + t, T )
where switching times t 1 , t 2 are such that 0 ≤ t 1 ≤ t 2 ≤ T -t, and

u b ( t; t) =          -1 if t ∈ [0, t 1 ) ψ(x(t 1 )) if t ∈ [t 1 , t 1 + t) +1 if t ∈ [t 1 + t, t 2 ) -1 if t ∈ [t 2 , T )
where switching times t 1 , t 2 are such that

0 ≤ t 1 ≤ t 2 -t ≤ T -t.
Note that t represents the duration of the trajectory spent on the singular arc x (with x = x(t 2 ) for the control u a ( t; •), and x = x(t 1 ) for the control u b ( t; •)). With the notations introduced in Definition 2, one has x m = x(t 2 ), x M = x with control u a ( t; •), and x m = x, x M = x(t 2 ) with control u b ( t; •). Note also that the particular case t = 0 corresponds to pure "bang-bang" trajectories (i.e. without singular arc) while t = T corresponds to the constant solution x (for these two particular cases, the definitions of u a and u b coincide). We show now that for any value of t, there exist unique controls u a , u b that are admissible and such that the trajectory is periodic with x M < x. The following proposition is in the spirit of Proposition 3.2 in [START_REF] Bayen | Optimal periodic control for scalar dynamics under integral constraint on the input[END_REF] but extended to the present context with singular arcs. Proposition 6. Under Hypotheses H1-H2-H, for any t ∈ [0, T ], there exist unique controls u a ( t; •), u b ( t; •) such that the solution of (6) satisfies the boundaries conditions (7) and belong to I ∩ {x < x}. Moreover, the corresponding x m , x M are the unique solutions in I ∩ {x < x} of the equations

x M xm η(ξ)dξ = T -t ( 18
)
and

x M xm η(ξ)ψ(ξ)dξ = T ū -tψ(x) (19)
with x = x M for the control u a ( t; •), and x = x m for the control u b ( t; •).

Proof. We consider controls u a only (the proof for controls u b is analogous). On the interval [0, t 1 ], one has ẋ = f (x) -g(x) < 0 and thus ξ : t → x(t) defines a diffeomorphism from [0, t 1 ] to its image, and similarly on the interval [t 2 + t, T ]. On the interval [t 1 , t 2 ], one has ẋ = f (x) + g(x) > 0 and again ξ : t → x(t) defines again a diffeomorphism from [t 1 , t 2 ] to its image. Then one can write

T 0 dt = x(t1) x dξ f (ξ) -g(ξ) + x x(t1) dξ f (ξ) + g(ξ) + t + x(T ) x dξ f (ξ) -g(ξ)
where x = x(t 2 ). The trajectory x(•) is T -periodic when x(T ) = x and one has then x m = x(t 1 ), x M = x, which amounts to have

T = x M xm 1 f (ξ) + g(ξ) - 1 f (ξ) -g(ξ) dξ + t = x M xm η(ξ)dξ + t
which is exactly equation [START_REF] Parulekar | Analysis of forced periodic operations of continuous bioprocesses: single input variations[END_REF]. In the same way, one can write

T 0 u(t)dt = - xm x dξ f (ξ) -g(ξ) + x M xm dξ f (ξ) + g(ξ) + tψ(x) - x x M dξ f (ξ) -g(ξ)
and get for an admissible control u(•)

T ū = x M xm 1 f (ξ) + g(ξ) + 1 f (ξ) -g(ξ) dξ + tψ(x) = x M xm η(ξ)ψ(ξ)dξ + tψ(x)
which is exactly equation [START_REF] Pontryagin | Mathematical theory of optimal processes[END_REF]. We show now that for t in [0, T ], there exists an unique pair (x m , x M ) in I ∩{x < x} that satisfy conditions [START_REF] Parulekar | Analysis of forced periodic operations of continuous bioprocesses: single input variations[END_REF] and [START_REF] Pontryagin | Mathematical theory of optimal processes[END_REF].

For the particular case t = T , condition (18) imposes to have x M = x m = x and condition [START_REF] Pontryagin | Mathematical theory of optimal processes[END_REF] to have ψ(x) = ū = ψ(x). However, under Hypothesis H, x = x is the only admissible constant solution in I ∩ {x < x}. We consider now t < T . Let us define the map

χ : (ξ -, ξ + ) → χ(ξ -, ξ + ) := ξ+ ξ- η(ξ) dξ, (ξ -, ξ + ) ∈ I 2
Under Hypotheses H1, H2, η is a positive map on I, and one can easily check that for any α ∈ I, χ(α, •) is C 1 and increasing with χ(α, α) = 0 and χ(α, b) = +∞. By the Implicit Function Theorem, there exists a unique map β : I → I of class C 1 , such that χ(α, β(α)) = T -t for any α ∈ I. Moreover, one has β(α) > α for any α ∈ I, and one can easily check that β(I) = I. Note that one obtains also

β (α) = - ∂ ξ-χ(α, β(α)) ∂ ξ+ χ(α, β(α)) = η(α) η(β(α)) > 0, α ∈ I.
Let us then consider the map 18) amounts to have β(x m ) = x M and condition [START_REF] Pontryagin | Mathematical theory of optimal processes[END_REF] to have F (x m ) = 0. Let us write equivalently the function F as follows

F (α) := β(α) α η(ξ)ψ(ξ)dξ -(T ū -tψ(β(α))), α ∈ I Condition (
F (α) := β(α) α η(ξ) ψ(ξ) -ψ(x) dξ + t ψ(β(α)) -ψ(x) , α ∈ I
Under Hypothesis H, one has ψ(ξ) > ψ(x) for ξ ∈ (x, β -1 (x)) and ψ(ξ) < ψ(x) for ξ ∈ (a, β -1 (x)). Therefore, one has

F (α) > 0, α ∈ (x, β -1 (x)) and F (α) < 0, α ∈ (a, β -1 (x))
By the Intermediate Value Theorem, we deduce that there exists α ∈ (β -1 (x), x) such that F (α) = 0. Moreover, one has

F (α) = η(β(α)) ψ(β(α)) -ψ(x) β (α) -η(α) ψ(α) -ψ(x) + tψ (β(α))β (α) = η(α)(ψ(β(α)) -ψ(α)) + tψ (β(α))β (α) > 0, α ∈ (β -1 (x), x)
Therefore, we deduce that there exists an unique x m ∈ I such that F (x m ) = 0 with β(x m ) < x, and x M is then uniquely defined as x M = β(x m ).

Remark 3. Under uniqueness of x m , x M solutions of (18), [START_REF] Pontryagin | Mathematical theory of optimal processes[END_REF], the controls u a ( t; •), u b ( t; •) can be expressed as follows

u a ( t; t) =          -1 if t < t 1 := inf{t > 0, x(t) = x m } +1 if t 1 ≤ t < t 2 := inf{t > t 1 , x(t) = x M } ψ(x M ) if t 2 ≤ t < t 2 + t -1 if t 2 + t ≤ t < t < T u b ( t; t) =          -1 if t < t 1 := inf{t > 0, x(t) = x m } ψ(x m ) if if t 1 ≤ t < t 1 + t +1 if t 1 + t ≤ t < t 2 := inf{t > t 1 + t, x(t) = x M } -1 if t 2 ≤ t < t < T
We state now our main result, which says that optimal trajectories are of the BSB type.

Theorem 1. Under Hypotheses H1-H2-H, and H5a, resp. H5b, there exists t ∈ [0, T ] such that the control u a ( t; •), resp. u b ( t; •) given by Proposition 6 is optimal for Problem (8) and the associated trajectory satisfies the slope condition (14), resp. (15) when t ∈ (0, T ).

Proof. Let u(•) be an optimal solution for Problem (8) and x(•) the corresponding trajectory. If x M ≤ x c or x m ≥ x c , then x(•) remains in a domain of I where γ does not change its concavity. One can then apply the former results of [START_REF] Bayen | Optimal periodic control for scalar dynamics under integral constraint on the input[END_REF] that state that the optimal trajectory on [0, T ] is either constant, or "bang-bang" with a single switch at x m and at x M . This amounts to claim that u a ( t; •) or u b ( t; •) is optimal with t = 0 or t = T . Let us now consider cases for which x M > x c and x m < x c . Assume that Hypothesis H5a is fulfilled (the proof under Hypothesis H5b is similar, where u a is replaced by u b , and is left to the reader).

θ(t) =          t if t < t 2 t + (t 3 -t 2 ) if t 2 ≤ t < t 2 + t 4 -t 3 t -(t 4 -t 3 ) if t 2 + t 4 -t 3 ≤ t < t 4 t if t 4 ≤ t ≤ T
so that the successive two peaks are now in the domain {x > x b } (see Figure 4). One can straightforwardly check that x θ (•) is another admissible solution that satisfies the constraints [START_REF] Bezanson | Julia: A fresh approach to numerical computing[END_REF] with the same cost than x(•). Take x ∈ (x b , x M ) and let t

= inf{t > t 1 , x θ (t) > x}, T (x) = inf{t > t M 2 -(t 3 -t 2 ), x θ (t) < x} -t.
On the interval [ t, t + T (x)], the trajectory x θ (•) is bang-bang with three switches (increasing up to x M , decreasing down to x b , increasing again up to x M and finally decreasing down to x), and one can write Therefore, by the Intermediate Value Theorem, we can choose x ∈ (x b , x M ) such that Ũ (x) = T (x)ψ(x), which amounts to have the average ũ of the control u • θ(•) on the interval [ t, t + T (x)] equal to ψ(x). On this interval, we can consider the optimal control problem (8) with T = T (x), ū = ũ and x = x. As γ is concave increasing on [x b , x M ], we can use the results of [START_REF] Bayen | Optimal periodic control for scalar dynamics under integral constraint on the input[END_REF] that claim that a non-constant trajectory cannot minimize the average of l • x θ (•) on this interval, leading to a contradiction with the optimality of x θ (•), and thus of x(•).

T (x) = x M x dξ f (ξ) + g(ξ) - x b x M dξ f (ξ) -g(ξ) + x M x b dξ f (ξ) + g(ξ) - x x M dξ f (ξ) -g(ξ) = x M x η(ξ)dξ + x M x b η(ξ)dξ
In a similar way, one can prove that x(•) cannot switch more than once at x m . Indeed, if it is the case one can consider an analogous construction of an optimal trajectory with a piece in the domain where γ is convex, and where it switches twice at x m , contradicting the former results of [START_REF] Bayen | Optimal periodic control for scalar dynamics under integral constraint on the input[END_REF] for the convex case.

Thus, if x(•) has no singular arc, it has exactly one switch at x M and one switch at x m , and is synthesized by the control u a (0; •), which is uniquely defined according to Proposition 6.

Finally, if x(•) possesses a singular arc at a certain x, we know from Proposition 4 that x M and x m are the only values of x(•) for which switches occur, and that x = x M . As x(•) cannot have more than one switch at x m we deduce that the set S = {t ∈ [0, T ], x(t) = x M } is connected. Therefore, x(•) has a unique singular arc of length t = |S| > 0 and is synthesized by a control with a BSB structure, such as u a ( t; •) which is uniquely defined according to Proposition 6. such that the slope condition is verified when t is not 0 or T , as illustrated in Section 6. Accordingly to Proposition 6, one can equivalently look for values x of the singular arc that give the best value of the criterion. For this purpose, one can first determine the subset X M , resp. X m , of values x M ∈ (x c , x) such that the slope condition ( 14) is fulfilled for some x m < x c (with a numerical tolerance), resp. of values x m < x c such that the slope condition (15) is fulfilled for some x M ∈ (x c , x). Then, one has simply to test the performances of the BSB strategy with x in X M , resp. X m .

Illustration on a bioprocess model

In the past decades, periodic operations of biological or chemical processes have been investigated to enhance their performances [START_REF] Bailey | Periodic operation of chemical reactors: a review[END_REF][START_REF] Abulesz | Periodic optimization of continuous microbial growth processes[END_REF][START_REF] Silveston | Periodic Operation of Chemical Reactors[END_REF][START_REF] Ruan | Comparison of several periodic operations of a continuous fermentation process[END_REF]. Several contributions have identified situations for which a periodic solution improves an objective function, such as the productivity, compared to its value at steady state [START_REF] Watanabe | Periodic control of continuous stirred tank reactors-I: The pi criterion and its applications to isothermal cases[END_REF][START_REF] Abulesz | Periodic optimization of continuous microbial growth processes[END_REF][START_REF] Parulekar | Analysis of forced periodic operations of continuous bioprocesses: single input variations[END_REF][START_REF] D'avino | On the choice of the optimal periodic operation for a continuous fermentation process[END_REF], or not [START_REF] Sadeghi | No switching policy is optimal for a positive linear system with a bottleneck entrance[END_REF]. In the recent work [START_REF] Bayen | Improvement of performances of the chemostat used for continuous biological water treatment with periodic controls[END_REF], an application for the piloting of waste water bioprocesses has been investigated. It has been shown that depending on the characteristics of the growth function of the micro-organisms, a non constant periodic flow rate could provide a lower average concentration of pollutant at the output of the process, compared to a constant flow rate treating the same quantity of contaminated water on a given period of time. However, when the growth function is neither convex nor concave, such as the Hill growth function (see below), a bang-bang periodic control is optimal when the nominal steady-state is in a region of local convexity of the growth function and when the period is small enough. For larger periods, this control strategy could lead the state of the dynamics to a region of concavity of the growth rate, and the criterion could be even worse than for a constant control. For these cases, a repetition of bang-bang over the period has been proposed as a sub-optimal strategy. We are now in position to show that this strategy is indeed not optimal and that the optimal bang-singular-bang does a much better job.

We recall the chemostat model, traditionally used in waste-water treatment modeling (see, e.g., [START_REF] Harmand | The Chemostat: mathematical theory of microorganisms cultures[END_REF]) Given T > 0 and D ∈ (D -, D + ), the optimal control problem considered in [START_REF] Bayen | Improvement of performances of the chemostat used for continuous biological water treatment with periodic controls[END_REF] is inf

) ṡ = -µ(s)b + D(s in -s) ḃ = µ(s)b -Db (20
D(•) 1 T T 0 s(t)dt s.t. s(0) = s(T ) ; 1 T T 0 D(t)dt = D (21)
Note that the system (20) can be reduced to a one-dimensional control dynamics. Indeed, for any periodic solution (s(•), b(•)) one has ż = -Dz where z = s in -s -b. Since z(•) is also periodic, one has necessarily z(t) = 0 for any t so that (20) becomes ṡ = (D(t) -µ(s))(s in -s)

The function µ is assumed to be C 1 increasing with µ(0) = 0. The nominal dilution rate D is chosen in (0, µ(s in )), so that there exists an unique steady-state s ∈ (0, s in ) for constant control D = D, as the unique solution of µ(s) = D, which is globally asymptotically stable on the domain (0, s in ).

Let us show that this problem falls exactly in the framework of Section 2. We take for I the largest open interval containing s that is invariant for [START_REF] Silveston | Periodic Operation of Chemical Reactors[END_REF] From the expression of f and g, we get ψ(s) = αµ(s) -β which is increasing. Hypothesis H is thus fulfilled.

Here, we have considered for the function µ the Hill function (as in [START_REF] Bayen | Improvement of performances of the chemostat used for continuous biological water treatment with periodic controls[END_REF]) which is a monotonic growth function given by the expression µ(s) := µ max s n K n s + s n , (n > 1) This function is convex for s lower than

s c = K s n -1 n + 1 1 n
and concave for s above this value (see Figure 5). Hypothesis H5a is thus fulfilled. 3. optimal bang-singular-bang control, for which the optimal value of t ∈ (0, T ) has been determined numerically, for which the value s of the singular arc satisfies the slope condition ( 14) (see Figure 7)

Computations have been performed with the programming language Julia [START_REF] Bezanson | Julia: A fresh approach to numerical computing[END_REF]. Results are summed up in Table 1, and Figure 6 depicts the corresponding trajectories. On Figure 7, one can also verify that the slope condition is

Conclusion

In this work, we have revisited a class of optimal periodic control problems linear with respect to the control, relaxing the convexity or concavity hypothesis on the dynamics. Based on the adjoint equations of the Maximum Principle, we have introduced several non-local techniques (slope condition, trajectory truncation, swap of pieces of trajectory...) to show that the optimal solution admits a single singular arc. This result generalizes former ones in the sense that a singular arc of null length gives a pure bang-bang solution which is optimal in the convex case, while a singular arc of full length is a constant solution that is optimal in the concave case. An illustration on a biological model shows the gains of the optimal strategy over bang-bang or steady-state solutions. More generally, this result shows the interest of "bang-singular-bang" periodic controls, compared to patterns considered in other approaches such as the π-criterion.

Figure 7: Graphs of the cost function J T (u a ( t, •)) as a function of t, for the four cases considered in Table 1. The portions of the curves in red correspond to BSB trajectories for which the slope condition ( 14) is verified (with a numerical tolerance of 5%). Dashed lines represents the costs of the constant controls.

Definition 1 .Remark 1 .

 11 Under H1-H2-H, let x := min{x ∈ I, s.t. ψ(x) = ū} and x := arg max x∈ Ī ψ(x) Under H1-H2-H, one has necessarily x ≤ x, with x being the only value fulfilling H. Moreover, having ψ non monotonic with at most one change of monotonicty implies that the function f and g are null at a or b.

Figure 1 :

 1 Figure 1: Example 1 fulfills Hypothesis H5a.

Figure 2 :

 2 Figure 2: Example 2 fulfills Hypothesis H5b.

Figure 3 :

 3 Figure 3: An illustration of the truncation in the proof of Proposition 5: the blue part is replaced by the red one

  )ψ(ξ)dξAs η is positive and ψ is increasing on [x m , x M ] (by Proposition 5), one getŨ (x b ) > T (x b )ψ(x b ) and Ũ (x M ) < T (x M )ψ(x M )

Figure 4 :

 4 Figure 4: Illustration of the swap of piece of trajectory in the proof of Theorem 1: the trajectory x(•) on the left is replaced by the trajectory x θ (•) on the right

  ) where s and b denote the concentrations of pollutant and biomass. The control variable is the dilution rate D (taking values in [D -, D + ] with 0 ≤ D -< D + ) and s in > 0 is the input pollutant concentration. The function µ(•) is the specific growth rate of the microbial population (the conversion rate of the bio-reaction has been kept equal to 1 without loss of generality, by a choice of the unit of b). One can straightforwardly see that non-trivial equilibria of (20) for constant D = D ∈ [D -, D + ] are of the form (s, b) = (s, s in -s) with D = µ(s)

  with controls in [D -, D + ] and positu := αD + β ∈ [-1, 1] with α := 2 D + -D - , β := -D + + D - D + -D -On the interval I, we consider the functionsf (s) := (-µ(s) -β/α)(s in -s), g(s) := (s in -s)/α and for the criterion (21) one takes (s) = s. Let us check that Hypotheses H1-H2 are fulfilled. First of all, the bounds a, b of I are such that µ(a) = D -and µ(b) = D + or b = s in . Then, one hasf (a) = g(a) = D + -D - 2 (s in -a), f (b) = -g(b) = -D + -D - 2 (s in -b) and f (s) -g(s) = (D --µ(s))(s in -s) < 0, f(s) + g(s) = (D + -µ(s))(s in -s) > 0, s ∈ (a, b)

Figure 5 :

 5 Figure 5: Graph of the Hill function for n = 2, K s = √ 3 and µ max = 2

Figure 6 :

 6 Figure 6: Examples of trajectories for the three control laws verified for the optimal BSB trajectory (given by the optimal t), in agreement with Proposition 4.

  x(•) is increasing at t} and T d := inf{T > 0 ; x(t d + T ) = x d } which are such that [t d , t d +T d ] ⊂ [0, T ]. On the time interval (t d , t d +T d ), x(•) is above x d and from what precedes, switching occurs only at x M with no singular arc. Therefore one has

  If x(•) does not have a singular arc, let us show that x(•) cannot switch more than once at x M on the interval [0, T ]. Otherwise, there exist t M 1 < t M 2 in (0, T ) such that x(t M 1 ) = x(t M 2 ) = x M with x(t) < x M for any t ∈ (t M 1 , t M 2 ). From Proposition 4, we know that there exists t I ∈ (t M Then, one has x(t) > x b for t ∈ (t 1 , t 2 ) ∪ (t 3 , t 4 ). Now, we swap the pieces of the trajectory x(•) on (t 2 , t 3 ) and (t 3 , t 4 ), defining a new trajectory x θ (t) = x(θ(t)), t ∈ [0, T ], where

		1 , t M 2 ) such that one has
	u(t) =	-1, a.e. t ∈ [t M 1 , t I ) 1, a.e. t ∈ [t I , t M 2 ]
	One can consider four numbers t i in (0, T ), i ∈ {1, . . . , 4}, such that
	(i) t 1 < t M 1 < t 2 < t 3 < t M 2 < t 4
	(ii) u(t) = 1 for a.e. t ∈ (t 1 , t M 1 ); u(t) = -1 for a.e. t ∈ (t M 2 , t 4 )
	(iii) x(t i ) = x b , i ∈ {1, 2, 3, 4}, with x b > x c

Acknowledgments

Most of this work has been achieved while the first author was in internship from ENSTA, Paris at MISTEA Lab, Montpellier, France. Since Dec. 2020, the first author's research is funded by the European Research Council Starting Grant MAJORIS ERC-2019-STG-850925.


Nicolas Hubert
email: nicolas.hubert@loria.fr

Pierre Monnin
email: pierre.monnin@orange.com

Armelle Brun
email: armelle.brun@loria.fr

Davy Monticolo
email: davy.monticolo@univ-lorraine.fr

New Strategies for Learning Knowledge Graph Embeddings: the Recommendation Case

Keywords: Negative Sampling, Knowledge Graph Embedding, Recommendation, Link Prediction, Ontology

Knowledge graph embedding models encode elements of a graph into a low-dimensional space that supports several downstream tasks. This work is concerned with the recommendation task, which we approach as a link prediction task on a single target relation performed in the embedding space. Training an embedding model requires negative sampling, which consists in corrupting the head or the tail of positive triples to generate negative ones. Although knowledge graph embedding models and negative sampling have extensively been investigated for link prediction, their combined use for performing recommendations over knowledge graphs remains largely unexplored in the literature. In this work, we propose two specialization strategies for training embedding models and performing knowledge graph-based recommendations. Both strategies first train an embedding model on the whole knowledge graph. Then, during a specialization phase, a dedicated negative sampling scheme is applied to refine the pre-trained model. Experimental results on two public datasets demonstrate that a simple strategy which refines a pre-trained model by sampling random negative tails for the target relation proves to be very effective. This strategy significantly improves performance with respect to traditional rank-based evaluation metrics as well as a newly introduced metric that reflects the semantic validity of the top-ranked candidate entities.

Introduction

A knowledge graph (KG) is a collection of facts (h, r, t) where h (head) and t (tail) are two entities of the graph, and r is the semantic relation that links them. KGs are used for several tasks including entity matching, question answering and link prediction [START_REF] Wang | Knowledge graph embedding: A survey of approaches and applications[END_REF]. The latter is the focus of this paper. Link prediction consists in assessing the probability of existence of a given triple, for example in a knowledge graph completion perspective. Several approaches address the link prediction task, especially Knowledge Graph Embedding (KGE) methods [START_REF] Rossi | Knowledge graph embedding for link prediction: A comparative analysis[END_REF][START_REF] Wang | A survey on knowledge graph embeddings for link prediction[END_REF]. They encode entities and relations of the KG into a low-dimensional vector space that preserves the structure of the original graph [START_REF] Wang | A survey on knowledge graph embeddings for link prediction[END_REF].

Training such KGE models requires both positive and negative triples. As KGs are usually made up of only positive triples, negative sampling (NS) is used to generate non-existent triples by corrupting the head or the tail of positive triples with any other entity from the KG [START_REF] Rossi | Knowledge graph embedding for link prediction: A comparative analysis[END_REF]. Resulting triples are called negative samples and they constitute the basis on which embedding learning is performed: embedding models iteratively learn to assign higher ranks to true triples than to negative ones. Hence, the way these models learn is significantly influenced by negative sampling methods, which therefore received much attention recently [START_REF] Hajimoradlou | Stay positive: Knowledge graph embedding without negative sampling[END_REF][START_REF] Islam | Negative sampling and rule mining for explainable link prediction in knowledge graphs[END_REF][START_REF] Kotnis | Analysis of the impact of negative sampling on link prediction in knowledge graphs[END_REF].

These negative sampling methods usually intervene in link prediction tasks that consider all relations in the KG. However, in some application domains there is a target relation, i.e. a certain type of link that is of interest for prediction. In this work, we address the recommendation task and we approach it as a link prediction task on a single relation. More specifically, the target relation represents the link between users and items to recommend [START_REF] Edwards | Explainable biomedical recommendations via reinforcement learning reasoning on knowledge graphs[END_REF][START_REF] Palumbo | Translational models for item recommendation[END_REF]. Recommendation consists in predicting one or a few relevant items of interest for a current user. In other words, for a given triple (u, r, ?), the goal is to recommend the more relevant items for user u, with r denoting the nature of the recommendation based on the application context. For instance, a use case could be recommending university curricula to high school students. Although KGE models have successfully been used for recommendation [START_REF] Chowdhury | Neural factorization for offer recommendation using knowledge graph embeddings[END_REF][START_REF] Palumbo | Translational models for item recommendation[END_REF], literature has primarily focused on KGE and NS for the more generic link prediction task. Predicting on a unique relation arguably responds to a different learning objective. Thus, we claim that new approaches are needed and we formulate the following research question: RQ1. Does refining a KGE model pre-trained on a generic link prediction task by specializing training on the target relation improve recommendation performance?

Once a KGE model is trained, its quality with regard to the link prediction task is traditionally assessed using rank-based metrics. These metrics face some limitations as they only focus on the presence (or not) of the ground-truth in the top-K list. From our view, the ability of a model at predicting links that are semantically close to the ground-truth is a supplementary dimension that needs to be evaluated in order to have a more comprehensive view of a model quality. This way, the ability of a model to retain the semantic profile (i.e. range type) of the target relation can be better assessed. Please note that in the rest of the paper, we only consider the range type of the relation when referring to its semantic profile. This raises our second research question: RQ2. What is the impact of different training strategies on the ability of KGE models to capture the semantic profile of the target relation?

Regarding RQ1, our motivation is to study one-hop KGE models that proved successful in downstream recommendation tasks [START_REF] Chowdhury | Neural factorization for offer recommendation using knowledge graph embeddings[END_REF][START_REF] Palumbo | Translational models for item recommendation[END_REF], and determine whether their performance can be enhanced by specializing the training procedure. RQ2 goes a step further, and we ask whether a more informed negative sampling method has a positive impact on the ability of an embedding model to retain the semantic profile of the target relation. The main contributions of our work are summarized as follows.

-We introduce two novel strategies for training knowledge graph embeddings for a downstream recommendation task. -We introduce a new metric that measures the semantic validity of the topranked candidate entities.

The remainder of the paper is structured as follows. Related work about KGE models for recommendation and negative sampling is presented in Section 2. In Section 3, we detail the models and the proposed strategies for making KGEbased recommendations. Dataset descriptions, experimental settings and key findings are provided in Section 4. A discussion is provided in Section 5. Lastly, Section 6 summarizes the key findings and outlines directions for future research.

Related Work

Knowledge Graph Embeddings for Recommendation

Several methods have been proposed for making recommendations over KGs. Most recent approaches based on Graph Neural Networks (GNNs) showcase impressive performance [START_REF] Wu | Graph neural networks in recommender systems: a survey[END_REF]. Their success in recommendation tasks derives from their ability to model higher-order connectivity and encode sparse semisupervised signals [START_REF] Gao | Graph neural networks for recommender system[END_REF]. However, GNN-based recommender systems have some limitations: due to their large memory usage and significant training time, GNNs are not always applicable in real-world scenarios [START_REF] Wu | Graph neural networks in recommender systems: a survey[END_REF].

On the contrary, one-hop embedding models are simpler models that proved to be successful in downstream recommendation tasks [START_REF] Liu | A survey of recommendation algorithms based on knowledge graph embedding[END_REF]. Grad-Gyenge et al. [START_REF] Grad-Gyenge | Graph embedding based recommendation techniques on the knowledge graph[END_REF] compare traditional collaborative filtering and embedding models for making recommendations over KGs. They clearly show that the latter significantly increase recommendation performance without suffering from an increasing amount of user interactions, contrary to traditional collaborative filtering algorithms. However, their experiments do not consider mainstream KGE models that are most commonly used. By contrast, [START_REF] Palumbo | Translational models for item recommendation[END_REF] analyses the experimental results obtained with popular KGE models. Their work is close to our line of research, as it is concerned with the recommendation task. Although the authors clearly emphasize the superiority of KGE models over traditional baselines in a recommendation framework, they only focus on translational models which include TransE [START_REF] Bordes | Translating embeddings for modeling multi-relational data[END_REF], TransH [START_REF] Wang | Knowledge graph embedding by translating on hyperplanes[END_REF] and TransR [START_REF] Lin | Learning entity and relation embeddings for knowledge graph completion[END_REF], and do not consider other popular and effective KGE models [START_REF] Rossi | Knowledge graph embedding for link prediction: A comparative analysis[END_REF]. In addition, they do not study the influence of negative sampling on recommendation performance.

Negative Sampling for Link Prediction in Knowledge Graphs

While KGs usually comprise positive triples only, training KGE models requires negative samples [START_REF] Kotnis | Analysis of the impact of negative sampling on link prediction in knowledge graphs[END_REF]. An early introduced method is Random Negative Sampling (RNS). It consists in replacing either the head h or the tail t of a triple with any other entity sampled uniformly from the set of observed entities in the KG [START_REF] Bordes | Translating embeddings for modeling multi-relational data[END_REF]. However, sampling random entities uniformly can generate positive triples. For example, replacing the tail of (CristianoRonaldo, playedFor, RealMadrid) with ManchesterUnited would generate the triple (CristianoRonaldo, played-For, ManchesterUnited) which actually represents a true fact. The approach presented in [START_REF] Wang | Knowledge graph embedding by translating on hyperplanes[END_REF] reduces the risk of creating such false-negative triples by setting different probabilities for replacing the head and the tail based on the nature of the relation that links them: if the relation r is 1-to-N (e.g. parentOf), the head h has a higher probability of being replaced. If the relation r is N-to-1 (e.g. bornIn), the tail t is more likely to be replaced. More specifically, [START_REF] Wang | Knowledge graph embedding by translating on hyperplanes[END_REF] uses a Bernoulli distribution to sample heads or tails with distinct probabilities.

However, the two aforementioned approaches cannot prevent the sampling procedure from producing semantically incorrect triples such as (Cristiano-Ronaldo, playedFor, SoccerShoes). Such nonsensical triples do not provide the model with sufficient signal to learn from, which causes the notorious zero loss problem [START_REF] Wang | Incorporating GAN for negative sampling in knowledge representation learning[END_REF]. Therefore, more sophisticated methods have been proposed to generate high-quality negative samples and consequently give more hints to the model training [START_REF] Zhang | Nscaching: Simple and efficient negative sampling for knowledge graph embedding[END_REF]. In particular, ontological constraints and domain knowledge can be leveraged to create meaningful negative samples [START_REF] Jain | Improving knowledge graph embeddings with ontological reasoning[END_REF][START_REF] Krompaß | Type-constrained representation learning in knowledge graphs[END_REF][START_REF] Weyns | Conditional constraints for knowledge graph embeddings[END_REF]. Intuitively, generating more realistic and robust negative samples helps the embedding model learn a better vector representation of the graph components. For instance, type-constrained negative sampling (TCNS) [START_REF] Krompaß | Type-constrained representation learning in knowledge graphs[END_REF] replaces the head or the tail with a random entity belonging to the same type as the ground-truth entity. By doing so, only semantically valid triples are generated during negative sampling. TCNS has been found to work better than pure RNS in several scenarios [START_REF] Kotnis | Analysis of the impact of negative sampling on link prediction in knowledge graphs[END_REF][START_REF] Krompaß | Type-constrained representation learning in knowledge graphs[END_REF]. However, it should be noted that entities are rarely typed [START_REF] Cai | KBGAN: adversarial learning for knowledge graph embeddings[END_REF][START_REF] Krompaß | Type-constrained representation learning in knowledge graphs[END_REF]. To the best of our knowledge, RNS and TCNS have not been studied in the specific frame of single-relation link prediction, especially recommendation. It would be interesting to investigate whether they demonstrate greater efficiency in such a framework.

Training Embedding Models for Recommendation

Fig. 1 outlines the whole approach that we further explicit in the following. In Section 3.1, we summarize the KGE models used in this work. Then, in Section 3.2 we elaborate on the specialization training and negative sampling strategies that we propose. These strategies are designed to fit the recommendation task. Finally, Section 3.3 details a newly introduced semantic-oriented metric that -combined with traditional rank-based metrics such as Hits@Kprovides a more comprehensive view of the quality of a KGE model. ), but differ regarding the negative sampling method. These two strategies are benchmarked against B-RNS in terms of Hits@K and our newly introduced semantic-oriented metric Sem@K.

Knowledge Graph Embedding Models

In line with [START_REF] Kotnis | Analysis of the impact of negative sampling on link prediction in knowledge graphs[END_REF], we use TransE [START_REF] Bordes | Translating embeddings for modeling multi-relational data[END_REF], TransH [START_REF] Wang | Knowledge graph embedding by translating on hyperplanes[END_REF], DistMult [START_REF] Yang | Embedding entities and relations for learning and inference in knowledge bases[END_REF], and Com-plEx [START_REF] Trouillon | Complex embeddings for simple link prediction[END_REF], which all are very popular models that have proven to work well in a wide range of link prediction tasks. These models are detailed below.

TransE is the earliest translational model. It learns representations of entities and relations such that for a triple (h, r, t), e h + e r ≈ e t where e h , e r and e t are the head, relation and tail embeddings, respectively. The scoring function is f (h, r, t) = -d(e h + e r -e t ) with d a distance function, usually the L1 or L2 norm. TransE does not properly handle 1-to-N, N-to-1 nor N-to-N relations [START_REF] Wang | Knowledge graph embedding: A survey of approaches and applications[END_REF] and yet has been found to be very efficient in multi-relational settings [START_REF] Chowdhury | Neural factorization for offer recommendation using knowledge graph embeddings[END_REF].

TransH is an extension of TransE. It allows entities to have distinct representations when involved in different relations. Specifically, e h and e t are projected into relation-specific hyperplanes with projection matrices w r . If (h, r, t) holds, the projected entities e h ⊥ = e h -w T r e h w r and e t ⊥ = e t -w T r e t w r are expected to be linked by the relation-specific translation vector d r . Thus, the scoring function is f (h, r, t) = -d(e h ⊥ +d r -e t ⊥ ). TransH often showcases better performance than TransE with only slightly more parameters [START_REF] Wang | Knowledge graph embedding by translating on hyperplanes[END_REF].

DistMult is a semantic matching model. It is characterized as such because it uses a similarity-based scoring function and matches the latent semantics of entities and relations by leveraging their vector space representations. More specifically, DistMult is a bilinear diagonal model that uses a trilinear dot product as its scoring function: f (h, r, t) = ⟨e h , W r , e t ⟩. It is similar to RESCAL [START_REF] Nickel | A three-way model for collective learning on multi-relational data[END_REF] -the very first semantic matching model -but restricts relation matrices W r ∈ R d×d to be diagonal. As the scoring function of DistMult is commutative, all relations are considered symmetric. This assumption does not hold in general. However, DistMult still achieves state-of-the-art performance in most cases [START_REF] Kadlec | Knowledge base completion: Baselines strike back[END_REF].

ComplEx is also a semantic matching model. It extends DistMult by using complex-valued vectors to represent entities and relations: e h , e r , e t ∈ C d . As a result, ComplEx is better able to model antisymmetric relations than DistMult [START_REF] Sun | Rotate: Knowledge graph embedding by relational rotation in complex space[END_REF]. Its scoring function uses the Hadamard product: f (h, r, t) = Re (e h ⊙ e r ⊙ e t ) where e t denotes the conjugate of e t .

New Specialization Strategies for Training KGE

To train the aforementioned KGE models, we consider the strategies depicted in Fig. 1. Contrary to the generic link prediction task, we assume that for a downstream recommendation task, the training phase should focus more on the target relation. However, the KGE model still needs to be trained considering all entities and relations before specializing in order to take into account all the available information in the KG. This motivates the pre-training step included in the two proposed strategies: both of them reuse a generic KGE model that was trained on the whole graph. It means that the training phase is first performed on all training triples, regardless of their relation. In the experiments, the generic KGE model trained on the whole graph with traditional RNS [START_REF] Bordes | Translating embeddings for modeling multi-relational data[END_REF] (top of Fig. 1) serves as our baseline and is referred to as B-RNS (standing for baseline random negative sampling).

Once the KGE model is pre-trained, triples whose relation differs from the target relation are filtered out from the train set. For both strategies presented below, training resumes by specializing the training of the KGE model on the resulting filtered train set. The way the specialization phase is achieved depends on the negative sampling scheme used: S-RNS stands for specialized training with random negative sampling. In this strategy, the embedding model is refined by applying uniform RNS when corrupting the tails of the remaining train triples. S-TCNS stands for type-constrained negative sampling. In this strategy, the embedding model is refined by applying TCNS [START_REF] Krompaß | Type-constrained representation learning in knowledge graphs[END_REF] when corrupting the tails of the remaining train triples.

3.3 Evaluating Recommendations: Hits@K and Sem@K Hits@K is a rank-based metric extensively used for link prediction tasks. This metric accounts for the proportion of positive triples that are ranked in the top-K positions against a set of negative triples. Hits@K is also used in recommendation [START_REF] Yang | Understanding negative sampling in graph representation learning[END_REF]. As this work focuses on the recommendation task, the generic definition of Hits@K [START_REF] Rossi | Knowledge graph embedding for link prediction: A comparative analysis[END_REF] has to be modified to account for the fact that only tails are corrupted. The modified Hits@K is defined in Equation [START_REF] Bordes | Translating embeddings for modeling multi-relational data[END_REF].

Hits@K = 1 |B| (h,r,t)∈B 1 rank (h,r) (t) ≤ K (1)
where B is a batch of positive triples and rank (h,r) (t) denotes the position of the ground-truth tail t in the sorted list of top-K entities scored by a given KGE model, for the head h, and the target relation r.

However, from our view, Hits@K remains limited when considering the recommendation task. Indeed, it only represents the ability of a model to rank the ground-truth higher in the top-K list. As such, this metric does not fully answer the following questions:

-When two KGE models have similar Hits@K, can we refine the evaluation process to safely favour one model? -When the ground-truth does not show up in the top-K list, how do we assess the extent to which the KGE model has captured the semantic profile of the target relation?

Traditionally, the aforementioned questions have been addressed by considering additional rank-based metrics such as Mean Rank (MR) and Mean Reciprocal Rank (MRR) [START_REF] Rossi | Knowledge graph embedding for link prediction: A comparative analysis[END_REF]. Compared to Hits@K, they take into account the position of the ground-truth without a threshold K. However, all rank-based metrics solely focus on the ground-truth at hand, without taking into consideration the other ranked entities. In some application domains, knowing the rank of the groundtruth is not sufficient. In the recommendation case, the catalog of items can be huge, so that recommending entities that are related to the ground-truth is also of interest. In the context of a KG, similarity between entities can be reflected through their types. As a result, it is desirable for a KGE model to also retain the semantic profile of the target relation in order to assign higher scores to triples that are semantically close to the ground-truth.

To this aim, we introduce Sem@K, a new semantic-oriented metric. Combining it with Hits@K gives a more comprehensive view of the quality of a KGE model. Sem@K reflects to what extent a K-list contains semantically valid candidates with regard to the range of the target relation. Hence the definition of Sem@K in Equation (2):

Sem@K = 1 |B| q∈B 1 K q ′ ∈S K q compatibility(q, q ′ ) (2)
where S K q is the top-K list of candidate triples scored by a given KGE model given a ground-truth triple q, and compatibility(q, q ′ ) (Equation (3)) assesses whether the candidate triple q ′ is semantically compatible with its ground-truth counterpart q. As this work focuses on the recommendation task, by semantic compatibility we refer to the fact that the predicted tail belongs to the range of the target relation:

compatibility(q, q ′ ) = 1, if type(q ′ t ) = range(q r ) 0, otherwise (3)
where type(e) returns the type of entity e and range(r) is the range of the relation r. q r and q ′ t denote the ground-truth relation and the tail of the candidate triple, respectively.

Compared to Hits@K that naturally increases or remains equal with higher values of K, Sem@K behaviour is non-monotonic. However, when the set of semantically valid candidates is limited, one should reasonably expect a decreasing Sem@K with higher K. Sem@K can be generalized to any other semantic context by adapting the semantic compatibility compatibility() operator with the context-dependent one. In our experiments, all strategies are evaluated using Hits@K and Sem@K, as depicted in Fig. 1.

Experiments

To address the relevance of the proposed specialization training strategies, experiments are conducted on real-world and public datasets and we subsequently evaluate these strategies in terms of Hits@K and the newly introduced Sem@K.

Datasets

As aforementioned, our contributions are evaluated on EduKG and KG20C, two KGs that we choose for their adequate entity typing: given a head-relation pair (h, r), the missing tail can only be of one single type. Consequently, we are able to study the influence of TCNS [START_REF] Krompaß | Type-constrained representation learning in knowledge graphs[END_REF]. Both datasets naturally lend themselves to the recommendation task, whereas in most datasets used for link prediction, it is more questionable to favour one relation over the others. Below, we provide a thorough description of the KGs used in the experiments and indicate their respective target relation. Their main characteristics are summarized in Table 1.

EduKG 4 is an educational KG that authors of this work built and that is instantiated with students and a broad spectrum of university curricula. The goal is to recommend university curricula to high school students. More formally, for each triple of the form (h, r, ?), we aim at retrieving the ground-truth tail t where h is an entity of type Student, r accounts for the relation likedCurriculum and t is an entity of type Curriculum. An example would consist in retrieving the correct tail for the following test triple: (Bob, likedCurriculum, ?). Hence, for the S-TCNS strategy, only entities of type Curriculum are used to replace tails of positive triples during negative sampling. In EduKG, both the users (students) and items (curricula) are highly connected to other entities of the KG. For instance, students are linked to a HighSchoolMajor, they are characterized by PersonalityTraits, they have a certain amount of favorite SchoolSubjects, and they provide Keywords reflecting their interests. Likewise, curricula are linked to recommended or mandatory HighSchoolMajors, they belong to one or more FieldsOfStudy, and they are also related to Keywords. Importantly, EduKG comprises a total of 286 curricula. This means there are 286 semantically valid tail entities out of 5,452 entities when it comes to recommending university curricula to students.

KG20C [START_REF] Tran | Exploring scholarly data by semantic query on knowledge graph embedding space[END_REF] is a scholarly KG encompassing 5 different entity types: Authors, Papers, Domains, Conferences, and Affiliations. The goal is to recommend a conference where to publish a paper. For each triple of the form (h, r, ?), we aim at retrieving the ground-truth tail t where h is an entity of type Paper, r accounts for the relation publishedIn and t is an entity of type Conference. An example would be retrieving the correct tail for the following test triple: (LearningToEfficientlyRank, publishedIn, ?). In this case, the ground-truth tail is SIGIR. Hence, for the S-TCNS strategy, only entities of type Conference are used to replace tails of positive triples during negative sampling. Compared to EduKG, the set of semantically valid tails for the relation publishedIn is much more limited: KG20C comprises 20 distinct conferences out of the 16,362 observed entities. The number of triples in EduKG and KG20C is comparable. However, it should be noted that EduKG contains fewer entities but more relations than KG20C (see Table 1).

Experimental Setup

The experiments are conducted using a 5-fold cross-validation. In each crossvalidation setting, the test fold only comprises triples whose relation r is the target relation. TransE, TransH, DistMult, and ComplEx are implemented using PyTorch. Importantly, when comparing different training strategies, models are instantiated with the same initialization seed. The choice of the number of epochs, negative samples, embedding dimensions, and learning rate are based on what was found to work best for these datasets. Regardless of the strategy used, we first perform 1,000 epochs of general training with early-stopping (B-RNS) to ensure that training is achieved in a reasonable amount of time and that the best evaluation metrics are recorded. 100 epochs of specialized training are subsequently performed with early-stopping by applying the two strategies S-RNS and S-TCNS. These two strategies are compared against the baseline B-RNS. All models are trained using max-margin loss and Adam optimizer as in [START_REF] Kotnis | Analysis of the impact of negative sampling on link prediction in knowledge graphs[END_REF]. The hyperparameters are shared across all configurations to ensure a fair comparison of their respective performance: number of negative triples per positive one C = 50 (in accordance with [START_REF] Trouillon | Complex embeddings for simple link prediction[END_REF]), embedding dimension k = 20, learning rate η = 0.01, margin γ = 1.0. For TransE and TransH, distance d = L2 was used. Due to the presence of 1-to-N, N-to-1 and N-to-N relations in EduKG and KG20C, negative sampling can still generate false-positive triples after the corruption phase. Consequently, such positive triples are filtered out before ranking. In this work, only filtered Hits@K are reported [START_REF] Rossi | Knowledge graph embedding for link prediction: A comparative analysis[END_REF]. Finally, all entities observed in the KG (regardless of their type) are scored during evaluation so that Sem@K can be reported.

Results

The experimental results of the strategies outlined in Section 3.2 are presented in Tables 2 and3.

Table 2. Evaluation results on EduKG. H@K and S@K stand for Hits@K and Sem@K respectively, for K ∈ {1, 5, 10}. Green cells indicate which strategy performs best for a given model and metric.

B-RNS

S-RNS S-TCNS H@1 H@5 H@10 H@1 H@5 H@10 H@1 H@5 H@10 TransE 4.66 16.12 25.49 6. [START_REF] Wu | Graph neural networks in recommender systems: a survey[END_REF] S@5 S@10 S@1 S@5 S@10 S@1 S@5 S@10 Baseline Strategy Comparison across Datasets. In this section, we focus on the performance of the baseline model (B-RNS) regarding Hits@K. Results achieved under B-RNS are presented in the top left parts of Tables 2 and3.

Overall, Hits@K are higher on KG20C than on EduKG. At first glance, this may seem counter-intuitive as the number of distinct entities is three times higher in KG20C (∼16K) than in EduKG (∼5K) (see Table 1). In this case, the lower Hits@K values achieved on EduKG compared to KG20C may reasonably be explained by the number of relations in EduKG, which exceeds the number of relations in KG20C.

On both datasets, the best performing model under B-RNS is TransH and the worst performing one is TransE. The superiority of TransH over TransE is in accordance with [START_REF] Wang | Knowledge graph embedding by translating on hyperplanes[END_REF]. In terms of Hits@K, DistMult is slightly better than ComplEx on EduKG and slightly worse than ComplEx on KG20C. Recall that Table 3. Evaluation results on KG20C. H@K and S@K stand for Hits@K and Sem@K respectively, for K ∈ {1, 5, 10}. Green cells indicate which strategy performs best for a given model and metric.

B-RNS

S-RNS S-TCNS H@1 H@5 H@10 H@1 H@5 H@10 H@1 H@5 H@10 S@1 S@5 S@10 S@1 S@5 S@10 S@1 S@5 S@ ComplEx has been proposed to better model antisymmetric relations than Dist-Mult [START_REF] Trouillon | Complex embeddings for simple link prediction[END_REF]. EduKG does not contain any antisymmetric relation, which may explain the relatively similar Hits@K between DistMult and ComplEx. However, in KG20C, there is one antisymmetric relation (citedBy), hence the slightly better Hits@K provided by ComplEx compared to DistMult. RQ1: Impact of the Training Strategies on Hits@K. In order to answer the first research question, we evaluate the impact of the specialization strategies on the recommendation performance, as measured by Hits@K. From a more general point of view, we note that S-RNS and S-TCNS consistently achieve better Hits@K compared to B-RNS, for all K ∈ {1, 5, 10} and regardless of the dataset and KGE model used (see Tables 2 and3).

Differences exist between S-RNS and S-TCNS. On EduKG, S-TCNS provides better Hits@K than S-RNS (on average +35.7% for S-TCNS and +22.8% for S-RNS on Hits@10, compared to the results achieved with the baseline B-RNS). The reason may come from the fact that S-TCNS puts even more emphasis than S-RNS on discriminating between valid candidates for replacement, as the negative sampling is type-constrained. On KG20C, the conclusion differs: S-RNS performs systematically better than S-TCNS (on average +62.0% for S-RNS and +12.3% for S-TCNS on Hits@10, compared to the results achieved with the baseline B-RNS). This could be attributed to the low number of semantically valid candidates in KG20C: as there are only 20 entities of type Conference, S-TCNS is limited to a narrow set of semantically valid entities when performing negative sampling. As such, training may quickly reach a stage where performance cannot be improved anymore because most negative triples stop providing any further guidance to the model on improving the embeddings. This echoes the zero loss problem [START_REF] Wang | Incorporating GAN for negative sampling in knowledge representation learning[END_REF] mentioned in Section 2.2. In our experiments, we indeed noted that under S-TCNS, early-stopping was usually triggered before S-RNS, especially for TransE and TransH. For TransE, early-stopping was triggered after 7 epochs in average under S-TCNS and after 70 epochs in average under S-RNS. For TransH, early-stopping was triggered after 4 epochs in average under S-TCNS and after 22 epochs in average under S-RNS.

Consequently, when the set of semantically valid candidates is relatively large, S-TCNS seems to be an appropriate strategy as it helps the KGE model focus on semantically valid triples only, which are harder to differentiate. When the set of semantically valid candidates is limited, S-RNS is expected to perform better by providing more diverse and numerous samples to learn from.

To sum up, although S-RNS and S-TCNS do not provide comparable performance gains, they both improve results in terms of Hits@K compared to the baseline strategy B-RNS. This directly answers RQ1: specializing training on a single relation actually enhances the performance of a pre-trained KGE model in a downstream recommendation task.

RQ2: Impact of Training Strategies on Sem@K. To answer the second research question, we evaluate Sem@K on all models with the three strategies B-RNS, S-RNS and S-TCNS. First, the impact of S-RNS is significant: this strategy achieves the best results across all configurations. Interestingly, the use of S-RNS may even allow weaker models to compete with the other ones in terms of Sem@K. For example, ComplEx achieves disappointing Sem@K on EduKG under the baseline B-RNS. But when using S-RNS, Sem@K values obtained with ComplEx are comparable to the other models.

Focusing on the impact of S-TCNS on Sem@K, we note that on both datasets, the combined use of this strategy with the two translational models TransE and TransH deteriorates the model ability to capture the semantic profile of the target relation, compared to the results achieved under B-RNS. On the contrary, using S-TCNS enhances Sem@K of DistMult and ComplEx, which are two semantic-matching models. As evidenced by the green cells in Tables 2 and3 for Sem@K, K ∈ {1, 5, 10}, we clearly see that S-RNS consistently performs better under all configurations. This answers RQ2: even though integrating the entity type into the negative sampling (S-TCNS) can improve the ability of a model to capture the semantic profile of the target relation, it is always a less interesting option compared to randomly sampling tails among all entities (S-RNS).

It appears that evaluating the quality of a KGE model by only using rankbased metrics provides a limited view of its performance. In some cases S-TCNS gives better Hits@K than S-RNS. By analyzing the influence of type-constrained sampling on the understanding of the semantic profile of the target relation, we see that S-TCNS performs poorly -sometimes even worse than the baseline B-RNS. Therefore, Sem@K is complementary to traditional rank-based metrics and special attention should be paid to this metric whenever there is a need for predicting semantically valid entities.

Discussion

Although the literature often presents RNS as an ineffective sampling strategy for the generic link prediction task [START_REF] Islam | Negative sampling and rule mining for explainable link prediction in knowledge graphs[END_REF][START_REF] Wang | Incorporating GAN for negative sampling in knowledge representation learning[END_REF], we have shown it can be successfully used in a recommendation framework when combined with a specialization training procedure. In particular, S-TCNS sometimes improves Hits@K at the expense of the model understanding of the semantic profile of the target relation. In this case, there seems to be a trade-off. On the contrary, S-RNS appears to pursue both objectives at the same time: improving the ability of a KGE model to assign a high score to the ground-truth, and better retain the semantic profile of the target relation. By generating both nonsensical and hard negatives, S-RNS reports substantial improvement over the baseline B-RNS. This leads us to think that when it comes to recommendation, focusing on triples whose relation is the target relation (S-RNS) may actually lead to better results than both focusing and using an informed negative sampling method (S-TCNS). Although S-RNS is a simple strategy that does not require any filtering or additional informationcontrary to S-TCNS that requires knowing the type of each entity -we clearly demonstrate it could significantly enhance the quality of a KGE model in a downstream recommendation task.

Jain et al. [START_REF] Jain | Do embeddings actually capture knowledge graph semantics?[END_REF] investigate whether embeddings are actually able to capture KG semantics. Although our research questions differ, we show that in the recommendation task, specific training procedures may improve the ability of an embedding model to capture the semantic profile of the target relation. Our experimental results even highlight that models that initially perform poorly on Sem@K could achieve competitive results after proper specialized training.

Compared to the baseline, S-RNS improves both Hits@K and Sem@K on the target relation. However, our work did not study whether the two proposed specialization strategies decrease the overall quality of a KGE model, i.e. its performance in terms of Hits@K and Sem@K for other relations. In addition, we choose RNS as our baseline. This may have an impact on the performance gains of the two specialization strategies. One may wonder whether choosing a stronger baseline would impact the outcomes of this work. Finally, it should be noted that in both EduKG and KG20C, the target relation cardinality is N-to-1. It would be interesting studying whether our proposed specialization strategies perform similarly on target relations of other cardinality, especially N-to-N relations that are frequently observed in recommendation.

Conclusion and Future Directions

In this work, we approach the recommendation task as a link prediction task on a single target relation of a knowledge graph, i.e. the relation that represents the links between users and items to recommend. To this aim, we consider knowledge graph embedding models and evaluate their performance with three training strategies: one baseline strategy that trains a model on the whole graph, and two specialization strategies that refine this model by focusing on the target relation. These two specialization strategies differ in their negative sampling method. Beside evaluating our models with the usual Hits@K metric, we introduce Sem@K, a new semantic-oriented metric that reflects the semantic validity of the top-ranked candidate entities. In light of these two metrics, we clearly show that the specialization strategy which refines a pre-trained embedding model by randomly sampling negative tails for the target relation consistently enhances both Hits@K and Sem@K compared to the baseline. In future works, we will extend our analysis using a broader range of models (e.g. GNNs). We will also address multi-typed KGs, different application domains, and propose an adjusted version of Sem@K that would benefit from further theoretical guarantees.

Fig. 1 .

 1 Fig.1. Approach outline. S-RNS and S-TCNS are the two specialization strategies that we propose in this work. Both only include the target relation in the training procedure (dashed arrows), but differ regarding the negative sampling method. These two strategies are benchmarked against B-RNS in terms of Hits@K and our newly introduced semantic-oriented metric Sem@K.

Table 1 .

 1 Characteristics of EduKG and KG20C. |E|, |R| and |T | stand for the number of entities, relations and triples, respectively. |V| denotes the number of semantically valid tails for the target relation.

	Dataset	|E|	|R|	|T |	|V|
	EduKG	5,452	27	36,301	286
	KG20C	16,362	5	55,607	20

purl.org/edukg/doc