Andrew Elvey Price
email: andrew.elvey@univ-tours.fr.

Enumeration of walks with small steps avoiding a quadrant

Keywords: Lattice path, elliptic function, cone

We address the enumeration of walks with weighted small steps avoiding a quadrant. In particular we give an exact, integral-expression solution for the generating function C(x, y; t) counting these walks by length and end-point. Moreover, we determine precisely when this generating function is algebraic, D-finite or D-algebraic with respect to x, showing that this complexity is the same as for walks in the quarterplane with the same starting point, as long as the starting point (p, q) of the walks lies in the quarter plane then. Finally, we give an integral-free expression for the solution in the cases where (p, q) lies just outside the quarter plane, that is p = 0 or q = 0 with our convention, proving a conjecture of Raschel and Trotignon.

Introduction

The systematic study of walks with small steps in the quarter plane was initiated by Bousquet-Mélou and Mishna in 2010 [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF], and since then there has been great progress on the model [START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF][START_REF] Fayolle | On the Holonomy or Algebraicity of Generating Functions Counting Lattice Walks in the Quarter-Plane[END_REF][START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF][START_REF] Mishna | Two non-holonomic lattice walks in the quarter plane[END_REF][START_REF] Melczer | Singularity analysis via the iterated kernel method[END_REF][START_REF] Bernardi | Counting quadrant walks via Tutte's invariant method[END_REF][START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF][START_REF] Dreyfus | On the nature of the generating series of walks in the quarter plane[END_REF][START_REF] Dreyfus | Walks in the quarter plane: Genus zero case[END_REF]. The model is defined as follows: given a step set S ⊂ {-1, 0, 1} 2 \ {(0, 0)}, determine the generating function

Q(x, y; t) = ∞ ∑ n=0 ∑ i,j≥1
q(i, j; n)t n x i y j , where q(i, j; n) is the number of walks of length n, starting at [START_REF] Bernardi | Counting quadrant walks via Tutte's invariant method[END_REF][START_REF] Bernardi | Counting quadrant walks via Tutte's invariant method[END_REF], and ending at (i, j) using steps in S and staying in the strictly positive quadrant. 1 A priori, there are 256 distinct step sets S, but after removing duplicates and cases that are equivalent to half-plane models, Bousquet-Mélou and Mishna indentified 79 non-trivial and combinatorially distinct models. The study of these models is now in some sense complete as it is known for each S precisely where the generating function fits into the hierarchy Algebraic ⊂ D-finite ⊂ D-Algebraic.

Recall that a generating function G(x) is called Algebraic with respect to the variable x if it satisfies some non-trivial polynomial equation P(G(x), x) = 0, whose coefficients do not depend on that variable (but may depend on other variables), and it is called D-finite (resp. D-algebraic) if it satisfies a linear (resp. polynomial) differential equation with respect to x whose coefficients are polynomials in x. For a multivariate series to be algebraic (resp. D-finite, D-algebraic) it must be algebraic (resp. D-finite, D-algebraic) with respect to each variable.

Of the 79 models proposed by Mishna and Bousquet-Mélou, 4 models admit an algebraic generating function [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF][START_REF] Bostan | The complete generating function for Gessel walks is algebraic[END_REF], 19 further models admit a D-finite generating function [START_REF] Bousquet | Walks with small steps in the quarter plane[END_REF][START_REF] Fayolle | On the Holonomy or Algebraicity of Generating Functions Counting Lattice Walks in the Quarter-Plane[END_REF], 9 further models admit a D-algebraic generating function [START_REF] Bernardi | Counting quadrant walks via Tutte's invariant method[END_REF][START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF] and the remaining 47 models admit a generating function which is not D-algebraic [START_REF] Dreyfus | On the nature of the generating series of walks in the quarter plane[END_REF][START_REF] Dreyfus | Walks in the quarter plane: Genus zero case[END_REF]. Moreover, in the 74 cases known as non-singular, an exact integral expression is known for the generating function [START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF], while other exact expressions are known in the 5 singular cases [START_REF] Mishna | Two non-holonomic lattice walks in the quarter plane[END_REF][START_REF] Melczer | Singularity analysis via the iterated kernel method[END_REF]. In recent years a number of articles have focused on the equivalent question for walks avoiding a quadrant [START_REF] Bousquet-Mélou | Square lattice walks avoiding a quadrant[END_REF][START_REF] Raschel | On Walks Avoiding a Quadrant[END_REF][START_REF] Bousquet | More models of walks avoiding a quadrant[END_REF][START_REF] Dreyfus | On the nature of four models of symmetric walks avoiding a quadrant[END_REF][START_REF] Bousquet-Mélou | Enumeration of three-quadrant walks via invariants: some diagonally symmetric models[END_REF], that is determining the generating function C(x, y; t) which counts walks starting at (1, 1) whose intermediate points are required to lie in the three-quadrant cone

C = {(i, j) : i > 0 or j > 0}.
Between them these 5 articles classify 10 models into the complexity heirarchy (algebraic, D-finite, D-algberaic), while excursions have been enumerated for 4 further models [START_REF] Budd | Winding of simple walks on the square lattice[END_REF][START_REF] Elvey | Counting lattice walks by winding angle[END_REF]. Remarkably the generating function has the same nature in each case as in the quarter plane, a fact that led Dreyfus and Trotignon to conjecture that the nature is the same for any of the 74 non-singular step-sets S [START_REF] Dreyfus | Walks in the quarter plane: Genus zero case[END_REF]. We give exact integral expression solutions for C(x, y; t) in each of these 74 cases, analogous to those of Raschel in the quarter-plane [START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF]. We then prove that the nature of C(x, y; t) as a function of x (or y) is the same as that of Q(x, y; t), and we conjecture that these series also have the same nature as functions of t. In fact we do this in the more general setting of walks with weighted steps and starting at any point in the positive quadrant or on the positive xaxis.

Note that by our definition, steps directly between (1, 0) and (0, 1) are allowed, whereas they are forbidden in [START_REF] Bousquet | More models of walks avoiding a quadrant[END_REF], for example. We do not expect this to affect the nature of the generating function.

Functional equations for walks avoiding a quadrant

We start with a step-set S ⊂ {-1, 0, 1} 2 \ {(0, 0)}, a weight w s > 0 for each s ∈ S and a starting point (p, q) with p > 0, q ≥ 0. We will determine the generating function C(x, y; t) counting walks starting at (p, q), taking steps from S with all intermediate points lying in the three-quadrant cone C and with the weight of the walk being the product of the weights w s of the steps. Note that the standard starting point is (p, q) = (1, 1) and in the unweighted case w s = 1 for each s ∈ S.

The following lemma results from considering the final step of a walk counted by C(x, y; t): Lemma 1. Define the single step generating function P(x, y) by

P(x, y) = ∑ (α,β)∈S w (α,β) x α y β Then there are series A H ( 1 x ; t) ∈ t x Z[ 1 x ][[t]], A V ( 1 y ; t) ∈ t y Z[ 1 y ][[t]] and B(t) ∈ tZ[[t]] which satisfy C(x, y; t) = x p y q + tP(x, y)C(x, y; t) -B(t) -A H 1 x ; t -A V 1 y ; t . (2.1)
Moreover, this equation together with the fact that c(i, j; n) = 0 for i, j ≤ 0, characterises the generating function

C(x, y; t) = ∑ t≥0 ∑ i,j∈Z c(i, j; n)x i y j t n ,
as well as the series A H , A V and B.

The series A H , A V and B in the lemma above can be understood combinatorially: They count walks starting at (p, q) and ending just outside C whose intermediate points all lie within C. More precisely, A H ( 1 x ; t) counts those walks ending on the negative x-axis, A V ( 1 y ; t) counts those walks ending on the negative y-axis, and B(t) counts those walks ending at (0, 0).

The unusual condition that the coefficients c(i, j; n) of C(x, y; t) vanish for i, j ≤ 0 makes this equation difficult to solve directly, so we partition C into three quadrants

Q -1 = {(i, j) : i > 0, j < 0}, Q 0 = {(i, j) : i > 0, j ≥ 0} and Q 1 = {(i, j) : i ≤ 0, j > 0},
as shown in figure 1. A similar decomposition was used in [START_REF] Bousquet-Mélou | Square lattice walks avoiding a quadrant[END_REF][START_REF] Bousquet | More models of walks avoiding a quadrant[END_REF], but we have shifted the quadrants Q -1 , Q 0 down one space compared to those articles so that it is impossible to step directly between Q -1 and Q 1 and so that our condition on the starting point (p, q) is now that (p, q) ∈ Q 0 . Now, for j = -1, 0, 1, we define Q j (x, y; t) to be the generating function counting walks in C, starting at (p, q) and ending in Q j , so

C(x, y; t) = Q -1 (x, y; t) + Q 0 (x, y; t) + Q 1 (x, y; t), and Q -1 ∈ x y Z x, 1 y [[t]], Q 0 ∈ xZ [x, y] [[t]] and Q 1 ∈ yZ 1 x , y [[t]
]. The following lemma rewrites (2.1) as three equations characterising Q -1 (x, y; t), Q 0 (x, y; t) and Q 1 (x, y; t).

