Michelle Schatzman

A CLASS OF NONLINEAR DIFFERENTIAL EQUATIONS OF SECOND ORDER IN TIME

Keywords: Existence and uniqueness, nonlinear equations of second order, monotone operators. I

IN WHAT follows,¢ will denote a lower semicontinuous convex proper function from R" = H to R u { + oo }. Here proper means that ¢ ¢:. + oo. The effective domain of¢ is the set dom ¢ = {x e RN/¢(x) < + oo }. We shall suppose that the interior of dom ¢ in RN is not empty, and ¢ ~ 0. These two assumptions do not restrict the generality. The scalar product in His denoted by (x, y).

Let us recall that the subdifferential of¢ is a (multivalued) operator defined on

y) for ally e H} with values o¢(x) = {z e H: ¢(x + y) -¢(x) ~ (z, y), Vy E H}.

The set o¢(x) is closed convex in Hand o¢ is a cyclically monotone operator, i.e. for all n e N, for all n-tuple (x 1 , ... , x.) of elements of D(o¢), for allY; e o¢(x;)

We define J;. =(I+ ).8¢)-1 on H; J;. is a contraction, and o¢;. =(I+ J;)/A is the Yosida approximation to o¢;8¢;. is Lipschitzian, with Lipschitz constant 1/A and o¢ .. (x)eo¢(J .. x).

If ¢;.(x) = inf {jx-yj 2 /(2).) + (¢/2)(y)}, o¢;. is the subdifferential of ¢;.• Explicitly, ¢;.(x) = ¢(JJ.x) + jx + J.J.xj 2 /(2).) and ¢ ;.(x) ~ ¢(x). Moreover, lim ¢ ;.(x) -¢(x) if x e H. The general

references for these results are refs [1,[START_REF] Rockafellar | Convex Analysis[END_REF].

;. .... o Before we proceed to the existence theorem, it is of some interest to give an explicit example. It will allow the reader to notice the difficulties of the problem. Assume u 0 > 0; we shall seek a solution u, which is locally Lipschitzian in t. The interesting case occurs when u 1 < 0. If t < u 0 /ul' the only solution of

d 2 u
dt2 + ol/fk(u) 3 0 is u(t) = x 0 + tu 1 • We must have u(t) ~ 0, for all t ~ 0. It is easy to check that any u of the form u(t) = 0 for for with v > 0 and -u 0 /u 1 ~ t 1 ~ oo is a solution. (see the figure below). If we assume that the energy is conserved, then necessarily u 0 (t) =u 1 (t + u 0 lu 1 ) fort ~u 0 /u 1 . There is an "optical reflection" in -u 0 /u 1 • The Yosida approximation gives, in the limit, the solution which conserves the energy. In fact, the approximating equation is

d 2 - Ul Ul -
----= 0 where r =min(r, 0); its solution is dt 2 A. '

ul(t) = u 0 + tu 1 u/t) = .j1u 1 sin [(t + t 0 )!JA] u/t) = -u 1 (t-n.JA -t 0 ) 0 ~ t ~ -u 0 /u 1 = t 0 t 0 ~ t ~ t 0 + nJA t 0 + nJA ~ t.
Clearly, the ul converge to the energy conserving solution, u 0 .

THE EXISTENCE THEOREM

Definition 1. Iff E 13(0, T; H) (T finite) and u 0 E dom cp, u 1 E Fi, we say that u is an energy-conserving solution of the problem (P)

(P)
when it satisfies the following requirements:

(1) u E W 1 • 00 ((0, T); H)

(2) u(t) E dom c/J, Vt E [0, T]

"initial conditions"

(3) there exists a bounded measure f.1. with values in H, such that (d 2 ujdt 2 ) + f.1. = fin the sense of distributions, and (4) for any continuous v, with values in H, such that ¢(v)E L 1 (0, T), we have:

I: (cp(v)-cp(u)) dt ~ (f.l., v-u)
(5) du/dt has left and right limits for any t E [0, T] (with the necessary modifications at 0 and T) (6) energy is conserved:

