Quentin Berger
email: quentin.berger@sorbonne-universite.fr

Niccol Ò Torri
email: niccolo.torri@sorbonne-universite.fr

BEYOND HAMMERSLEY'S LAST-PASSAGE PERCOLATION: A DISCUSSION ON POSSIBLE LOCAL AND GLOBAL CONSTRAINTS

Keywords: Last-passage percolation, non-directed polymers. 2010 Mathematics Subject Classification: 60K35, 82B44

Hammersley's Last-Passage Percolation (LPP), also known as Ulam's problem, is a well-studied model that can be described as follows: consider m points chosen uniformly and independently in r0, 1s 2 , then what is the maximal number Lm of points that can be collected by an up-right path? We introduce here a generalization of this standard LPP, in order to allow for more general constraints than the up-right condition (a 1-Lipschitz condition after rotation by 45 ˝). We focus more specifically on two cases: (i) when the constraint is a γ-Hölder (local) condition, we call it H-LPP; (ii) when the constraint is a path-entropy (global) condition, we call it E-LPP. These generalizations also allows us to deal with non-directed LPP. We develop motivations for directed and non-directed constrained LPP, and we give the correct order of Lm in a general manner.

Introduction

In this introduction, we recall the original Hammersley LPP problem, and we show how to generalize this process by enlarging the set of paths allowed to collect points, by changing the increasing constraint, to a more general compatibility condition. We point out that the condition in the Hammersley's LPP is local, the constraint depending only on two consecutive points. Conversely, a global condition is a constraint that takes in account the whole path trajectory that collects points.

In Section 2, we introduce some specific constraints of interest (local and global) in the directed setting and we derive the correct order for the corresponding LPP problems. In Section 3, we consider a non-directed LPP and we also derive its correct order. In Section 4, we present some contexts where our generalized LPP can be useful-it has already proven useful in [START_REF] Berger | Directed polymers in heavy-tail random environment[END_REF]. We conclude the paper by presenting some simulations, and discuss some conjectures, see Appendix A.

1.1. Hammersley's Last Passage Percolation. Let us take m points independently as uniform random variables in the square r0, 1s 2 , and denote the coordinates of these points Z 1 :" pt 1 , x 1 q, Z 2 :" pt 2 , x 2 q, etc... We say that a sequence pz i q 1ď ďk is increasing if t i ą t i ´1 and x i ą x i ´1 for any 1 ď ď k (we set by convention i 0 " 0 and z 0 " p0, 0q).

Then, the question is to study the length of the longest increasing sequence among the m points which is equivalent to the length of the longest increasing subsequence of a random (uniform) permutation of length m. We denote: L m :" sup k ; D pi 1 , . . . , i k q s.t. pZ i q 1ď ďk is increasing ( .