Q 0 Q -1 Q 1 Figure 1: The three-quadrant cone C partitioned into three quadrants Q 1 , Q 0 and Q -1 . Lemma 2. Define the kernel K(x, y; t) = tP(x, y) -1. There are series V 1 (y; t), V 2 (y; t) ∈ Z[y][[t]] and H 1 (x; t), H 2 (x; t) ∈ Z[x][[t]] satisfying the three equations K(x, y; t)Q -1 (x, y; t) = A V 1 y ; t + H 1 (x; t) + 1 y H 2 (x; t) (2.2)
K(x, y; t)Q 0 (x, y; t) = -xy + B (t) -V 1 (y; t) -xV 2 (y; t) -H 1 (x; t) - 1 y H 2 (x; t) (2.3) K(x, y; t)Q 1 (x, y; t) = A H 1 x ; t + V 1 (y; t) + xV 2 (y; t). (2.4)
Moreover, these three equations characterise the series

Q -1 (x, y; t), Q 0 (x, y; t), Q 1 (x, y; t), V 1 (y; t), V 2 (y; t), H 1 (x; t), H 2 (x; t), A H 1 x ; t , A V 1
y ; t and B(t).

Combinatorially, the series

(V 1 (0; t) -V 1 (y; t)) (resp. xV 2 (y; t), (H 1 (x; t) -H 1 (0, t)), 1 y (H 2 (0; t) -H 2 (x; t))) counts walks whose final step is from Q 0 (resp. Q 1 , Q -1 , Q 0 ) to Q 1 (resp. Q 0 , Q 0 , Q -1 ).

Parameterisation of the kernel curve

Following the method used in the quarter plane pioneered by Fayolle and Raschel [START_REF] Fayolle | Random walks in the quarter-plane[END_REF][START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF] we start by fixing t ∈ 0, 1 ∑ s∈S w s and then we consider the curve W = {(x, y) : K(x, y; t) = 0}. From now on, we will make the following assumption: Assumption: S is a non-singular step-set. That is, for any line through the origin, at least one element of S lies on each side of . As explained in [START_REF] Bousquet | More models of walks avoiding a quadrant[END_REF], if S did not have this property, the generating function C(x, y; t) would be algebraic.

Under this assumption, the curve W is known to have genus 1, so we will be able to parameterise it using elliptic functions X(z) and Y(z). More precisely the following lemma follows from [10, Proposition 2.1, Lemma 2.6]. Lemma 3. There are meromorphic functions X(z), Y(z) : C → C ∪ {∞} and numbers γ, τ ∈ iR with (πτ) > (2γ) > 0 satisfying the following conditions

• K(X(z), Y(z)) = 0 • X(z) = X(z + π) = X(z + πτ) = X(-γ -z) • Y(z) = Y(z + π) = X(z + πτ) = Y(γ -z) • |X(-γ 2 )|, |Y( γ 2 )| < 1 •
Counting with multiplicity, the functions X(z) and Y(z) each contain two poles and two roots in each fundamental domain {z c + r 1 π + r 2 πτ : r 1 , r 2 ∈ [0, 1)}. Moreover, X(z) and Y(z) are differentially algebraic with respect to z.

We intend to substitue x → X(z) and y → Y(z) into (2.2), (2.3) and (2.4), however we can only do this as long as the series in these equations converge, which occurs as long as |x| ≤ 1 ≤ |y| for (2.2), |x|, |y| ≤ 1 for (2.3) and |y| ≤ 1 ≤ |x| for (2.4). So to substitute x → X(z) and y → Y(z), we need to understand how |X(z)| and |Y(z)| compare to 1, for which we use the following lemma, which follows from [10, Lemma 2.9]. Lemma 4. The complex plane can be partitioned into simply connected regions {Ω s } s∈Z (see Figure 2) satisfying s∈Z

Ω 4s ∪ Ω 4s+1 = {z ∈ C : |Y(z)| < 1}, s∈Z Ω 4s ∪ Ω 4s-1 = {z ∈ C : |X(z)| < 1} and for s ∈ Z, π + Ω s = Ω s , sπτ + γ -Ω 2s ∪ Ω 2s+1 = Ω 2s ∪ Ω 2s+1 , sπτ -γ -Ω 2s ∪ Ω 2s-1 = Ω 2s ∪ Ω 2s-1 .

Analytic reformulation of functional equations

Using the results in the previous section, we can substitute x = X(z) and y = Y(z) into (2.2), (2.3) and (2.4) for z in the regions Ω -1 , Ω 0 and Ω 1 , respectively, yielding (2.9), (2.10) and (2.11) in the following proposition: Proposition 1. The functions

Ω 0 Ω 1 Ω 2 Ω 3 Ω 4 Ω -1 Ω -2 Ω -3 Ω -4 0 π -π γ 2 -γ 2 -πτ -γ 2 -πτ 2 -πτ +γ 2 -πτ + γ 2 -πτ πτ +γ 2 πτ 2 πτ -γ 2 πτ -γ 2 πτ |X(z)|, |Y (z)| < 1 |Y (z)| < 1 ≤ |X(z)| |X(z)|, |Y (z)| < 1 1 ≤ |X(z)|, |Y (z)| |X(z)|, |Y (z)| < 1 |Y (z)| < 1 ≤ |X(z)| |X(z)| < 1 ≤ |Y (z)| |X(z)| < 1 ≤ |Y (z)| 1 ≤ |X(z)|, |Y (z)|
L H (z) := H 1 (X(z); t) + 1 Y(z) H 2 (X(z); t), for z ∈ Ω 0 ∪ Ω -1 , (2.5)
L V (z) := V 1 (Y(z); t) + X(z)V 2 (Y(z); t), for z ∈ Ω 0 ∪ Ω 1 , (2.6)
P V (z) := A V 1 Y(z) ; t , for z ∈ Ω -1 ∪ Ω -2 , (2.7
)

P H (z) := A H 1 X(z) ; t , for z ∈ Ω 1 ∪ Ω 2 . (2.8)
are well defined and satisfy the equations

0 = P V (z) + L H (z) for z ∈ Ω -1 , (2.9
) 0 = -X(z) p Y(z) q + B (t) -L V (z) -L H (z) for z ∈ Ω 0 , (2.10)
0 = P H (z) + L V (z) for z ∈ Ω 1 (2.11) P H (z) = P H (πτ -γ -z) = P H (z + π) (2.12) P V (z) = P V (-πτ + γ -z) = P V (z + π) . ( 2.13)
While these equations are apriori defined on different sets, they can be used to show that the functions extend meromorphically to all of C, and so the equations hold on all of C. Simply taking the sum of the three equations (2.9), (2.10) and (2.11) yields (2.14) in the theorem below. Theorem 1. The functions P H (z) and P V (z) extend to meromorphic functions on C which, along with the constant B(t), are uniquely defined by the equation

X(z) p Y(z) q = P V (z) + B(t) + P H (z), (2.14)
along with (2.12), (2.13) and the conditions

• P H (z) has no poles in Ω 0 ∪ Ω 1 ∪ Ω 2 ,
• the poles of X(z) for z ∈ Ω 1 ∪ Ω 2 are roots of P H (z),

• P V (z) has no poles in Ω 0 ∪ Ω -1 ∪ Ω -2 ,
• the poles of Y(z) for z ∈ Ω -1 ∪ Ω -2 are roots of P Y (z).

Note that combining (2.14), (2.12), (2.13) yields

P H (2πτ -2γ + z) -P H (z) = W(z), (2.15)
where W(z) is an elliptic function with periods π and πτ given by

W(z) := (X(z -2γ) p -X(z) p ) Y(z) q .
3 Solving the functional equation

In the previous section we reduced the problem to finding the unique meromorphic functions P V , P H : C → C ∪ {∞} and constant B(t) characterised by Theorem 1 (for each t), as these determine A H ( 1 x , t) and A V ( 1 y , t) using 2.8 and 2.7, respectively, after which C(x, y; t) is determined by (2.1).

an equation analogous to (2.14) was found by Raschel for walks in the quarter plane [START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF], the only difference being that the transformations z → πτγz and z → -πτ + γz here are z → γz and z → -γz in the quarter plane. Raschel used this equation to derive an integral-expression solution determining Q(x, y; t), and the equation has since been used to determine precisely when Q(x, y; t) is differentially algebraic [START_REF] Bernardi | Counting quadrant walks via Tutte's invariant method[END_REF][START_REF] Dreyfus | On the nature of the generating series of walks in the quarter plane[END_REF][START_REF] Hardouin | On Differentially Algebraic Generating Series for Walks in the Quarter Plane[END_REF] and to determine when it is algebraic or D-finite with respect to x or y [START_REF] Fayolle | On the Holonomy or Algebraicity of Generating Functions Counting Lattice Walks in the Quarter-Plane[END_REF][START_REF] Kurkova | On the functions counting walks with small steps in the quarter plane[END_REF].

Due to this striking similarity we were able to use these methods to prove the same results for C(x, y; t), in particular showing that it is D-algebraic in exactly the same cases as Q(x, y; t) and that it is algebraic or D-finite with respect to x (or y) in the same cases as Q(x, y; t). We note that Fayolle and Raschel also showed that the unweighted models that are algebraic or D-finite with respect to t have the same nature with respect to t, however these results relied on the precise ratios πτ γ that could occur in these cases, so they do not apply so readily to our equation. Nonetheless, we expect that the same result holds for C(x, y; t).

Finally in the infinite group cases which do not decouple, the generating function can be shown to be non-D-algebraic in x using galois theory of q-difference equations, as in [START_REF] Dreyfus | On the nature of the generating series of walks in the quarter plane[END_REF][START_REF] Hardouin | On Differentially Algebraic Generating Series for Walks in the Quarter Plane[END_REF] for Q(x, y; t).

Special case: walks starting on x-axis