I d :~ (tf + cp(u(t)) = I d;tu (tf + cp(u(t)) = Ju 1 J 2 + cp(u 0 ) + I~ (u(s),f(s)) ds
almost everywhere on [0, T]; here u stands for du/dt (7) the initial conditions are satisfied in the following sense:

u(O) = u 0
and if K 0 is the closure of dom ¢, 1/1 Ko the indicator function of K 0 :

d+u -u 1 + dt(O) + iJI/fK 0 (u 0 )30.
THEOREM I. (a) For any f E 13(0, T; H), u 0 E dom ¢ and u 1 E H, the problem ( P) has an energyconserving. solution in the sense of Definition 1. This solution is obtained as the strong limit in H 1 ((0, T); H) and the weak * limit in W 1 • 00 ((0, T); H) of a subsequence of the sequence of solutions of(~):

(P;) (b) Moreover, if¢ is Lipschitzian in a neighbourhood of u 0 with respect to K 0 , and if -u 1 belongs to C, the tangent cone to K 0 at u 0 (i.e.

C = u r(K 0 -u 0 )), then t>O d+u (8) - (0) = 2P u -u dt c l 1
where P c is the projection onto C.

Proof Part (a)

1. Preliminary estimates We have the energy equality for (P;)

Interpretation of J.l•

Let dJ-1. = g. dt + dJ.l, be the decomposition of J.l with respect to the Lebesgue measure on [0, T].

Then Corollary 5.A of ref. [ 5], gives us the following results:

(13) g(t) E ilc/J(u(t)) almost everywhere (with respect to the Lebesgue measure) on [0, T].

Let N(t) be the normal cone to K 0 = dom c/J at u(t). Let J.l, = h ./J-1.,/ with h a J-1..-integrable function. Then We shall often say in what follows that J.l is the measure associated with the solution u of(P).

The properties of dujdt

We know that the injection M 1 (0, T) ~ H-1 (0, T) is compact. As J.l;. converges vaguely to J.l in M 1 (0, T; H) ~ (M 1 (0, T)t, J.l;.. converges strongly to J.l in H-1 (0, T; H) ;;:: (H-1 (0, T)r, and therefore du du . d/ -> dt strongly m L 2 (0, T; H).

As /du;./dt/ :s;; E, for all t and A., (du;./dt)-> (dujdt) in ll(O, T; H), for all p E [1, oo). On the other hand, as d 2 ujdt 2 is a measure, du/dt has right and left limits in every point of (0, T), a right limit in 0, and a left limit in T, and we can write

Energy conservation

It is clear that d- IT dt u = U 1 + 0 f(s) ds -JL([O, T)) d+u IT dt = u 1 + 0 f(s) ds -JL([O, T]).
because u;.-J;.u;.-> 0 in C 0 ([0, T]; H) and (u;.-J;.u;)j).. ....... Jl in M 1 ([0, T]; H). On the other hand, (iu;.-J;,ul)!).. is bounded in L 00 (0, T). Thus, (iu;.-J;,u;.I 2 )/A. converges to 0 in L 00 (0, T) weak*. As cl>;,(u;) converges to a certain x, cf>(J;,u)-cf>;.(u;) -lu,_ + J;,u;.I 2 /(2A) has the same limit in L 00 (0, T) weak*. We have the inequality IJcf>(u)-cf>(J;.u;.))dt ~ (JL;.,u-J;.u) asJL;.(t)eocf>{J;.u 4 (t))forte[O, T].

Passing to the limit:

I: (cf>(u) -x) dt ~ 0. But: lim cf>(J;.u;.) ~ cf>(u).
This implies x ~ cf>(u), thus proving that x = cf>(u).

If JL({t 0 }) = 0, we see from (9) that lim cf> ;,(u;.(t 0 )) = lim cf>(u;.(t 0 )) = t lu 1 1 2 + cf>(u 0 ) + I' (u(s)f(s)) ds;

;,--.o ;,-o Jo hence:

tlu(t)il + cf>(u(t)) = tlu 1 1 2 + cf>(u 0 ) +I (u(s),f(s)
) ds, almost everywhere on [0, T].

Initial conditions

It is quite clear that u(O) = u 0 .

To finish the proof, we need only consider the interpretation (13), (14

) of Jl. In fact, N(t) = ot/J Ko(u(t)). If d + u/dt(O) # ul' then Jls = (-u 1 + d + u/dt(O)) c5 0 + fl.

Part (b)

The case when uo E int Ko is quite simple. So we make the hypothesis Uo E oKo. The idea of the proof is to compare u;. with the solution v;. of (15)

d 2 v d/ + (ot/Jc);. (v;,-u 0 ) = 0 V;,(O) = u 0 dv;, dt = ul Notice that ot/Jc;.(x) = (x-Pcx)/A.; v;_ is given explicitly by v;_(t) = u 0 + tPc u 1 + .JX sin(t/.JX) (u 1 -Pcu 1 ) v;_(t) = u 0 + tPcu 1 + (t-n.JX)(u 1 -Pcu 1 ) ifO ~ t ~ n.JX if t ~ n.JX
We can check these formulas using the fact that the decomposition of an arbitrary element of H into the sum of its projections onto C and C_j_ = N is unique. This result is given in ref. [START_REF] Zarantonello | Contributions to Nonlinear Functional Analysis[END_REF], Lemma 2.2. Knowing that (Ct/1 ct is Lipschitzian, we can see that V;_ is the solution of (15). Let us show now that 8¢). is locally near (ot/1);_ in an adequate sense.

PROPOSITION I. If¢ is Lipschitzian in a neighbourhood of u 0 , there exists positive p and A. 0 such that, for Jx-u 0 / ~pandA.~ A. 0 :

(16) (ot/l);_(x)-of/>;_(x) = h(x-u 0 )/A + A;_(x)
where: h(x-u 0 ) = PK/x)-Pc(x-u 0 ); /h(x)/ ~ Jx/F.(Jxi) and 8(r) decreases to zero as r goes to zero; As e is arbitrary, we obtain x(x) = ({>(x). We can extend this equality to all of the domain of({>, by continuity. Let us show that xis Lipschitzian: let x and x' be given in H; we have

h(x) = 0 on K 0 -u 0 /A;_(x)J ~ k Proof. 1. Let ¢ be Lipschitzian over dom ¢ n BJUJ with Lipschitz constant k. Then dom ¢ n BJUJ is closed: in fact, if (x.).,
X(X') -X(X) ~ ({>(y~) + (z~, X' -y~) + & -({>(y~, X -y~) = (z~, x' -x) + e ~ k/x' -x/ + e,
if t: is arbitrary andy: and z: are chosen adequately. We can bound from below x(x')x(x) by the same type of argument, and thus we have shown that lx(x') -x(x)l ~ kjx' + xl-

Decomposition of 4).

Denote by ift the indicator function of dom 4) = K.

Obviously 4) = "' + X; then by Theorem 23.8 of ref. [START_REF] Rockafellar | Convex Analysis[END_REF], al/)(x) = ox(x) + oift(x) for all X in K.

We have z .. + Aol/t(z;.) + AY;. 3 x where 9;. E OX(z_.) and is thus bounded by k;

z'-=(I+ Aoift)-1 (x-Ag..). !at,b .. (x)-Bl/t;.(x)l =l[x -•(I+ },oift)-1 (x-Ag;.)-x +(I+ Aoift)-1 x]I/A = 1/A I<I + Aoift)-1 (X-Ag)-(I+ AOI/t)-1 xl ~ IY .. I ~ k.
Lemma 4.6. of Zarantonello [START_REF] Zarantonello | Contributions to Nonlinear Functional Analysis[END_REF] allows us to write:

PR(x + u 0 ) = u 0 + P eX + h(x) with jh(x)j ~ lxis(!xl) and h(x) = 0 if x E K -uo- Then !oiftix)-(oiftc);.(x-u 0 )j = !Pc(x-u 0 ) -PR(x-u 0 )1/A ~ s(jx-u 0 l) jx-u 0 j.

Comparison of ocf>._ and at,&._

The sequence (I+ Aoc/>)-1 converges to PKox when A goes to zero; but (J + Aoc/>)-1 is a contraction; this convergence is therefore uniform on compact sets. So, there exists a function j of pandA, decreasing to zero as A~ 0, such that j(J + Aoc/>)-1 x-P Koxl ~)(A, p) on the ball BP(u 0 ), and in an analogous fashion

j(I + Aot,b)-1 x-PRxl ~ ](A,p)
on the ball BP(u 0 ).

Clearly, PdB/u 0 )) c B/u 0 ) PR(BP(u 0 )) c BP(u 0 ) Vp > 0 Vp > 0.
Take p = u/2, and choose A 0 so small that max (j(A 0 , uj2),](A 0 , u/2)) < u/2.

Then !<I + Aocp)-1 x -u 0 ! < u, and I<I + Aot,b)-1 x -u 0 ! < u iflxl < uj2. Let y = (I + ).ocf>)-1 x andy = (I + Aot,b)-1 x.
We know that cf>lo,.(uoJ = ¢1o,.(uor

Therefore (1/A)(x-y, v) + cf>(y + v)-cf>(y) ~ 0 (1/A)(x -y, v) + c/)(y + v) -c/)(Y) ~ o VvEH VvEH.
If we add these two inequalities, taking v = yy, and v = -v, we obtain y = y. This achieves the proof of Proposition 1. This completes the proof of Theorem 1.

COUNTEREXAMPLES TO WELLPOSEDNESS

3.a Discontinuity

The idea of this counterexample is quite simple.

Take H = R 2 , K = {(xl' x 2 ): x 1 ~ 0, x 1 + x 2 ~ 0}, ¢ = ljlk, f = 0; take as initial data u~ = (1 -h,! + h), u~ = ( -1, -!)
where I hi < !• It is easy to check that the solutions are unique.

If h = 0, according to part (b) of Theorem 1, the solution is

u 0 (t) = (I -t, !O -t)) if t ~ I if t > 1.
If h > 0, the solution is

if t ~ I
and it has a unique reflection at timet = 1 on the side

x 1 + x 2 = 0 of K. Then uh(t) = (t(t -1) -h, t -1 + h) if t > 1.
If h < 0, the solution has a first reflection at timet = 1 + 2h; then uh(t) = (-3h -(t -1 -2h), (t -1 -2h)/2) until the time 1 + 4h, when it has a second reflection, after which

uh(t) = ( -1t + 1 -h, t -1 + h).
As h tends to zero, remaining negative, uh tends to ii 0 defined by

ii 0 (t) = (1 + t, 10 -t)) if t ~ I ii 0 (t) = (-1{t-l),t-1) ift >I.
We can see now that, as a function of h, uh is right-but not left-continuous.