Using sub-additive techniques, Hammersley [START_REF] Hammersley | A few seedlings of research[END_REF] first proved that m ´1{2 L m converges a.s. and in L 1 to some constant, that was believed to be 2. Further works then proven that the constant was indeed 2 [START_REF] Logan | A variational problem for random young tableaux[END_REF][START_REF] Vershik | Asymptotics of the plancherel measure of the symmetric group and the limiting form of young tables[END_REF]. Moreover, and quite remarkably, this model has been shown to be exactly solvable by Baik, Deift and Johansson [START_REF] Baik | On the ditribution of the longest increasing subsequence of random permutations[END_REF], and they identified the fluctuations of L m around 2 ? m, showing that the model is in the so-called KPZ universality class. More precisely, in [START_REF] Baik | On the ditribution of the longest increasing subsequence of random permutations[END_REF] the authors showed the following result.

Theorem. The recentered and renormalized quantity m ´1{6 pL m ´2? mq converges in distribution to the Tracy-Widom GUE distribution. Moreover, Johansson [START_REF] Johansson | Transversal fluctuations for increasing subsequences on the plane[END_REF] proved that the typical transversal fluctuations of a path collecting the maximal number of points is of order m ´1{6 . (In [START_REF] Johansson | Transversal fluctuations for increasing subsequences on the plane[END_REF] Johansson actually considers up-right paths going from p0, 0q to pN, N q in a Poisson Point process of intensity 1: he shows that the typical transversal fluctuations away from the diagonal of a path collecting the maximal number of points is of order N 2{3 .) We also mention that in [START_REF] Deuschel | Limiting curves for i.i.d. records[END_REF], the case when the points are not chosen uniformly in r0, 1s 2 but have some given density ppx, yq has also been solved: the limiting constant lim nÑ8 L m { ? m and the limiting curve are identified.

1.2. General definition of path-constrained Last Passage Percolation. We now perform a 45 degree clockwise rotation, and generalize Hammersley's LPP by introducing a general constraint on paths (that can be either local or global ): we introduce it via a notion of compatibility of the points that can be collected. We need three ingredients: ' a domain Λ; ' a (finite or countable) random set of points Υ Ă Λ, whose elements are denoted by Z i " pt i , x i q, its law is denoted P; ' a compatibility condition, i.e. a set C of compatible subsets of Λ. Then, we define the C-compatible Last-Passage Percolation as the maximal number of Ccompatible points in Υ, that is ) .

Remark 1.1. This fits the definition of Hammersley's LPP as defined above: the compatibility set C being the set of all increasing subsets of r0, 1s 2 . After a rotation by 45 ˝, we end up with the domain Λ :" px, yq, 0 ă x ă ? 2, |y| ď minp1, 1 ´tq ( , and Υ " Υ m a set of m independent uniform random variables in Λ. The compatibility set is then taken to be (with the convention pt 0 , x 0 q " p0, 0q)

C " ď kě0 ! ∆ " tpt i , x i qu 1ďiďk ; 0 ă t 1 ă ¨¨¨ă t k ă ? 2, |x i ´xi´1 | |t i ´ti´1 | ď 1 for all 1 ď i ď k ) ,
which corresponds to sets of points that can be collected via a 1-Lipschitz function.

Now, there are at least two reasonable ways of defining the compatibility condition: (i) by replacing the Lipschitz condition by a Hölder constraint; (ii) by considering a path-entropy constraint (a global constraint on the path), that also allows to deal with non-directed paths. We restrict ourselves to the case of the dimension d " 2 for the simplicity of the exposition, but it can easily be extended to the case of higher dimensions.

Several other constraints can be (and have been) considered, and let us mention a few. For instance the constraint that the path is convex has been studied in [START_REF] Ambrus | Longest convex chains[END_REF], and is related to the question of counting the number of lattice convex shapes, see [START_REF] Bárány | The limit shape of convex lattice polygons[END_REF][START_REF] Ya | A probabilistic approach to the analysis of the statistics of convex polygonal lines[END_REF][START_REF] Vershnik | The limit form of convex integral polygons and related problems[END_REF] and more recently in [START_REF] Bureaux | On the number of lattice convex chains[END_REF]. The question of pattern-avoiding permutation has also gained some interest recently, see in particular [START_REF] Hoffman | Pattern-avoiding permutations and brownian excursion part i: Shapes and fluctuations[END_REF][START_REF] Madras | Structure of random 312-avoiding permutations[END_REF][START_REF] Miner | The shape of random pattern-avoiding permutations[END_REF].

Directed LPP: Hölder and entropy constraints

In this section, we consider directed paths. We work with a domain Λ t,x " r0, ts r´x, xs, for some (fixed) t, x ą 0. Then, we let m independent r.v. uniform in Λ t,x form the set Υ m . We will use L m as a short notation for L Υm . Moreover, we say that a set ∆ " tpt i , x i qu 1ďiďk Ă R `ˆR is directed if 0 ă t 1 ă ¨¨¨ă t k . We deal first with the (local) Hölder constraint, before we turn to the (global) Entropy constraint.

2.1. Local Hölder constraint. For any γ ě 0, we can define the γ-Hölder norm of a finite set ∆ " pt i , x i q 1ďiďk (in which the points are ordered t 1 ă ¨¨¨ă t k , with the convention pt 0 , x 0 q " p0, 0q)

(2.1) H γ p∆q :" sup 1ďiďk |x i ´xi´1 | |t i ´ti´1 | γ .
Notice that this is not the γ-Hölder norm of the linear interpolation of the points, since (2.1) only considers consecutive points: one can think of this quantity as a local γ-Hölder norm. In particular, the case γ ą 1 is not trivial here, and the case γ " 0 is also of interest.

Then, for some fixed A ą 0, we define a compatibility set (2.2)

H A γ :" ∆ Ă R `ˆR ; ∆ directed, H γ p∆q ď A ( .
The γ-Hölder Last Passage Percolation, abbreviated as H γ -LPP, is defined as

(2.3) L pH A γ q m pΛ t,x q :" sup ! |∆| ; ∆ Ă Υ m , ∆ P H A γ ) .
We prove the following result.

Theorem 2.1. There are constants c 1 , c 2 (depending only on γ, during the course of the proof one finds that c 1 ď cp1 `γq ´1{2 ) such that for any t, x and B, for any 1 ď k ď m

P ´LpH A γ q m pΛ t,x q ě k ¯ď ´c1 At γ m xk 1`γ ¯k , (2.4) P ´LpH A γ q m pΛ t,x q ď k ¯ď exp " c 2 k ´1 ´c2 ´At γ xk γ ^1¯m k ¯* . (2.5)
As a consequence, there is some C ą 0 such that for any fixed t, x, γ, A, P-a.s. there is some m 0 such that

1 C ď L pH A γ q m pΛ t,x q pAt γ {xq 1{p1`γq m 1{p1`γq ď C for all m ě m 0 .
We stress that the constants in (2.4)-(2.5) are uniform in the parameters m, A, t, x: the results are still valid when considering the situation when A, t, x Ñ 8 as m Ñ 8, which is useful for some applications, see [START_REF] Berger | Directed polymers in heavy-tail random environment[END_REF].

We have that L

pH A γ q m " L pH A
γ q m pΛ t,x q is of order m κ , with κ " 1{p1 `γq. Then, it is very natural to expect that L pH A γ q m {m κ converges a.s. to a constant as m Ñ 8: we discuss this convergence in Section 2.3, see in particular Remark 2.6. The value of the constant is discussed in Appendix A.

Remark 2.2. One could naturally generalize Hölder LPP to a cone-shaped LPP: define a region R " tpt, xq P R `ˆR, f 2 ptq ď x ď f 1 ptqu, with f 1 ď f 2 two functions R `Ñ R, and let the compatibility condition for ∆ be that for any pt i´1 , x i´1 q, pt i , x i q P ∆ we have pt i ´ti´1 , x i ´xi´1 q P R (i.e. the next point in ∆ has to be in the cone-shaped region R from the previous point). In this framework, H γ -LPP is simply the cone-shaped LPP with R " tpt, xq, ´tγ ď x ď t γ u, and one could easily adapt the proof of Theorem 2.1: the key quantity is V puq " ş u 0 |f 1 ´f2 |pvqdv, the area of R close to the origin, and one finds that L m is of the order of V ´1p1{mq (recovering the m 1{p1`γq in the Hölder case).

2.2. Global Entropy constraint. Another type of constraint that is natural to consider is a global constraint: we talk about an entropy constraint, since it arises naturally when considering random walk paths (the entropy being a measure of the non-likelihood of a path). This is a generalization of the study initiated in [START_REF] Berger | Entropy-controlled last-passage percolation[END_REF], which was motivated by applications to directed polymer in random heavy-tail environment and helped answer Conjecture 1.7 in [START_REF] Dey | High temperature limits for p1 `1q-dimensional directed polymer with heavy-tailed disorder[END_REF]. For any a ě b ě 0, a ą 0, we define the pa, bq-Entropy of a set ∆ " pt i , x i q 1ďiďk (again, the points are ordered t 1 ă ¨¨¨ă t k , and we use the convention pt 0 , x 0 q " p0, 0q)

(2.6)
Ent a,b p∆q :"

k ÿ i"1 |x i ´xi´1 | a |t i ´ti´1 | b .
In particular, we are interested in two special subcases. First, when b ą 0 and a " b `1: in that case, we can generalize the notion of entropy to continuous paths s : r0, ts Ñ R, by Ent b psq " ş t 0 |s 1 puq| b du, corresponding to the L b norm of s 1 (it is related to the p1, bq-Sobolev norm of s) and the entropy of a set ∆ corresponds to the entropy of the linear interpolation of ∆. Second, when b " 0: then the entropy can be generalized to non-necessarily continuous paths s : r0, ts Ñ R, by Ent a psq " sup ř i |spt i q ´spt i´1 q| a ( , the supremum being over all finite subdivisions t 1 ă ¨¨¨ă t k of r0, ts. This corresponds to the "a-variation" norm of s (the total variation for a " 1, and the quadratic variation for a " 2).

For fixed B ą 0, we define a compatibility set

(2.7) E B a,b :" ! ∆ Ă R `ˆR ; ∆ directed, Ent a,b p∆q ď B ) ,
so that a set of points ∆ is compatible if it can be collected by a path with entropy smaller than B. The path-Entropy constrained LPP, abbreviated as E-LPP, is then defined as

(2.8) L pE B a,b q m pΛ t,x q :" sup ! |∆| ; ∆ Ă Υ m , ∆ P E B a,b
) .

We prove the following result.

Theorem 2.3. There are constants c 3 , c 4 (depending only on a, b) such that for any t, x and any B, for any

1 ď k ď m P ´LpE B a,b q m pΛ t,x q ě k ¯ď ´c3 pBt b {x a q 1{a m k pa`b`1q{a ¯k , (2.9) P ´LpE B a,b q m pΛ t,x q ď k ¯ď exp " c 4 k ´1 ´c4 ´pBt b {x a q 1{a k pa`bq{a ^1¯m k ¯* . (2.

10)

As a consequence, there is a constant C such that for any fixed t, x, a, b, B, P-a.s. there is some m 0 such that

1 C ď L pE B a,b q m pΛ t,x q pBt b {x a q 1{pa`b`1q m a{pa`b`1q ď C for all m ě m 0 .
Again, the constants are uniform in the different parameters (and explicit, see the proof of Theorem 2.3), and this fact could reveal to be useful, in particular for the problem developed in Section 4.1. Also here,

L pE B a,b q m " L pE B
a,b q m pΛ t,x q is of order m κ with κ " a{pa `b `1q, and it is natural to expect that L pE B a,b q m {m κ converges a.s. to a constant as m Ñ 8. This convergence is discussed in Section 2.3, and the value of the constant in Appendix A. Notice that in the case where a " b `1 (which is one of the most natural, since it arises from LDP of random walks, see Remark 2.4), we find κ " 1{2, exactly as in the case of a Lipschitz constraint. In the case b " 0, we find κ " a{pa `1q so κ " 1{2 when a " 1 (total variation case) and κ " 2{3 when a " 2 (quadratic variation case).

Remark 2.4. The entropy of a set ∆ as defined in (2.6) appears naturally when considering large deviations for random walks: consider S a symmetric random walk with unbounded jumps, with stretch exponential tail PpS 1 " xq xÑ8 " e ´|x| ν , for some ν ą 0 (the case of the usual simple random walk corresponds to taking ν " 8). Then, when considering the probability that a point pn, x n q (with n Ñ 8, x n " ? n) is visited (or collected) by the simple random walk path, we realize that

(2.11) ´log PpS n " x n q nÑ8 " # nIpx n {nq if ν ą 1, or ν P p0, 1q and x n ! n 1{p2´νq , Jpx n q if ν P p0, 1q and x n " n 1{p2´νq ,
with some LDP rate functions Ip¨q, Jp¨q. More specifically, we have Ipxq " x 2 {2 as x Ñ 0 (moderate deviation regime, see [START_REF] Cramér | Sur un nouveau théorème limite de la théorie des probabilités[END_REF] for the standard Cramér case, [START_REF] Nagaev | Integral limit theorems taking into account large deviations when Cramér's condition does not hold[END_REF] for the case ν P p0, 1q), Ipxq " x ν as x Ñ 8 (super-large deviation, see [24, Thm. 2.1]), and Jpxq " x ν (one-jump deviation, see [24, Thm. 2.1]). Hence, the entropy defined in (2.6) is the natural scaling limit of the log-probability that a random walk path visits a given set of points. We chose the specific form (2.6) instead of using general LDP rate functions Ip¨q, Jp¨q because: (i) we are able to perform computations with this formula, (ii) we can usually bound the rate function c|x| a ď Ipxq ď c 1 |x| a for some a ą 0. In (2.11), we therefore have: in the first part a " 2, b " 1 if x n {n Ñ 0 or a " ν, b " ν ´1 (ν ą 1) if x n {n Ñ 8; in the second part, a " ν, b " 0. However we keep the parameters a, b in the definition (2.6), to be able to deal with all these cases at once.

Poissonian (point-to-point) version of path-constrained LPP.

Similarly to the standard LPP, we can define a Poissonian (point-to-point) version of the path constrained LPP, reproducing the idea of Hammersley [START_REF] Hammersley | A few seedlings of research[END_REF] to prove the convergence of L m { ? m. For any λ ą 0, let Υ λ be a Poisson point process of intensity λ on R 2 , and we define the point-to-point version of constrained LPPs. Let us consider z " px, yq P R 2 . For a given set ∆ Ă R ˆp0, yq, we set ∆ pzq " ∆ Y tzu so that it extends ∆ to make it end at z. We consider the domain Λ t " r0, ts ˆR for t ą 0, and for any A ą 0, B ą 0, we define the point-to-point constrained LPP:

L pH A γ q Υ λ ptq " L pH A γ q λ ptq :" sup ! |∆|; ∆ Ă Υ λ X Λ t , ∆ directed, H γ p∆ pt,0q q ď A ) , L pE B a,b q Υ λ ptq " L pE B a,b q λ ptq :" sup ! |∆|; ∆ Ă Υ λ X Λ t , ∆ directed, Ent a,b p∆ pt,0q q ď Bt ) .
Let us note that the entropy constraint grows linearly in t. We realize that in both cases, `LpCq λ pnq ˘ně1 forms a super-additive ergodic sequence, in the sense that (2.12)

L pCq Υ λ pn ` q ě L pCq Υ λ pnq `LpCq θ n Υ λ p q
, where θ n is the translation operator: θ n pt, xq " pt `n, xq. The super-additivity comes from the fact that the concatenation of two sets have: (i) a H γ norm equal to the maximum of the H γ norms of the two sets; (ii) an entropy equal to the sum of the entropies of the two sets. Therefore, Kingman's sub-additive ergodic theorem [START_REF] Kingman | Subadditive ergodic theory[END_REF] implies the existence of the limit lim nÑ8 n ´1L pCq Υ λ pnq. In the following result we show that the limit is finite (and can be taken along the real line).

Proposition 2.5. For any λ ą 0, the limits

(2.13) C H λ,A " lim tÑ8 1 t L pH A γ q λ ptq, C E λ,B " lim tÑ8 1 t L pE B
a,b q λ ptq exist a.s. and in L 1 , and are finite, constant P-a.s. Moreover the constants

C H λ,A and C E λ,B
satisfy the following scaling relations

(2.14) C H λ,A " pλAq 1 1`γ C H 1,1 ; C E λ,B puq " pλB 1{a q a a`b`1 C E 1,1 .
We refer to Appendix A for a discussion on the value of the constants.

Proof. We have already noted that the limit along the integers n Ñ 8 exists. We can extend the limit along the real line t Ñ 8, using that L pCq λ pttuq ď L pCq λ ptq ď L pCq λ prtsq. We now prove that the constants are finite., as a consequence of our Theorems 2.1-2.3. Let us deal only with the Hölder case, and let us set A " 1,λ " 1 for simplicity. The proof is standard but we include it for the sake of completeness. Thanks to (2.16) below, we get that L 1 ptq had the same distribution as L t 1`γ p1q, and to prove that the constant in (2.13) is finite it therefore suffices to show that lim sup ρÑ8 ρ ´1{p1`γq L ρ p1q ă `8 a.s.

First, removing the point-to-point constraint gives that L ρ p1q ď L

pH A γ q
Υρ pΛ 1,8 q, where the latter is the H γ -LPP in the domain Λ 1,8 " r0, 1s ˆR with a set Υ ρ which is a Poisson point process of intensity ρ, see Section 2.1. We cannot directly apply Theorem 2.1 because Λ 1,8 is not bounded and Υ ρ does not have a fixed number of points. However, we can write

L pH A γ q Υρ pΛ 1,8 q " lim jÑ8 L pH A γ q
Υρ pΛ 1,j q with Λ 1,j " r0, 1s ˆr´j, js, so that for any v ą 0

P `LpH A γ q
Υρ pΛ 1,8 q ě vρ 1{p1`γq ˘"

lim jÑ8 P `LpH A γ q
Υρ pΛ 1,j q ě vρ 1{p1`γq ˘.

Then, we denote N pρq j

:" |Υ ρ XΛ 1,j | the number of Poisson points in Λ 1,j : using Theorem 2.1 (with m " 4ρj), we can write

P `LpH A γ q
Υρ pΛ 1,j q ě vρ 1{p1`γq ˘ď P `N pρq j ě 4ρj ˘`P `L4ρj pΛ 1,j q ě vρ 1{p1`γq (2.15)

ď P `N pρq j ě 4ρj ˘`´4 c 1 v 1`γ ¯vρ 1{p1`γq .
The first probability goes to 0 as j Ñ 8 (N pρq j is a Poisson r.v. of parameter 2ρj), so that choosing v 0 " p8c 1 q 1{p1`γq , we obtain that

P `LpH A γ q
Υρ pΛ 1,8 q ě v 0 ρ 1{p1`γq ˘ď 2 ´v0 ρ 1{p1`γq , which concludes the argument.

To show the scaling relation (2.14), we consider two different scaling relations satisfied by

L pH A γ q λ and L pE B a,b q λ
. For this purpose, we start by considering the following maps: (i) pt, xq Þ Ñ pλ 1{p1`γq t, λ γ{p1`γq xq, which does not change the γ-Hölder norm of a set ∆; (ii) pt, xq Þ Ñ pλ a{pa`b`1q t, λ pb`1q{pa`b`1q xq, which multiplies the entropy of a set ∆ (and t) by λ a{pa`b`1q . Therefore, since the image of Υ λ through these maps has the distribution of Υ 1 , we obtain the following identities in distribution (2.16)

L pH A γ q λ ptq pdq " L pH A γ q 1 `λ1{p1`γq t ˘and L pE B a,b q λ pt, tuq pdq " L pE B a,b q 1 `λa{pa`b`1q t ˘.
As a consequence, by using (2.13), we also get the existence of the following limits, for any fixed t ą 0, A, B ą 0

(2.17) lim λÑ8 1 λ 1{p1`γq L pH A γ q λ ptq " tC H 1,A ; lim λÑ8 1 λ a{pa`b`1q L pE B a,b q λ ptq " tC E 1,B .
Note that we recover the same order for L λ as in Theorems 2.1-2.3. From (2.17) we directly obtain that

(2.18) C H λ,A " λ 1{p1`γq C H 1,A , and
C E λ,B " λ a{pa`b`1q C E 1,B .
Applying another scaling, we can also reduce to the case where A " 1, B " 1. We consider the following maps, that preserves the distribution of Υ λ :

(i) pt, xq Þ Ñ pA 1{p1`γq t, A ´1{p1`γq xq, which divides the γ-Hölder norm by A;

(ii) pt, xq Þ Ñ pB 1{pa`b`1q t, B ´1{pa`b`1q xq, which multiplies the entropy by B ´1ˆB 1{pa`b`1q . Then, we obtain that

L pH A γ q λ ptq pdq " L pH 1 γ q λ `A1{p1`γq t ˘and L pE B a,b q λ ptq pdq " L pE 1 a,b q λ `B1{pa`b`1q t ˘.
As a consequence, we have that

(2.19) C H 1,A " A 1{p1`γq C H 1,1 , and
C E 1,B " B 1{pa`b`1q C E 1,1 .
In the end, (2.18), together with (2.19), give (2.14).

Remark 2.6. When considering t " 1 with λ " m, this corresponds to the LPP problem in Λ 1,8 with Υ a Poisson point process of intensity m. In principle, one could use (2.17) (with λ " m), together with a de-Poissonization argument (cf. [START_REF] Hammersley | A few seedlings of research[END_REF]), in order to prove the convergence for the point-to-point version of the H γ -LPP and E-LPP of Sections 2.1-2.2 to the constants in (2.13). However, the argument should fail (and the constants differ) when the transversal fluctuations of the optimal path become too large: indeed, restricting the paths to stay in a box r0, 1s ˆr´1, 1s is then an important constraint.

Non-directed LPP

The notion of compatible-LPP allows for even more general constraints, and for example enables us to deal with non-directed cases. Let us consider a natural framework, as an example: we work with a time horizon r0, ts, and define the Entropy of a subset ∆ " px i q 1ďiďk of R 2 (the points are considered in a given order), by considering the optimal Entropy of a path going through the points of ∆ (in the correct order) in a time horizon t:

Ent a,b pt, ∆q :" inf " k ÿ i"1 }x i ´xi´1 } a |t i ´ti´1 | b ; t 1 ă ¨¨¨ă t k subdivision of r0, ts * , (3.1)
where }¨} denotes the Euclidean norm on R 2 . Another way of presenting it is by saying that Ent a,b pt, ∆q is smaller than A if and only if there exists a path s : r0, ts Ñ R 2 collecting the points of ∆ which has entropy smaller than A. We notice right away that we are able to identify the optimal subdivision 0 ď t 1 ă ¨¨¨ă t k ď t used by a path to collect all points of ∆: the optimal choice is t i ´ti´1 " t}x i ´xi´1 } a{pb`1q `řk i"1 }x i ´xi´1 } a{pb`1q ˘´1 . Then we obtain that the Entropy of ∆ is

(3.2) Ent a,b pt, ∆q " 1 t b ´k ÿ i"1 }x i ´xi´1 } a{pb`1q ¯b`1 .
Here again, the case b ą 0 with a " b `1 will be of particular interest for us, since it arises naturally from a LDP for non-directed random walks to visit a certain set of points. In the case a " b `1, the optimal choice for the subdivision is to take t i ´ti´1 proportional to the distance between the points, and (3.2) corresponds to the pb `1q-th power of the length of the linear interpolation of the points of ∆-it can then easily be extended to continuous curves s : r0, ts Ñ R 2 . The case b " 0 also arises when considering random walks with increments with a stretch-exponential tail, and correspond to the a-variation norm of a curve s : r0, ts Ñ R.

We will work with the domain Λ r " tx P R 2 , }x} ď ru, for r ą 0 (this choice is not crucial). For m ě 1, we let Υ m be a set of m independent variables uniform in Λ r . For some fixed B ą 0, the non-directed Entropy compatible sets with time horizon r0, ts is defined by

E t,B a,b " ∆ Ă R 2 ; Ent a,b pt, ∆q ď B ( ,
and finally the non-directed LPP is

(3.3) L pE t,B a,b q m pΛ r q :" sup ! |∆| ; ∆ Ă Υ m , ∆ P E B a,b ptq
) .

(We use a curly font for L and E to visually mark the difference with the directed LPPs.)

We prove the following result, for non-directed LPP.

Theorem 3.1. There exist constants c 5 , c 6 such that for any t, r and B, for any 1 ď k ď m

P ´L pE t,B
a,b q m pΛ r q ě k ¯ď ´c5 pBt b {r a q 2{a m k 2pb`1q{a ¯k , (3.4)

P ´L pE t,B
a,b q m pΛ r q ď k ¯ď e ´c6 m `exp

" c 6 k ´1 ´c6 m a{2pb`1q k `Bt b {r a ˘1{pb`1q ¯* . (3.5)
Finally, there is some C ą 0 such that P-a.s. there is some m 0 such that

(3.6) 1 C ď L pE t,B a,b q m pΛ r q m ^pBt b {r a q 1 b`1 m a 2pb`1q ď C
for all m ě m 0 .

We have that L m is of order m κ with κ " a 2pb`1q ^1: we also expect that L m {m κ converges a.s. to a constant as m Ñ 8. Let us highlight the fact that we find κ " 1{2 (as for the standard LPP) in the case a " b `1.

Remark 3.2. We stress that we could have defined a corresponding non-directed γ-Hölder-LPP, the analogous of (3.2) ending up being

H γ pt, ∆q " 1 t γ ´k ÿ i"1 }x i ´xi´1 } 1{γ ¯γ .
It is very similar to (3.2), with γ " pb `1q{a (possibly changing the constants t, B): one finds that the corresponding non-directed LPP L m is of order m κ with κ " 1 2γ ^1 (hence κ " 1{2 for a Lipschitz constraint, as in the original Hammersley LPP).

Some applications of the (entropy) constrained LPP

Our main goal has been to introduce a generalized LPP, and the results we stated give the first properties of such models, which are already useful in some contexts-it has proven useful in [START_REF] Berger | Directed polymers in heavy-tail random environment[END_REF]. We now present briefly two applications of the directed and non-directed LPPs, to the context of polymer models. We define here a very natural variational problem, which encapsulate the energy-entropy competition inherent to models of polymers in random environment. The random environment is given by a Poisson point process Υ λ on R `ˆR of intensity λ ą 0 (its law is denoted P), and for β ą 0, we define the following (point to point) variational problem (4.1)

Z λ,β ptq :" sup s:r0,tsÑR,sp0q"sptq"0

! β ˇˇs X Υ λ ˇˇ´Entpsq ) ,
with Entpsq defined as in (2.6)-because Υ λ is countable, Entpsq is well-defined. This variational problem constitute a simplified model to study the energy-entropy competition of polymer models, |sXΥ λ | being viewed as a measure of the energy of a trajectory s Again, the central cases that we have in mind is when a " b `1 or b " 0 in the definition of the entropy (2.6), see Remark 2.4 (when the entropy derives from the LDP of a simple random walk, we have a " 2, b " 1). The idea of this model is similar to that of [START_REF] Comets | Localization transition for polymers in poissonian medium[END_REF] which considers a Brownian polymer in Poissonian medium. However, here, we only consider trajectories maximizing the energy-entropy balance, and we also allow for more general entropy than that of the Brownian motion (for which a " 2, b " 1). Let us stress that the variational problem (4.1) has already appeared in [START_REF] Bakhtin | Space-time stationary solutions for the Burgers equation[END_REF] (in the case a " 2, b " 1) as a solution for a Hamilton-Jacobi equation used to study the stationary solutions of a Burgers equation (with a forcing induced by the points of a PPP). It has proven to be useful for the study of the thermodynamic limit for directed polymers, cf. [START_REF] Bakhtin | Thermodynamic limit for directed polymers and stationary solutions for the Burgers equation[END_REF].

First of all, we notice that Z λ,β ptq is a super-additive ergodic sequence, so that Kingman's sub-additive ergodic theorem gives that the limit (4.2) f pλ, βq :" lim tÑ8 1 t Z λ,β ptq exists a.s. and in L 1 , and is P-a.s. constant. The fact that f pλ, βq is finite derives from our estimates in Theorem 2.3 (together with the argument in Section 2.3, see (2.15)), so we skip it-we mention that this fact was an important part of the study in [START_REF] Bakhtin | Space-time stationary solutions for the Burgers equation[END_REF]. We also have scaling relations for Z λ,β ptq. Indeed, consider the two following maps: (i) pt, xq Þ Ñ pλ ´a{pa`bq t, λ ´b{pa`bq xq whose image of Υ λ has distribution Υ 1 and which preserves the entropy; (ii) pt, xq Þ Ñ pβ ´1{pa`bq t, β 1{pa`bq xq, which multiplies the entropy by β, while preserving the distribution of Υ λ . We therefore obtain that

(4.3) Z λ,β ptq pdq " Z 1,β `λ´a{pa`bq t ˘and Z λ,β ptq pdq " βZ λ,1 `β´1{pa`bq t ˘.
A first consequence is that we get that f pλ, βq " pβ a`b`1 λ a q 1{pa`bq f p1, 1q, where f p1, 1q is a constant that needs to be determined. Another consequence is that, if we consider the alternative problem where we take λ Ñ 8 (instead of t Ñ 8), we get that, for any fixed positive t, β, the limit (4.4) lim λÑ`8 1 λ a{pa`bq Z λ,β ptq " tf p1, βq " tβ pa`b`1q{pa`bq f p1, 1q exists a.s. and in L 1 .

For this model, some important questions remain unanswered: (i) what is the value of the constant f p1, 1q? (ii) what does the maximizer of Z λ,β ptq look like? For instance, what is its typical transversal fluctuation exponent? We mention that in [START_REF] Bakhtin | Space-time stationary solutions for the Burgers equation[END_REF][START_REF] Bakhtin | Thermodynamic limit for directed polymers and stationary solutions for the Burgers equation[END_REF], the results are mostly qualitative, such as the existence and coalescence of semi-infinite maximizers for this model.

4.2.

Application II: non-directed polymers in heavy-tail environment. The directed E-LPP have already proved to be useful to understand the transversal fluctuations and scaling limits of directed polymers in heavy-tail random environment, see [START_REF] Berger | Directed polymers in heavy-tail random environment[END_REF]. The continuous limit of the model is found to be an energy-entropy variational problem, and E-LPP appears central to ascertain its well-posedness. Here, we define an analogous variational problem in the non-directed setting, and show that it is well defined. It should also appear as the scaling limit of some non-directed polymer model in heavy-tail random environment.

As a continuum disorder field, we let P :" tpw i , x i , y i q : i ě 1u be a PPP on r0, 8q ˆR2 , of intensity µpdwdxdyq " α 2 w ´α´1 1 twą0u dwdxdy -it derives from the scaling of a discrete field of disorder with heavy-tail distribution, with tail exponent α. For a continuous path s : r0, 1s Ñ R 2 , we can then define its energy by summing the weights in P "collected" by s, πpsq " ř px i ,y i qPs w i . We can also define its length psq " ş 1 0 }s 1 puq}du, and we consider psq ν for some ν ą 1 as a measure of its entropy. Indeed, if s is a linear interpolation of a finite number of points in P, then psq ν is nothing but the non-directed entropy defined in (3.2) with a " b `1 and b `1 " ν. This choice derives from LDP for a random walk, and ν " 2 corresponds to the moderate deviation regime of the simple random walk.

Thanks to the non-directed LPP of Section 3, we are able to show that the energy/entropy variational problem is well defined, when α P p2{ν, 2q. The proof follows exactly the same scheme as that in [7, Section 4], with Proposition 4.1 in place of [START_REF] Berger | Entropy-controlled last-passage percolation[END_REF]Theorem 2.4] so we skip it.

Polymers in random environment have mostly been considered in the directed framework, see [START_REF] Comets | Directed polymers in random environments, 46th Saint-Flour Probability Summer School[END_REF] for a thorough review, or in the semi-directed context of stretched polymers, see [START_REF] Ioffe | Crossing random walks and stretched polymers at weak disorder[END_REF][START_REF] Zygouras | Strong disorder in semidirected random polymers[END_REF], or [START_REF] Ioffe | Stretched polymers in random environment[END_REF] for a review. Proposition 4.1 therefore shows that our generalized LPP can be useful to study non-directed polymers: the variational problem can be thought as an energy/entropy model for a polymer in continuous random environment. The most natural question is now to consider a (discrete) non-directed polymer model in random environment (the Hamiltonian being the sum of the weights of the sites visited by the random walk), and prove its convergence to (4.5), in the case of a heavy-tail environment (as done in [START_REF] Berger | Directed polymers in heavy-tail random environment[END_REF]).

Proofs of the constrained LPP results

We prove here Theorems 2.1-2.3-3.1. The almost sure statements are straightforward applications of the first parts of the theorems (via the Borel-Cantelli lemma), so we skip their proof. We write the details only for the E-LPP, the H-LPP results following exactly the same scheme-for the upper bound, the ideas are similar to those developed in [START_REF] Berger | Entropy-controlled last-passage percolation[END_REF]Part 1], in a special case of the E-LPP. Some more technical details are needed to obtain (3.5).

5.1. Entropy-constrained LPP. We prove first (2.9), and then (2.10).

Upper bound. Define E k pt, Bq the set of k (ordered) elements up to time-horizon t that have an entropy bounded by B:

E k pt, Bq " ! pt i , x i q 1ďiďk ; 0 ă t 1 ă ¨¨¨ă t k ă t, Ent a,b `pt i , x i q 1ďiďk ˘ď B
) .

We are able to compute exactly the volume of E k pt, Bq.

Lemma 5.1. For any t ą 0 and B ą 0, we have for any k ě 1

Vol `Ek pt, Bq ˘" 2 k `1 a ˘k Γp 1 a q k Γ `k a `1˘Γ p a`b a q k Γ `k pa`bq a `1˘ˆB k{a t kpa`bq{a .
In particular, it gives that there exists some constant C " C a,b (during the course of the proof, one finds that C a,b ď cpa `bq ´1{2 ) such that

VolpE k pt, Bqq ď ´CB 1{a t pa`bq{a k pa`b`1q{a ¯k .
Proof. Again, using a decomposition over the left-most point in E k pt, Bq at position pu, yq (by symmetry we can assume y ě 0): it leaves k ´1 points with remaining time horizon t ´u and constraint B ´|y| a u b , we obtain the key induction formula below We give the details of the induction for the sake of completeness, but the proof is a straightforward calculation. First of all, we have for k " 1

VolpE 1 pt, Bqq " 2 ż t u"0 ż pBu b q 1{a y"0 dudy " 2B 1{a ż t 0 u b{a du " 2B 1{a a a `b t pa`bq{a .
For k ě 2, by induction, we have

Vol `Ek pt, Bq ˘" 2 k´1 `1 a ˘k´1 Γp 1 a q k´1 Γ `pk ´1q{a `1˘Γ p a`b a q k´1 Γ `pk ´1q pa`bq a `1ż t u"0 ż pBu b q 1{a y"0 pt ´uq pk´1qpa`bq{a `B ´ya u b ˘pk´1q{a dydu.
Then, by a change of variable z " y a {pBu b q, we get that

ż pBu b q 1{a y"0 `B ´ya u b ˘pk´1q{a dy " B pk´1q{a ż 1 0 p1 ´zq pk´1q{a 1 a z 1{a´1 B 1{a u b{a dz " 1 a A k{a u b{a Γ `pk ´1q{a `1˘Γ p1{aq Γpk{aq .
Moreover, we also have, with a change of variable w " u{t ż t u"0 u b{a pt ´uq pk´1qpa`bq{a du " t pk´1qpa`bq{a`b{a`1 ż 1 0 w b{a p1 ´wq pk´1qpa`bq{a dw " t kpa`bq{a Γ `b{a `1˘Γ`p k ´1qpa `bq{a `1Γ `kpa `bq{a `1˘, and this completes the induction. For the inequality in the second part of the lemma, we use Stirling's formula Γp1 `xq " ? 2πxpx{eq x as x Ñ 8 to control Γ `kpa `bq{a `1˘a nd Γ `k{a `1˘, and we obtain

VolpE k pt, Bqq ď c k a 1{a a pa `bq{a ˆ2 a Γp 1 a qΓp a`b a q ˆB1{a t pa`bq{a `e´1 {a ˘1{a `e´1 pa `bq{a ˘pa`bq{a k 1{a k pa`bq{a ˙k .
Thanks to the asymptotics of Γpαq as α Ñ `8 and α Ñ 0, we find that there is a constant c such that for all a, b

VolpE k pt, Bqq ď a ? a `b ˆcB 1{a t pa`bq{a pa `bq 1{2 k 1{a k pa`bq{a ˙k .
We then use Lemma 5.1 to control the probability that L pE B a,b q m pΛ t,x q is larger than k:

(5.2) P ´LpE B a,b q m pΛ t,x q ě k ¯" PpN k ě 1q ď ErN k s, where N k " Cardt∆ Ă Υ m ; ∆ P E B a,b u is the number of sets of k points in Υ m that are E B
a,b -compatible. Since all the points of Υ m " tZ 1 , . . . , Z m u are exchangeable, we have ErN k s " ˆm k ˙P´D σ P S k s.t. pZ σp1q , . . . , Z σpkq q P E k pt, Bq ¯.

Since the pZ i q 1ďiďm are i.i.d. uniform in Λ t,x " r0, ts ˆr´x, xs (of volume 2tx), we get that

(5.3) ErN k s " ˆm k ˙ˆVol `Ek pt, Bq p2txq k {k! ,
where the k! comes from the fact that we rearrange the Z i 's so that 0 ă t 1 ă ¨¨¨ă t k ă t. Using Lemma 5.1 together with `m k ˘ď m k {k 1 , we therefore obtain that (5.4)

P ´LpE B a,b q m pΛ t,x q ě k ¯ď ˆm k ˙ˆVol `Ek pt, Bq p2txq k {k! ď ˆCB 1{a t pa`bq{a m txk pa`b`1q{a ˙k .
This gives the upper bound (2.9).

Lower bound. For any k ě 1, consider for 1 ď i ď 4k the sub-boxes of Λ t,x

B i :" " pi ´1qt 4k , it 4k
¯ˆ" ´B1{a pt{4q b{a 2k pb`1q{a ^x,

B 1{a pt{4q b{a 2k pb`1q{a ^xı .
Then, notice that if there are at least k boxes among tB 2i u 1ďiď2k containing (at least) one point, then this set of k points has an entropy which is bounded by

k ˆpB 1{a pt{4q b{a k ´pb`1q{a q a pt{4kq b ď B.
Hence, we get that (5.5)

P ´LpE B a,b q m pΛ t,x q ě k ¯ď P ´2k ÿ i"1 1 t|ΥmXB 2i |ě1u ď k ¯" P ´2k ÿ i"1 1 t|ΥmXB 2i |"0u ď k ¯.
For the last probability, we use a union bound and the fact that the 1 t|ΥmXB 2i |"0u are exchangeable, to get that

P ´LpE B a,b q m pΛ t,x q ď k ¯ď ˆ2k k ˙P´Υ m X k ď i"1 B i " H ď 2 2k ´1 ´B1{a t b{a 4 b{a k pa`bq{a x ^1 4 ¯m . (5.6)
In the second inequality we used that Υ m is a set of m independent random variables uniform in Λ t,x (of volume 2tx), and that

Ť k i"1 B i has volume B 1{a pt{4q pa`bq{a k pb`1q{a ^tx 2 .
Therefore, using also that 1 ´x ď e ´x we obtain that (5.7)

P ´LpE B a,b q m pΛ t,x q ď k ¯ď exp " ck ´1 ´c´B1{a t b{a xk pa`bq{a ^1¯m k ¯* ,
which concludes the proof of the (2.10).

5.2.

Hölder-constrained LPP. We only give a brief outline of the proof. Upper bound. We define

H k pt, Aq " ! pt i , x i q 1ďiďk ; 0 ă t 1 ă ¨¨¨ă t k ă t, H γ `pt i , x i q 1ďiďk ˘ď A ) .
Then, as above, we are able to compute exactly the volume of H k pt, Aq: for any t ą 0 and A ą 0, we have for any k ě 1

Vol `Hk pt, Aq ˘" p2Aq k Γp1 `γq k Γ `kp1 `γq `1˘t kp1`γq .

We do not develop the proof, which comes from an induction formula analogous to (5.1):

Vol `Hk pt, Aq ˘" 2

ż t u"0 ż Au γ y"0
Vol `Hk´1 pt ´u, Aq ˘dydu.

As a consequence of Stirling's formula, there exist constants c, C such that

(5.8) VolpH k pt, Aqq ď c ˆ2AΓp1 `γqt 1`γ `p1 `γq{e ˘1`γ k 1`γ ˙k ď ˆCAt 1`γ p1 `γq 1{2 k 1`γ ˙k .
To obtain (2.4), one then follows exactly the same scheme as in (5.2)-(5.4) above, using (5.8) in place of Lemma 5.1. Lower bound. For any k ě 1, we consider for 1 ď i ď 4k the sub-boxes of Λ t,x :

B i :" " pi ´1qt 4k , it 4k
¯ˆ" ´Apt{kq γ 2 ^x, Apt{kq γ 2 ^xı .
Note that, if there are at least k boxes among tB 2i u 1ďiď2k containing (at least) one point, then this set of k points has a γ-Hölder norm which is bounded by Apk{tq γ {pt{kq γ ď A.

Then, we obtain (2.5) exactly as above, see (5.5)-(5.7) above.

5.3.

Non-directed E-LPP. We proceed analogously to the two previous sections, some details differing for the lower bound.

Upper bound. We define

E k pt, Bq " ! ∆ " px i q 1ďiďk ; Ent a,b pt, ∆q ď B ) " ! ∆ " px i q 1ďiďk ; k ÿ i"1 }x i ´xi´1 } a{pb`1q ď D ) ": Ẽk `D˘,
with D " pBt b q 1{pb`1q -we used (3.2) to get the second equality. As above, we are able to obtain its volume: setting γ " pb `1q{a for simplicity, we have for any D ą 0 and any

k ě 1 Vol `Ẽ k pDq ˘" p2πγq k Γp2γq k Γp2kγ `1q D 2kγ .
This is easily proven by iteration, using the recursion formula, for k ě 2

Vol `Ẽ k pDq ˘" ż D γ 0 2πrVol `Ẽ k´1 pD ´r1{γ q ˘dr .

We leave the details to the reader. Then, an easy application of Stirling's formula gives that there exists some constant C such that (5.9) VolpE k pt, Bqq ď ´CpBt b q 2{a k 2pb`1q{a ¯k .

The upper bound (3.4) then comes from the exact same scheme as for (5.2)-(5.4) above, using (5.9) in place of Lemma 5.1.

Lower bound. The idea of the proof is similar to the one in the directed context, with more technicalities due to the non-directedness. We consider a partition of the plane into small squares of side δ :" πr{ ? m: for any x P pδZq 2 we let B x be the square of side δ centered at x. It is easy to see that there are at least m{4 disjoint squares B x (provided that m is large enough) that can be placed into a rectangle (inscribed in Λ r ) ordered as follows: we let x 0 " 0 and then we enumerate x 1 , . . . , x m{4 following a spiral in a clockwise way, in order to have that any two consecutive B x i , B x i`1 are adjacent (see Figure 1).

Note that a square B x has volume π 2 r 2 {m (and recalling Λ r has volume πr 2 ), B x contains at least one point of Υ m with probability 1 ´p1 ´π{mq m ě 1 ´e´π . We define Q m{4 the number of non-empty squares among B x 0 , . . . , B x m{4 , and we define iteratively the indices I j of the non-empty squares, by I 0 " 0 and for 1 ď j ď Q m{4

I j " inf i ą I j´1 ; B x i X Υ m ‰ Hu .
For k ě 1, and if Q m{4 ě k, we may consider a path ∆ collecting one point in exactly all B x I 1 , . . . , B x I k : the entropy of such ∆ is bounded by (see Figure 1)

1 t b ´k ÿ j"1 `4pI j ´Ij´1 qδ ˘a{pb`1q ¯b`1 ď 4 a r a t b m a{2 ´k ÿ j"1 U j ¯b`1 ,
where we set U j :" pI j ´Ij´1 q a{pb`1q . Therefore, for L pE t,B a,b q m pΛ r q to be smaller or equal than k, one needs to have either Q m{4 ă k or that the entropy of ∆ chosen above is larger In the picture we put m " 24 points uniformly on Λr and we consider a rectangle built by 6 " m{4 squares Bx 0 , ¨¨¨, Bx 5 enumerated following a spiral in a clockwise way starting from the origin. Then we consider the non-empty rectangles (in orange) and their indices. In this example we have I1 " 1, I2 " 2, I3 " 5. Finally we draw a path starting from the origin and collecting one point in exactly all BI 1 , ¨¨¨, BI 3 .

than B: this leads to (5.10) P ´L pE t,B a,b q m pΛ r q ď k ¯ď P `Qm{4 ă k ˘`P ´Qm{4 ě k ,

k ÿ j"1 U j ą ´Bt b m a{2 4 a r a ¯1{pb`1q ¯.
For the first term, and for k ď ε 2 m{4 (with ε ą 0 small, fixed in a moment), we realize that Q m{4 ă k implies that there are at least p1 ´ε2 qm{4 empty squares, which gives by a union bound that

P `Qm{4 ă k ˘ď ˆm{4 p1 ´ε2 qm{4 ˙P´Υ m X p1´ε 2 qm{4 ď i"1 B x i " H ¯ď e cεm ´1 ´p1 ´ε2 qπ 4 ¯m .
For the second inequality, we used that the volume of Ť p1´ε 2 qm{4 i"1 B x i is p1 ´ε2 qπ 2 r 2 {4. We note that the constant c ε goes to 0 as ε goes to 0: we can therefore fix ε ą 0 sufficiently small so that (5.11) P `Qm{4 ă k ˘ď e ´πm{8 for all k ď ε 2 m{4.

For the second term in (5.10), let us write V :" k ´1`B t b m a{2 {r a ˘1{pb`1q -we will consider only the case when V is large-, so that we need to bound (5.12)

P ´Qm{4 ď k , k ÿ j"1 U j ą kV ¯ď P `Nk ą εm ˘`P ´Qm{4 ď k , N k ď εm , k ÿ j"1 U j ą kV ¯,
where N k denotes the total number of points in the non-empty squares B x I 1 , . . . , B x I k . We easily have that where the denominator in the first inequality comes from the fact that we work conditionally on the fact that k squares are non-empty (which has probability bounded below by e ´ck ).

Hence, since we work with k ď ε 2 m{4, and provided that ε has been fixed small enough, we get that there is a constant c ą 0 such that PpN k ą εmq ď e ´cm .

For the last part, note that since the squares B x are exchangeable, we can control for 1 ď i 1 ă ¨¨¨ă i k ď m{4

P `I1 " i 1 , . . . , I k " i k ; N k ď εm " ÿ n 1 ,...,n k 1ďn 1 `¨¨¨`n k ďεm ˆm n 1 , . . . , n k ˙´π m ¯n1 `¨¨¨`n k ´1 ´πi k m ¯m´pn 1 `¨¨¨`n k q ď ´1 ´πi k m ¯p1´εqm ÿ n 1 ,...,n k 1ďn 1 `¨¨¨`n k ďεm π n 1 n 1 ! ¨¨¨π n k n k ! ď e ´p1´εqπi k e πk .
Where we used that in order to have I 1 " i 1 , . . . , I k " i k there must be exactly k nonempty squares among the first i k (with n 1 , . . . , n k points in them) and i k ´k empty ones.

The remaining m ´pn 1 `¨¨¨`n k q points must be outside the first i k squares. For the second inequality, we used that n 1 `¨¨¨`n k ď εm, and that the multinomial coefficient is bounded by m n 1 `¨¨¨`n k {pn 1 ! ¨¨¨n k !q. Hence, there is a constant c such that

P `I1 " i 1 , . . . , I k " i k ; N k ď εm ˘ď e ck j " i j ´ij´1 for all 1 ď j ď k ˘,
where pG j q jě1 are i.i.d. geometric random variables, of parameter 1´e ´p1´εqπ . We therefore obtain that, provided that V is large enough

P ´Qm{4 ď k , N k ď εm , k ÿ j"1
U j ą kV ¯ď e ck P ´k ÿ j"1 pG j q a{pb`1q ą kV ¯ď e ´c1 kV .

To conclude, we have obtained that there are constants such that for k ď ε 2 m{4, and for V :" k ´1`B t b m a{2 {r a ˘1{pb`1q large enough, (5.13) P

´L pE t,B
a,b q m pΛ r q ď k ¯ď e ´cm `e´c 1 kV .

One obtains (3.5) by observing that when V is small e ´ckpV ´1q is larger than 1. The statements holds for all k ď m by adjusting the constants.

Appendix A. Further simulations and conjectures

In this appendix, we present some simulations, that help us make some predictions on the values of the constants in (2.13), and support the belief that the model is in the KPZ universality class. We treat only the directed case because in the non-directed case simulations are much more greedy and do not bring any convincing insight-our algorithm could probably be improved, but our goal is simply to hint for some conjectures, and our simulations fill that role perfectly.

A.1. Directed H γ -LPP. For the H γ -LPP, we performed simulations in the Poissonian context of Section 2.3: we work with intensity λ " 1 and constraint A " 1, so we write Lptq for L pH A γ q λ ptq to simplify notations.

(1) Value of the constant. Let us present here the results of our simulations to test the value of the constant C " C 1,1 " lim tÑ8 t ´1Lptq in (2.17). We ran simulations for t " 1000, in the box r0, ts ˆr´t 2{3 , t 2{3 s (with λ " 1 and A " 1).

Our simulations are in accordance with the fact that 1 t Lptq converges a.s. to some constant, whose dependence on γ is presented in Figure 3 (we present the result of only one simulation, but several simulations give values for 1 t Lptq very close to those presented here). In view of the dependence on γ of the constant c 1 in Theorem 2.1 (see in particular (5.8)), a wild guess is that the constant is proportional to p1 `γq ´1Γp1 `γq 1{p1`γq : the dotted grey line in Figure 3 represents the function γ Þ Ñ 2 3{2 1`γ Γp1 `γq 1{p1`γq -the factor 2 3{2 is chosen so that it fits the value ? 2 when γ " 1, corresponding to the standard Lipschitz LPP (the missing factor ? 2 comes from the length of the diagonal in Hammersley's LPP process). The two curves match quite closely, but they seem to disagree when γ " 0 (the constant C 1,1 seems very close to 2.75, whereas 2 3{2 « 2.83).

(2) Convergence of the recentered and renormalized LPP. In order to test the convergence in distribution of t ´1{3 pLptq ´C1,1 tq, we performed 1000 simulations for the point-to-point H γ -LPP with t " 500, for the three values γ " 0, γ " 0.5 and γ " 1.5. The histograms presented in Figure 4 seem to confirm the convergence to a Tracy-Widom distribution, leading to a (far-reaching) conjecture, for the (point-to-point) H γ -LPP.

Conjecture A.1. For every γ ě 0, there exists a constant C γ (equal to 2 3{2 1`γ Γp1`γq 1{p1`γq ?) and a constant c γ such that, for the point-to-point H γ -LPP in Poisson environment with intensity λ " 1 and γ-Hölder constraint A " 1, we have

The histogram presented in

!

  |∆| ; ∆ Ă Υ, ∆ P C

4. 1 .

 1 Application I: a model for a directed polymer in Poissonian environment.

Proposition 4 . 1 . 1 .

 411 For any ν ą 1, the following variational problem is well defined for all β ě 0, when α P p2{ν, 2q, βπpsq ´ psq ν ( .For β ą 0, we have that T pνq β ą 0 a.s. and ErpT pνq β q κ s ă 8 for any κ ă α ´2{ν. Moreover, for any α P p2{ν, 2q, we have the scaling relation T On the other hand, if α P p0, 2{νs, we have that T pνq β " `8 a.s.

ż pBu b q 1{a y" 0

 0 Vol ´Ek´1 pt ´u, B ´ya u b q ¯dydu.

Figure 1 .

 1 Figure 1.In the picture we put m " 24 points uniformly on Λr and we consider a rectangle

P `Nk ą εm ˘ď 1 e ´ck ˆm εm ˙´πk m ¯εm ď e ck pπkq εm pεmq! ,

Figure 2 .

 2 Figure 2. Optimal paths for the Hγ-LPP with t " 1000, for different values of γ. The same set of points is used in all four simulations. For γ " 0 we have here Lptq " 2707, for γ " 0.5 Lptq " 1715, for γ " 1 Lptq " 1408, and for γ " 1.5 Lptq " 1238.

Figure 3 .

 3 Figure 3. Approximated values of the Hγ-LPP constant: the function represents the value of t ´1Lptq with t " 1000, for different values of γ P r0, 3s. The dotted grey line represents the function γ Þ Ñ 2 3{21`γ Γp1 `γq 1{p1`γq , which seems to fit quite well the values of t ´1Lptq.

  (a) γ " 0. (b) γ " 0.5. (c) γ " 2.

Figure 4 .

 4 Figure 4. Histograms of k " 10 3 simulations of the point-to-point Hγ-LPP with t " 500. The three subfigures (a), (b) and (c) correspond to the cases γ " 0, γ " 1{2 and γ " 3{2 respectively. In each case, we superimpose the graph of the Tracy-Widom GUE density, after a recentering by Cγt (with Cγ « 2.75, 1.75, 1.26 from left to right), and a renormalization by cγt 1{3 (with cγ « 2.5, 1.3, 0.65 from left to right).

(A. 1 )

 1 Lptq ´Cγ t c γ t 1{3 pdq Ý Ý Ñ F GU E as t Ñ `8 .A.2. Directed E-LPP. As far as the directed E-LPP is concerned, we also performed simulations in the setting of Section 2.3 with t " 100, with a Poisson intensity λ " 1 and a constraint B " 1. Simulations are much less efficient, and the simulated annealing procedure only gives an approximate (under-estimated) value for Lptq " L pE B a,b q λ pt, 0q.

Figure 5 .

 5 Figure 5. Simulation of Poisson point-to-point E-LPP with t " 100, via a simulated annealing procedure. The plots represents a path which collects a number of points that approximate Lptq, with different parameters a, b. From left to right we have: a " 2, b " 1 (C1,1 « 1.83), a " 4, b " 1 (C1,1 « 1.96), a " 1, b " 0 (C1,1 « 2.08), a " 2, b " 0 (C1,1 « 2.55).

Figure 5 1 t

 51 Figure 5 presents some simulations to test the dependence of the constant C 1,1 " lim tÑ8 1 t Lptq on the parameters a, b. The only conjecture we may risk to formulate (thanks to simulations for others values of a, b that we do not present here) is that the constant should be non-decreasing in a and non-increasing in b. Further conclusions are hard to draw from our simulations.

Figure 6 .

 6 Figure 6. Histogram of 1000 realizations of Lptq for t " 100 (with λ " 1, B " 1), with a " 2, b " 1. We also plotted the graph of the GUE density, centered by Ca,bt with C a,b « 1.89, and rescaled by c a,b t 1{3 with c a,b « 1.4.

Figure 6

 6 makes it natural to conjecture that the Poisson point-to-point E-LPP, when properly recentered and renormalized, converges in distribution to a Tracy-Widom GUE distribution.

N. Torri was supported by a public grant as part of the "Investissements d'Avenir" program (ANR-11-LABX-0020-01 and ANR-10-LABX-0098). Q. Berger acknowledges the support of grant ANR-17-CE40-0032-02. Both authors also acknowledge the support of PEPS grant from CNRS, which led to the development of this work. The authors are also most grateful to N. Zygouras for several discussions on the subject, and in particular for discussing the application presented in Section 4.1.


Piccioni L Cento

Dr Samuel Depraz

socialista di parco nazionale in Europa Centrale? » In

A rather widespread representation has to be fought in western opinion: Central Europe, understood here as the German-Danubian area between the Baltic Sea and the Hungarian Great Plain, and mostly located in the Socialist camp during the second half of the 20 th Century, was neither a distant far East, nor an environmental desert during this whole period of time. Contrasting with the idea of the Socialism as a lagging-behind area in the field of Nature protection, National Parks have been created there during the very same period as in Western Europe, or even before Western Europe in some cases.

 for public policies concerning the environmental field in Central Europe, with common features between neighbouring countries?

An old nature protection policy in Central Europe

), and other Central European areas had established at least nature reserves during the same period.

In Poland, for instance, the first attempts to create a National Park in the Pieniny mountain range date back from 1921, owed to Professor Władysław Szafer, who was then head of the National Commission for the Preservation of Nature (Państwowa Komisja Ochrony Przyrody), created in 1919. A small private protected area (7.5 ha) existed on the very same area, created by Earl Drohojowski around the ruins of an old castle. Polish government launched in 1928 land purchases, while Szafer published in 1929 an essay on "National parks in Poland" to fasten the process. On May, 23 rd of 1932 the Ministry of Agriculture created a "National Park in the Pieniny", on an area of about 7 sq. km (7.36 km²).

The history sounds very much alike for the Bialowieza National Park, which was first established in 1921 as a Forest Reserve, based on an ancient Royal Forest property, and turned into a national park by the 1932 Act.

In the neighbouring Czechoslovakia, a mirror of the polish Pieniny National Park was created in 1933 on the other side of the Pieniny, in order to create an "international landscape park" and to secure the borders, after the common agreement of the Krakow treaty on the same year. Though the purpose of this protected area was less nature protection than border protection, it has been the first opportunity for local researchers to gain some audience and to obtain a first protected area in the country.

A close connexion to western Europe

At this time, the first movements dealing with nature protection in Central Europe were quite significantly connected with western Europe. The training of the elite in Environmental protection, in botany, geology and forestry, had often been completed in western Europe. Those connexions, dating back from the pre-socialist era, lasted also after the socialism outbreak.

For instance, Władiszław Szafer (1886( -1970, Poland), Poland), paleobotanist, geologist and university Professor in Krakow, had studied in Vienna, at the very same time when Hugo Conwentz (1855Conwentz ( -1922)), botanist himself, raised a concern for Nature Protection in Europe at the Congress of Paris (1909) and established the very first public institution dedicated to Nature protection in the German speaking area (Staatliche Stelle für Naturdenkmalpflege, 1906Naturdenkmalpflege, -1910)). The last works of Conwentz about "Nature Protection" (1911) and the efficient action of other German botanists such as Wilhelm Wetekamp (1859Wetekamp ( -1945) ) or Alfred Jentzsch could not make this new interest for Nature Protection in the German speaking area the sole idea of some isolated scientists, but a real powerful concern.

As another example, Károly Kaán (1867-1940, Hungary), a well-known Hungarian agronomist and forester, academician researcher and Secretary of State for Economy, was also such a "transmitting" scientist. He studied forestry in Karlsruhe (Germany) and travelled a lot in Europe. He was responsible for the reforestation of the Hungarian Great Plain after the first World War, but was also very sensitive to Nature monuments and Nature protection. He published in 1931 a book whose title was very close from Conwentz' one: "Nature Protection and Natural Monuments" (Természetvédelem és a természeti emlékek). Though he did not directly claim for the creation of National Parks in Hungary, he initiated the 1935 law for Nature Reserves and launched the National Council for Nature Protection in 1938 (Országos termésetvédelmi tanács), which is still in charge of the Protected Area Policy of Hungary today. He made possible the establishment of two nature reserves in 1934-35, which were used as a basis for the future Kiskunság national Park (est. 1962).

Therefore, the process of creation of National Parks in Central Europe is very much alike what one could see in other European countries, since there is a common background for Nature protection in Europe that was built at the beginning of the 20 th Century among scientific, political and cultural elites. One can summarize as follows the general "ingredients" for the implementation of the first National Parks (see figure 2).

National parks in the context of the Socialist Era

The systemic change of 1948 towards socialism did not erase the existing situation, so that it appears to be very difficult to speak of a single Socialist model of National parks. There is not one single path in the former so called "Eastern Block": in fact, there was no "block" at all, but it existed a strong diversity of national policies, even under the socialist rule. The environment was indeed not a central priority of the socialist regime and each country could therefore enjoy a significant level of self-decision, in so far as it would not hinder the political and economical priorities decided by the central party. Therefore the Socialist power has not stopped the pre-existing structures of Nature protection; in contrary, it sometimes promoted them, mostly in the 60's, since they were even part of the ideology on a healthy nature and a controlled development.

Moreover, the Socialist Regime showed an official interest for landscape ecology and natural sciences: in USSR, Lenin himself was rather keen to the Academies of Sciences in the Eastern Block, which were considered as an element of the soft power of the East [START_REF] Batou | Révolution russe et écologie 1917-1934[END_REF].

However, reality was often less positive than discourses on Nature protection. In Poland, for instance, existed in 1990 thirteen National Parks already, with a rather strong level of protectionmost of them falling into the II category of the IUCN. But they were covering altogether only 0.5% of the national territory. People were also convinced by propaganda that Nature in the Socialist camp was better protected than in the capitalist countries, since the latter could nothing but ruin their natural assets by their frantic search of profit [START_REF] Plit | La dégradation de l'environnement en Pologne[END_REF]. Only acid rains in Silesia were broadly known, but they were described as a legacy of the German industrialisation of the pre-war era. Thus the voice of Szafer, though respected, was considered as exaggerated by far.

Czechoslovakia created one new national park in 1949, in the Tatras chain range, as a symbol for the picturesque and highest symbolic value of this area in the country (2655m). It waited however until 1963 to establish the next one in the Giant Mountains (Krkonoše), highest point of the Czech part of the country. This "timing" had to deal with the raising influence of the country in nature protection, with a general law on nature protection in 1956, the IUCN membership of the country in 1958, the creation of an Institute for nature protection (Český ústav ochrany přírody, now agency for nature and landscape protection) on the same year and, finally, the accession of the botanist Jan Čerovsky (1930-), leader of nature protection in the country, at the position of chairman of the IUCN educational board in the 60's (he also became vice-president of the IUCN in 1991). National parks were also quite small, and rather strongly protected (cat. II after the IUCN classification).

Hungary waited longer, since this country established its first two national parks in the 70's (Hortobágy, 1972;Kiskunság, 1973), after the Stockholm summit. Surprisingly enough, both protected areas are really big (about 620 km² each!), though located in the heart of the very agricultural Hungarian Great Plain. But they appear to be a clear compromise between the needs of collective farms and nature protection, as they were constituted on a basis of many scattered small nature samples: between 9 and 21 units each (see figure 3)which is sharply contrasting with the obligation of continuity that can be found in many others countries for National Parks. This network of open-air biological laboratories are perfectly matching whith the soil fertility map, avoiding any loessic area, and covering every salted terrace or ecologically significant wetland of the Danube and the Tisza riverbanks. Many border effects, and a strong interaction with human activity make them fall into the V category of the IUCN. They were mostly dedicated to scientific research, with very few touristic featuresbut had an educational value for local people and pupils. Last but not least, Hungary included those two National Parks into their Man and Biosphere application (1972), so that both of them are Biosphere reserves of the UNESCO at the same time, with nature and culture preservation goals at the same time. It is thus a rather mildor even weakform of nature protection, compared with the former countries. As for the former German Democratic Republic, no National Park was ever created before the reunification, in 1990, despite several claims of civil society in the 50's and the 60's for the creation of national parks in the Saxony Mountains and the Harz. This regional exception is lacking a good explanation, but several factors could explain the situation: a fear of any "national" and centralistic structure after the Nazi period; the disinterest of the Soviet nomenklatura for Nature Protection, since the local elite was using former nature reserves as game areas; a stronger political priority for industrial development, without any charismatic leader for nature protection [START_REF] Schurig | Politischer Naturschutz : warum wurde in der D.D.R. (1949-1989) kein Nationalpark gegründet ?[END_REF]. Another explanation could lay in the rather strong density of rural areas in Germany, so that very few areas could fit with the idea of a pristine nature that had to be protected, as it was the case in the American Parks. The concept of wilderness (Wildnis) was rather a theoretical approach of Nature, and German conservationists, at the end of the 19 th Century, rather fought for the preservation of a cultural landscape (Kulturlandschaft)that is a landscape with mixed cultural and natural features that had to be held together, and that shaped with time a harmonious state of equilibrium.

So, as one can easily see, neither a unified policy, nor a common representation of Nature existed in the former Socialist block in the domain of protected areas.

Beyond specificities, a current convergence in Nature protection.

The systemic change of 1989 had a deep effect on national environmental policies. First of all, people in the Eastern block, since the beginning of the 80's, were claiming for more environmental transparency through a strong social unrest. They discovered after the fall of the iron curtain the lacks of the former socialist environmental management and endorsed their new governments with the responsibility of a new, more efficient environmental policy. On the other hand, the Europan Union asked Central European candidate coutries to enforce in their legislation the environmental requirements of the "Acquis communautaire", with, for instance, new laws and planning programmes for nature protection (e.g. the National environmental Programme 1996-2002 in Hungary, for instance).

This process of post-socialist transformation, pushed by an endogenous will and pulled by the europeanization process, ended up in a "catching up" period where many nature protection structures have been reinforced or newly created, among which many new national parks, considered as the visible witnesses of the political change (see figure 4). Germany, for instance, launched in 1990 for the New Länder of the East an ambitious "National Park Programme", including the creation of 5 national parks, 3 nature parks and 6 biosphere reserves. Twelve major protected areas have followed since that period, rising the level of territorial protection up to 10% of the regional territory. Hungary also increased its coverage with national parks and others protected areas up to 10% of the national territory.

However, the purposes and the management of those new National Parks has somewhat changed. It is now question to link nature protection management with rural development policies, with local participation so as to ensure a good economic integration of protected areas in their social context. There is no objective of a pure, untouched nature any moreas it could be the case in the heart of some national parks of the 70's in Bavaria or in the Hungarian Great Plainbut a slowly evolving nature "towards an optimal level of biodiversity", after the words of the German scientist Michael Succow (Europarc Deutschland, 2000), including sustainable rural activities and economic cooperation with local representatives. Hungarian new national parks are even meant to foster some local identity and regional marketing, for instance around the Balaton lake or the Danube bend. The Directions of National Parks are even taking part into some rural development projects under the 2007-2013 programmation of the European Agricultural Fund for Rural Development (EAFRD). As for the Czech Republic, the peripheral position of its national parks allow several transboundaries cooperations, not only for scientific and ecologic purposes, but also for tourism management and local development.

Conclusion

Therefore there is neither a real "socialist" model of a national park, nor a "post-socialist" one, but rather a sum of very different national policies that converge today in a global European framework that has been built within the European Union.

Every Central European country is evolving towards an integrated policy, where new national parks have quickly been created since 1990 in a "catching up" strategy, but with a much broader range of functions than before: not only ecological ones, but also economic and social ones in the idea of gaining a better social acceptance and applying the principles of a sustainable development of Central European rural areas. ___________

Figure 1 .

 1 Figure 1. the twelve Countries that have first implemented a National Park Policy in Europe. Source: WDPA 2006.

Figure 2 :

 2 Figure 2 : theoretic approach of the sources and processes of the creation of the first National Parks in Europe. Source: adapted from Depraz, 2008.

Figure 3 .

 3 Figure 3. The scattered network of National Parks and Protected areas in Hungary -Source: Depraz, 2003.

  Creation of national Parks and legislative evolution about Nature protection after 1989 in Central European countries -Source: national ministries, 2009.

		National Parks in 1989	National Parks in 2007	General law in
								force on Nature
		Nb area (km²)	share Nb area (km²)	share	protection
	Germany	4	621,5*	0,17% 14	1 866,0*	0,52%	1976, revised
	Among which New Länder	0	0,0	0%	7	808,2*	0,74%	1998 and 2002
	Hungary	4	1 413	1,52% 10	4 857,6	5,22%	1997
	Slovakia	5	1 931	3,93%	9	3 178,9	6,48%	2002
	Poland	13	1 819	0,58% 23	3 082,3	0,99%	1991
	Czech Republic	1	363	0,46%	4	1 195,5	1,52%	1992
	Figure 4.


Aurore Blelly

Matheus Felipe-Gomes

Anne Auger

Dimo Brockhoff

Stopping Criteria, Initialization, and Implementations of BFGS and their Effect on the BBOB Test Suite

Keywords: Computing methodologies → Continuous space search; Benchmarking, Black-box optimization, BFGS, Influence of parameters and initialization, Implementation impact

published or not. The documents may come   L'archive ouverte pluridisciplinaire

INTRODUCTION

Benchmarking algorithms is an important task in optimization. With the right numerical experiments, we can understand algorithms and their general properties and make recommendations about which algorithms to use in certain conditions in real-world situations. However, we must keep in mind that numerical experiments are comparing algorithm implementations and specific parameter settings, not a theoretical construct. Hence, it is important to understand the impacts of the algorithms' internal parameters on the algorithm performance. Moreover, it is interesting to compare various algorithm implementations, potentially also over different programming languages.

To assist in benchmarking experiments, the Comparing Continuous Optimizers platform (COCO, [START_REF] Hansen | COCO: A Platform for Comparing Continuous Optimizers in a Black-Box Setting[END_REF]) has been developed. But even when almost automated benchmarking platforms such as COCO are used, care must be taken that details of the benchmarking experiments might have important consequences in comparisons. Two aspects come into mind immediately for experiments with test suites from the COCO platform: (i) the choice of the initialization in a generally unbounded search space and (ii) the choice of the function instances. The latter are a way to introduce slight modifications of a function [START_REF] Hansen | COCO: Performance Assessment[END_REF] where the introduced differences in difficulty are assumed to be smaller among instances of the same function than between instances of different functions. Changing the instances over time allows to avoid overfitting of algorithms to the experimental setting, but is the mentioned assumption on the similarity of instances actually valid?

In this paper, we address the above questions about the influence of algorithmic and experimental setups on the performance of an algorithm for the representative example of the state-of-the-art BFGS method [START_REF] Wright | Numerical optimization[END_REF]. The BFGS algorithm has been already compared on the Comparing Continuous Optimizers platform (COCO, [START_REF] Hansen | COCO: A Platform for Comparing Continuous Optimizers in a Black-Box Setting[END_REF]) and the data of this experiment, run in MATLAB, has been available with the COCO platform since 2009 [START_REF] Ros | Benchmarking the BFGS algorithm on the BBOB-2009 function testbed[END_REF]. The algorithm is not only the default optimizer in MATLAB's fminunc but also the standard algorithm in the scipy module of Python (and available in almost any programming language to date).

Our main focus of this paper is thus to compare the Python and MATLAB implementations of BFGS and in particular to see whether the performance of BFGS stayed stable between the MATLAB version of 2009 and the 2017 version. Moreover, we will investigate how basic parameter choices in BFGS can affect its performance on the noiseless bbob test suite of COCO [START_REF] Hansen | Real-Parameter Black-Box Optimization Benchmarking[END_REF] and also investigate how the setting of the benchmark suite itself (in form of initialization and instance choice) affects the performance visualization.

In summary, this paper studies the impact of algorithm implementations, algorithm parameter settings and benchmark setup on the conclusions drawn from numerical benchmarking experiments and in particular reminds us that we have to be careful with respect to general statements about the reproducibility of benchmarking experiments. Out of the scope of this paper, though, is to understand where these differences actually come from. The reason to leave out this investigation is the fact that the BFGS implementations (in particular the ones of MATLAB) are black-boxes themselves for which we can only tune a few parameters but literally do not have access to the source code. We can therefore not really hope to gain a deep understanding about algorithmic differences ourselves.

THE BFGS ALGORITHM

Quasi-Newton methods address the problem of unconstrained blackbox optimization by the determination of the stationary point of a function using a second-order approximation. The idea is to build an approximation of the Hessian matrix, instead of exactly computing it as in the Newton method and then following, in each step of the algorithm, the estimated Newton direction by a line search.

In order to tackle black-box problems, also the gradient is estimated here in the derivative-free mode by finite differences. In standard implementations, in addition to the current iterate, n solutions (where n denotes the problem dimension) are evaluated along the coordinate axes with a constant Euclidean distance between them and the current iterate. When using symmetric differences, even 2n function evaluations are needed in each iteration. With the information of the estimated gradient, the Hessian is approximated, and a line search along the estimated Newton direction is performed to compute the next iterate.

The most used quasi-Newton method is the approach, independently proposed by Broyden, Fletcher, Goldfarb, and Shanno (BFGS, see for example [START_REF] Wright | Numerical optimization[END_REF])-and also the focus of our study. It is implemented in the basic optimization packages (and often the default) in many programming languages such as MATLAB, Python, or R and thus one of the first choices when solving non-linear (black-box) optimization problems in practice.

We will focus here on three implementations: (i) the MATLAB 2009 version benchmarked by Ros [START_REF] Ros | Benchmarking the BFGS algorithm on the BBOB-2009 function testbed[END_REF], (ii) the MATLAB R2017a version via function fminunc, and (iii) the current version of Python's scipy.optimize module (version 1.0.1, function fmin_bfgs).

PERFORMANCE COMPARISONS AND GENERAL SETUP

Results from experiments according to [START_REF] Hansen | COCO: The Experimental Procedure[END_REF] and [START_REF] Hansen | COCO: Performance Assessment[END_REF] on the benchmark functions given in [START_REF] Finck | Real-Parameter Black-Box Optimization Benchmarking 2009: Presentation of the Noiseless Functions[END_REF][START_REF] Hansen | Real-Parameter Black-Box Optimization Benchmarking[END_REF] will be presented later in Figures 3,4, 5, and 6. All experiments were performed with COCO [START_REF] Hansen | COCO: A Platform for Comparing Continuous Optimizers in a Black-Box Setting[END_REF], version 2.0, the plots were produced with version 2.2.1. 1The average runtime (aRT), used in the figures and tables, depends on a given target function value, f t = f opt + ∆f , and is computed over all relevant trials as the number of function evaluations executed during each trial while the best function value did not reach f t , summed over all trials and divided by the number of trials that actually reached f t [START_REF] Hansen | Real-Parameter Black-Box Optimization Benchmarking[END_REF][START_REF] Price | Differential evolution vs. the functions of the second ICEO[END_REF].

SCIENTIFIC QUESTIONS AND EXPERIMENTAL PROCEDURE

We ran several BFGS variants in both MATLAB and Python in order to answer the following scientific questions:

• What are the effects of general benchmarking parameters such as the domain of the initial search point or the concrete bbob problem instances in COCO? • What is the difference between the MATLAB and Python implementations of BFGS and did the implementations improve over time when compared on the bbob suite of COCO?

• What are the effects of changing/tuning the few internal algorithm parameters that the BFGS implementations provide to the outside?

Algorithm Tuning . We start with the last question in order to keep the investigation of the first two as simple as possible, using the best parameter setting found when answering the last question.

To this end, we tuned the algorithms over two specific functions: f10 (the rotated ellipsoid function) and f11 (the discus function), for dimensions 5 and 20. The choice was made on these functions because the algorithms presented a strange behavior in preliminary experiments on particularly these two functions when the default parameters were used: both the 2017 MATLAB and the Python version slowed down in performance significantly for no reason as if the algorithm decided to restart by itself.

For python's fmin_bfgs, we varied the parameter epsilon which characterizes the precision to which the derivative of the problem function will be approximated; for MATLAB's fminunc we changed the parameter FiniteDifferenceStepSize which is a scalar or vector step size factor used to create the finite differences in the gradient approximation. We only tuned it as a scalar, since we do not have a preferential direction. For both parameters, the default value is 10 -8 and we decided to test values in {10 -8 , 10 -9 , 10 -10 , 10 -11 }, given the experimentally found performance with the peak performance in the middle of this interval.

Figures 1 and2 show the results in which the MATLAB versions of BFGS are denoted by M-1e-XX and the Python versions as P-1e-XX indicating the chosen parameter with their names. What we can see for both programming languages and in all shown settings, the default version falls behind the variants with smaller parameter values for epsilon and FiniteDifferenceStepSize respectively. Decreasing the parameters below the value of 10 -10 almost always results in worse behavior-indicating that on the ellipsoid and discus functions, the value of 10 -10 shall be chosen over the default here. All subsequent experiments described will use this setup. We can note already here that the effect of the two parameters is not exactly the same in both programming languages with the Python version being more sensitive but resulting in better performance than the MATLAB version.

Note further that changing the setting of the algorithms by augmenting the precision of the gradient estimation increased the CPU timing for the experiments by a factor of about 10. Now that we have taken care of tuning the parameter related to the gradient estimation2 , we can continue with the more generic scientific questions.

Main Experiments and Algorithms Compared.

We continue to answer the other two scientific questions above, by running Python and MATLAB versions of BFGS on the bbob test suite of COCO. We denote the default variants, running with the above tuned parameters on the BBOB-2009 instances (three times each instance from 1 to 5), and initialized uniformly at random within (-5, and therefore not tuned by us, [START_REF] Ros | Benchmarking the BFGS algorithm on the BBOB-2009 function testbed[END_REF]), and as M-2017 for the R2017a MATLAB version.

To see the effects of initialization and the choice of the actual function instances in COCO, we distinguish three additional variants of P-2009:

• P-range: initialization uniformly at random in (-4, 4⌋ n instead of in (-5, 5⌋ n • P-StPt: the starting point is fixed at 0 D (the middle of the bounding box) instead of chosen randomly. • P-instances: the instances used are the one from 2017 (i.e.

1-5 and 61-70) All other parameters are set as in P-2009 which corresponds to the setting of Ros [START_REF] Ros | Benchmarking the BFGS algorithm on the BBOB-2009 function testbed[END_REF]. In addition, we add, denoted as P-ScipyB here, the data set from Baudiš [START_REF] Baudiš | COCOpf: An algorithm portfolio framework[END_REF] of the same BFGS algorithm in scipy but which was run with a slight modification: each time the algorithm restarts, the restart is done at a point chosen randomly in the neighborhood to where the algorithm was stopped, instead of being independently chosen at random in (-5, 5⌋ n . This strategy is known under the name "Basin hopping" and is available in the scipy module as well.

CPU TIMING

In order to evaluate the CPU timing of the algorithms, we have run the BFGS algorithm on the bbob test suite [START_REF] Hansen | Real-Parameter Black-Box Optimization Benchmarking[END_REF] with restarts for a maximum budget equal to 2 ⋅ 10 5 n function evaluations according to [START_REF] Hansen | COCO: The Experimental Procedure[END_REF]. The Python and MATLAB codes were run on an Intel(R) Xeon(R) CPU E5-2683 v4 @ 2.10GHz with 64 processor cores (nonexclusively). The time per function evaluation for dimensions 2, 3, 5, 10, 20, and 40 can be seen in the following table (all values are given in * 10 -4 seconds):

RESULTS

The aim of this section is to answer the remaining two scientific questions, mentioned above: the impact of the algorithmic and experimental setups on the performance as well as the question of how much the actual implementations of the BFGS algorithm differ in different languages and over time.

Influence of the Experimental Set-up

When looking at the summary graphs, aggregating over all 24 bbob functions in Figs. 3 and4, we do not see a large effect of the experimental setup-neither a changing starting condition nor the change of the instances have a large effect. However, this changes if we look at single functions. First of all, the starting point has the biggest impact on the Griewank-Rosenbrock F8F2 function (f 19 ) where choosing the origin as the first search point improves significantly over a random choice-solving immediately about 30% of the targets with the first evaluation. To a lesser extend, the positive impact of evaluating the origin first can also be seen for the rotated Rosenbrock function (f 9 ) and in low dimension on the Gallagher 101 peaks function (f 21 ). This effect, however, is quite specific to the choice of the test functions in COCO and rather a defect in the test suite than a desirable algorithm feature.

Changing the initial sampling from within (-5, 5⌋ n to (-4, 4⌋ n on the contrary has no clear effect-neither positive nor negative.

Changing the instances (here for the comparison between the instances of BBOB-2009 and BBOB-2017) can also have an impact on the results, though overall small. Examples of differences, without a trend towards easier or harder years of the BBOB workhop instances can be seen on f 10 , f 11 , and f 14 for the larger budgets/harder targets and for f 21 for the easier targets and thus smaller budgets. The observed differences, however, are rather small, meaning that the instances of a given function represent globally the same difficulties over the years.

Comparison between Python's and MATLAB's BFGS

Arguably the most surprising differences can be observed between the MATLAB and the Python implementations of BFGS. Compared to the small effects of internal algorithm parameters and experimental setup, it plays a significant role which algorithm implementation we choose. The implementations in MATLAB and Python show entirely different ECDF characteristics where deviations become larger in higher dimensions.

The most significant differences can be observed on the illconditioned function group where the python versions are all dominating the MATLAB versions with the exception of the scipy implementation using the "Basin Hopping" strategy from [START_REF] Baudiš | COCOpf: An algorithm portfolio framework[END_REF], see below for details on this algorithm.

When looking at single functions, the 2009 Python and MATLAB versions are still almost similar on 15 of the 24 bbob functions (in 5-D) and on 16 functions in 20-D. The largest deviations can be observed on the ellipsoid and discus functions and for high precisions (i.e. difficult targets) on the bent cigar, sharp ridge and different powers functions. The latter might come from different handling of numerical imprecisions. Differences between the Python and MATLAB implementations becomes larger in higher dimension.

Comparison between Matlab 2009 and Matlab 2017. Benchmark results comparing algorithms in the same software package but from different versions are very rare and one would typically expect that the performance of an algorithm increases over time rather than the opposite. For the default MATLAB implementation of BFGS, however, the opposite is true: the R2017a version is clearly worse than the data set from 2009 provided by Ros.

M-2017 performs worse than M-2009 on many problems, especially on the easier ones. Both algorithms typically perform almost identical in the beginning of the search and at some point, the 2017 version degrades compared to the 2009 version. This is well seen on the separable and non-separable ellipsoid, the attractive sector, the bent cigar, and the Gallagher functions and, in higher dimension, also on the Rosenbrock functions. The opposite is the case for the discus, sharp ridge, and sum of different powers functions where the 2009 version becomes worse at some point.

Unfortunately, no installation of a 2009 MATLAB version is available in order to investigate in depth where these performance differences come from. It is not unlikely that the experiments of Ros from BBOB-2009 included a different parameter setting that was not mentioned in the original publication.

In order to double-check that it is not a bad parameter setting for BFGS' epsilon parameter that causes the observed differences, one can look at the impact of the change in epsilon from the above mentioned parameter tuning experiment and observes that the changes in performance caused by a different epsilon value are far smaller than the differences observed between the 2009 and the 2017 MATLAB versions (and also smaller than the sensitivity of Python's BFGS on its internal parameters).

Effects of Basin Hopping: Weak global structure vs adequate global structure. Last, we look in detail on the Basin Hopping strategy which differentiates Baudiš' BFGS version from the ones benchmarked here. Baudiš' BFGS algorithm (P-ScipyB) performs clearly different from the other BFGS variants, even if it is the same algorithm to begin with.

The performance of P-ScipyB is as expected. On functions with clear global structure, that is for which the function values of neighboring local optima are highly correlated, the Basin hopping strategy works well: if a small perturbation at a restart allows to "hop" to a neighboring basin of attraction with a corresponding local optima with better function value, the performance is increased. An example of such a well-structured function is the Rastrigin function. If there is no or only a weak global structure or in other words, if the local optima are randomly placed like for the Gallagher functions, "basin hopping" is ineffective and it is better to perform entirely independent restarts.

CONCLUSION

Application engineers often rely on benchmarking results when they have to choose an optimization algorithm to solve a given realworld (black-box) optimization problem. If not much knowledge about the chosen algorithm is available, practitioners fall back on default settings and thus often assume that the default settings do not change the performance over different implementations and/or that new software updates rather improve the algorithm behavior than to degrade it.

In this paper, we have investigated the Python and MATLAB implementations of BFGS, one of the most common (non-linear) optimization algorithms in a black-box setting (estimating the gradients by finite differences). Extensive numerical experiments on the well-known bbob function suite from the COCO platform reveal some interesting and at least unexpected behavior: (i) differences between the Python and MATLAB implementations are larger than the effects of certain internal parameter changes, (ii) the performance of Python's BFGS implementation from the scipy module gives consistently better results than the MATLAB version, and (iii) the comparison between the 2009 MATLAB version as benchmarked at BBOB-2009 by Ros shows better performance than the latest R2017a version of the same algorithm.

Moreover, we have also clarified with our experiments what are the performance impacts when changing the initialization of the algorithm and the set of instances coming from the COCO platform. Compared to the differences among the algorithm implementations, these differences are rather small on the bbob test suite, indicating that it will become most important in the future to educate the optimization community to pay more attention when generalizing statements on algorithm performance in particular when only a single algorithm implementation is tested. all functions separable fcts moderate fcts ill-conditioned fcts multi-modal fcts weakly structured multi-modal fcts

Figure 1 :

 1 Figure 1: Expected running time by dimension for dimension 5 (upper figures) and 20 (lower figures) for different values of the step epsilon used to approximate the function derivative in Python's BFGS (values 10 -8 (default), 10 -9 , 10 -10 , and 10 -11 ).

Figure 2 :

 2 Figure 2: Expected running time by dimension for dimension 5 (upper figures) and 20 (lower figures) for different values of the parameter FiniteDifferenceStepSize used as a step size factor for finite differences in Matlab's BFGS (values 10 -8 (default), 10 -9 , 10 -10 , and 10 -11 ).

Figure 3 :Figure 4 :

 34 Figure 3: Bootstrapped empirical cumulative distribution of the number of function evaluations divided by dimension for 51 targets with target precision in 10 (-8..2⌋ for all functions and subgroups in 5-D. As reference algorithm, the best algorithm from BBOB 2009 is shown as light thick line with diamond markers. In the background, all BBOB 2009 algorithms in gray.all functions separable fcts moderate fcts

Figure 5 :

 5 Figure 5: Empirical cumulative distribution of simulated (bootstrapped) runtimes, measured in number of objective function evaluations, divided by dimension (FEvals/DIM) for the 51 targets 10 (-8..2⌋ in dimension 5.

Figure 6 :

 6 Figure 6: Empirical cumulative distribution of simulated (bootstrapped) runtimes, measured in number of objective function evaluations, divided by dimension (FEvals/DIM) for the 51 targets 10 (-8..2⌋ in dimension 20.

Actually, the source code of the development branch of COCO was used to postprocess the algorithm data for this paper, resulting in the slightly increased version number of

2.2.9 in the plots.

which is one of only few externally accessible parameters of the BFGS Python implementation and according to preliminary experiments the most sensitive one besides the initialization as we will see below