We will now study the special cases where the walk starts at some point (p, 0) for p > 0. Trotignon and Raschel conjectured that with this starting point all finite group models admit algebraic generating functions [START_REF] Raschel | On Walks Avoiding a Quadrant[END_REF]. Indeed, if q = 0 it is easy to see that the orbit sum E(z) defined is section 3.2 is equal to 0, so this follows from our more general results. Moreover, if q = 0, the model trivially decouples, so even in the infinite group case the generating function C(x, y; t) is D-algebraic.

The following lemma follows directly from Theorem 1, where ω(z) is defined as in Section 3.1.

Lemma 5.

If the starting point of the walks is (p, 0) for some p ≥ 1, then there is a degree p polynomial H satisfying P V (z) = H(ω(z)) -H(0),

B(t) = H(0), (3.4)
P H (z) = X(z) p -H(ω(z)).

(3.6)

Moreover, this polynomial is uniquely determined by the fact that the right hand side of (3.6) has a root at z = δ.

In fact, we can convert these directly to formulae for A H , A V and B using series

W 1 1
x ; t ∈ xZ[ ; t = ω(z) for z ∈ Ω -1 ∪ Ω -2 and W 2 1 Y(z) ; t = ω(z) for z ∈ Ω 1 ∪ Ω 2 . Note that these depend on the step-set but not the starting point (p, q) of the walk. For general p, we can rewrite Lemma 5 as the following theorem: Theorem 3. If the starting point of the walks is (p, 0) for some p ≥ 1, then there is a degree p polynomial H satisfying

A V 1 y = H W 2 1 y ; t -H(0), (3.7)
B(t) = H(0), (3.8)

A H 1 x = x p -H W 1 1 x ; t . (3.9)
Moreover, this polynomial is uniquely determined by the fact that the right hand side of (3.9) is a series in

Figure 2 :

 2 Figure 2: The complex plane partitioned into regions Ω j . For z on the blue lines, |Y(z)| = 1, while on the red lines |X(z)| = 1.

Note that most of the literature has considered the equivalent question of walks starting at (0, 0) and staying in the non-strictly positive quadrant, for which the resulting generating function is[START_REF] Bernardi | Counting quadrant walks via Tutte's invariant method[END_REF] xy Q(x, y; t).

Andrew Elvey Price

Integral expression

In this section we give integral expressions analogous to those of Raschel [START_REF] Raschel | Counting walks in a quadrant: a unified approach via boundary value problems[END_REF] which determine P V (z) and P H (z) exactly. In order to write these expressions, we define an auxiliary elliptic function ω(z) which satisfies

and shares the poles of X(z) in Ω 1 ∪ Ω 2 , while 1/ω(z) has the same poles as Y(z) in

Theorem 2. Let z 0 ∈ Ω 0 and let L be a path from z 0 to z 0 + π contained in the closure Ω 0 of Ω 0 . Then P V (z), P H (z) and B(t) are given by the integrals

The proof of this theorem involves checking that these expressions satisfy the conditions in Theorem 1.

Classification of C(x, y; t) into complexity hierarchy

In this section we very briefly describe the properties of the step set S, or equivalently X(z) and Y(z), which determine the nature of the generating function C(x, y; t).

In certain cases, called finite group cases, γ = M N πτ for some positive M, N ∈ Z independent of t. Then applying (2.15) N times yields

where E(z) is called the orbit sum of the model. We can use this equation to solve for P H (z), yielding an expression for C(x, y; t) which is D-finite in x. in the cases where E(z) = 0, we can even prove that C(x, y; t) is algebraic in x.

In all other cases we have γ πτ / ∈ Q for generic t. The model is then said to decouple if there are rational functions R 1 , R 2 satisfying X(z) p Y(z) q = R 1 (X(z)) + R 2 (Y(z)). These cases can be solved (with integral-free expressions) as, using (2.14), the function

is an elliptic function which can be determined exactly. In these cases every function used is D-algebraic in all of its variables.

Andrew Elvey Price

In the p = 1 case, we have W 2

x , which can be used as alternative definitions for W 1 and W 2 .

Special case: simple walks

We now describe the case of simple walks, that is, unweighted walks with step-set S = {(0, 1), (1, 0), (0, -1), (-1, 0)}. In this case X(z) and Y(z) can be written in terms of the Jacobi theta function

as

where γ = πτ 4 and is related to t by

Moreover, the function ω(z) defined in Section 3.1 is given by

2 )ϑ(3γ, 3τ 2 )

, which has π and 3πτ 2 as periods. Since X(z) and ω(z) share the periods π and 3πτ, they are related by a polynomial equation. One such equation is

where c 1 and c 2 are given by

,

Then for any starting point (p, 0), the generating functions A H , A V , B and hence C(x, y; t) can be determined by Theorem 3. Moreover, c 1 , c 2 and t can be shown to be modular functions of τ, so they are all algebraically related. Hence in these cases the generating function C(x, y; t) is algebraic in t as well as the other variables.

4 Nature of C(x, y; t) with respect to t

The main remaining problem is to prove that the generating function C(x, y; t) has the same nature (algebraic, D-finite, D-algebraic) as a function of t as it does as a function of x and y. Even for Q(x, y; t), which counts walks confined to a quadrant, this has not been proven for weighted models, so it is not surprising that we have so far been unable to prove it for C(x, y; t). However, we expect that if this is proven for Q(x, y; t), the result for C(x, y; t) will follow using the same method applied to Theorem 1.


O P Ferreira

• G N Grapiglia

E M Santos

J C O Souza

A subgradient method with non-monotone line search

Keywords: Subgradient method, Non-monotone line search, Convex function

published or not. The documents may come

A subgradient method with non-monotone line search

Introduction

The subgradient method for solving non-differentiable convex optimization prob-lems has its origin in the 60's, see [START_REF] Ermol'ev | Methods of solution of nonlinear extremal problems[END_REF][START_REF] Shor | Minimization methods for nondifferentiable functions[END_REF]. Over the years it has been the subject of much interest, attracting the attention of the scientific community working on Proposition 1 The function f ∶ ℝ n → ℝ is -strongly convex with modulus ≥ 0 if and only if f (y) ≥ f (x) + ⟨v, y -x⟩ + ( ∕2)‖y -x‖ 2 , for all x, y ∈ ℝ n and all v ∈ f (x).

A function f ∶ ℝ n → ℝ is L f ,C -Lipschitz continuous on C ⊂ ℝ n if there exist a constant L f ,C > 0 such that �f (x)f (y)� ≤ L f ,C ‖x -y‖ , for all x, y ∈ C . Whenever C = ℝ n we set L f ≡ L f ,ℝ n.

Proposition 2 Let f ∶ ℝ n → ℝ be a convex. Then, for all x ∈ ℝ n the set f (x) is a non-empty, convex, compact subset of ℝ n . In addition, f is L f ,C -Lipschitz function on C ⊂ ℝ n if and only if ‖v‖ ≤ L f ,C for all v ∈ f (x) and x ∈ C.

Remark 1

In view of Proposition 2, if C ⊂ ℝ n is a compact set then f is a L f ,C -Lip- schitz function on C ⊂ ℝ n for some L f ,C > 0.

Definition 3 Let C ⊂ ℝ n be a closed convex set. The projection map, denoted by P C ∶ ℝ n ⇉ C , is defined as follows P C (y) ∶= arg min{‖y -z‖ ∶ z ∈ C}.

The next lemma presents an important property of the projection.

Proposition 4 Let y ∈ ℝ n and z ∈ C . Then, we have � � P C (y)z � � 2 ≤ ‖y -z‖ 2 .

Definition 5 Let S be a nonempty subset of ℝ n . A sequence (v k ) k∈ℕ ⊂ ℝ n is said to be quasi-Fejér convergent to S, if and only if, for all v ∈ S there exists k ≥ 0 and a summable sequence ( k ) k∈ℕ , such that ‖v k+1 -v‖ 2 ≤ ‖v k -v‖ 2 + k for all k ≥ k.

In the following lemma, we state the main properties of quasi-Fejér sequences that we will need; a comprehensive study on this topic can be found in [START_REF] Combettes | Quasi-Fejérian analysis of some optimization algorithms[END_REF].

Lemma 6 Let (v k ) k∈ℕ be quasi-Fejér convergent to S. Then, the following conditions hold:

(i) the sequence (v k ) k∈ℕ is bounded; (ii) if a cluster point v of (v k ) k∈ℕ belongs to S, then (v k ) k∈ℕ converges to v.

Subgradient method with non-monotone line search

We are interested in the following constrained optimization problem [START_REF] Beck | First-Order Methods in Optmization[END_REF] min f (x) s.t. x ∈ C, where f ∶ ℝ n → ℝ is a convex function and C ⊂ ℝ n is a closed and convex set. Denote by Ω * the optimal set of the problem [START_REF] Beck | First-Order Methods in Optmization[END_REF] and by f * the optimal value. Throughout the paper we will consider problem [START_REF] Beck | First-Order Methods in Optmization[END_REF] under the following two assumptions:

(H1) f ∶ ℝ n → ℝ is a convex function and L f ,C -Lipschitz continuous;

(H2) f * ∶= inf x∈C f (x) > -∞.
We propose the following conceptual algorithm to find a solution of problem [START_REF] Beck | First-Order Methods in Optmization[END_REF].