b. N onuniqueness

Two examples will be given, both of them with

<P = 1/J K" {i). Take H = R, K = R+, </J = 1/JK, u 0 = U 1 = 0.
x,

We seek an infinitely differentiable nonpositive f which gives us two solutions. The first solution will be formed of an infinite number of arches, smaller and smaller as t gets nearer to 0 (see figure below). The associated measure Jl. will then be atomic. The second solution will be u = 0, Jl. =f More precisely, let p E g?(R) be an even, nonnegative function, the support of which is included in [ -1, + 1], and satisfying JRp(x) dx = 1. Denote p,(x) = p(x/s). Let Y, From now on we fix an e, and write Y, = y, y 1 = J~ y(s) ds and y 2 = g y(s)(1 + s) ds. Obviously

y 1 = 2y 2 •
We look for anf defined on each interval [a,., a,._ 1 ] as follows:f = 0 on [a,., a,. + a,.]

( t -a -a) f(t) = -11,.Y "
" on [a,.+ a,., a,.+ r,.] =[a,.+ a,.,a,._J.

r,. -a,.
f is coo except perhaps in 0, if it is defined.

We have necessarily

u = f on [a,., a,._ 1 ] u(a,.) = u(a,._ 1 ) = 0 d+u d-u lfwewrite dt(a,.) = v,. then dt(a,._ 1 ) = -v,._ 1 •
Our aim is now to look for necessary conditions which will insure thatfhas a meaning and is coo, and u has a meaning and is a solution of (P). n + 1 11. = 12~ (n-4)! and a.= n(n-2)(n-3)' For u to be a solution of (P), we have only to check that

1 I ,u({a.}) = 2 I v. = 2 I 1 24 v 4 < + oo n~4 n~4
n;;?!:4n.

L r. = L n + 1 n + 1 < + oo. n,H nHn(n-2)(n-3)n-1
Then a 4 < + oo and we can choose T = a 4 .

For fto be C"' up to zero we need