Remark 2 It follows from [START_REF] Hiriart-Urruty | Convex analysis and minimization algorithms. I[END_REF]Theorem 4.2.3] that the set where convex functions fail to be differentiable is of zero measure. Consequently, almost every opposite direction of a subgradient is a descent direction. Therefore, we expect Algorithm 1 to be able to skip non-differentiability points that are not minimum points and then behave similarly to the gradient method with non-monotonic line search at differentiability points. It is worth to noting that the idea of using general non-monotone line searches in differentiable optimization, generalizing the non-monotone searches proposed in [START_REF] Grippo | A nonmonotone line search technique for Newton's method[END_REF][START_REF] Zhang | A nonmonotone line search technique and its application to unconstrained optimization[END_REF], have appeared in [START_REF] Grapiglia | On the worst-case evaluation complexity of non-monotone line search algorithms[END_REF][START_REF] Sachs | Nonmonotone line searches for optimization algorithms[END_REF]. A modified version of the subgradient method with the non-monotone line search proposed in [START_REF] Grippo | A nonmonotone line search technique for Newton's method[END_REF] was considered in [START_REF] Krejic | Spectral projected subgradient method for nonsmooth convex optimization problems[END_REF][START_REF] Loreto | Convergence analysis for the modified spectral projected subgradient method[END_REF][START_REF] Loreto | A numerical study of applying spectral-step subgradient method for solving nonsmooth unconstrained optimization problems[END_REF], see also [START_REF] Jerinkić | AN-SPS: Adaptive sample size nonmonotone line search spectral projected subgradient method for convex constrained optimization problems[END_REF].

In the following lemmas we establish general inequalities that are important in our analysis. We begin presenting the well definition of k defined in Step 2 of Algorithm 1 and two inequalities that follows as a consequence.

Lemma 7

There exists k satisfying [START_REF] Bertsekas | Nonlinear Programming, Athena Scientific Optimization and Computation Series[END_REF]. As a consequence, the following inequalities hold: and x k+1 ∈ C , for all k ∈ ℕ.

Proof Since f and the projection P C are continuous functions and the point

x k ∈ C , we have lim →0 + (f (P C (x k -s k )) -f (x k )+ ‖s k ‖ 2 )=0 . Hence, due to 𝛾 k > 0 , ( 3
) k+1 ≤ c k , f (x k+1 ) ≤ f (x k ) - k+1 ‖s k ‖ 2 + k , ∀k ∈ ℕ, there exists 𝜂 k > 0 such that f (P C (x k -𝛼s k )) -f (x k )+𝜌𝛼‖s k ‖ 2 <𝛾 k , for all ∈ (0, k ] , or equivalently,
Hence, due to ∈ (0, 1) we have lim →0 + k = 0 , and since 𝜂 k > 0 , we obtain that there exists * ∈ ℕ such that ≥ * implies k ∈ (0, k ] . Therefore, due to (4) be hold for all ∈ (0, k ] , there exists k satisfying [START_REF] Bertsekas | Nonlinear Programming, Athena Scientific Optimization and Computation Series[END_REF], which proves the first statement. The inequalities in (3) and inclusion x k+1 ∈ C follow from the definitions of x k+1 and k+1 in Step 3.

◻ From now on (x k ) k∈ℕ denotes the sequence generated by Algorithm 1. In the next lemma we recall a classical inequality used in the study of subgradient methods, see for example [START_REF] Beck | First-Order Methods in Optmization[END_REF]Lemma 8.11] and se also [START_REF] Correa | Convergence of some algorithms for convex minimization[END_REF]. We give the proof here for the sake of completeness.

Lemma 8

For any x ∈ ℝ n there holds In addition, if f is a -strongly convex function then there holds Proof Since the inequality (6) becomes (5) for = 0 , it is sufficient to prove [START_REF] Cristianini | An Introduction to Support Vector Machine and other Kernel-Based Learning Methods[END_REF]. It follows from the definition of x k+1 in Step 3 of Algorithm 1, Proposition 4 and also definition of k+1 that Therefore, considering that f is a -strongly convex function, it follows from Proposition 1 that ⟨s k , x - 2 , which substituting into [START_REF] Ermol'ev | Methods of solution of nonlinear extremal problems[END_REF] yields [START_REF] Cristianini | An Introduction to Support Vector Machine and other Kernel-Based Learning Methods[END_REF]. The inequality (5) follows from ( 6) by letting = 0 . ◻ Next we present an important relationship between ( k ) k∈ℕ and ( k ) k∈ℕ .

x k ⟩ ≤ f (x) -f (x k ) -( ∕2)‖x k -x‖

Lemma 9

The following inequality holds:

Proof The inequality [START_REF] Goffin | Convergence of a simple subgradient level method[END_REF] immediately holds for k = 1 . Suppose by an absurd that there exists k ∈ ℕ such that (4)

f (P C (x k -s k )) ≤ f (x k ) -‖s k ‖ 2 + k , ∈ (0, k ].
(5)

2 k+1 (f (x k ) -f (x)) ≤ ‖x k -x‖ 2 -‖x k+1 -x‖ 2 + 2 2 k+1 ‖s k ‖ 2 , ∀k ∈ ℕ. (6)
2 k+1 (f (x k ) -f (x)) ≤ (1 - k+1 )‖x k -x‖ 2 -‖x k+1 -x‖ 2 + 2 2 k+1 ‖s k ‖ 2 , ∀k ∈ ℕ. ( 7
)
‖x k+1 -x‖ 2 = ‖P C (x k -k k s k ) -x‖ 2 ≤ ‖x k -k k s k -x‖ 2 . = ‖x k -x‖ 2 + 2 k+1 ⟨s k , x -x k ⟩ + 2 2 k+1 ‖s k ‖ 2 . ( 8
) k ≥ min 1 , c k , k (1 + )L 2 f ,C
, ∀k ∈ ℕ.

Since we are supposing that ( k ) k∈ℕ is a non-increasing sequence, using the defini- tion of k+1 in Step 3 of Algorithm 1 together with (9), we conclude that Thus, in particular, we have Considering that f is L f ,C -Lipschitz continuous and x k ∈ C , using Proposition 4 we have Using again the L f ,C -Lipschitz continuity, it follows from Proposition 2 that ‖s k ‖ ≤ L f ,C . Thus, after some algebraic manipulations, the two previous inequalities imply that Hence, using [START_REF] Grant | Graph implementations for nonsmooth convex programs[END_REF] we obtain that f

(P C (x k -𝛽 k -1 𝛼 k s k )) -f (x k ) + 𝜌𝛽 k -1 𝛼 k ‖s k ‖ 2 < 𝛾 k , or equivalently
which, together with [START_REF] Grapiglia | On the worst-case evaluation complexity of non-monotone line search algorithms[END_REF], contradicts the definition of k in (2). Thus, [START_REF] Goffin | Convergence of a simple subgradient level method[END_REF] holds for all k and the proof is complete. ◻ Remark 3 It is worth to noting that the choice of 1 is crucial for the performance of the method. However, we are not aware of any theoretically founded criterion for choosing the initial stepsize in the context of line search methods. In the cases in which L f ,C is known, a conservative choice is since in this case it follows from Lemma 9 that the line search condition at iteration 1 of Algorithm 1 will be directly satisfied (with 1 = 0).

(9) 𝛼 k+1 < min 𝛼 1 , c𝛽𝛾 k+1 , 𝛾 k+1 (1 + 𝜌)L 2 f ,C . ( 10
) 𝛽 k -1 𝛼 k = 𝛼 k+1 < min 𝛼 1 , c𝛽𝛾 k+1 , 𝛾 k+1 (1 + 𝜌)L 2 f ,C ≤ min c𝛽𝛾 k , 𝛾 k (1 + 𝜌)L 2 f ,C . ( 11
) k -1 k ≤ c k . f � P C (x k -k -1 k s k ) � -f (x k ) ≤ L f ,C ‖P C (x k -k -1 k s k ) -x k ‖ ≤ L f ,C ‖x k -k -1 k s k -x k ‖ = L f ,C k -1 k ‖s k ‖. f � P C (x k -k -1 k s k ) � -f (x k ) + k -1 k ‖s k ‖ 2 ≤ L f ,C k -1 k ‖s k ‖ + k -1 k ‖s k ‖ 2 ≤ k -1 k (1 + )L 2 f ,C . f � P C (x k -𝛽 k -1 𝛼 k s k ) � < f (x k ) -𝜌𝛽 k -1 𝛼 k ‖s k ‖ 2 + 𝛾 k , 1 = min c 1 , 1 (1 + )L 2 f ,C
In the following we combine the inequalities (3) in Lemma 7 with those in Lemmas 8 and 9 to provide an inequality that will allow us to prove the convergence of (x k ) k∈ℕ and obtain some iteration-complexity bounds. For that, it is con- venient to define the following positive constants for 𝜌> 1∕2: Lemma 10 Assume that Ω * ≠ ∅ . Let (x k ) k∈ℕ be generated by Algorithm 1 and x * ∈ Ω * .Then, following inequality holds:

In addition, if f is a -strongly convex function then there holds Proof First of all, note that the inequality ( 14) becomes ( 13) for = 0 . Then, it is sufficient to prove the inequality [START_REF] Jerinkić | AN-SPS: Adaptive sample size nonmonotone line search spectral projected subgradient method for convex constrained optimization problems[END_REF]. It follows from Lemma 7 that

k+1 ‖s k ‖ 2 ≤ (f (x k ) -f (x k+1 ) + k )∕ , which combined with inequality (6) in Lemma 8 yields
On the other hand, by using Lemma 9, considering that ( k ) k∈ℕ is a non-increasing sequence and also using the first equality in [START_REF] Grippo | A nonmonotone line search technique for Newton's method[END_REF] we obtain that Besides, we know from Lemma 7 that k+1 ≤ c k , which combined with ( 15) and ( 16) yield Therefore, taking into account [START_REF] Grippo | A nonmonotone line search technique for Newton's method[END_REF], the last inequality implies ( 14) and the proof is concluded.

◻ Remark 4 It is worth to compare the classical inequalities ( 5) and ( 6) in Lemma 8 with, respectively, the inequalities ( 13) and ( 14) in Lemma 10. This comparison shows that the latter inequalities allow transfer to the sequence of non-monotonicity parameters ( k ) k∈ℕ the classical conditions usually imposed on the sequence of step sizes ( k ) k∈ℕ that control the behavior of (x k ) k∈ℕ , see for example [1, 2]. This way, (12)

Θ ∶= min 1 1 , c , 1 (1 + )L 2 f ,C , Γ ∶= Θ 2 - . ( 13
) Γ k+1 (f (x k ) -f * ) ≤ ‖x k -x * ‖ 2 -‖x k+1 -x * ‖ 2 + 1 c 2 k , ∀k ∈ ℕ. ( 14
) Γ k+1 (f (x k ) -f * ) ≤ (1 -Θ k+1 )‖x k -x * ‖ 2 -‖x k+1 -x * ‖ 2 + 1 c 2 k , ∀k ∈ ℕ. ( 15
) � 2 - � k+1 (f (x k ) -f * ) ≤ (1 - k+1 )‖x k -x * ‖ 2 -‖x k+1 -x * ‖ 2 + 1 k+1 k . ( 16
) k+1 ≥ min 1 1 , c , 1 (1 + )L 2 f ,C k+1 = Θ k+1 . � 2 - � Θ k+1 (f (x k ) -f * ) ≤ (1 -Θ k+1 )‖x k -x * ‖ 2 -‖x k+1 -x * ‖ 2 + 1 c 2 k ,
the method itself will select the step sizes k , which are usually prefixed in the classical formulations of sugbgradient method. In fact, for each prefixed non-increasing exogenous sequence ( k ) k∈ℕ , it follows from Lemmas 7, 9 and first equality in (12) that Algorithm 1, by performing a non-monotone line search, select the step sizes k satisfying the following inequalities which shows that our method is different from the ones that appeared in [START_REF] Krejic | Spectral projected subgradient method for nonsmooth convex optimization problems[END_REF][START_REF] Loreto | Convergence analysis for the modified spectral projected subgradient method[END_REF][START_REF] Loreto | A numerical study of applying spectral-step subgradient method for solving nonsmooth unconstrained optimization problems[END_REF]. Moreover, our line search allows different choices for the sequence ( k ) k∈ℕ that con- trols the non-monotonicity.

Convergence analysis

In this section we analyze the behavior of the sequence (x k ) k∈ℕ under assumptions (H1), (H2) and more two additional assumptions. The additional assumptions will be used separately and only when explicitly stated. The new assumptions are as follows:

(H3) The sequence of non-monotonicity parameters ( k ) k∈ℕ satisfies (H4) The sequence of non-monotonicity parameters ( k ) k∈ℕ satisfies Theorem 11 Assume that Ω * ≠ ∅ . Let (x k ) k∈ℕ be generated by Algorithm 1 with 𝜌 > 1∕2 and x * ∈ Ω * . Then, for each fixed N ∈ ℕ , the following inequality hold:

Consequently, if (H3) holds then lim N→+∞ min f (x k ) -f * ∶ k = 1, … , N = 0.
Proof Let k ≤ N . Using the inequality (13) in Lemma 10 and taking into account that min

� f (x k ) -f * ∶ k = 1, … , N � ∑ N k=1 k+1 ≤ ∑ N k=1 k+1 (f (x k ) -f * ) , we obtain that (17) Θ k+1 ≤ k+1 ≤ c k , k ∈ ℕ, lim N→+∞ ∑ N k=1 2 k ∑ N k=1 k+1 = 0. lim N→+∞ ∑ N k=1 2 k N N+1 = 0. ( 18
) min � f (x k ) -f * ∶ k = 1, … , N � ≤ 1 Γ � ‖x 1 -x * ‖ 2 + -1 c N � k=1 2 k � 1 ∑ N k=1 k+1 . Γ min � f (x k ) -f * ∶ k = 1, … , N � N � k=1 k+1 ≤ ‖x 1 -x * ‖ 2 + 1 c N � k=1 2 k ,
which implies [START_REF] Loreto | Convergence analysis for the modified spectral projected subgradient method[END_REF]. For concluding the proof, first note that assumption (H3) implies that lim N→+∞ ∑ k N =1 k+1 = +∞ . Thus, using [START_REF] Loreto | Convergence analysis for the modified spectral projected subgradient method[END_REF], the last statement follows. ◻

Let us state and prove a special instance of Theorem 11. For that we need a result, which can be found in [START_REF] Beck | First-Order Methods in Optmization[END_REF]Lemma 8.27].

Lemma 12 Let a > 0 , d ≥ 0 and N ≥ 1 . Then, Remark 5 If ( k ) k∈ℕ satisfies (H4), then ( k ) k∈ℕ also satisfies (H3). The sequence ( k ) k∈ℕ with k = 1∕(k 1-∕2 ) and ∈ (0, 1) satisfies (H4). Using Lemma 12 we can also prove that sequence

( k ) k∈ℕ with k = 1∕ √ k satisfies (H3).
The proof of the next theorem follows by combining inequality [START_REF] Loreto | Convergence analysis for the modified spectral projected subgradient method[END_REF] of Theorem 11 with Lemma [START_REF] Grippo | A nonmonotone line search technique for Newton's method[END_REF].

Theorem 13 Let x * ∈ Ω * , (x k ) k∈ℕ be generated by Algorithm 1 with 𝜌 > 1∕2 and Then, for each fixed N ∈ ℕ , the following inequality hold:

Consequently, lim N→+∞ min f (x k ) -f * ∶ k = 1, … , N = 0.
Remark 6 Since Lemma 12 implies that sequence ( k ) k∈ℕ with k = 1∕ √ k satisfies (H3), we conclude that the inequality in Theorem 13 is an explicit rate of convergence, namely, O(ln(N)∕

√ N).

We end this section by showing that (x k ) k∈ℕ generated by Algorithm 1 converges to a solution of the problem (1) whenever Ω * ≠ ∅ . To this end, we assume that the sequence ( k ) k∈ℕ satisfies the following conditions:

(H5) ∑ +∞ k=1 2 k ≤ +∞; (H6) ∑ +∞ k=1 k = +∞.
Remark 7 If ( k ) k∈ℕ satisfies (H5) and (H6), then ( k ) k∈ℕ also satisfies (H3). The sequence ( k ) k∈ℕ with k = 1∕k satisfies (H5) and (H6).

d + a ∑ N k=1 1 k ∑ N k=1 1 √ k+1 ≤ 4(d + a + a ln(N)) √ N . k = 1 √ k , ∀k ∈ ℕ. min � f (x k ) -f * ∶ k = 1, … , N � ≤ 4 Γ ‖x 1 -x * ‖ 2 + -1 c + -1 c ln(N) √ N
. Theorem 14 Let (x k ) k∈ℕ be generated by Algorithm 1 with 𝜌 > 1∕2 . Assume that (H5) holds. If Ω * ≠ ∅ , then (x k ) k∈ℕ is bounded. Moreover, if (H6) hold, then (x k ) k∈ℕ converges to a solution of problem [START_REF] Beck | First-Order Methods in Optmization[END_REF].

Proof Let x ∈ Ω * . Using (13) in Lemma 10 we obtain after some algebraic manipu- lations that Thus, considering that f (x k )f * ≥ 0 , for all k ∈ ℕ , it follows from the last inequal- ity that Hence, (H5) together with Definition 5 implies that the sequence (x k ) k∈ℕ is quasi- Fejér convergent to Ω * . Since Ω * ≠ ∅ , the item (i) of Lemma 6 implies that (x k ) k∈ℕ is bounded and the first statement is proved. To proceed, define a subsequence (x k N ) N∈ℕ of the sequence (x k ) k∈ℕ such that Since (x k ) k∈ℕ is bounded, we conclude that (x k N ) N∈ℕ is also bounded. Without loss of generality we can assume that

(x k N ) N∈ℕ converges. Set x = lim N→∞ x k N .
Under the assumptions (H3) and (H6) we have from the last part of Theorem 11 that 0 = lim N→+∞ (f (x k N )f * ) . Thus, using that x = lim N→∞ x k N , we conclude that f (x) = f * , which implies that x ∈ Ω * . Therefore, due (x k ) k∈ℕ be quasi-Fejér conver- gent to Ω * , by applying item (ii) of Lemma 6 we obtain the (x k ) k∈ℕ converges to x , which completes the proof. ◻

Convergence analysis for compact constraint set

The aim of this section is to analyze the behavior of (x k ) k∈ℕ under assumptions (H1), (H2) (H3) and one new additional assumption. The new assumption is as follows:

(H7) The set C is compact.

To state the next theorem let us introduce the following auxiliary positive constant and to prove it we also need an additional result, which can be found in [START_REF] Beck | First-Order Methods in Optmization[END_REF]Lemma 8.27].

Lemma 15 Let a > 0 , d ≥ 0 and N ≥ 2 . Then,

‖x k+1 -x‖ 2 ≤ ‖x k -x‖ 2 -Γ k+1 (f (x k ) -f * ) + 1 c 2 k , ∀k ∈ ℕ. ‖x k+1 -x‖ 2 ≤ ‖x k -x‖ 2 + 1 c 2 k , ∀k ∈ ℕ. f (x k N ) -f * ∶= min f (x k ) -f * ∶ k = 1, … , N , N ∈ ℕ. D ≥ max x,y∈C ‖x -y‖ 2 ,
In the next theorem we show that for suitable choice of the sequence