1 .v1
rtnl{mii'n~1 r.)' ~ (n-4)! (Cn)P Tyl < + 00 V p;

thus, we obtain the supplementary information thatj<Pl(O) = 0, V pEN. Clearly 0 with associated measure {1 = fis a solution. Thus we have built an infinitely differentiable/ such that (P) has two solutions.

(ii) Take H = R 2 ,f = 0. We intend to build a convex set K of cao boundary, such that with an initial velocity tangent to the boundary, we obtain two different solutions; one "along" the boundary, the other having an infinity of reflexions on it. We shall use the results and notations of the preceding paragraph. Let us define a continuous parametrized curve with values inC~ R 2 as follows: This curve will be continuously differentiable if

e' n 1 -i -(a) = e' n+ 1 1 -i -(a) . •p ( d + u ) •p ( d-u ) dt n dt n
Then, necessarily Pn -Pn+ 1 = 2 arctan vn. As vn = 24v 4 /n!, the series L Pn converges. Moreover, if we choose v 4 small enough, I Pn < <n/2, which means that t ~---+ nF(t) will have no tangent n=4 parallel to the imaginary axis. We have F"(t) = ei<tJ"-" 12 lf(t) on [an, an_ 1 ]. Butfis constructed in such a way that j<Pl(an) = 0 for all p ?: 0, n ?: 4. Therefore F is C"' on [0, TYMoreover, the sign of the curvature of F((O, T]) is the sign of fr 1 F 2 -fr 2 F 1 , where

F = F 1 + iF 2 .
We can easily check that f 1 F 2 -F 2 F 1 =f(t) ?: 0. We can thus see that

F([O, T]) is the boundary of a con vex set K of C ~ R 2 •
Take now initial conditions u 0 = 0, u 0 = a > U, and define a function r/la on [0, T] by

1 I' r/JJt) = ~ Jo IF( a) Ida.
Let <Pa be the reciprocal of r/la.

Then v(t) = F(<fta(t)) is a solution of(P) on [0, r/J 0 (T)].

In fact, v(t) E K, for all t E [0, r/la(T)].

d 2 v d • . dt2 = a dt [F(<f>a(t))/jF(<f>a(t))j].
As F(a) =I 0, for all a E [0, T], d 2 ujdt 2 is a bounded function which can be identified with a bounded measure. On the other hand, it is clear that d 2 v/dt 2 is normal to iJK, (dv/dt)is continuous at every point, jdv/dtj =a and the initial conditions are satisfied. Therefore u is a solution of(P) in the sense of Definition 1.

The other solution will be given by Clearly, v (t) E K for all t. We have

d +- v "(J -(a /a)= ae' n dt n d-- _v (a /a) = a eifJn+' dt n [ an an-1] on -, -- a a d2iJ .
dt 2 = 0 1ft E (an, an-J Therefore It is easy to check, using the interpretation of the measure associated with a solution of (P), (13), (14), that v is a solution of (P); clearly, the energy is conserved, and the initial conditions are satisfied.

Comments on this part. These results are closely connected with results on the propagation of singularities of a hyperbolic problem on a manifold with boundary. The first one obviously refers to diffraction in an angle. The second one was figured out by thinking of a tennis player who succeeds in making his ball bounce higher and higher, from a rest position, only by hitting it downwards. Professor L. Amerio told me that he had built an analogous example. The third type of counterexample is given, with a different construction by M. E. Taylor in his paper [START_REF] Taylor | [END_REF] concerning reflection of singularities of wave equations in an exterior domain of RN. When the complement of this domain is not convex, Taylor's theorem fails as there appear phenomena of non uniqueness of the wave front set. I cannot see, presently, how all these results could be taken in account together in reasonable mathematical theory. is in the interior of fi'K(u(t)). The local uniqueness is then clear. The only difficult case is when u(t) E oK, and ((d-u/dt (t)), n(u(t))) = 0. We need the following result.

LEMMA 2. If oK is of class C 3 and its gaussian curvature is strictly positive, then there exists no sequence of points of oK, (um)meN converging to U 00 , such that um is a reflexion point for all m, i.e. I um -um-1 I um -um-1 1 I um + 1 -um I I um + 1 -um I such that um+ 1 -um has a limit direction, and such that L lum+ 1 -uml < + OC.

Let us show that this lemma implies local uniqueness. With Uo E oK, (n(u(to)), (d-u/dt)(to)) = 0, then necessarily ((d+ u/dt) (t 0 ), n(u(t 0 ))) = 0. Suppose that there is no right neighbourhood of t 0 such that u(t) belongs tooK in all this neighbourhood. Then we can find a t 1 , arbitrarily near t 0 , such that u(t 1 )¢oK. There must exist at most a finite number of reflections between t 0 and t 1 , in order to satisfy Lemma 2. Then ((d + u/dt(t 0 )),n(u(t 0 ))) < 0 and we obtain a contradiction. Therefore there exists an '1 > 0 such that u(t) E oK for to ~ t ~ to + '1•

  Take H = R, K = R +, ¢ = 1/J the indicator function of K, i.e. ¢(x) = + oo ifx¢K ¢(x) = 0 ifxeK Then o¢(x) = {0} ifx > 0 o¢(x) = (-oo; OJ ifx = 0 o¢(x) = 0 if X< 0.

Fig.!.

  Fig.!.

  (9) ~Ju;.(t>Jl + cp;.(u;_(t)) = ~Jul + ¢;,(u 0 ) +I~ (u;,(s),f(s)) ds from which follows the inequality

  ) E N(t) /J-1../ -almost everywhere on [0, T].

  , and the conclusion of Part (a) of Theorem 1 holds.

Fig. 2 .

 2 Fig. 2.

  = ll•Jl, 1 _, 121 * p, 12 with e < 1• Clearly Y, = I on [s, I -s], supp Y, c: [0, I], andY, is coo. It is an easy exen:ise to check that 2 I Y,(s)(Is) ds -I Y,(s) ds = 0.

uFig. 3 .

 3 Fig. 3.

  which gives us u(t) = v,.(t -a.) on [a,., a,. + a,.] u(t) = v,.(t-a,.) -11. J:"+"" y(s)(t + s)ds on [a,.+ n,.,a,._ 1], v,.r,. = 11,.Yz(<,.a,.)2 v,. + v,.-1 = 11nY1(r,.a,.). Let vn-1 = O!,.V,.. Choose 0!,. = n for n ~ 4. This implies v 4 (n 2 -1)4! 12v 4 n 2 -1 11,.11,. = 2y1 n! = ~-~• Take v 4

4 .

 4 A UNIQUENESS THEOREM IN A PARTICULAR CASE THEOREM 2. Let <P = lj; K' f = 0. Assume that the boundary iJK of the closed convex set K is of class C 3 , and that its gaussian curvature is strictly positive. Then the problem (P) admits a unique solution on [0, + oo] in the sense of Definition 1. Moreover, if the initial data u 0 is given on oK and u1 is tangent to oK, then u runs along the geodesic of oK passing through Uo and tangent to u 1 with the speed lu 1 1. lfthe initial data are not such, then u is never tangent tooK, and it has a finite number of reflections in a finite time.Proof Denote by fl' K(u) the tangent cone to K at u, i.e . .?/ K(u) = v r(Ku) and by n(u) the T>O exterior unit normal to K at u. Remark that fi'K(u) = {v: (v, n(u)) ;:,: 0} for all u E oK.

l

  (um -um_ 1 , n(um)) (um -um+ 1 , n(um)) d ~T---=--=---,,=-= an lumum-11 lum-um+11 um-um-1 (um-um_l'n(um))n(um) = um+1-um -(um+1-um,n(um))n(um)

  be the center of a closed ball of radius p, contained in the interior of dom tj>. By general theorems, we may suppose that t/> is bounded on a + BP by a constant C.

	(11) We may therefore extract a new subsequence, still denoted by u;., such that ilc/J;.(u;.)-> J.l vaguely J: /ilcfJ;.(u;.(t))/ dt :s;; C' independent of A.. tiu_.(t)!l ~ tlutl 2 + t/>(uo) + !JIL2(0,T;H)(f~ !u_.(s)jldsy
	in M 1 ([0, T]; H), the set of bounded measures on [0, T] with values in H. In the sense of distribu-tions, d 2 u/dt 2 + J.l = f, which is precisely (3). ~tlutl 2 + t/>(uo) + ti!IL2co, T;HJ ( 1 + f~ lu_.(s)jl ds) If v is an arbitrary element of C 0 ([0, T]; H),
	by the relation x ~ (1 + x 2 )/2. Gronwall's lemma implies:	lim c/J ;.(v(t)) = c/J(v(t)). ;.-o
	t/>,.(u,.(t)) + ltu,~.(t)jl ~ (tlutl Let v be such that c/J(v)EI!(O, T). Then c/J(v;.) is also in L 1 (0, T). We have 2 + t/>(uo) + tlf!L'(O,T;H})exp(Tiflv,o.T;Hl) Set (10) (12) I: (c/J;.(v(t))-c/J;.(u;.(t))) dt ~I: (ilc/J;.(u;.(t)), v(t)-u;.(t)) dt.
	It is clear that the right-hand side tends to
			(J.I., v-u)
	as A. goes to infinity. We have	lim I: cP;.(u;.(t)) ~I: c/J;.(u;.(t)) dt :s;; I: c/J(u(t)) dt.
	Hence, taking the upper limit in (12), we get I: (c/J(v(t)) -c/J(u(t))) dt ~ (J.I., v -u), i.e. (4)
				For an arbitrary con-
	tinuous z such that jz(t)j ~ 1 for all t in [0, T], we may write
	(8tf> .. (u(t)), a + z(t) -u(t)) ~ tf> .. (a + pz(t)) -t/>J.(u,~.(t)).
	Integrating from 0 to T, we have p J: (otf>..(uit)),z(t))dt ~ CT + J: e:~.<-f,a-u,~.)dt ~
	( ~CT+ d;,a-u;. du	0 ) IT IT I du 12 IT 0 0 + dr" dt+	(f,a-u;)dt
	If we choose
	we obtain the estimate

We may therefore extract a subsequence, still denoted by u,~., such that

u_. -+ u in C 0 ([0, T]; H) strong du du. _,~. _.. -m L 00 (0 T: H) weak* dt dt ' ' t/>._(u)-"X in L 00 (0,

T)weak*. Astj>;.(u;) ~ E,!u_.-J_.u .. l ~ JTI.Eandtf>(J .. u_.) ~E. Wehave E ~ \i!}ttf>(JJ.u;.(t)) ~ tf>(u(t)) and u(t) e dom tj>, for all tin [0, T]. Hence we obtain (1) and (2). 2. Main estimate Let a

  is a sequence of points of dom ¢ n BJUJ converging

	to X	00	, we have	¢(x) ~ J~n; ¢(x.

) ~ J~n; (k/x.-xP/ + f/>(xp)) = f/>(xP) + Jx-xP/' which shows that x E dom ¢. 2. Lipschitzian extension of ¢/ 8 "<•ol' Denote by ({> the convex function equal to ¢ in dom ¢ u BJUJ and + w elsewhere. Obviously ({> is lower semicontinuous. Define a convex function x by X(X) = SUp{({>(y) + (z, X -y): y E int dom ({>and Z E o({>(y)}.

In fact xis a Lipschitzian extension of ({>Jdam.P: x(x) is never infinite, thanks to the relation x(x) ~ ({>(y) + k/x -yJ (clearly a({> is bounded by k on int dom ({>). If x E dom ({>, x(x) ~ ({>(x). On the other hand, given 8 > 0, there exists a Y, E int dom ({> and a z, E o({>(y,) such that X(X) ~ ({>(y.) + (z,, X -y.) + 8. Therefore x(x) ~ ({>(x) + 8.

  it were not the case, we could find a sequence v. with Pv. converging to u 0 , and a strictly positive number '1o such that(v.-PKovn, ill)~ '1o lutllv.-PKovJWe can see that (v. + Pv.)!iv. + Pv.l converges to a certain w, which must be inN, and therefore, we obtain a contradiction. We may assume 17(b) to be an increasing function of <5, such that

	(17)	iu;.(t)-v;_(t)l ~ ch J-x( k ~ + £ ;;). e(Et))
	(18)	Et lu;.(t)-v;.(t)i ~ kt + Ue(Et) + ;:ch .JI k 31 +• 4 !). e(Et). 2 1 t ( t 3 Et 4 )
	Proof Define a transformation Y;_ on CO([ 0, T] ; H) by IPKov-uol ~ b implies (v-PKov, ul) ~ '7(<5) lull
	Write now Then u;. satisfies (u ;.(t), u 1 ) = (u;.(ny'l), u 1 ) + (u ;.(ny'l), u 1 ) (t -ny'I) + ( f_,:r (f(s) -A ;.u ;.(s))(t -s) ds, u 1 ) (T;.w)(t) = Uo + tul +I (f(s)-o<f>)w(s)))(t-s)ds.
		T;.u;. = u;.. -ft _([u .. (s)-PK 0 u;.(s)],u 1 )(t-s)ds
		7ty'.l.
		t312 +lflu !1 +k--17(Et) t2 ~A) 2	ft 1ty'X	(l/A.)Iu;.(s)-PKou;.(s)llu 1 l(t-s)ds
	From Proposition 1, and the estimate (11), we have:
	Therefore
	and finally we obtain the estimate (17). The estimate (18) is a straightforward consequence of (17), thanks to the relation lti;.(t)-v).(t)l ~ r i(ot/JJ,(v;.(t))-o<f>;.(v.~.(t)l dt + r io<t>;.(v;.(t))-o<f>.~.(u.~.(t))i dt.
	End of proof of Theorem I, part b.

LEMMA I. u;. and v;. satisfy the inequalities: Estimate r;w -r;w by a standard recurrence argument: i(T;.w-T;.(w)(t)l ~ ~~~~wwllco([o.toll

Then

As we know that r;w converges to u;. as n ~ oo, for any initial w, and on any compact time interval, we may write Take w = v;. defined by (15).

(~v).v;.)(t) = Uo + tul -I: o<f>;.(v .. (s))(ts) ds-Uo -tul + L(ot/Jc);.(v_.(s))(ts) ds.

If we assume t 0 ~ p/E and). ~ ). 0 , we may apply the conclusions of Proposition I for x = v;.(t).

Denote ii 1 = 2P cU 1 -u 1 . Clearly, ii 1 is an element of C. Let us notice that, for any given 11 > 0, there exists a b(17

) > 0 such that, if IPKovu 0 1 ~ b(17), then (v-PK 0 v,ii 1 ) ~ 11lii 1 llv-PKovl.

If ~ (u;.(ny'I), u 1 ) + (u .. (ny'I), u 1 )(t + ny'I) J: (1/A.)Iu;.(s) -P Kou;.(s)l ds ~ C' + kT. We obtain, in the limit as A.-+ 0 (u(t) -U 0 , U 1 ) ~ lu 1 l 2 t -o(t), from Where (d;tu(O),al) ~ lutl 2 •

On the other hand, as a result of

(6)

, and of the fact that¢ is continuous in a neighbourhood of u 0 Conclusion (8) is now clear.

  Let us first prove the local uniqueness at every point t. If u(t) e int K, or if u(t) e oK and (d-ujdt) (t) is the interior of fi'K(u(t)), the local uniqueness is immediate. If u(t) E oK, and d-ujdt (t) ¢ fi'K(u(t)), then

	and
	d+u -dt	d-u (t) --dt	(t) = kn(u(t))
	according to Theorem 1.
	Necessarily the vector

l d+u I ~d-u I dt(t) = dt(t). d + u d-u (d-u ) dt (t) = dt (t) -2 dt (t), n(u(t)) n(u(t))

Let fl be the measure associated with u, and define a real valued measure (fl, z) with z E C 0 ([0, T]; H) by ((fl, z), <P > = (fl, z <P > V </1 E C 0 ([0, T]). Lets = (w -(w, n(u))n(u)) x with wE H, and X E C 0 ([0, T]), supp x c: [t 0 , t 0 + 17]. It is clear that s(t) E fl K(u(t)), and sis universally integrable on [0, T]. According to the interpretation of Jl, (13) and ( 14), necessarily (fl, s> = 0.

So

If we set v = (pj(to.to+>~l' n(u)), we may then identify pj(to,to+ nl and n(u)v. Suppose u(t 0 ) = 0, which does not restrict the generality, and denote n(t 0 ) = n 0 , uN = -(u, n 0 ), u' = u -(u, n 0 )n 0 . Represent oK in a neighbourhood of 0 as follows:

Herejis convex, twice continuously differentiable, and Df(O) = 0. We differentiate the relation uN(t) = j(u'(t)) on [t 0 , t 0 + ' JJ.

dt ts contmuous, as dt = dt , dtdt = kn(u (1or a certam real k , and

We now differentiate (19) in the sense of distributions:

Therefore, v can be identified with a function and

This is precisely the equation of the geodesics of oK. As oK is of class C 3 , we know there is uniqueness. By a classical argument, local uniqueness implies global uniqueness.

To complete the proof of Theorem 2, we need only to establish Lemma 2.

Proof of Lemma 2. Suppose there. exists a sequence um E oK such that as m-+ w,

In a neighbourhood U of uoo we have the representations of oK given by

where fm is of class C 3 and Dfm(O) = 0 ;fm is convex.

Obviously (21)

On the other hand,

with fm(Pm(um-1 -um))

The function h does not depend on m; lim h(r) = 0, and h is increasing r~o From ( 21) and ( 22) we obtain:

Since we have assumed that the gaussian curvature of oK at U 00 is strictly positive, "m ;;:=: K 0 > 0 form large enough. Dividing both sides of (23) by IP m(um_ 1 -urn) I we obtain Ko/IP m(Um+l-u'")l_ t/ ~ IIPm(um+l-um)l_ t/ h(IPm(um+l-um)l) IPm(um-1-u,.)l IP'"(um-1-u'")l + h(IP'"(urn-1-u'")l) + h(IP'"(um+l-u'")i).

If we choose m 0 such that On the other hand we have Therefore P m(um-tu'") -f'"(P '"(um-t -u'")) n(u'") = um-1u'".

So we have a constant K such that (25) and analogously

From ( 24), ( 25) and (26) we obtain

Since lm converges to 0, we can find an arbitrarily large m 0 such that lm ~ lmo' for all m ~ m 0 . Then Therefore It is clear that we can choose m 0 so large that the right hand side of this inequality is arbitrarily large. We obtain therefore a contradiction, as um+ 1 -um is supposed to have a limit direction when m tends to infinity. This completes the proof of Theorem 2.

The main results of this paper have been stated in ref. [6].


Maurice Clerc
email: maurice.clerc@writeme.com

Total Memory Optimiser: Proof of concept and compromises

published or not. The documents may come

Motivations

Today (2016-03) all iterative optimisers do forget some positions they have previously sampled in the search space, sooner or later, even a method like Tabu Search [START_REF] Glover | [END_REF]]. This is a lost of information about the "shape" of the landscape of the problem at hand. An obvious drawback is that the same position may be sampled and evaluated several times, which is useless. In order to prevent this undesirable behaviour, the classical algorithms progressively define "bad areas" in which the probability to be sampled is null or extremely small.

On the one hand, there is a risk to be wrong by doing that, but, on the other hand, there is no doubt that most of these methods are efficient in practice on many problems. We claim here that it is because for these problems a "Nearer is Better in probability" assumption is valid.

But what if it is not true? In such a case, it may be useful to make use of an algorithm that takes into account all the information that is collected during the iterative search.

Nearer is Better assumption

The NisB assumption has been studied in [Clerc(2007)] and [Clerc(2015)]. Let us just give here a short definition and a few examples.

Definition

What we call here the NisB correlation can be estimated as follows:

• sample at random (uniform distribution) N times three positions and sort them so that f (x) 1 ≤ f (x) 2 ≤ f (x 3 );

• let n isB be the number of times we have f (x) 1 ≤ f (x) 2 < f (x 3 ) and distance(x 1 , x 2 ) < distance(x 1 , x 3 ).

• then the correlation is defined so that it is in [-1, 1] by

ρ = -1 + 2 n isB N (1)

Examples

For a strictly monotonic function, the NisB correlation is of course equal to 1.

For most usual problems it is positive. However, as we can see in the table 1 it can easily be negative, as soon as there are some plateaus1 . The precise definitions of these four problems are in the Appendix. Also, if it is not equal to 1, it means that it is sometimes locally negative. For example, for the Parabola of the figure 1 the global correlation is 17/18 = 0.944, not equal to 1 because of triplets of points "around" the minimum.

Actually, it may be interesting to evaluate the correlation as a function of the vicinity. Here, we define this vicinity as a proportion of the search space around each point. So, the global correlation is given for a vicinity equal to 1. As intuitively expected, the smaller the vicinity, the higher the correlation, but not a lot, and not even always (see the Flash example).

Basic Total Memory Optimiser

We now define a Total Memory Optimiser, just a basic one for the moment, in the hope it can outperform usual methods on deceptive problems, i.e. the ones with negative NisB correlation. At first glance, according to the figure 3, the components of this algorithm seem quite classical. However, by examining them in details we will see some important specific features.

Initialisation (first samples)

At the very beginning we know nothing, except the search space. It is then easy to prove that the first point to sample must be the centre of this search space, in order to minimise the risk to be wrong (see the Appendix).

For the other points, we have to anticipate a bit the next step, which is triangulation. We want that the triangulation is able to cover the whole search space, so that, in principle, any point may be then sampled. As the search space is supposed to be a convex polyhedron, a sure way to do that is to sample all the corners. In practice the search space is a D-rectangle (which can easily be transformed into a D-square, in order to later simplify strategies like "search around"). So, finally, the number of initial points is 2 D + 1.

Of course, it increases very rapidly with D, and it may be unacceptable for small computers. But for the moment, to describe this basic TMO, we do not care. We will see later some possible compromises.

Cycle: From Sampling to Triangulation

At a given time step we have sampled N points. We will explain in the next step that the surrogate function is made of "triangular" facets (interval for D = 1, real triangles for D = 2, tetrahedron for D = 3, etc.), whose projections on the search space are of course also "triangles". In order to have no overlapping of these "triangles" an elegant way is to define a Delaunay's triangulation between the N points. Actually, this is a simplified variant of the approach described in [ [START_REF] Beyhaghi | Delaunay-based derivative-free optimization via global surrogates, part I: linear constraints[END_REF].

The figure 5 shows two such triangulations, coming from the Alpine problem that is described in the Appendix.

Again, this method is very costly when the dimension increases, again we do not care for the moment, and, again, there are some possible cheaper compromises.

Cycle: From Triangulation to Surrogate function

Using surrogate functions is not at all new. See for example [START_REF] Han | [END_REF]]. However, here, we modify it after each new sampling and, moreover, we want to use the best one under as few hypotheses as possible. Indeed, most "aesthetic" surrogate functions do suppose some superfluous properties like differentiability everywhere, at least implicitly.

To simplify the reasoning, let us consider a 1D problem whose value space is [y min , y max ], two sampled points x 1 , x 2 , and their values f (x 1 ), f (x 2 ). We do not know the values of f between the two points, and we want to estimate them by using the surrogate function g that minimises the risk to be wrong, i.e. the risk to sample x with g (x) = f (x). We must have g(x 1 ) = f (x 1 ) and g(x 2 ) = f (x 2 ), but for any other point x in ]x 1 , x 2 [ we just know that we must have y min ≤ g(x) ≤ y max . If we do not make any hypothesis, it is easy to prove that the best g is given by g(x) = ymin+ymax 2 (see the figure 6a and the Appendix). This is not satisfying for this plateau function does not increase the quantity of information (even if only guessed) we can use.

So, we do make a hypothesis. Here, it is that the NisB correlation between the two points is locally positive2 . It implies that g must be strictly monotonic. But there is still an infinity of possible functions (figure 6b). So, we also apply the Occam's razor, or, more formally, we assume that the variability (see the Appendix for a formal definition) of the function must be minimal. Then, the only possible function is the linear one. More generally, on D dimensions problems, the surrogate function is made of "triangular" facets (see figures 6c and 6d).

Cycle: From Surrogate function to Estimation of Distribution

This step is of course crucial. TMO is stochastic, and therefore it has to make use of an estimation of distribution, as all stochastic methods do, either implicitly or explicitly. Here, it is explicitly. Let us consider the surrogate function of the figure 6c. It contains all the information collected during the iteration: the sure one (sampled points), and the probable one (interpolations). Let us suppose first the problem is a maximisation. The high values of the surrogate function tell us where probably are the high values of the true function. So, it seems reasonable (still because the local NisB principle) to more probably sample "around" the points of high value, and conversely less probably "around" the points of low value.

It means that the probability distribution should have the same "shape" as the surrogate function (see figure 7a). And in case of minimisation, this is the contrary: it should have an opposite shape (see figure 7b).

So, we have a straight way to define the estimation of distribution: just transforming the surrogate function into a probability distribution, either directly, or by taking its opposite (in practice by applying a formula like minimum + maximum -g).

Note that it is perfectly possible to "distort" the distribution thanks to a userdefined morphing parameter, either optimistic or pessimistic (see the Appendix). To keep the presentation simple, we will not do that in the examples.

Cycle: From Estimation of Distribution to Sampling

This step is a classical one. Moreover, as the distribution is entirely defined by the sampled points, it is technically easy. In order to improve the efficiency of TMO, we also make use of "representatives" of the triangular facets. A representative can for example be:

1. the centre of the facet; In what follows, we simply use the method 1 (see the figure 8). We virtually put all the values (of the sure points and of the representatives) along a line, side by side, draw at random a number (uniform distribution) between 0 and their sum, and go back to the corresponding value.

If it is a representative, we indeed sample this new point. If it is an already known point x 1 ,we sample "around" it. In practice, the search space has been normalised as a D-square (if D ≥ 2), and "around" means "inside a small Dsquare centred on the known point". If D = 1, we of course just consider intervals.

In the examples, "small" is defined as follows:

• find the nearest known point x 2 ;

• the edge of the D-square is 2α x 1 -x 2 , where α is a user-defined parameter.

In the examples of this paper α = 1 3 . Note that instead of using the g(x) values it is perfectly possible to sort them and to use their ranks. Actually some experiments suggest that it may be a better way, and this is what is done here.

Compromises

As soon as the dimension of the problem increases, it is clear that the computing cost becomes rapidly unacceptable in practice, as we can see on the figure 9.

So it is useful to study some compromises. An easy first one is to replace the initial set of 2 D + 1 positions by a smaller one. Keeping the centre of the search space is costless, but for the other initial points we may for example:

• sample at random N points (a very usual method, in fact);

• sample at random N points and C corners (typically C = 1).

It means that the "covering" of the search space by triangulation is now just a partial one, but if we launch several runs, we hope that the solution will be inside a triangle, and has a non null probability to be found. Actually, it is the way classical optimisers do work.

The complete Delaunay's re-triangulation after each new sampled point is a costly process. We can replace it by a local re-triangulation. A very simple one is shown on the figure 10. We just subdivide the "triangle" in which is the new point.

Comparisons

We can now make some comparisons between TMO (basic and some variants with compromises) and a few classical optimisers. For fair comparisons, we have to carefully specify two things: • the budget;

• the user's demand.

Budget

A budget for iterative optimisation on a computer has at least three components:

• a maximum number of evaluations E;

• a maximum computing time T ;

• a maximum memory size M .

In this paper, we want to check how efficient is TMO in taking into account all the information collected during the iterative process. So, for comparisons, we will just use the same E for several methods. Actually, this is a classical approach.

Demand

Many studies take as comparison criterion the mean result over n runs, or the median value, and perform statistical analyses to estimate in which extend such values are reliable. But in practice a user does not care of means or medians. His/her question is (in case of minimisation): "With this budget and this algorithm, what is the probability to get a result smaller than ε ".

It is out of the scope of this paper to analyse in details how to spend a given budget. We just apply here the classical method: n independent runs of E/n evaluations. But keep in mind this is far to always be the best way.

To answer the user's question, we need to estimate the probability distribution of the results. In practice, it means we need to build an estimation of the PDF (Probability distribution function) or, easier to use, an estimation of the CDF (Cumulative Distribution Function). By doing that, when comparing two algorithms A 1 and A 2 , it often happens that the CDF curves have at least one cross point, for a given result ε * . Let us suppose CDF(A 1 ) is "above" CDF(A 2 ) for results smaller than ε * , and the contrary for higher values. If the user is very demanding (i.e. does accept only values smaller than ε max ≤ ε * , then A 1 is the best choice. But if the user accepts values smaller than ε max > ε * , then, on the contrary, A 2 is the best choice.

Some results

We first compare a few TMO variants, with some compromises, and the basic TMO. As we will see, some variants may be better than this basic TMO. But to better highlight the specificity of TMO, i.e. its efficiency on problems of negative global NisB correlation, we will compare then three classical methods only to the basic TMO.

TMO variants

On the figure 12, "init 2" is for the initialisation method of the basic TMO (centre + corners), and "init 0" is for centre + random initialisation (here with 89 positions). And "reTriang k " means Delaunay's re-triangulation every k new positions, local simplified re-triangulation else. In particular "reTriang Inf " means Delaunay's triangulation just once, after initialisation, and then only the simplified method is used. The figure 11 shows that the computing time is easily then far smaller.

Moreover, at least for problem with a positive NisB correlation like Alpine, not only complete and systematic re-triangulation is not necessary, but partial ones may give better results: higher probability for small values, as we can see on the figure 12.

When the NisB correlation is negative, as for the Brush function, we have something similar. On the figure 13 the three curves with "init 0" are better than the ones with "init 2". Note that, though, we are here in a case where the number of corners is far smaller than the number of random initial points. The conclusion may not be valid for dimension greater than 6. Unfortunately, the laptop used for this study can not cope with Delaunay's triangulations in dimension 7 or greater.

So, we now consider only the basic TMO for comparisons with classical methods, i.e "init 2, reTriang 1".

TMO vs others

The figure 14 represents the CDFs of four methods on the Alpine function. As said, the first one is the basic TMO, and the other ones are GA-MPC 3 , CMA-ES Figure 12: Alpine, TMO variants, 100 runs of 150 evaluations, PDFs curves.

[ Hansen(2009)] , and APS 11. GA-MPC [START_REF] Elsayed | GA with a New Multi-Parent Crossover for Solving IEEE-CEC2011 Competition Problems[END_REF] was the winner of the CEC 2011 competition, CMA-ES the winner of the CEC 2005 competition (in fact, we used a more recent and better version 3.62, downloaded from https://www.lri.fr/~hansen/cmaes_inmatlab.html). For APS [START_REF] Omran | [END_REF]], a well-documented MATLAB © implementation can be downloaded from http://aps-optim.info. It easily outperforms both GA-MPC and on the CEC 2011 problems, but the point here is that TMO is clearly the worst method on Alpine, unless results greater than 0.4 are acceptable: in that case it outperforms CMA-ES (but still not the other ones).

The conclusions are different on a very deceptive function like Brush (see the figure 15). Now TMO is the best choice as soon as we accept only good (small) results. Note that on such a problem CMA-ES is particularly bad. This is probably because it assumes more than the other methods that the NisB assumption holds, and is also more biased, as we can see on the signatures (see the Appendix).

When and how using TMO?

In this study we have given a precise definition of "deceptive problems", by saying there are the ones for which the global NisB correlation is negative. However, in the field of optimisation, "deceptive" usually just means "very difficult". In particular, combinatorial problems a often said to be defective.

Preliminary tests show that for many combinatorial problems, if not all, the NisB correlation is positive. Of course, this is done by using a specific distance, for example the Kendall tau one's, or, in a more intuitive way, the minimum number of transpositions to transform a given "position" (typically a On the one hand, we have said that TMO is for problems with negative NisB correlation, so it is probably not a good tool for combinatorial problems. On the other hand, for these problems, as the correlation is just slightly positive it may be nevertheless worth trying to apply it.

Also, TMO could be combined with a classical iterative algorithm A, by using the following strategy:

• compute the NisB correlation after each new evaluation;

• if positive, use A;

• if negative, use TMO.

Again, nothing proves it will work, but, again, it seems worth trying.

If it appears that TMO, either alone or in combination, indeed gives good results on some real world problems, it will be necessary to increase its computational efficiency. We already have seen a few possible ways, but more are possible, and should be tested. (2) with x d,δ = x d -δd. In this case, we have simply chosen δ = 1. This parameter serves to ensure that the minimum is not at the center of the search space or on a diagonal. The problem is multimodal and non-separable.

Deceptive 1 (Flash)

The search space is [0, 1]. Function f is defined as:

           x ≤ 2c 1 → f (x) = c 2 2c1 < x ≤ 3c 1 → f (x) = c 2 -c2 c1 (x -2c 1 ) 3c 1 < x ≤ 4c 1 → f (x) = 2c2 c1 (x -3c 1 ) 4c 1 < x ≤ 5c 1 → f (x) = 2c 2 -c2 c1 (x -4c 1 ) x ≥ 5c 1 → f (x) = c 2       (3)
with, in this case, c 1 = 0.1 and c 2 = 0.5. The problem is unimodal, but with plateaus.

Deceptive 2 (Comb)

The search space is [0, 10]. Function f is defined as:

Figure 15: Brush, TMO vs others, 100 runs of 150 evaluations, CDFs curves. On this "negative" NisB problem, TMO is the best method to find good results (smaller than 0.2), but for higher acceptable results, APS11 and even GA-MPC are better. For any demand, CMA-ES is largely the worst.

f (x) = min c 2 , 1 + sin (c 1 x) + x c 1 (4)
with, in this case, c 1 = 10 andc 2 = 1. The problem is multimodal, but with plateaus.

Deceptive 3 (Brush)

The search space is [0, 10] 2 . Function f is defined as:

f (x 1 , x 2 ) = min c 2 , 2 d=1 |x d sin (x d )| + x d c1 (5)
with, in this case, c 1 = 10 and c 2 = 1. The problem is multimodal and nonseparable.

When we know nothing, the middle is the best choice

On the search space Let x * be the solution point (we do suppose here it is unique). If we sample x, the error is x -x * . At the very beginning, as we know nothing, the probability distribution of x * is uniform on the search space. Roughly speaking, it can be anywhere with the same probability. So, we have the sample x in order to minimise the risk given by

r = x * ∈S x -x * (6)
Let us solve it for D = 1, and S = [x min , x max ]. We have

r = ´x u=xmin (x -u) du + ´xmax u=x (u -x) du = xu -u 2 2 x u=xmin + u 2 2 -xu xmax u=x = x 2 -(x max + x min ) x + x 2 max +x 2 min 2
And the minimum of this parabola is given by

x = x max + x min 2
For D > 1 the proof is technically more complicated, but the result is the same: the less risky first point is the centre of the search space.

On the value space

The same reasoning can be applied to the value space, when we do not make any hypothesis like say a positive local NisB correlation. On any unknown position of the search space the distribution of the possible values on [y min , y max ] is uniform and therefore the less risky is, again, the middle, i.e. ymax+ymin 2 .

Variability of a landscape

We use here a specific definition, which is different from the definition of variance in probability theory. Let f be a numerical function on the search space S. What we call variability on a subspace s of S is the quantity

v = ŝ4 f (x 2 ) -f (x 1 ) x 2 -x 1 - f (x 3 ) -f (x 1 ) x 3 -x 1 (7)
where {x 1 , x 2 , x 3 } is an element of s 3 = s ⊗ s ⊗ s (Euclidean product), under the constraint x 3 = x 1 + λ (x 2 -x 1 ) or, equivalently, (x 2 -x 1 ) × (x 3 -x 2 ) = 0 (cross product). The definition may seem to be complicated, but it just means that in any direction the slope of the landscape is constantly the same.

Morphing an estimation of distribution

There are many possible ways to "distort" a given distribution. In this study we use one based on a simple user-defined numerical parameter. The principle (in case of minimisation) is to temporarily increase/decrease the good (small) Figure 16: Distortions of a list of values, in case of minimisation. When morph<1, good (small) values are temporarily increased, and the contrary for morph>1.

The figure 16 shows how the values are temporarily distorted in two cases: optimistic (morph=0.5), when the user thinks that the process can safely be more greedy, or, on the contrary, cautious (morph=1.5), when the user thinks there is a risk of premature convergence.

The figures 17 present two examples of modified probability distributions We are in the case of minimisation, and the original distribution is the one of the figure 7b.

Signatures

The concept of signature of an optimiser is presented in [Clerc(2015)]. Basically, a signature is a 2D plot of 10,000 points. To generate them we consider the Impossible Plateau problem defined by f (x) = 1 on [0, 1] 2 . We run 10 times the algorithm, letting it generate 1000 points each time, and we plot all these points on the same figure. For stochastic algorithms two signatures may be different but nevertheless similar, like handwritten personal signatures.

Thanks to this approach, some biases can be detected. The most common ones are a bias in favour of the centre of the search space, and a bias in favour of the borders. Also if the plot seems to be not very dense, it means that many points are (almost) on the same position: they are quasi-duplicates. Note that this last property does not necessarily mean that the algorithm is not efficient. It may just mean that it is able to refine its search "around" a given position (what is often called "exploitation").

On the contrary, centre bias and border bias are often drawbacks, for they mean than some areas may be not well explored. The figure 18 presents the signatures of four methods, including TMO. From this point of view, the worst is CMA-ES, but TMO (at least the basic one) is also slightly concerned by these defaults.

Figure 1 :

 1 Figure 1: When Nearer is Worse, locally. However, globally, the correlation is positive.

Figure 2 :

 2 Figure 2: NisB correlation vs Vicinity.

Figure 3 :

 3 Figure 3: Basic Total Memory Optimiser.

Figure 4 :

 4 Figure 4: Initialisation: centre + corners.

Figure 5 :

 5 Figure 5: Delaunay's triangulations (Alpine problem, solution point on (1, 2)).

  (a) No hypothesis. The best surrogate function is a plateau. (b) NisB correlation locally positive, and minimal variability.

  (c) Piece-wise linear surrogate function (1D). (d) Piece-wise linear surrogate function (2D).

Figure 6 :

 6 Figure 6: Choosing the "best" surrogate function. Without any hypothesis, it is a plateau. With the locally positive NisB correlation hypothesis, it is monotonic. And with the minimum variability constraint, it is a piece-wise linear one.

Figure 7 :

 7 Figure 7: Estimations of distribution, derived from the surrogate function of the figure 6c.

  2. a weighted gravity centre (weights depending on the values of the vertices); 3. a random point inside the facet.

Figure 8 :

 8 Figure 8: Sampling from the estimation of distribution.

Figure 9 :

 9 Figure 9: Alpine function. Computing time vs dimension.

Figure 10 :

 10 Figure 10: Simplifying the re-triangulation.

Figure 11 :

 11 Figure 11: Using simplified retriangulation dramatically reduces the computing time (Alpine, 150 evaluations).

Figure 13 :

 13 Figure 13: Brush, TMO variants, 100 runs of 150 evaluations, PDFs curves.

Figure 14 :

 14 Figure 14: Alpine, TMO vs others, 100 runs of 150 evaluations, CDFs curves.On this "positive" NisB problem, TMO is the worst method, unless the user is not very demanding, accepting results greater than 0.4. In that case, CMA-ES is the worst.

Figure 17 :

 17 Figure 17: Morphing an estimation of distribution.

Table 1 :

 1

	Name	Representation	ρ
	Alpine		0.36
	Flash		-0.57
	Comb		-0.73
	Brush		-0.95

Examples of Nearer is Better correlation.

This is an open question: is it possible to define a lipschitzian function without any plateau but with a negative NisB correlation?

It may seems contradictory with the fact that we want to cope with problems for which the NisB correlation is globally negative. Even in such a case, it is sometimes locally positive, and more and more when the number of points increases.

We would like to thank Dr. Saber Elsayed for providing the MATLAB © code of GA-MPC.

Appendix

Problem definitions

Alpine

For dimension D, the search space is [0, 4D] D . Function f is defined as:

values, in order to increase/decrease the probability to be selected by a uniform random choice.

A safe way to present it is to give a code. Here is a possible MATLAB © one.

function