( k ) k∈ℕ the rate of convergence of Algorithm 1 is O(1∕ √ k).
Theorem 16 Let x * ∈ Ω * , (x k ) k∈ℕ be generated by Algorithm 1 with 𝜌 > 1∕2 and

Then, for each fixed N ∈ ℕ with N ≥ 2 , the following inequality hold:

Consequently, lim N→+∞ min f (x k ) -f * ∶ k = 1, … , N = 0.
Proof It follows from [START_REF] Grant | Graph implementations for nonsmooth convex programs[END_REF] in Lemma 13 and definition of k in ( 19) that Thus, summing this inequality over k = ⌈N∕2⌉, ⌈N∕2⌉ + 1, … , N we conclude that Since min

� f (x k ) -f * ∶ k = 1, … , N � ∑ N k=⌈N∕2⌉ 1 √ k+1 ≤ ∑ N k=⌈N∕2⌉ 1 √ k+1 (f (x k ) -f * )
and considering that D ≥ max x,y∈C ‖x -y‖ 2 , we obtain

The last inequality implies that which combined with Lemma 15 yields the desired inequality. The second statement of theorem is an immediate consequence of the first one. ◻ Theorem 17 Let f ∶ ℝ n → ℝ be a -strongly convex function and 𝜎 > 0 . Let (x k ) k∈ℕ be generated by Algorithm 1 with 𝜌 > 1∕2,

d + a ∑ N k=⌈N∕2⌉ 1 k ∑ N k=⌈N∕2⌉ 1 √ k+1 ≤ 4(d + a ln(3)) √ N + 2 . ( 19
) k = 1 √ k , ∀k ∈ ℕ. min � f (x k ) -f * ∶ k = 1, … , N � ≤ 4 � D + c ln(3) � Γ √ N + 2 . Γ 1 √ k + 1 (f (x k ) -f * ) ≤ ‖x k -x * ‖ 2 -‖x k+1 -x * ‖ 2 + c 1 k , ∀k ∈ ℕ. Γ N � k=⌈N∕2⌉ 1 √ k + 1 (f (x k ) -f * ) ≤ ‖x ⌈N∕2⌉ -x * ‖ 2 -‖x N+1 -x * ‖ 2 + c N � k=⌈N∕2⌉ 1 k . Γ min � f (x k ) -f * ∶ k = 1, … , N � N � k=⌈N∕2⌉ 1 √ k + 1 ≤ D + c N � k=⌈N∕2⌉ 1 k . min � f (x k ) -f * ∶ k = 1, … , N � ≤ D + c ∑ N k=⌈N∕2⌉ 1 k Γ ∑ N k=⌈N∕2⌉ 1 √ k+1
, and x * ∈ Ω * . Then, for each fixed N ∈ ℕ , the following inequality holds:

As a consequence, lim N→+∞ min f (x k ) -f (x * ) ∶ k = 1, … , N = 0.
Proof Since k = 2∕( Θk) satisfies (H3), it follows from ( 14) in Lemma 10 and 𝜎 > 0 that

Taking into account that k+1 = 2∕( Θ(k + 1)) , the last last inequality becomes Hence, multiplying the last inequality by 2k we obtain that Thus, due to min

� f (x k ) -f (x * ) ∶ k = 1, … , N � ∑ N k=1 k ≤ ∑ N k=1 k(f (x k ) -f (x * )) ,
= 2 Θk , ∀k ∈ ℕ. min f (x k ) -f (x * ) ∶ k = 1, … , N ≤ 8 c ΘΓ 1 (N + 1) . Γ Θ (f (x k ) -f (x * )) ≤ 1 -Θ k+1 Θ k+1 ‖x k -x * ‖ 2 - 1 Θ k+1 ‖x k+1 -x * ‖ 2 + c Θ 2 k k+1 . Γ Θ (f (x k ) -f (x * )) ≤ k -1 2 ‖x k -x * ‖ 2 - k + 1 2 ‖x k+1 -x * ‖ 2 + 2 c ( Θ) 2 2 k . 2Γ Θ k(f (x k ) -f (x * )) ≤ k(k -1)‖x k -x * ‖ 2 -k(k + 1)‖x k+1 -x * ‖ 2 + 8 c ( Θ) 2 . 2Γ Θ min � f (x k ) -f (x * ) ∶ k = 1, … , N � N � k=1 k ≤ -N(N + 1)‖x N+1 -x * ‖ 2 + 8 c ( Θ) 2 N. Γ min f (x k ) -f (x * ) ∶ k = 1, … , N ≤ 8 c Θ 1 (N + 1) ,

Illustrative numerical experiments

In this section we present some examples to illustrate the efficiency of the proposed method comparing its performance with other subgradient methods using classical step size rules. 1 It is not our intention to compete with these classical methods or other problem-specific algorithms, but rather to show that a general approach using our method performs remarkably well in a variety of settings. To this end, we consider the same set of constants in all methods and instances. More precisely, we perform Algorithm 1 (subgradient method with non-monotone line search) with c = 1 , = 0.9 , = 0.8 , 1 = 0.1 and k = √ k in all numerical experiments, for all k ≥ 1 and for some values of (which will be presented in the Sects. 4.1, 4.2 and 4.3). The other four subgradient methods use different step sizes k described in Table 1. All the methods start from the same initial point "zeros(n,1)" which means the zero vector in ℝ n In each case, simple modifications could be made to to improve the performance of our method, but these examples serve to illustrate an implementation of the proposed method and highlight several features. All numerical experiments are implemented in MATLAB R2020b and executed on a personal laptop (Intel Core i7, 2.30 GHz, 8 GB of RAM).

Maximum of a finite collections of linear functions

The experiments of this section are generated by the class of functions which are point wise maximum of a finite collections of linear functions. These functions are defined as follows:

where a j ∈ ℝ n and b j ∈ ℝ . In this case, f (x) = conv { f i (x) ∶ f i (x) = f (x)} . In this example, we consider the vectors a j = (a j,1 , … , a j,n ) ∈ ℝ n and b j ∈ ℝ randomly ( 20) As mentioned before, all the methods start from the same initial point and they stop if the iterate k = 3000 is attained. We compare the performance of the methods for dif- ferent dimensions n = 2 , n = 5 , n = 10 , n = 20 , n = 50 and n = 100 , where in Algo- rithm 1 we consider the values of c = 1 , = 0.9 , = 0.8 , 1 = 0.1 and k = √ k with as 0.01, 0.5, 1.0, 0.95, 1.5 and 3.3, respectively. The comparison of the methods is done in terms of the difference f bestf min , where the value f best stands to the best value of f (x k ) attained and f min denotes the solution of the problem computed by CVX, a pack- age for specifying and solving convex programming; see [START_REF] Grant | Cvx: Matlab software for disciplined convex programming[END_REF][START_REF] Grant | Graph implementations for nonsmooth convex programs[END_REF].

f (x) = max{f j (x) = a j ⊤ x + b j ∶ j = 1, … , m},
The computation results are displayed in Figs. 1 and2 and Tables 2 and3. In these tables, the first column denotes the dimension n and the number of functions f j , j = 1, … , m , in (20). The other columns represent, for each method, the best value obtained for f bestf min and the respective iterate it best where it was attained. As we can see, the results show that Algorithm 1 outperforms the other methods providing a better solution or a similar solution in less iterates in all the test problems. In some instances, the subgradient method with the step sizes "constant step", "fixed length" and "sqrsum nonsum" fail to find an acceptable solution in the sense that these methods stop to decrease the objective function in few iterates. In this sense, Algorithm 1 and the subgradient method with the step size "nonsum" have a better performance than the previous ones.

We also investigate the behavior of the sequences { k } and { k } in terms of the ine- quality 17, i.e., where Θ = min 1, 1 (1+ )L2 f . In this example, we consider the Lipschitz constant L f of the function f in [START_REF] Nedić | Convergence rate of incremental subgradient algorithms[END_REF] as L f = max{||a j || ∶ j = 1, … , m} . The results are reported in Figs. 3 and4 illustrating the theoretical result stated in Remark 4.

Fermat-Weber location problem

The experiment of this section is the well known Fermat-Weber location problem; see for instance Brimberg [START_REF] Brimberg | The Fermat-Weber location problem revisited[END_REF]. Let a 1 , … , a m be given points in ℝ n . The Fermat-Weber location problem is to solve the following minimization problem In our particular application, we consider the data points a i , for i = 1, … , 27 , given by the coordinate 2 of the cities which are capital of all 26 states of Brazil and

Θ k+1 ≤ k+1 ≤ c k , k ∈ ℕ, min x∈ℝ n f (x) = m ∑ i=1 w i ||x -a i ||. (a) (c)
Fig. 2 Best value of f (x k ) -f min (using log. scale) for Algorithm 1 and each step size in Table 1 Brasília (the Federal District, capital of Brazil). We take equally weights for all a i , namely, w i = 1 , i = 1, … , 27 , and consider the integer part of the coordinates con- verting it from positive to negative to match with the real data. Our goal is to find a point that minimizes the sum of the distances to the given points representing the cities in order to see how distance is such a point from Brasília (the capital of Brazil). We denote by the solution found by the MATLAB package CVX; see [START_REF] Grant | Cvx: Matlab software for disciplined convex programming[END_REF][START_REF] Grant | Graph implementations for nonsmooth convex programs[END_REF]. As mentioned in the beginning of this section, we perform Algorithm 1 and other four subgradient methods each of them with different step sizes k as described in Table 1. All the methods start from the same initial point and they stop at k = 200 iterates. As in the previous example, in Algorithm 1, we take c = 1 , = 0.9 , = 0.8 , 1 = 0.1

and k = √ k with = 2.
In Table 4, we present in the first two columns the solution x * = (x * 1 , x * 2 ) found by each method, in the third column the best value to |f bestf min | , where f best stands to the best value of the objective function for each method and f min is given by [START_REF] Nedić | The effect of deterministic noise in subgradient methods[END_REF]. The last column shows the iterate it best in which the best value |f bestf min | was attained. As we can notice, Algorithm 1 and the subgradient method with constant step size found a better solution compared to the solution known ( f min and x min ) than the other methods. However, Algorithm 1 found its best value in 29 iterates while [START_REF] Nedić | The effect of deterministic noise in subgradient methods[END_REF] f min = 312.9232964118977,

x min = (-45.9630806884547, -12.7465709013343) the subgradient method with constant step size takes 90 iterates to attain its best value. The performance of each method is presented in Fig. 5b showing the efficiency of the Algorithm 1 for this example. In Fig. 5a, we present the data of this example as well as the iterates of the Algorithm 1 and the solution found by the method.

Support vector machine

In this section, we apply Algorithm 1 and other four subgradient methods using different step sizes k as described in Table 1 for solving a binary classification problem. Support Vector Machine (SVM) is an effective and popular classification learning tool. In its native form, it is an unconstrained empirical loss minimization with a penalty term for the norm of the classifier that is being learned. However, the task of learning a support vector machine is modeled as a constrained quadratic problem formally stated as follows: where S = {(x i , y i )} m i=1 is a given training set with input features x i ∈ ℝ n , its respec- tive labels y i ∈ {-1, 1} , a regularization parameter 𝜆 > 0 and a bias term b. For simplicity, we omit the bias and consider only linear kernel model throughout our experiments; see more details in [START_REF] Cristianini | An Introduction to Support Vector Machine and other Kernel-Based Learning Methods[END_REF].

(22) min w,b Φ(w) = 𝜆 2 ||w|| 2 subject to y i (w ⊤ x i + b) ≥ 1, i = 1, … , m, (b)
We consider the following optimization problem for learning with a SVM introduced in [START_REF] Shalev-Shwartz | Primal Estimated sub-GrAdient SOlver for SVM[END_REF] where C = {x ∈ ℝ n ∶ ��x�� ≤ 1 √ } and L(w;(x, y)) = max{0, 1yw ⊤ x} is the hinge loss function. Therefore, the subdifferential of L(⋅ ;(x, y)) at w is given by We consider the Iris flower data set (or Ficher's Iris data set). 3 This data set is one of the best known data set found in pattern recognition literature. The data set consists of 3 classes, 50 instances and 4 numeric attributes (sepal length, sepal width, petal length and petal width) where each class refers to a type of Iris plant namely Iris setosa, Iris versicolor and Iris verginica. The first class is linearly separable from others while that latter are not linearly separable. We use the following code to generate our data test.

As in the previous sections, in Algorithm 1 we take c = 1 , = 0.9 , = 0.8 , 1 = 0.1 and k = √ k with = 10 . We run all the methods starting from the same initial point "zeros(n,1)" and they stop if the iterate k = 50000 is attained. As mentioned in [START_REF] Shalev-Shwartz | Primal Estimated sub-GrAdient SOlver for SVM[END_REF] and references therein, for different data sets usually small 22) and ( 23) (the same value in both problems). As in the previous examples, the comparison of the methods is done in terms of the difference f bestf min , where the value f best stands to the best value of f (x k ) attained and f min denotes the solution of the problem [START_REF] Nesterov | Subgradient methods for huge-scale optimization problems[END_REF] computed by CVX; see [START_REF] Grant | Cvx: Matlab software for disciplined convex programming[END_REF][START_REF] Grant | Graph implementations for nonsmooth convex programs[END_REF].

The results are presented in Tables 5 and6. In these tables, the first column denotes the value of in [START_REF] Nesterov | Subgradient methods for huge-scale optimization problems[END_REF] and [START_REF] Polyak | Introduction to optimization[END_REF]. The other columns represent, for each method, the best value obtained for f bestf min and the respective iterate it best where it was attained. The values f bestf min throughout the sequence are shown in Figs. and 7. As we can see, the results show that Algorithm 1 outperforms the other methods providing a better solution in all the test problems.

Conclusions

In this paper we have presented a subgradient method with a non-monotone line search for the minimization of convex functions with simple convex constraints. The non-monotone line search allows the method to adaptively select step sizes.

As preliminary numerical tests show, this method performs better than the standard subgradient method with prefixed step sizes, which we hope to motivate further research on this subject.

Fig. 1

 1 Fig. 1Best value of f (x k ) -f min (using log. scale) for Algorithm 1 and each step size in Table1

Fig. 4

 4 Fig. 3 Behavior of the sequences { k } and { k } (using log. scale) for Algorithm 1

Fig.

  Fig. Subgradient methods for solving the Fermat-Weber location problem

Fig. 6

 6 Fig. 6 Subgradient methods for solving the binary classification problem

6

 6

Fig. 7

 7 Fig. 7 Subgradient methods for solving the binary classification problem

  In Theorems 16 and 17 we provide two different choices for k . The one given in Theorem 16 is simpler than in Theorem 17. On the hand, if we know the Lipschitz of f, then we can use k given in Theorem 17 to improve the convergence rate given in Theorems 16.

			we
	have
	Therefore, due to	∑ N k=1 k = N(N + 1)∕2 , we conclude that
	which is equivalent the desired inequality. The second statement of theorem is an
	immediate consequence of the first one.	◻
	Remark 8

k

Table 1

 1 Comparison methods: step sizes in the subgradient method

	Abbr.	Subgradient method	Step size
	Constant step	Constant step size	k = 0.1
	Fixed length	Fixed step length	k =	0.2 ||g k ||
	Nonsum	Non-summable diminishing step	k =	0.1 √
				k
	Sqrsum nonsum	Square summable but not summable step	k =	0.5 k

Table 2

 2 Iteration where each algorithm attains the best value of f (x k )f min

		Algorithm 1		Constant step		Fixed length
		f best -f min	it best	f best -f min	it best	f best -f min	it best
	n = 2 , m = 10	1.23289e-07	2838	5.9329e-04	1863	1.29047e-03	2990
	n = 5 , m = 30	6.11231e-04	2872	0.038322	858	0.0239323	1579
	n = 10 , m = 50	1.73369e-03	2286	0.118048	1215	0.0455682	795
	n = 20 , m = 100	2.63594e-03	2675	0.389903	235	0.169888	2698
	n = 50 , m = 150	0.0157351	2895	1.32626	25	0.37411	2175
	n = 100 , m = 500	0.0483826	2696	1.59047	2	0.613463	2820

Table 3

 3 Iteration where each algorithm attains the best value of f (x k )f min

		Nonsum		Sqrsum nonsum
		f best -f min	it best	f best -f min	it best
	n = 2 , m = 10	1.4022e-05	2034 2.1927e-06	2363
	n = 5 , m = 30	9.0404e-04	2412 1.7e-03	2949
	n = 10 , m = 50	2.90217e-03 2686 2.4701e-03	2765
	n = 20 , m = 100	6.96234e-03 2699 2.57007e-03 2959
	n = 50 , m = 150	0.0266287	2978 0.205205	2964
	n = 100 , m = 500 0.0646978	2868 0.39232	2972

Table 4

 4 Solution found for the Fermat-Weber location problem

		x * 1	x * 2	|f best -f min |	it best
	Algorithm 1	-45.963064141347097	-12.746621089909885	2.66879e-07	29
	Constant step	-45.963064140711523	-12.746621088320897	2.42824e-08	90
	Fixed length	-38.605444422335090	-9.623064720309808	40.7379	200
	Nonsum	-43.842367512948982	-11.429938434104701	4.02647	200
	Sqrsum nonsum	-44.521197252917077	-11.740733447040283	1.9869	200

Table 5

 5 Iteration where each algorithm attains the best value of f (x k )f min

		Algorithm 1		Constant step		Fixed length
		f best -f min	it best	f best -f min	it best	f best -f min	it best
	= 0.1	3.279e-04	87	0.63306518	1	0.1445231	67
	= 0.01	1.0672e-03	308	0.87381057	1	0.05335602	221
	= 0.001	3.8742e-03	3472	0.95494822	1	0.0200689	751
	= 0.0001	2.1166e-04	49,892	0.18407921	50,000	6.08677e-03	4604

Table 6

 6 Iteration where each algorithm attains the best value of f (x k )f min

		Nonsum		Sqrsum nonsum
		f best -f min	it best	f best -f min	it best
	= 0.1	0.63306518	1	0.63306518	1
	= 0.01	0.33602865	5	0.87381057
	= 0.001	0.09793562	5	0.90521288	49,998
	= 0.0001	0.02867965	49,991	0.16502491	49,998

An extensive numerical comparison between the proposed method and other nonmonotone subgradient methods is beyond the scope of the present paper and will be left for a future work. The aim of our numerical experiments is just to illustrate the proposed method and its properties.

The latitude/longitude coordinates of the Brazilian cities can be found, for instance, at ftp:// geoftp. ibge. gov. br/ Organ izacao/ Local idades.

This data set can be found at http:// archi ve. ics. uci. edu/ ml.

Acknowledgements

We would like to thank the referees for their constructive remarks which allow us to improve our work.O. P. Ferreira was partially supported in part by CNPq -Brazil Grants 304666/2021-1, G. N. Grapiglia was partially supported by CNPq -Brazil Grant 312777/2020-5, J.C.O. Souza was supported in part by CNPq Grant 313901/2020-1. The project leading to this publication has received funding from the French government under the "France 2030" investment plan managed by the French National Research Agency (reference: ANR-17-EURE-0020) and from Excellence Initiative of Aix-Marseille University -A*MIDEX.

Data availibility

The data that supports the findings of this study is available from the corresponding author upon request.

Code availability

The code that supports the findings of this study is available from the corresponding author upon request.

Declarations

Conflict of interest

The aut hors declare that they have no conflict of interest.


Mélanie Bonhivers

Anne-Lise Sahin

Nicolas Landrein

Yeast two-hybrid interaction assay v1

Keywords:

published or not. The documents may come

LICENSE

This is an open access document distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited From Matchmaker Gold Yeast Two-hybrid system (Clontech/Takara Bio):

Vectors and yeast cell lines: plasmids pGADT7 (Prey) and Y187 (Leucine auxotrophy); plasmid pGBKT7 (Bait) and Y2HGold (Tryptophan auxotrophy) Clone your genes in both vectors.

For DNA sequencing: on pGADT7 and pGBKT7 use T7 promoter primer 5'-TAATACGACTCACTATAGGG . on pGADT7 use primer 5'-AGATGGTGCACGATGCACAG on pGBKT7 use primer 5'-TTTTCGTTTTAAAACCTAAGAGTC 1.Transformation of haploids : 1.Transformation of haploids :

The day before : The day before :

Plate Y187 (MATalpha) and Y2HGold (MATa) yeast cell lines on YPDA. The plates must be generously covered.

The day of transformation:

The day of transformation: -For each transformation (include the No DNA transformation control), take a sterile loop-full of yeast cells from overnight growth on a plate, resuspend in 1 ml sterile H 2 O (in 1. -Centrifuge 30 sec, 16000g and discard the supernatant (transformation mix).

-Resuspend the yeast cell pellet in 200ul sterile H2O and plate 20ul and ≈180ul on SC-Leucine (SC-L, for pGADT7 vectors) and SC-Tryptophan (SC-W, for pGBKT7 vectors).

-Incubate at 30°C for 3-4 days and pick 4 colonies.

-Make frozen stocks.

2.Toxicity test. 2.Toxicity test.

Both the prey and bait need to be tested for toxicity before the interaction test.

The growth of your "constructs" need to be compared to the growth of the cells transformed by the empty pGADT7 or pGBKT7 vectors using the drop test (see below).

Drop test Drop test on 120x120 plates (ref 688102, GBO):

WARNING: Humidity will spread your drops, so you really need to dry your plates thoroughly before performing the drop test.

-In 10 mL SC-W or SC-L liquid culture put a loop of yeast cells from a single haploid colony and grow ON, 30°C, 250 rpm.

-Next day, count your cells (Mallassez cell or OD 600nm : one OD unit = 10 7 cells/ml).

-Pellet 10 8 cells by spinning 5 min, 3000 rpm using a benchtop centrifuge.

-Resuspend the pellet in 1 ml sterile H 2 O. Cells are at 1.10 8 cells/ml.

-Make 1 mL dilutions to 10 7 -10 6 -10 5 -10 4 -10 3 cells/ml in sterile water -Load by 10 ul drops your 6 dilutions onto a plate: Your first drop contains 10 6 cells and the last drop 10 cells.

-Incubate at 30°C, 3 to 7 days.

Autoactivation test. Autoactivation test.

The pGBKT7 haploid transformed cells are plated on the interaction test media (SC-W-H, and SC-W-Ade, and/or +aureobasidine, and/or +X-a-Gal) to assess their autoactivating properties by drop test. The growth of your "constructs" need to be compared to the absence of growth of the cells transformed by the empty pGBKT7 vector. Do a drop test as described above.

5. Yeast mating for diploids 5. Yeast mating for diploids -For each haploid MATa and MATalpha and using the tip of a fresh cone, take a small swipe and mix together in a 50 mL tube containing 500 ul 2x YPDA medium at 30°, 250 rpm, O/N or all day. For 2x YPD : add adenine (2x final) to YPD medium.

To select the diploids:

-Centrifuge (3-5 min at 3000 rpm), remove the supernatant -Wash the pellet with 1 ml of H -After 2-3 days, you can collect 2-4 colonies.

6. Interaction assay 6. Interaction assay Do a drop test with your diploids, with the positive and negative controls.

-The positive control is pGBKT7-53 (which encodes the Gal4 DNA-BD fused with murine p53) and pGADT7-T (encodes the Gal4 AD fused with SV40 large T-antigen). Since p53 and large T-antigen are known to interact in a yeast two-hybrid assay, diploid cells will grow on interaction test media.

-The negative control is pGBKT7-Lam (which encodes the Gal4 BD fused with lamin) and pGADT7-T. The diploid cells will not grow on interaction test media.

-Load your 10 ul drops (see 3. Drop test) on the chosen interaction medium depending on the stringency: L-Leucine (100 X) Sigma L-8000 10 g/L Uracil (100 X) Sigma U-0750 2 g/L 0.8 g uracil + 1.68 g bicarbonate (NaHCO3) for 400 ml H2O (hot H2O) L-Histidine (100 X) Sigma H-8000 2 g/L Adenine (100 X) sigma A-8626 4 g/L 2 g for 450 ml H2O (hot H2O) + 2.08 ml HCl 12N L-Tryptophan (100 X)Sigma T0254 5 g/L X-alpha-Galactose Euromedex EU0012 800 ul of stock solution for 400 mL stock : 20 mg/ml in Dimethyl Formamide, -20°C

SC-W-L (growth control) SC-W-L-H SC-W-L-A SC-W-L+X-aGal SC-W-L+Aur-A SC-W-L+ X-a Gal+Aur-A -incubate

Glycerol stocks

Glycerol stocks Store your yeast cell stocks at -80°C in 1 ml of 15% glycerol/85% appropriate SC medium.

On day 1, plate your cells (cover the totality of the plate). ON.

  5 ml tube) by vortexing. -Spin 30 sec, 16000g, RT -Remove the supernatant -Add to the pellet in the tube without pipetting and in the following order : Salmon sperm carrier DNA 2 mg/mL in H2O 50 ul boiled 5-10 min and place on the ice, vortex before pipetting Plasmid DNA 1-5 ug in 34 uL H2O final. Alternatively, use 15uL of a miniprep diluted with 19uL H2O. 2 Citatio n: Citatio n: Mà ©lanie Bonhivers, Anne-Lise Sahin, Nicolas LANDREIN Yeast two-hybrid interaction assay https://dx.doi.org/10.17504/protocols.io.btzenp3e This is an open access protocol distributed under the terms of the Creative Co mmo ns Attributio n License Creative Co mmo ns Attributio n License (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, -Mix by vortexing. -Incubate at 42°C for 2-3 hours.

  at 3000 rpm), remove the supernatant -Add 1 ml of water -On three separate plates, spread 100 ul, 10 ul (add 10 ul to 90 ul H2O), and remaining (spin, resuspend in 200ul H 2 O) on SC-L-W plates. 3 Citatio n: Citatio n: Mà ©lanie Bonhivers, Anne-Lise Sahin, Nicolas LANDREIN Yeast two-hybrid interaction assay https://dx.doi.org/10.17504/protocols.io.btzenp3e This is an open access protocol distributed under the terms of the Creative Co mmo ns Attributio n License Creative Co mmo ns Attributio n License (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium,

  at 30°C for 3-7 days and compare growth with controls. Aliquot in 400ml bottles and autoclave at 110°C, 30 min.-->Add Adenine (100x stock, 4°C) before use -To pour 120x120 plates, add 10g agar agar (euromedex ref 1330-D) for 400 ml, autoclave, add adenine (1x from 100x stock) and pour the plates.

	Amino acid and nucleotide stocks in H Amino acid and nucleotide stocks in H 2 2 O ; autoclave 110°C, 30 min O ; autoclave 110°C, 30 min
	A	Reference	Concentration / dilution Comment
	Aureobasidine-A	clontech 630466 100ul of stock solution in 400 mL stock : 500 ug/ml in ethanol (stored at 4°C). Short life.
				Media, recipes Media, recipes
	SC medium SC medium
	component			1L	4x400mL	4L
	YNB (w/o ammonium sulfate) (BD, #233520) 1.7g	2.7g	6.8g
	Ammonium sulfate (Euromedex, #2019)	5g	8g	20g
	CSM (-L, -H, -W, -Ade, -Ura) (MP, #4550-122) 0.59g	0.944g	2.36g
	Dextrose (D-+-Glucose) (Euromedex, #UG3050) 20g	32g	80g
	SC composition
	-Aliquot in 400ml bottles and autoclave 110°, 30 min and store at RT.
	-To pour 120x120 plates, add 10g agar agar (euromedex ref 1330-D) for 400ml, autoclave and pour the plates.
	YPD-A YPD-A
	Component		4L	4x400mL
	Yeast extract (Euromedex, #Uy2010)40 g	16 g
	Bactopeptone (BD, #211677)	40 g	16 g
	Dextrose (Euromedex, #UG3050)	80 g	32 g
	YPD composition

4 Citatio n: Citatio n: Mà ©lanie Bonhivers, Anne-Lise Sahin, Nicolas LANDREIN Yeast two-hybrid interaction assay https://dx.doi.org/10.17504/protocols.io.btzenp3e This is an open access protocol distributed under the terms of the Creative Co mmo ns Attributio n License Creative Co mmo ns Attributio n License (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, -