Benjamin Aubin

Will Perkins

Lenka Zdeborová

Storage capacity in symmetric binary perceptrons

We study the problem of determining the capacity of the binary perceptron for two variants of the problem where the corresponding constraint is symmetric. We call these variants the rectangle-binary-perceptron (RPB) and the u-function-binary-perceptron (UBP). We show that, unlike for the usual step-functionbinary-perceptron, the critical capacity in these symmetric cases is given by the annealed computation in a large region of parameter space (for all rectangular constraints and for narrow enough u-function constraints, K < K * ). We prove this fact (under two natural assumptions) using the first and second moment methods. We further use the second moment method to conjecture that solutions of the symmetric binary perceptrons are organized in a so-called frozen-1RSB structure, without using the replica method. We then use the replica method to estimate the capacity threshold for the UBP case when the u-function is wide K > K * . We conclude that full-step-replica-symmetry breaking would have to be evaluated in order to obtain the exact capacity in this case.

I. INTRODUCTION

In this paper we revisit the problem of computing the capacity of the binary perceptron [START_REF] Gardner | Optimal storage properties of neural network models[END_REF][START_REF] Krauth | Storage capacity of memory networks with binary couplings[END_REF] for storing random patterns. This problem lies at the core of early statistical physics studies of neural networks and their learning and generalization properties, for reviews see e.g. [START_REF] Timothy Lh Watkin | The statistical mechanics of learning a rule[END_REF][START_REF] Hs Seung | Statistical mechanics of learning from examples[END_REF][START_REF] Engel | Statistical mechanics of learning[END_REF][START_REF] Nishimori | Statistical Physics of Spin Glasses and Information Processing: An Introduction[END_REF] . While the perceptron problem is motivated by studies of simple artificial neural networks as discussed in detail in the above literature, in this paper we view it as a random constraint satisfaction problem (CSP) where the vector of binary weights w ∈ {±1} N (a solution) must satisfy M step constraints of the type

N i=1 X µi w i ≥ K , (1)
where µ = 1, . . . , M , K ∈ Ê is the threshold, the random variables X µi are iid Gaussian variables with zero mean and variance 1/N , and the rows of the matrix X ∈ R M×N are called patterns. We define an indicator function associated to the perceptron with a step constraint as ϕ s (z) = ½ z ≥ K .

We say that a given vector w is a solution of the perceptron instance if all M constraints given by eq. ( 1) are satisfied. The storage capacity is then defined similarly to the satisfiability threshold in random constraint satisfaction problems: we denote the constraint density as α ≡ M/N and define the storage capacity α c (K) as the infimum of densities α such that in the limit N → ∞, with high probability (over the choice of the matrix X) there are no solutions. It is natural to conjecture that the converse also holds, i.e. the storage capacity α c (K) equals the supremum of α such that in the limit N → ∞ solutions exist with high probability. In this case we would say the storage capacity is a sharp threshold.

Gardner and Derrida in their paper 1 assume the storage capacity α c (K) is a sharp threshold and they apply the replica calculation to compute it, but reach a result inconsistent with a simple upper bound obtained by the first moment method. Mézard and Krauth 2 found a way to obtain a consistent prediction from the replica calculation and concluded that the storage capacity α s c (K) for the step binary perceptron (SBP), i.e. associated to the constraint ϕ s , is given by the largest α for which the following quantity, the entropy in physics, is positive:

φ s RS (α, K) = SP q0,q0    1 2 (q 0 -1) q0 + Dt log 2 cosh t q0 + α Dt log   ∞ K-t √ q 0 √ 1-q 0 Du      , (2)
where Dt = e -t 2 /2 √ 2π dt is a Gaussian measure, and SP stands for "saddle point" meaning that the expression is evaluated where the derivatives on the curl-bracket, with respect to q 0 ≥ 0 and q0 ≥ 0, is zero.

Several decades of subsequent research in the statistical physics of disordered systems are consistent with the conjectured Mézard-Krauth formula for the storage capacity of the binary perceptron. Despite the simplicity of the above conjecture and decades of impressive progress in the mathematics of spin glasses and related problems, (see e.g. [START_REF] Talagrand | The Parisi formula[END_REF][START_REF] Talagrand | Spin glasses: a challenge for mathematicians: cavity and mean field models[END_REF][START_REF] Mézard | Information, Physics, and Computation[END_REF][START_REF] Achlioptas | On the solution-space geometry of random constraint satisfaction problems[END_REF][START_REF] Panchenko | The Parisi formula for mixed p-spin models[END_REF][START_REF] Ding | Proof of the satisfiability conjecture for large k[END_REF] and many others), the storage capacity of the binary perceptron remains an open mathematical problem.

In fact, even the very existence of a sharp threshold, i.e. the fact that in the limit N → ∞ the probability that patterns can be stored drops sharply from one to zero at the capacity, is an open problem. Up to very recently only widely non-matching upper bounds and lower bounds for the storage capacity of the binary perceptron were available [START_REF] Han | Covering cubes by random half cubes, with applications to binary neural networks[END_REF][START_REF] Stojnic | Discrete perceptrons[END_REF] . As the present work was being finalized Ding and Sun [START_REF] Ding | Capacity lower bound for the Ising perceptron[END_REF] proved in a remarkable paper a lower bound on the capacity that matches the Krauth and Mezard conjecture (note that much like Theorem 4 below, the main theorem in [START_REF] Ding | Capacity lower bound for the Ising perceptron[END_REF] depends on a numerical hypothesis). A matching upper bound remains an open challenge in mathematical physics and probability theory.

In this paper we introduce two simple symmetric variants of the binary perceptron problem. Let z µ (w) = N i=1 X µi w i . For a threshold K ∈ Ê + , we consider two different types of symmetric constraints:

• The rectangle binary perceptron (RBP) requires |z µ | ≤ K, ∀µ = 1, . . . , M . Its associated indicator function is ϕ r (z) = ½ |z| ≤ K .

• The u-function binary perceptron (UBP) requires |z µ | ≥ K, ∀µ = 1, . . . , M . Its associated indicator function

is ϕ u (z) = ½ |z| ≥ K .
These constraints are symmetric in the sense that if w is a solution then -w is a solution as well.

The main result of the present paper, presented in section II, is a proof, subject to a numerical hypothesis, of a formula for the storage capacity, defined in the same way as for the step-function binary perceptron above. In particular, we show that in these symmetric variants the first moment upper bound (corresponding to the annealed capacity in physics) on the storage capacity is tight (except for K > K * ≃ 0.817 for the UBP case). We prove this statement using the second moment method.

Let Z ∼ N (0, 1), and for K ∈ Ê + let p r,K = P[|Z| ≤ K] and p u,K = P[|Z| ≥ K].

• The storage capacity for the rectangle binary perceptron is:

α r c (K) = -log(2) log(p r,K ) ∀K ∈ R + . (3)
• The storage capacity for the u-function binary perceptron is:

α u c (K) = -log(2)
log(p u,K ) for 0 < K < K * ≃ 0.817 .

The constant K * ≃ 0.817 stems from the properties of the second moment entropy eq. (10). In the physics terms it is defined as the point of intersection between the annealed capacity α u a (K) and the local stability of the RS solution α u AT (K) eq. ( 17). That is, K * is the solution of the following equation:

πp 2 u,K e K 2 log(p u,K ) = -2 log(2)K 2 . (5)
The two symmetric variants of the perceptron problem considered here share many of the intriguing geometric properties of the original step-function binary perceptron problem. Most significant is the conjectured frozen-1RSB 2 nature of the space of solutions that splits into well separated clusters of vanishing entropy at any α > 0. Remarkably, this frozen-1RSB property can be deduced from the form of the second moment entropy as we explain in section III. Our justification of the frozen-1RSB property does not rely on the replica method and is hence of independent interest.

For the UBP and K > K * , the second-moment proof technique fails, and this failure marks tightly the onset of the replica symmetry breaking region. In that region, we evaluate the one-step replica symmetry breaking (1RSB) approximation for the storage capacity, but conclude that full-step replica symmetry breaking (FRSB) would be needed to obtain the exact result. While the FRSB equations can be written along the lines of [START_REF] Franz | Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems[END_REF] , they are more involved than the ones for the Sherrington-Kirkpatrick model [START_REF] Parisi | Infinite number of order parameters for spin-glasses[END_REF][START_REF] Parisi | A sequence of approximated solutions to the sk model for spin glasses[END_REF][START_REF] Parisi | The order parameter for spin glasses: a function on the interval 0-1[END_REF] , and solving them numerically or getting additional insight from them is a challenging task left for future work. We present the replica analysis in section IV. Table I contains the summary of our main results along with the predictions for the step-function perceptron.

Finally let us comment on the simpler and more commonly considered case of spherical perceptron where the binary constraint on the vector w is replaced by the spherical constraint w ⊺ w = N i=1 w 2 i = N . For K = 0 the spherical perceptron reduces to the famous problem of intersection of half-spaces with capacity α c = 2 as solved by Wendell 20 and Cover 21 . For K > 0 the Gardner-Derrida solution 1 is correct as proven in [START_REF] Shcherbina | Rigorous solution of the Gardner problem[END_REF][START_REF] Stojnic | Another look at the Gardner problem[END_REF] . For K < 0 the situation is more challenging and FRSB is needed to compute the storage capacity; for recent progress in physics see [START_REF] Franz | Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems[END_REF][START_REF] Franz | The simplest model of jamming[END_REF] , while mathematical considerations about this case were presented in [START_REF] Stojnic | Negative spherical perceptron[END_REF] .

Binary perceptron Constraint Constraint function Range of K Storage capacity

Step-function

z ≥ K ϕ s (z) = ½ z ≥ K ∀K ∈ R RS eq. (2) Rectangle |z| ≤ K ϕ r (z) = ½ |z| ≤ K ∀K ∈ R + Annealed eq. (3) U -function |z| ≥ K ϕ u (z) = ½ |z| ≥ K 0 < K < K * = 0.817
Annealed eq. ( 4)

U -function |z| ≥ K ϕ u (z) = ½ |z| ≥ K ∀K > K * = 0.817 FRSB?

II. PROOF OF CORRECTNESS OF THE ANNEALED CAPACITY

To state the main results precisely we introduce some definitions. Let X(N, M ) be the random M × N pattern matrix. Define the partition functions

Z r (X) = w∈{±1} N M µ=1 ϕ r (z µ (w)) and Z u (X) = w∈{±1} N M µ=1 ϕ u (z µ (w)) ,
which count respectively the number of solutions for the rectangle and u-function constraints respectively. Let E r (N, M ) and E u (N, M ) be the events that Z r (X) ≥ 1 and Z u (X) ≥ 1. We formally define the storage capacity.

Defintition 1. The storage capacity α r c (K) is α r c (K) = inf{α : lim N →∞ P[E r (N, ⌊αN ⌋)] = 0} ,
and likewise for α u c (K).

It is believed that there is a sharp threshold for the existence of solutions.

Conjecture 2. The storage capacity is a sharp threshold:

α r c (K) = sup{α : lim N →∞ P[E r (N, ⌊αN ⌋)] = 1} ,
and likewise for α u c (K).

The corresponding conjecture for the random k-SAT model is the celebrated 'satisfiability threshold conjecture' proved for k large by Ding, Sly, and Sun 12 .

Next, couple two standard Gaussians Z 1 , Z β by letting Z and Z ′ be independent standard Gaussians and setting

Z 1 = √ βZ + √ 1 -βZ ′ and Z β = √ βZ - √ 1 -βZ ′ . Let    q r,K (β) = P[|Z 1 | ≤ K ∧ |Z β | ≤ K] = q K (β) , q u,K (β) = P[|Z 1 | ≥ K ∧ |Z β | ≥ K] = 1 -2p r,K + q K (β) , (6)
with q K (β) the probability that two standard Gaussians with correlation 2β -1 are both at most K in absolute value, that is:

q K (β) = 1 2π K -K dy K+(1-2β)y 2 √ β(1-β) -K+(1-2β)y 2 √ β(1-β) e -x 2 +y 2 2 dx .
Note that q t,K (1) = p t,K and q t,K (1/2) = p 2 t,K for t ∈ {r, u}. We now introduce the functions that dictate the effectiveness of the second moment bound. Let

F r,K,α (β) = H(β) + α log q r,K (β) (7) F u,K,α (β) = H(β) + α log q u,K (β) (8)
where

H(β) = -β log β -(1 -β) log(1 -β) is the Shannon entropy function.
We state a numerical hypothesis in terms of the derivatives of these two functions.

Hypothesis 3. For all choices of K > 0 and α > 0 so that F ′′ r,K,α (1/2) < 0, there is exactly one β ∈ (1/2, 1) so that F ′ r,K,α (β) = 0. The same holds for F u,K,α . Our main theorem is a proof, under Hypothesis 3, that the storage capacity is given by the annealed computation. Theorem 4. Under the assumption of Hypothesis 3, the following hold.

1. For all K > 0, we have α r c (K) =log(2)/ log(p r,K ). 2. For all K ∈ (0, K * ), we have α u c (K) =log(2)/ log(p u,K ). Under our definition of α r c (K) and α u c (K), we must prove two statements to show that α r c (K) =log(2)/ log(p r,K ) (and similarly for α u c (K)). We use the first moment method to show that for α >log(2)/ log(p r,K ), lim N →∞ Pr(E r (N, M )) = 0; then we use the second moment method to show that for α <log(2)/ log(p r,K ), lim inf N →∞ Pr(E r (N, M )) > 0 (a result analogous to what Ding and Sun prove for the more challenging step binary perceptron [START_REF] Ding | Capacity lower bound for the Ising perceptron[END_REF] ). Conjecture 2 asserts the stronger statement that for α <log(2)/ log(p r,K ), lim N →∞ Pr(E r (N, M )) = 1.

A. First moment upper bound Proposition 5.

1. If α > α r a (K) = -log(2)
log(pr,K ) , then whp there is no satisfying assignment to the binary perceptron with the rectangle activation function.

If α > α u

a (K) = -log(2) log(pu,K ) , then whp there is no satisfying assignment to the binary perceptron with the u-function activation function.

Proof. We give the proof for the rectangle function as the proof for the u-function is identical. Let ǫ = α-α r a (K) > 0. Let 1 denote the vector of dimension N with all 1 entries. 1. If α < -log [START_REF] Krauth | Storage capacity of memory networks with binary couplings[END_REF] log(pr,K ) , then lim inf

P[E r (N, αN )] ≤ E[Z r (X(N, αN ))] = 2 N E
N →∞ P[E r (N, αN )] > 0.
2. If K < K * and α < -log(2) log(pu,K ) , then lim inf

N →∞ P[E u (N, αN )] > 0.
To prove Proposition 6 we will apply the second-moment method in a similar fashion to Achlioptas and Moore 26 who determined the satisfiability threshold of random k-SAT to within a factor 2 by considering not-all-equal satisfying assignments (not-all-equal satisfiability (NAE-SAT) constraints are symmetric in the same way the rectangle and u-function constraints are symmetric). Recall the Paley-Zygmund inequality.

Lemma 7. Let X be a non-negative random variable. Then

P[X > 0] ≥ E[X] 2 E[X 2
] .

We will also use the following application of Laplace's method from Achlioptas and Moore 26 .

Lemma 8. Let g(β) be a real analytic function on [0, 1] and let

G(β) = g(β) β β (1 -β) 1-β .
If G(1/2) > G(β) for all β = 1/2 and G ′′ (1/2) < 0, then there exists constants c 1 , c 2 so that

c 1 G(1/2) N ≤ N l=0 N l g(l/N ) N ≤ c 2 G(1/2) N .

Rectangle binary perceptron

We calculate

E[Z r (X) 2 ] = w1,w2∈{±1} N P[w 1 , w 2 satisfying] = 2 N w∈{±1} N P[1, w satisfying] = 2 N N l=0 N l q r,K (l/N ) αN ,
where we recall q r,K from eq. ( 6). Define

G r,K,α (β) ≡ exp(F r,K,α (β)) = q r,K (β) α β β (1 -β) 1-β , (9)
If we can show that G r,K,α (1/2) > G r,K,α (β) for all β = 1/2 and G ′′ r,K,α (1/2) < 0, then by Lemma 8, we have

E[Z r (X) 2 ] ≤ c 2 4 N q r,K (1/2) αN = c 2 4 N p 2αN r,K .
Then since Z r (X) is integer valued, we have

P[Z r (X) ≥ 1] ≥ E[Z r (X)] 2 E[Z r (X) 2 ] = (2 N p αN r,K ) 2 E[Z r (X) 2 ] ≥ (2 N p αN r,K ) 2 c 2 4 N p 2αN r,K = 1/c 2 > 0 .
It remains to show that when α < -log [START_REF] Krauth | Storage capacity of memory networks with binary couplings[END_REF] log(pr,K ) , then G r,K,α (1/2) > G r,K,α (β) for all β = 1/2 and G ′′ r,K,α (1/2) < 0. By eq. ( 9) and the fact that G ′ r,K,α (1/2) = 0, it is enough to show the same for F r,K,α . Certainly one necessary condition is that F r,K,α (1/2) > F r,K,α (1). This reduces to the condition 2p 2α r,K > p α r,K or α < -log(2) log(pr,K ) which is exactly the condition of Proposition 6. Next consider F ′′ r,K,α (1/2). A calculation shows that

F ′′ r,K,α (1/2) = 4 -1 + 2 π αK 2 e -K 2 p 2 r,K . In particular, F ′′ r,K,α (1/2) < 0 if and only if α < π 2 p 2 r,K K 2 e -K 2 .
But a calculation also shows that

- log(2) log(p r,K ) < π 2 p 2 r,K K 2 e -K 2
for all K > 0 and so the condition of Proposition 6 implies that F ′′ r,K,α (1/2) < 0. Moreover, since F r,K,α (β) is symmetric around β = 1/2 and it has a local maximum at β = 1/2, Hypothesis 3 implies that the global maximum of F r,K,α (β) occurs at either 1/2 or 1, and since F r,K,α (1/2) > F r,K,α (1), we have that F r,K,α (1/2) > F r,K,α (β) for all β = 1/2, completing the proof of Proposition 6 for the rectangle binary perceptron.

u-function binary perceptron

The proof for the u-function is similar. We can calculate

E[Z u (X) 2 ] = 2 N N l=0 N l q u,K (l/N ) αN = exp (N (log(2) + F u,K,α (β))) ,
where we recall q u,K from eq. ( 6). Using Lemma 8 and Hypothesis 3 again, it suffices to show that for 0 < K < K * and α < -log(2) log(pu,K ) we have F u,K,α (1/2) > F u,K,α (1) and F ′′ u,K,α (1/2) < 0. The first follows immediately from the fact that α < -log [START_REF] Krauth | Storage capacity of memory networks with binary couplings[END_REF] log(pu,K ) . For the second, we have

F ′′ u,K,α (1/2) = 4 -1 + 2 π αK 2 e -K 2 p 2 u,K
and so

F ′′ u,K,α (1/2) < 0 if and only if α < π 2 p 2 u,K K 2 e -K 2 .
Unlike with the rectangle function it is not true that

- log(2) log(p u,K ) < π 2 p 2 u,K K 2 e -K 2 (10)
for all K: the left and right sides of the inequality cross at K = K * , which implicitly defines K * . Thus for K < K * and α < -log(2) log(pu,K ) we have F ′′ u,K,α (1/2) < 0, which completes the proof of Proposition 6 for the u-function binary perceptron. 2 is the maximizer while for α * ≤ α ≤ α u a = 0.604 (dashed yellow), the maximizer is non-trivial β = 0.

Illustration

As an illustration, we plot the second moment entropy density lim N →∞

1 N log E[Z 2 t ] = log(2)+F t,K,α for t ∈ {r, u} at K = 1 > K * in fig. 1.
For the rectangle function (a), the second moment is tight: the maximum is reached for β = 1/2 for all α smaller than the first moment α r a (dashed pink). Exactly the same happens for the u-function with K < K * . However for K > K * , the second moment method fails (b): β = 1/2 becomes a minimum and the maximum is obtained for non trivial values β = 1/2 for constraint density smaller than the first moment α u a (dashed yellow).

III. FROZEN-1RSB STRUCTURE OF SOLUTIONS IN BINARY PERCEPTRONS

One of the most striking properties of the canonical step-function perceptron is the predicted frozen-1RSB 2 nature of the space of solutions. This means that the dominant (measure tending to one) part of the space of solutions splits into well separated clusters each of which has vanishing entropy density at any α > 0. This frozen-1RSB scenario and quantitative properties of the solution space were studied in detail recently [START_REF] Wong | Entropy landscape of solutions in the binary perceptron problem[END_REF][START_REF] Huang | Origin of the computational hardness for learning with binary synapses[END_REF] . Following up on conjectures that such a frozen structure of solutions implies computational hardness in diluted constraint satisfaction problems [START_REF] Zdeborová | Constraint satisfaction problems with isolated solutions are hard[END_REF] , it was argued that finding a satisfying assignment in the binary perceptron should also be algorithmically hard since its solution space is dominated by clusters of vanishing entropy density [START_REF] Huang | Origin of the computational hardness for learning with binary synapses[END_REF] . Yet this conjecture contradicted empirical results of [START_REF] Braunstein | Learning by message passing in networks of discrete synapses[END_REF] . This paradox was resolved in [START_REF] Baldassi | Subdominant dense clusters allow for simple learning and high computational performance in neural networks with discrete synapses[END_REF] where the authors identified that there are subdominant parts (i.e. parts of measure converging to zero as the system size diverges) of the solution space that form extended clusters with large local entropy and all the algorithms that work well always find a solution belonging to one of those large-local-entropy clusters. These sub-dominant clusters are not frozen and somewhat strangely are not captured in the canonical 1RSB calculation [START_REF] Baldassi | Subdominant dense clusters allow for simple learning and high computational performance in neural networks with discrete synapses[END_REF] . It was argued that existence of these large-local-entropy clusters bears more general consequences on the dynamics of learning algorithms in neural networks, see e.g. [START_REF] Baldassi | Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes[END_REF] .

While frozen-1RSB structure has also been identified in constraint satisfaction problems on sparse graphs [START_REF] Zdeborová | Locked constraint satisfaction problems[END_REF][START_REF] Zdeborová | Quiet planting in the locked constraint satisfaction problems[END_REF] , we want to note that its nature in the binary perceptron is of a rather different nature. In sparse systems a simple argument using expansion properties of the underlying graph and properties of the constraints show that each cluster with high probability contains only one solution. In the perceptron model, which has a fully connected bipartite interaction graph, this argument from sparse models does not apply.

In the present paper, we deduce from the second moment calculation of the previous section that the space of solutions in the symmetric binary perceptrons is also of the frozen-1RSB type and this property moreover extends to any finite temperature (with energy being defined as the number of unsatisfied constraints). This is different from the locked constraint satisfaction problems of [START_REF] Zdeborová | Constraint satisfaction problems with isolated solutions are hard[END_REF][START_REF] Zdeborová | Quiet planting in the locked constraint satisfaction problems[END_REF] living on diluted hypergraphs, where the solution-clusters have extensive entropy at any non-zero temperature. Another difference is that whereas in the locked constraint satisfaction problems the size of each cluster is one with high probability, in the binary perceptron there are still many solutions in the clusters, it is only their entropy density (i.e. logarithm of their number per variable) that vanishes as N → ∞.

Investigation of the large local entropy clusters and their implications for learning in the symmetric perceptrons is also of great interest, but left for future work. Clearly since mathematically the symmetric perceptrons are simpler than the step-function one, they should also be the proper playground to deepen our understanding of the large local entropy clusters and their relation to learning and generalization.

We present the frozen-1RSB scenario as a conjecture and then below indicate how the second moment calculation gives evidence for this conjecture. Given an instance X and a solution w, let Γ(w, d) denote the set of solutions w ′ with Hamming distance at most d from w. Conjecture 9. For every K > 0 and every α ∈ (0, α r c (K)) there exists d min > 0 so that with high probability over the choice of the random instance X from the RBP, the following property holds: for almost every solution w,

1 N log |Γ(w, d min )| → 0 as N → ∞.
The same holds for the UBP for all K ≤ K * .

A. The link between the second-moment entropy and size of clusters

In this section we use t ∈ {r, u} and note that the form of the second moment entropy density 1 N log E[Z 2 t ] has very direct implications on the structure of solutions in the corresponding models. As we defined it above, the second moment entropy is the normalized logarithm of the expected number of pairs of solutions of overlap β.

For problems such as the symmetric binary perceptrons where the quenched and annealed entropies are equal in leading order, there is a striking relation between the planted and the random ensemble of the model [START_REF] Achlioptas | Algorithmic barriers from phase transitions[END_REF][START_REF] Krzakala | Hiding quiet solutions in random constraint satisfaction problems[END_REF] . The random ensemble is the problem we have considered so far, while the planted ensemble is defined by starting with a configuration of the weights (a solution) and then including only constraints that are satisfied by this planted configuration. As long as the quenched and annealed entropies of the random ensemble are equal in leading order the planted and random ensembles should be contiguous, meaning that high-probability properties that hold in one ensemble also hold in the other. Moreover the planted configuration in the planted ensemble has all the properties of a configuration sampled uniformly at random in the random ensemble. These properties follow on the heuristic level from the cavity method reasoning [START_REF] Krzakala | Hiding quiet solutions in random constraint satisfaction problems[END_REF] . They were established fully rigorously in a range of models, see e.g. [START_REF] Achlioptas | Algorithmic barriers from phase transitions[END_REF][START_REF] Mossel | Reconstruction and estimation in the planted partition model[END_REF][START_REF] Coja-Oghlan | Information-theoretic thresholds from the cavity method[END_REF] . In the present case of symmetric binary perceptrons we have not yet managed to prove contiguity between the random and the planted ensemble, and so we leave a rigorous mathematical result for future work. (In fact the missing ingredient is a version of Friedgut's sharp threshold result 39 suitable for perceptrons; such a result combined with Theorem 4 would also prove Conjecture 2). We hence rely on the above heuristic argument and assume it holds in what follows.

Given a planted solution w and a configuration w β that agrees with w on βN coordinates, the probability that w β is a solution in the planted model is (q t,K (β)/p t,K ) M , and thus the expected number of solutions at Hamming distance βN from the planted solution in the planted ensemble is

E[Z β ] = N βN (q t,K (β)/p t,K ) M ,
and its entropy density is

ω t (β) ≡ lim N →∞ 1 N log E[Z β ] = F t,K,α (β) -α log p t,K for t ∈ {r, u} . (11)
Recalling that contiguity implies that the planted solution has the properties of a uniformly chosen solution in the random ensemble then this entropy gives us direct access to properties of the solution space in the random ensemble at equilibrium. Most notably we notice (see derivation in section III B below) that the derivative of ω t (β) at β = 1 is +∞ thus implying that ∀ǫ > 0 with high probability there are no solutions at overlap

β ∈ [d min (α, K), (1 -ǫ)].
In turn, this means that the dominant (measure converging to one as N → ∞) part of the solution space splits into clusters each of which has vanishing entropy density (i.e. logarithm of the number of solutions in the cluster divided by N goes to zero as N → ∞). The missing ingredient in a full proof of Conjecture 9 is a proof of the contiguity statement. In fig. 2a we plot ω r (β) for the rectangle binary perceptron, at K = 1, α = 1.80 ≤ α r c (K = 1). Thanks to the contiguity between the planted and random ensembles that holds as long as the second moment entropy density is twice the first moment entropy density, this curve represents also the annealed entropy of solutions at overlap β with a random reference solution. We see notably that there is an interval of distances in which no solutions are present. Analytically we can see from the properties of the functions F t,K,α (β) and log p t,K that F t,K,α (1) = α log p t,K and the derivative of F t,K,α (β) → ∞. This is in contrast with, for instance, the satisfiability problems studied in [START_REF] Achlioptas | The asymptotic order of the random k-SAT threshold[END_REF] , where the function corresponding to F t,K,α (β) would have a negative derivative in β = 1 (see fig. 2b). There could still be an interval of forbidden distance, but the bump in entropy for β ≈ 1 corresponds to the size of the clusters to which typical solutions belong and those would be extensive.

Frozen 1RSB in rectangle binary perceptron

In the rectangle binary perceptron, the random and planted ensembles are conjectured to be contiguous for all K > 0 and α ∈ (0, α r c (K)). Using eq. ( 8), the first derivative of ω r (β), eq. ( 11), is given by (see Appendix VI E)

∂ω r ∂β = ∂F r,K,α ∂β = log 1 -β β + α q r,K,T (β) 1 π β(1 -β) e -K 2 2(1-β) e (2β-1)K 2 2(1-β)β -1 ,
and it diverges for all K ∈ R + , α > 0 in the limit β → 1:

∂ω r ∂β ---→ β→1 +∞ . ( 12
)
This implies vanishing entropy density of clusters to which typical solutions belong.

Frozen 1RSB in the u-function binary perceptron

In the u-function binary perceptron, the random and planted ensembles are conjectured to be contiguous for all 0 < K ≤ K * and α ∈ (0, α u c (K)). Using eq. ( 8), the first derivative of ω u (β) eq. ( 11), is given by

∂ω u ∂β = ∂F u,K,α ∂β = log 1 -β β + α q u,K,T (β) 1 π β(1 -β) e -K 2 2(1-β) e (2β-1)K 2 2(1-β)β -1 -→ β→1 +∞ ,
thus reaching the same conclusion on presence of frozen-1RSB.

In appendix VI E we extend the second moment calculation to finite temperature (for both the rectangle and u-function case). This means that we define energy of a configuration E(w) as the number of constraints that are violated by this configurations. Then the corresponding partition function is defined Z(T ) = w e -E(w)/T . There is a one-to-one mapping between the temperature T and energy density e = E/N , consequently the corresponding finite-temperature second moment entropy density counts the number of pairs of solutions at overlap β and energy density e. In appendix VI E we apply the same argument as here connecting the random and planted ensemble, and deduce that the finite-temperature solution space of the models is of also of the frozen-1RSB type for any T < ∞.

C. Frozen-1RSB as derived from the replica analysis

We stress that we derived the frozen-1RSB nature of the space of solutions without the use of replicas. For completeness we summarize here how this translates to the properties of the one-step-replica-symmetry breaking solution. This is the way this phenomena was originally discovered and described in [START_REF] Krauth | Storage capacity of memory networks with binary couplings[END_REF][START_REF] Wong | Entropy landscape of solutions in the binary perceptron problem[END_REF][START_REF] Oc Martin | Frozen glass phase in the multi-index matching problem[END_REF] . For readers not familiar with the replica method this section should be read after reading section IV.

In general, three kinds of fixed points of the 1RSB equations are possible:

• The replica symmetric (RS) solution q 0 = q 1 = q RS < 1 ,

• The frozen-1RSB solution (f1RSB) (q 0 , q 1 ) = (q RS , 1) ,

• The 1RSB solution (q 0 , q 1 ) with q 1 = 1 . The frozen-1RSB is characterized by an inner-cluster overlap q 1 = 1 and an inter-cluster overlap q 0 = q RS , which means that clusters have vanishing entropy density and remain far from each other. Mathematically RS and f1RSB solutions are equivalent in the sense that these solutions have the same free energy eq. ( 20) Φ 1RSB {q RS , q RS } = Φ 1RSB {q RS , 1}, and the complexity of the f1RSB solution equals the RS entropy Σ(φ = 0) = φ RS eq. (22, 15). However, RS and f1RSB do not share the same configuration space. The RS phase is associated to a single cluster of solution with typical size 1q RS , while the f1RSB configuration space is composed of many point-like solutions of size q 1 ≃ 1 and at distance 1q 0 = 1q RS of each other, see fig. 3. From this point of view f1RSB is the correct description of the phase space.

IV. REPLICA CALCULATION OF THE STORAGE CAPACITY

In this section we recall the replica calculation leading to the expression of the storage capacity in the step-function binary perceptron. We show that in the symmetric binary perceptrons the annealed calculation is reproduced by the replica symmetric result. For the u-function binary perceptron we show that K * coincides with the onset of replica symmetry breaking and we evaluate the 1RSB capacity for K > K * .

A. Replica calculation

For the purpose of the calculations, we introduce the constraint function C(z) that returns 1 if w satisfies all the constraints {ϕ(z µ )} M µ=1 and 0 otherwise

C(z) = M µ=1 ϕ(z µ ) with z µ = X µ w .
Recall the partition function Z is the number of satisfying vectors w, with prior distribution P w (w), for a given matrix X

Z(X) = w∈{±1} N M µ=1 ϕ (X µ w) = dwP w (w) dz C(z)δ(z -Xw) .
The replica method allows one to compute explicitly the quenched average E X [log(Z(X))] [START_REF] Schülke | Statistical physics of linear and bilinear inference problems[END_REF] . More precisely, using the replica trick, the average of the logarithm can be expressed as the limit n → 0 of the derivative with respect to n of the average of the n-th moment of the partition function. Finally the free entropy reads:

φ(α) ≡ lim N →+∞ 1 N E X [log(Z(X))] = lim N →+∞ lim n→0 1 N n ∂ log (E X [Z(X) n ]) ∂n . ( 13
)
Computing the n-th moment of the partition function Z, for n ∈ AE, is equivalent to considering n copies, also called replicas, of the initial system. For a given disorder, these n replicas are non-interacting and Z n can be computed easily. However, averaging over the "disorder" with distribution P X makes the replicas interacting: replicated weight-vectors w a and w b , for a, b ∈ [1 : n], are correlated by the overlap matrix

Q = (Q ab ) n a,b=1 = 1 N N i=1 w a i w b i n a,b=1
.

We show in Appendix VI A that after averaging over the distribution P X , using an analytical continuation for n ∈ Ê and finally reversing the limits N → ∞ and n → 0, the free entropy φ eq. ( 13) can finally be expressed as a saddle point equation over n × n symmetric matrices Q and Q

φ(α) = -SP Q, Q lim n→0 ∂S n (Q, Q) ∂n , ( 14
)
where Q is a parameter involved in the change of variable between {w a , w b } and Q ab and with

             S n (Q, Q) = 1 2 Tr(Q Q) -log(I n w ( Q)) -α log (I n z (Q)) , I n w ( Q) = Ê n d wP w ( w)e 1 2
w⊺ Q w

where w ∈ Ê n and P w ( w) = n a=1

[δ( wa -1) + δ( wa + 1)] ,

I n z (Q) = Ê n dzP z (z)C(z)
where z ∈ Ê n and P z N (0, Q) .

In order to be able to compute the derivative of S n with respect to n eq. ( 14), we need an analytical formulation of Q and Q as a function of n.

B. RS entropy

The simplest ansatz is to assume that the overlap matrix Q is Replica Symmetric (RS), which means that all replicas play the same role: the correlation between two arbitrary, but different, replicas is denoted q 0 , and therefore the RS ansatz reads:

∀(a, b) ∈ [1 : n] × [1 : n], 1 N (w a • w b ) = q 0 if a = b , Q = 1 if a = b .
It enforces the matrix Q to present the same symmetry, respectively with parameters q0 and Q = 1. Using this ansatz and the n → 0 limit, the Replica Symmetric (RS) entropy can be expressed as a set of saddle point equations over scalar parameters q 0 and q0 , evaluated at the saddle point (Appendix VI B):

φ RS (α) = SP q0,q0 - 1 2 + 1 2 (q 0 q0 -1) + I w RS (q 0 ) + αI z RS (q 0 ) , (15)
with      I w RS (q 0 ) ≡ Dt log (g w 0 (t, q0 )) , I z RS (q 0 ) ≡ Dt log (f z 0 (t, q 0 )) ,

and for i ∈ AE          g w i (t, q0 ) ≡ dw w i P w (w) exp (1 -q0 ) 2 w 2 + t q0 w , f z i (t, q 0 ) ≡ Dz z i ϕ( √ q 0 t + 1 -q 0 z) . (16)
Note that above and in what follows Dt = e -t 2 /2 √ 2π dt. In the binary perceptron case, the function P w is defined as P w (w) = [δ(w -1) + δ(w + 1)] (note that this is not a probability distribution because of the normalization), and recall ϕ(z) is the indicator function, checking that a constraint on the argument is satisfied (e.g in the step case, ϕ s (z) = 1 if z > K).

While in the step binary perceptron (SBP) the fixed point solution (q 0 , q0 ) is non-trivial, the symmetry of the activation function in the RBP and UBP cases enforces the configuration space to be symmetric and the fixed point (q 0 , q0 ) = (0, 0) to exist. If this symmetric fixed point is stable and has the lowest free energy, the RS free entropy matches the annealed entropy φ t a (α) = log(2) + α log(p t,K ) = 1 N log E X [Z t (X)] from section II A with t ∈ {r, u}.

Rectangle

Solving numerically the corresponding saddle point equations leads to the single symmetric fixed point (q 0 , q0 ) = (0, 0). Hence the RS entropy saturates the first moment bound: φ r RS (α) = log(2) + α log (p r,K ) = φ r a (α) , and the RS capacity equals the annealed capacity eq. (II A):

α r RS (K) = α r a (K) = -log(2)
log (p r,K ) .

U -function

• For K ≤ K * , only the symmetric fixed point (q 0 , q0 ) = (0, 0) exists, which leads again to the annealed free entropy:

φ u RS (α) = log(2) + α log (p u,K ) = φ u a (α)
, and annealed capacity eq. (II A):

α u RS (K) = α u a (K) = -log(2) log (p u,K
) .

• For K > K * , the RS entropy does not match the annealed entropy because the fixed point (q 0 , q0 ) = (0, 0) corresponds to a lower free energy than the symmetric fixed point (0, 0). The symmetric fixed point becomes unstable for K > K * , where K * is remarkably given by the same value as in the independent section II B 2.

Hence it naturally verifies eq. ( 5) even though its definition derives from the stability of the RS solution, that we study in the next section.

C. Stability

The local stability of the RS solution can be studied using de Almeida and Thouless (AT) method [START_REF] De Almeida | Stability of the Sherrington-Kirkpatrick solution of a spin glass model[END_REF] , based on the positivity of the Hessian of S n (Q, Q). The replica symmetric AT-line α AT is given by the solution of the following implicit equation (Appendix VI D):

1 α = 1 (1 -q 0 (α)) 2 Dt f z 0 (f z 0 -f z 2 ) + (f z 1 ) 2 2 (f z 0 ) 4 (t, q 0 (α)) Dt g w 0 g w 2 -(g w 1 ) 2 2 (g w 0 ) 4 (t, q0 (α)) .
As illustrated above, for the rectangle and u-function, the symmetry of the weights P w and the constraint ϕ imposes the existence of the symmetric fixed point (q 0 , q0 ) = (0, 0). This simplifies the previous condition and becomes equivalent to the linear stability condition of the symmetric fixed point (q 0 , q0 ) = (0, 0) (see Appendix VI D):

1 α AT = f z 2 -f z 0 f z 0 2 gw 2 gw 0 2
, where for i ∈ AE:

       gw i = dww i P w (w)e w 2 2
,

f z i = Dzz i ϕ(z) .
We plotted the annealed capacity, the replica symmetric capacity and the AT-line for the step, rectangle and u-function binary perceptrons as functions of K in fig. 4, 5, 6.

Step binary perceptron

We note that for the step binary perceptron the RS solution is always stable towards 1RSB, even for negative threshold K < 0. This is interesting in the view of recent work on the spherical perceptron with negative threshold where the replica symmetry breaks for all K < 0, and full-step RSB is needed to evaluate the storage capacity [START_REF] Franz | Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems[END_REF] .

Rectangle

As the RS capacity α r RS is always below the AT line α r AT , the RS solution is always locally stable.

u-function

There is a crossing between the values of the RS capacity α u RS and the AT-line α u AT , which defines implicitly the value K * ≃ 0.817, and matches the equality in eq. ( 10):

-

log (2) log (p u,K * ) = π 2 (p u,K * ) 2 e -(K * ) 2 (K * ) 2 . ( 17
)
For K ≤ K * , the RS solution is locally stable, while for K > K * the RS solution becomes unstable, and a symmetry breaking solution appears. Step binary perceptron (SBP): the RS capacity α s RS (black) does not match the annealed capacity α s a (blue) and is always below the AT-line α s AT (orange). The AT-line is closest to the annealed capacity for Kmin ≃ 3.62 where the difference α s ATα s a ≃ 0.0012. For K = 0, we retrieve well known results 2 : α r RS ≃ 0.833, α r AT ≃ 1.015 and α r a = 1. The left and right hand sides, and the inset, represent the same data on different scales. The satisfiable (SAT) phase is represented by the beige shaded area and is located below the RS capacity, while the unsatisfiable (UNSAT) starts at the capacity (black line) and extends for a larger number of constraints. RS (black) matches the annealed bound α r a (blue), and the RS solution is locally stable for all K: α r RS < α r AT . The AT-line (orange) is closest to the annealed capacity for Kmin ≃ 1.24 where the difference α s ATα s a ≃ 0.15. The left and right hand sides, and the inset, represent the same data on different scales. The satisfiable (SAT) phase is represented by the beige shaded area and is located below the RS capacity, while the unsatisfiable (UNSAT) starts at the capacity (black line) and extends for a larger number of constraints. FIG. 6. U -function binary perceptron (UBP): the RS capacity black) matches the annealed bound (blue) for K < K * . At K = K * , the RS capacity crosses the AT-line (orange). For K > K * , the RS solution is unstable and the RS capacity deviates from the annealed capacity. The left and right hand sides, and the inset, represent the same data on different scales. The satisfiable (SAT) phase is represented by the beige shaded area and is located below the RS capacity, while the unsatisfiable (UNSAT) starts at the capacity (black line) and extends for a larger number of constraints.

D. 1RSB calculation

In the previous section we concluded that the replica symmetric solution is unstable in the u-function binary perceptron for K > K * , we analyze therefore the first-step of replica symmetry breaking (1RSB) ansatz in this section. This ansatz and calculations is due to seminal works of G. Parisi and is classic in the field of disordered systems and well presented in the literature [START_REF] Parisi | Infinite number of order parameters for spin-glasses[END_REF][START_REF] Parisi | A sequence of approximated solutions to the sk model for spin glasses[END_REF][START_REF] Parisi | The order parameter for spin glasses: a function on the interval 0-1[END_REF][START_REF] Virasoro | Spin glasses and beyond[END_REF] , we thus mainly give the key formulas and defer the details into the Appendix VI C.

The 1RSB ansatz assumes that the space of configurations splits into states. Consequently replicas are not symmetric anymore and instead n replicas are organized in n m groups containing m replicas each:

∀(a, b) ∈ [1 : n] × [1 : n], 1 N (w a • w b ) =      q 1 if a,b belong to the same state, q 0 if a,b do not belong to the same state, Q = 1 if a = b . (18)
Following [START_REF] Monasson | Structural glass transition and the entropy of the metastable states[END_REF] , the partition function Z m associated to m replicas falling in the same state is expressed as a sum over all possible states Ψ weighted by their corresponding free entropy φ:

Z m = {Ψ} exp(N mφ(Ψ)) = {φ} N φ exp(N mφ) = {φ} exp(N Σ(φ)) exp(N mφ) ∼ dφ exp(N (mφ + Σ(φ)) ,
where we introduced the number of states at a given free entropy φ: N φ ≡ exp(N Σ(φ)) and the complexity Σ(φ), also called the configurational entropy.

Using the saddle point method in the N → ∞ limit, the 1RSB replicated free entropy Φ 1RSB is written as a function of the Parisi parameter m, the free entropy φ and the complexity Σ(φ):

Φ 1RSB (m, α) ≡ lim N →∞ 1 N E X [log(Z m (X))] = mφ + Σ(φ) . ( 19
)
Injecting the 1RSB ansatz eq. ( 18) in the replica derivation eq. ( 14), the 1RSB replicated free entropy Φ 1RSB is written as a saddle point equation over q = (q 0 , q 1 ) and q = (q 0 , q1 ) (see Appendix VI C):

Φ 1RSB (m, α) = SP q,q m 2 (q 1 q1 -1) + m 2 2 (q 0 q0 -q 1 q1 ) + mI w 1RSB (q) + αmI z 1RSB (q) ( 20
)
with

   I w 1RSB (q) = 1 m Dt 0 log Dt 1 g w 0 (t, q) m , I z 1RSB (q) = 1 m Dt 0 log Dt 1 f z 0 (t, q) m ,
denoting t = (t 0 , t 1 ), and for i ∈ AE:

     g w i (t, q) = dw w i P w (w) exp (1-q1) 2 w 2 + √ q0 t 0 + √ q1 -q0 t 1 w , f z i (t, q) = Dz z i ϕ( √ q 0 t 0 + √ q 1 -q 0 t 1 + √ 1 -q 1 z) . ( 21
)
Taking the derivative of Φ 1RSB with respect to m, the free entropy φ and complexity Σ can be written as:

       φ(α) = ∂Φ1RSB(m,α) ∂m = SP q,q 1 2 (q 1 q1 -1) + m (q 0 q0 -q 1 q1 ) + J w 1RSB (q) + αJ z 1RSB (q) , Σ(φ) = Φ 1RSB -mφ = SP q,q m 2 2 (q 1 q1 -q 0 q0 ) + m(I w 1RSB -J w 1RSB )(q) + mα(I z 1RSB -J z 1RSB )(q) , (22)
with

     J w 1RSB (q) = ∂(mI w 1RSB ) ∂m = Dt 0 Dt1 log(g w 0 (t,q))g w 0 (t,q) m Dt1g w 0 (t,q) m , J z 1RSB (q) = ∂(mI z 1RSB ) ∂m = Dt 0 Dt1 log(f z 0 (t,q))f z 0 (t,q) m Dt1f z 0 (t,q) m .

E. 1RSB results for UBP

From now on we only consider the u-function binary perceptron, whose RS solution is unstable for K > K * . The Parisi parameter m is fixed to its equilibrium value by maximizing the total entropy in the SAT phase, φ tot = φ + Σ(φ), under the constraint that the free entropy and complexity are both positive φ ≥ 0 and Σ(φ) ≥ 0:

m eq = max m|φ≥0,Σ≥0 φ + Σ(φ) .
Using the expressions eq. ( 22) and varying the Parisi parameter m ∈ [0; 1], we obtain the curve of the complexity Σ(φ) as shown in fig. 7. At m = 1, the complexity is negative. Decreasing m, complexity increases and becomes positive at the value m eq . Besides for small values of m, an unphysical (convex) branch appears, as commonly observed in other systems solved by the replica method.

We note that at α increases both the equilibrium complexity and free entropy decrease. In constraint satisfaction problems such as K-satisfiability or random graph coloring the mechanism in which the satisfiability threshold appears is that the maximum of the complexity becomes negative. In the present UBP problem it is actually both the free entropy and the complexity that vanish together, as illustrated in fig. 7. Complexity reaches Σ = 0 (black dot) at meq. For K = 1.5 and α = 0.33 a) the free-entropy corresponding to meq is positive φeq > 0, whereas for α = 0.34 b) the free entropy at meq is negative φeq < 0 and therefore there is no part of the curve where both complexity and free entropy are positive: thus this value of α is beyond the 1RSB storage capacity, and the capacity is in the interval [0.33; 0.34].

Computing the equilibrium value m eq (α), we have access to the corresponding equilibrium overlaps q * 0 and q * 1 , that we may compare with the RS solution q RS . All these are depicted in fig. 8. We also compute the 1RSB entropy φ u 1RSB ≤ φ u RS which vanishes at the 1RSB capacity α u 1RSB as depicted in fig. 9a. The 1RSB solution provides a small correction to the RS result for storage capacity, as illustrated in fig. 9b, where we plotted the difference between the annealed upper bound and the capacity for the RS and 1RSB solutions: α u aα u RS and α u aα u 1RSB . Overlaps at equilibrium q RS , q * 0 , q * 1 at K = 1.5

α u RS α u 1RSB α u AT m eq q RS q * 0 q * 1 0.0 0.2 0.4 0.6 0.8 1.0
Parisi parameter at equilibrium m eq FIG. 8. Equilibrium values of the overlap q * 0 = qRS, q * 1 and the Parisi parameter meq for the UBP at K = 1.5. For K < K * , the RS solution is stable and the only fixed point is q0 = q1 = qRS = 0. aα u 1RSB (orange) and the RS capacity α u aα u RS (blue). Below K * the RS solution is stable: RS and 1RSB entropies match exactly. Above K * , the RS solution is unstable: the 1RSB entropy deviates slightly from the RS solution.

F. 1RSB Stability

In the previous section we evaluated the 1RSB storage capacity of the u-function binary perceptron for K > K * . In this section we will argue that this cannot be an exact solution to the problem.

We could investigate the stability of 1RSB towards further levels of replica symmetry breaking along the same lines we did for the RS solution. However, in the present case we do not need to do that to see that the obtained solution cannot be correct. The explanations lies in the breaking of the up-down symmetry in the problem. This symmetry must either be broken explicitly as in the ferromagnet, where the system would acquire an overall magnetization, but we have not observed any trace of this in the present problem. Or this up-down symmetry must be conserved in the final correct solution. The conservation of the up-down symmetry is manifested in the value q 0 = 0 in the replica symmetric phase. The fact that in the 1RSB solution evaluated above we do not observe q 0 = 0, but instead q 0 > 0 is a sign of the fact that we are evaluating a wrong solution. The only possible way to obtain an exact solution we foresee is to evaluate the full-step replica symmetry breaking with a continuity of overlaps q(x), the smallest one of them should be 0 in order to restore the up-down symmetry. We let the evaluation of the full-RSB for future work.

Finally let us note that the 1RSB solution obtained in the previous section can be interpreted as frozen-2RSB. In 2RSB we would have 3 kinds of overlaps, q 0 , q 1 and q 2 . In frozen 2RSB we would have q 2 = 1, q 1 = q 1RSB 1 , q 0 = q 1RSB 0 .

V. CONCLUSION

The step-function binary perceptron has thus far eluded a rigorous establishment of the conjectured storage capacity, eq. ( 2). This prediction is expected to be exact because of the frozen-1RSB nature of the problem [START_REF] Krauth | Storage capacity of memory networks with binary couplings[END_REF][START_REF] Wong | Entropy landscape of solutions in the binary perceptron problem[END_REF] . At the same time the work of 31 sheds light on the fact that the structure of the space of solutions is not fully described by the frozen-1RSB picture, and that rare dense and unfrozen regions exist and in fact are amenable to dynamical procedures searching for solutions. It remains to be understood how is it possible that the 1RSB calculation does not capture these dense unfrozen regions of solutions [START_REF] Baldassi | Subdominant dense clusters allow for simple learning and high computational performance in neural networks with discrete synapses[END_REF] . They do not dominate the equilibrium, but the RSB calculation is expected to describe rare events via their large deviations, which in this case it does not.

In this paper we focus on two cases of the binary perceptron with symmetric constraints, the rectangle binary perceptron and the u-function binary perceptron. We prove (up to a numerical assumption) using the second moment method that the storage capacity agrees in those cases with the annealed upper bound, except for the u-function binary perceptron for K > K * eq. (5). We analyze the 1RSB solution in that case and indeed obtain a lower prediction for the storage capacity. However, we do not expect the 1RSB to provide the exact solution because it does not respect the up-down symmetry of the problem. Though the precise nature of the satisfiable phase for the u-function binary perceptron for K > K * remains illusive, we can conjecture it is full-RSB [START_REF] Parisi | Infinite number of order parameters for spin-glasses[END_REF][START_REF] Parisi | A sequence of approximated solutions to the sk model for spin glasses[END_REF][START_REF] Parisi | The order parameter for spin glasses: a function on the interval 0-1[END_REF] . Establishing this rigorously would provide much deeper understanding and remains a challenging subject for future work.

We present here the replica computation for general prior distribution P w and constraint function ϕ. In order to compute the quenched average of the free entropy, we consider the partition function of n ∈ N identical copies of the initial system. Using the replica trick, and an analytical continuation, the averaged free entropy φ of the initial system reads:

φ(α) ≡ lim N →+∞ 1 N E X [log(Z(X))] = lim N →+∞ lim n→0 1 N ∂ log (E X [Z(X) n ]) ∂n , (23)
where the replicated partition function can be written as

E X [Z(X) n ] = dXP X (X)Z(X) n = dXP X (X) n a=1
dw a P w (w a ) dz a C(z a )δ(z a -Xw a ) ,

with the global constraint function

C(z) = M µ=1 ϕ(z µ ).
We suppose that inputs are iid distributed from P X N 0, 1 N . More precisely, for i, j

∈ [1 : N ], µ, ν ∈ [1 : M ], E X [X iµ X jν ] = 1 N δ µν δ ij . Hence z a µ = N i=1 X iµ w a i is the sum of iid random variables. The central limit theorem insures that z a µ ∼ N E X [z a µ ], E X [z a µ z b µ ] ,
with two first moments:

E X [z a µ ] = N i=1 E X [X iµ ]w a i = 0 E X [z a µ z b µ ] = ij E X [X iµ X jµ ]w a i w b j = 1 N ij δ ij w a i w b j = 1 N N i=1 w a i w b i . (25)
In the following we introduce the symmetric overlap matrix

Q ≡ ( 1 N N i=1 w a i w b i ) a,
1 = dQ a≤b δ N Q ab - N i=1 w a i w b i = dQ d Q exp - N 2 T r(Q Q) exp 1 2 N i=1 w⊺ i Q wi ,
the replicated partition function becomes an integral over the matrix parameters Q and Q, that can be evaluated using Laplace method in the N → ∞ limit,

E X [Z(X) n ] = dQd Qe -N 1 2 Tr(Q Q)-log d wP w ( w)e 1 2 w⊺ Q w -α log( dzPz (z)C(z)) (26)
= dQd Qe -N Sn(Q, Q) ≃ N →∞ e -N •SP Q, Q{Sn (Q, Q)} , (27)
where SP states for saddle point and we defined

         S n (Q, Q) = 1 2 Tr(Q Q) -log(I w n ( Q)) -α log (I z n (Q)) I w n ( Q) = R n d wP w ( w)e 1 2
w⊺ Q w

I z n (Q) = R n dzP z (z)C(z). (28)
Finally, using eq. ( 23) and switching the two limits n → 0 and N → ∞, the quenched free entropy φ simplifies as a saddle point equation

φ(α) = -SP Q, Q lim n→0 ∂S n (Q, Q) ∂n , (29)
over general symmetric matrices Q and Q. In the following we will assume simple ansatz for these matrices that allows to get analytic expressions in n in order to take the derivative.

B. RS entropy

Let's compute the functional S n (Q, Q) appearing in the free entropy eq. ( 29) in the simplest ansatz: the Replica Symmetric ansatz. This later assumes that all replica remain equivalent with a common overlap q 0 = 1

Q =        Q q 0 ... q 0 q 0 Q ... ... ... ... ... q 0 q 0 ... q 0 Q        and Q =        Q q0 ... q0 q0 Q ... ... ... ... ... q0 q0 ... q0 Q       . (30)
Let's compute separately the terms involved in the functional S n (Q, Q) eq. ( 28): the first is a trace term, the second a term of prior I w n and finally the third a term depending on the constraint I z n . a. Trace term The trace term can be easily computed and takes the following form:

1 2 Tr(Q Q) RS = 1 2 nQ Q + n(n -1)q 0 q0 . (31)
b. Prior integral Evaluated at the RS fixed point, and using a gaussian identity also known as a Hubbard-Stratonovich transformation, the prior integral can be further simplified

I w n ( Q) RS = d wP w ( w)e 1 2 w⊺ Q w = d wP w ( w) exp ( Q -q0 ) 2 n a=1 ( wa ) 2 exp   q0 n a=1 wa 2   (32) = Dt dwP w (w) exp ( Q -q0 ) 2 w 2 + t q0 w n . (33)
c. Constraint integral Recall the vector z ∼ P z N (0, Q) follows a gaussian distribution with zero mean and covariance matrix Q. In the RS ansatz, the covariance can be rewritten as a linear combination of the identity I and J the matrix with all ones entries of size n × n: Q| RS = (Qq 0 )I + q 0 J, that allows to split the variable z a = √ q 0 t + √ Qq 0 u a with t ∼ N (0, 1) and ∀a, u a ∼ N (0, 1). Finally, the constraint integral reads:

I z n (Q)| RS = dzP z (z)C(z) = Dt n a=1 Du a ϕ √ q 0 t + Q -q 0 u a (34) = Dt Duϕ √ q 0 t + Q -q 0 u n . (35)
d. Summary and RS free entropy φ RS Finally putting pieces together, the functional S n taken at the RS fixed point has an explicit formula and dependency in n:

S n (Q, Q) RS = 1 2 Tr(Q Q) -log(I n w ( Q)) -α log (I n z (Q)) RS (36) ≃ n→0 1 2 nQ Q + n(n -1)q 0 q0 -n Dt log dwP w (w) exp ( Q -q0 ) 2 w 2 + t q0 w (37)
nα Dt log Duϕ y, √ q 0 t + Qq 0 u .

Finally taking the derivative with respect to n and the n → 0 limit, the RS free entropy has a simple expression

φ RS (α) = SP q0,q0 - 1 2 Q Q + 1 2 q 0 q0 + I w RS (q 0 ) + αI z RS (q 0 ) , (39)
with Q = Q = 1 and the following notations,

     I w RS (q 0 ) ≡ Dt log dwP w (w) exp ( Q-q0) 2 w 2 + t √ q0 w I z RS (q 0 ) ≡ Dt log Dzϕ √ q 0 t + √ Q -q 0 z . (40)

C. 1RSB entropy

The free entropy eq. ( 23) can also be evaluated at the simplest non trivial fixed point: the one step Replica Symmetry Breaking ansatz (1RSB). Instead assuming that replicas are equivalent, it assumes that the symmetry between replica is broken and that replicas are clustered in different states, with inner overlap q 1 and outer overlap q 0 . Translating this in a matrix formulation, the matrices can be expressed as

Q = q 0 J n + (q 1 -q 0 ) I n m ⊗ J m + (Q -q 1 ) I n and Q = q0 J n + (q 1 -q0 ) I n m ⊗ J m + Q -q1 I n . (41)
a. Trace term Again, the trace term can be easily computed

1 2 Tr(Q Q) 1RSB = 1 2 nQ Q + n(m -1)q 1 q1 + n(n -m)q 0 q0 . (42)
b. Prior integral Separating replicas with different overlaps, the prior integral can be written as

I w n ( Q) 1RSB = d wP w ( w)e ( Q-q1 ) 2 n a=1 ( wa ) 2 + ( q1 -q0 ) 2 n m k=1 km a,b=(k-1)m+1 wa wb + q0 2 ( n a=1 wa ) 2 (43) = Dt 0 Dt 1 dwP w (w) exp ( Q -q1 ) 2 w 2 + q0 t 0 + q1 -q0 t 1 w m n m (44)
c. Constraint integral Again the vector z ∼ P z N (0, Q) follows a gaussian vector with zero mean and covariance Q| 1RSB = q 0 J n + (q 1q 0 ) I n m ⊗ J m + (Qq 1 ) I n . The gaussian vector of covariance Q| 1RSB can be decomposed in a sum of normal gaussian vectors t 0 ∼ N (0, 1), ∀k ∈ [1 : n m ], t k ∼ N (0, 1) and ∀a ∈ [(k -1)m + 1 : km], u a ∼ N (0, 1):

z a = √ q 0 t 0 + √ q 1 -q 0 t k + √ Q -q 1 u a .
Finally the constraint integral reads

I z n (Q)| 1RSB = Dt 0 n m k=1 Dt k km a=(k-1)m+1 Du a ϕ( √ q 0 t 0 + √ q 1 -q 0 t k + Q -q 1 u a ) (45) = Dt 0 Dt 1 Duϕ( √ q 0 t 0 + √ q 1 -q 0 t 1 + Q -q 1 u) m n m . (46)
2. Existence and stability of the RS fixed point (q0, q0) = (0, 0)

We provide an alternative approach to get the instability condition of the RS solution for symmetric prior and constraint. In this symmetric case, the stability can be derived from the existence and stability of the symmetric fixed point (q 0 , q0 ) = (0, 0). Let's define

     F (q 0 ) ≡ α Dt (f z 1 ) 2 -2t √ q0f z 0 f z 1 +q0t 2 (f z 0 ) 2 (1-q0) 2 (f z 0 ) 2 (t, q 0 ) , G(q 0 ) ≡ Dt g w 2 -tq -1/2 0 g w 1 g w 0 (t, q0 ) , with    f z i (y) ≡ Dzz i ϕ(z) , gw i ≡ dww i P w (w)e w 2
2 .

(58)

In fact the saddle point equations at the RS fixed point eq. ( 15) can be written using the functions F, G, and can be reduced to a single fixed point equation over q 0 :

   q 0 = G(q 0 ) , q0 = F (q 0 ) , ⇒ q 0 = G • F (q 0 ) ≡ H(q 0 ) . (59)
As stressed above, the RS stability is equivalent to the existence and stability of the fixed point q 0 = 0. According to that, let's compute the stability of the above fixed point equation eq. ( 59). Computing F, F ′ , G, G ′ in the limit (q 0 , q0 ) → (0, 0), expanding {f z i ,g w i } i as functions of { f z i , gw i } i and finally using the symmetry that implies f z 1 = 0 and gw

1 = 0:                              F (q 0 ) = q0→0 α f z 1 f z 0 2 + q 0 ( f z 2 -f z 0 ) 2 ( f z 0 ) 2 + 3 ( f z 1 ) 4 ( f z 0 ) 4 -4 ( f z 1 ) 2 ( f z 2 -f z 0 ) ( f z 0 ) 3 + O(q 2 0 ) ∼αq 0 f z 2 -f z 0 f z 0 2 -→ q0→0 0 , ∂F ∂q0 (q 0 ) = q0→0 α f z 2 -f z 0 f z 0 2 + f z 1 f z 0 2 3 ( f z 1 ) 2 ( f z 0 ) 2 -4 ( f z 2 -f z 0 ) f z 0 + O(q 0 ) -→ q0→0 α f z 2 -f z 0 f z 0 2 , G(q 0 ) =
E. Moments at finite temperature

In this section we generalize the definition of the partition function for any temperature T . The energy of a configuration w is defined as the number of unsatisfied constraints and the corresponding partition function is defined by Z(X, T ) =

w∈{±1} N e -E(w)/T . In particular for the rectangle and u-function constraints, the partition functions at temperature T read Z r (X, T ) =

We define the probabilities that constraints are satisfied at temperature T :

              
p r,K,T ≡ Dze

and this derivation holds similarly for the step and u-function.

where we defined q r,K,T the probability that two standard Gaussians with correlation β are both at most K in absolute value at temperature T . Defining ρ(β) = 1 -2β and The derivative of each integral involved in eq. ( 71) can be easily computed as (72)

I α2,
∂ β I α2,
Hence taking the derivative of each term of the form I α2,β2 α1,β1 and simplifying it, the probability q r,K,T reads: q r,K,T (β) = - ±∞ .

½

  |zµ(1)|≤K = 2 N p αN r,K = exp(N (log(2) + α log(p r,K ))) = exp(N ǫ log(p r,K )) → 0 as N → ∞ . B. Second moment lower bound Proposition 6.

FIG. 1 . 1 2

 11 FIG. 1. Second moment entropy densities. a): the rectangle binary perceptron for α ≤ α r a = 1.816 (dashed pink), β = 1 2 is the global maximizer. For α ≥ α r a , β = 0 and β = 1 are the maximizers. b): the u-function binary perceptron for α ≤ α * = 0.430, β = 12 is the maximizer while for α * ≤ α ≤ α u a = 0.604 (dashed yellow), the maximizer is non-trivial β = 0.

  FIG.2. a) Density of the annealed entropy of solutions at overlap β from a random solution in the rectangle binary perceptron at K = 1, α = 1.80 ≤ α r c (K = 1). We see there are no solution in an interval of overlaps (1dmin, 1ǫ). This curve is obtained from the second moment entropy and contiguity between the random and planted ensembles. It implies the frozen-1RSB nature of the space of solutions. The same holds for the u-function. b) To compare we plot the density of the annealed entropy of solutions at overlap β from a random solution in the k-NAE SAT model 26 at k = 7, α = 40. We see the density is positive in a large region close to β = 1, showing the absence of frozen-1RSB structure in this problem.

FIG. 3 .

 3 FIG. 3. Illustration of the configuration space for the different phases: a): RS -solutions are concentrated in a single cluster of typical size 1 -qRS. b): 1RSB -solutions form clusters of size 1 -q1 at a distance 1 -q0 from each other. c): f1RSBclusters are point-like (1 -q1 ≃ 0) at a distance 1 -q0 = 1 -qRS from each other.

  FIG. 4.Step binary perceptron (SBP): the RS capacity α s RS (black) does not match the annealed capacity α s a (blue) and is always below the AT-line α s AT (orange). The AT-line is closest to the annealed capacity for Kmin ≃ 3.62 where the difference α s ATα s a ≃ 0.0012. For K = 0, we retrieve well known results 2 : α r RS ≃ 0.833, α r AT ≃ 1.015 and α r a = 1. The left and right hand sides, and the inset, represent the same data on different scales. The satisfiable (SAT) phase is represented by the beige shaded area and is located below the RS capacity, while the unsatisfiable (UNSAT) starts at the capacity (black line) and extends for a larger number of constraints.

FIG. 5 .

 5 FIG. 5. Rectangle binary perceptron (RBP): the RS capacity α rRS (black) matches the annealed bound α r a (blue), and the RS solution is locally stable for all K: α r RS < α r AT . The AT-line (orange) is closest to the annealed capacity for Kmin ≃ 1.24 where the difference α s ATα s a ≃ 0.15. The left and right hand sides, and the inset, represent the same data on different scales. The satisfiable (SAT) phase is represented by the beige shaded area and is located below the RS capacity, while the unsatisfiable (UNSAT) starts at the capacity (black line) and extends for a larger number of constraints.

FIG. 7 .

 7 FIG.7. Complexity Σ(φ) as a function of the free entropy φ for the u-function binary perceptron at K = 1.5 > K * . Complexity reaches Σ = 0 (black dot) at meq. For K = 1.5 and α = 0.33 a) the free-entropy corresponding to meq is positive φeq > 0, whereas for α = 0.34 b) the free entropy at meq is negative φeq < 0 and therefore there is no part of the curve where both complexity and free entropy are positive: thus this value of α is beyond the 1RSB storage capacity, and the capacity is in the interval [0.33; 0.34].

FIG. 9 .

 9 FIG.9. a): Comparison of the RS (blue) and 1RSB (orange) entropy for the UBP at K = 1.5. For α < αAT ≃ 0.118, RS and 1RSB entropies are equalled. For α > αAT, 1RSB entropy deviates slightly of the RS entropy before vanishing respectively at α u 1RSB ≃ 0.337 and α u RS ≃ 0.334. The inset represents the same data on a different scale. b): Difference between the annealed upper bound and the 1RSB capacity α u aα u 1RSB (orange) and the RS capacity α u aα u RS (blue). Below K * the RS solution is stable: RS and 1RSB entropies match exactly. Above K * , the RS solution is unstable: the 1RSB entropy deviates slightly from the RS solution.

  b=1..n . Define zµ ≡ (z a µ ) a=1..n and wi ≡ (w a i ) a=1..n . zµ follows a multivariate gaussian distribution zµ ∼ P z N (0, Q) and P w ( w) = n a=1 [δ( wa -1) + δ( wa + 1)]. Introducing the change of variable and the Fourier representation of the δ-Dirac function that involves a new parameter Q:

  a = b and a norm Q = 1 N N i=1 w a i w a i , leading to the following expressions of the matrices Q and Q ∈ R n×n :

1 ≡

 1 existence and stability conditions of the fixed point (q 0 , q0 ) = (0, 0) translate as an explicit condition over α that defines α AT α AT .

1 T 1 - 1 T 1 -

 1111 ½ z µ (w) ≤K and Z u (X, T ) = ½ z µ (w) ≥K .

- 1 T 1 - 1 T 1 - 1 T 1 -= 2

 1111112 ½ |z|≤K = e -1 T + (1e -1 T )p r,K , p u,K,T ≡ Dze -½ |z|≥K = e -1 T + (1e -1 T )p u,K , p s,K,T ≡ Dze -½ z ≥ K = e -1 T + (1e -1 T )p s,K .(63)1. First moment at finite temperature Let E r (N, M, T ) the event that Z r (X, T ) ≥ 1. Let's compute the first moment in the rectangle case, P[E r (N, αN, T )] ≤ E[Z r (X(N, αN ), T )] = 2 N E N p αN r,K,T = exp(N (log(2) + α log(p r,K,T ))) .

2 . 1 T 1 - 1 T 1 - 1 T 1 -

 2111111 Second moment at finite temperature Again we show the computation for the rectangle and it can be done similarly for the u-function.a. Expression of F r,K,α,T E[Z r (X(N, αN ), T ) 2 ] = w1,w2∈{±1} N ½ z µ (w 1 ) ≤K e -½ z µ (w 2 ) ≤K ½ z µ (1) ≤K + 1-½ z µ (w) ≤K K,T (l/N ) αN ≡ exp(N (log(2) + F r,K,α,T )) ,

2 dydxe -y 2 +x 2 2 , 2 dxdy e - 1 2 1 T 1 - 1 TI+ e - 2 TI

 22211112 (69) the function F r,K,α,T at finite temperature can be writtenF r,K,α,T = H(β) + α log q r,K,T (β) , where q r,K,T (β) ≡ Ê (x 2 +y 2 +2ρ(β)xy) 2π 1ρ(β) 2 e -½ z µ (1) ≤K + 1-½ z µ (w) ≤K (70) = I -K,K -K,K + e --K,K -∞,-K + I -K,K K,+∞ + I -∞,-∞,-K -∞,-K + I K,+∞ -∞,-K + I -∞,-K K,+∞ + I of ∂ β F r,K,α,TTo compute the derivative of q r,K,T , we first introduce G

  β2 α1,β1 (ρ(β)) = -1 4(β(1β)) 3/2 G α2,β2 β1 -G α2,β2 α1 (ρ(β)) .

1 4 ( 2 dxdy e - 1 2 1 T 1 -

 42111 β(1β)) 3/2 G -K,K K -G -K,K -K (ρ)(1e -1/T ) 2 = (1e -1/T ) 2 π β(1β) e -K 2 2(1-β) e (2β-1)K 2 2(1-β)β -1 .In the end, the derivative of the second moment can be evaluated for β = 0 and β = 1 at all temperature T : of ∂ β F u,K,α,T Adapting the previous steps and usingq u,K,T (β) ≡ Ê (x 2 +y 2 +2ρ(β)xy) 2π 1ρ(β) 2 e -½ z µ (1) ≤K + 1-½ z µ (w) ≤K = I -∞,-K -∞,-K + I K,+∞ -∞,-K + I -∞,-K K,+∞ + I K,+∞ K,+∞ + e -1 T I -K,K -∞,-K + I -K,K K,+∞ + I -∞,-K -K,K + I K,+∞ -K,K + e -2 T I -K,K -K,K = q r,K,-T e -2 T ,and eq. (74) the derivative for the u-function is straightforward to compute and is given by ∂F u,K,α,T ∂β (

TABLE I .

 I This table summarizes results for storage capacity in binary perceptrons with different types of constraints. The result for canonical step-function is from 2 . The results for the rectangle and u-function are obtained in this paper.

ACKNOWLEDGEMENT

We thank Florent Krzakala, Joe Neeman, and Pierfrancesco Urbani for useful discussions. We acknowledge funding from the ERC under the European Unions Horizon 2020 Research and Innovation Programme Grant Agreement 714608-SMiLe. WP was supported in part by EPSRC grant EP/P009913/1.

d. Summary and 1RSB free entropy φ 1RSB Gathering the previous computations eq. (42, 44, 46), the functional S n evaluated at the 1RSB fixed point reads:

Let's introduce the replicated free entropy following [START_REF] Monasson | Structural glass transition and the entropy of the metastable states[END_REF] . We consider m reals replicas of the same system and we imagine we put a small field, that allows the m replicas to fall in the same state. The replicated free entropy is the free entropy corresponding to these m uncorrelated copies in the limit of zero coupling. To compute it, we consider n ′ = n m replicas. Denoting q = (q 0 , q 1 ) and q = (q 0 , q1 ), the replicated free entropy reads as m times the free entropy of n replicas with 1RSB structure:

with t = (t 0 , t 1 ), g w 0 and f z 0 defined in eq. ( 21) and

D. RS Stability 1. De Almeida Thouless RS Stability

The stability of a given saddle point ansatz is related to the positivity the hessian of the functional S n . This stability analysis has first been done by de Almeida Thouless and following [START_REF] Gardner | Optimal storage properties of neural network models[END_REF][START_REF] Engel | Statistical mechanics of learning[END_REF][START_REF] De Almeida | Stability of the Sherrington-Kirkpatrick solution of a spin glass model[END_REF] , replicons eigenvalues of the RS ansatz λ A 3 and λ B 3 can be expressed as functions of {g w i , f z i } 2 i=0 defined in eq. ( 16):

The instability AT-line is defined when the determinant of the hessian vanishes that translates as an implicit equation over α, where q 0 , q0 are solution of the saddle point equations eq. ( 15) at α = α AT :

However for α < α AT , (q 0 , q0 ) = (0, 0) is the only solution. Using { f z i , gw i } 2 i=0 defined eq. ( 58), this expression simplifies because of the symmetry of the prior distribution P w and the constraints ϕ in the rectangle and u-function cases. In fact the symmetry imposes f z 1 = 0 and gw 1 = 0 and the condition reads:


Nathan Michel
email: nathan.michel@onera.fr

Sorin Olaru
email: sorin.olaru@l2s.centralesupelec.fr

Sylvain Bertrand
email: sylvain.bertrand@onera.fr

Giorgio Valmorbida
email: giorgio.valmorbida@l2s.centralesupelec.fr

Didier Dumur
email: didier.dumur@centralesupelec.fr

Invariant Set Design for Constrained Discrete-Time Linear Systems with Bounded Matched Disturbance

Keywords: Invariant set, disturbance, state constraints, input constraints, nonlinear control

Invariant set theory has been recognized as an important tool for control design of constrained systems subject to disturbances. Indeed, for a given control law, entering an invariant set guarantees recursive state and input constraint satisfaction in closed-loop. This paper focuses on discrete-time linear systems subject to bounded matched additive disturbance. The problem of the joint synthesis of control laws and associated invariant sets that are optimized with regards to the state constraints is investigated. An interpolation method is used to enlarge the controllable region.

INTRODUCTION

Constrained control of dynamic systems in presence of disturbance faces two main challenges: the impact of the disturbances on the local behavior around a nominal equilibrium and the characterization of the controllable region. Both challenges have been addressed in several control design frameworks according to the tools and modelling assumptions: set theoretic methods [START_REF] Blanchini | Set invariance in control[END_REF]), interval based approaches [START_REF] Jaulin | Interval constraint propagation with application to bounded-error estimation[END_REF]), or robust Model Predictive Control [START_REF] Mayne | Robust model predictive control of constrained linear systems with bounded disturbances[END_REF]).

Set theoretic methods require a set description of the disturbances. A systematic way to assess the influence of disturbances is to compute invariant sets. Indeed, invariant sets are certificates for robust constraints satisfaction, recursive feasibility, and mitigation of the disturbances for a given control law [START_REF] Mayne | Constrained model predictive control: Stability and optimality[END_REF]). Such approaches have been studied in the context of model predictive control [START_REF] Mayne | Robust model predictive control of constrained linear systems with bounded disturbances[END_REF]), robust time-optimal control [START_REF] Mayne | Robust time-optimal control of constrained linear systems[END_REF]), or design of reference governors [START_REF] Falcone | A reference governor approach for constrained piecewise affine systems[END_REF]). A series of results regarding invariant set have been established for linear systems, with a linear control law, subject to additive bounded disturbance, see for example [START_REF] Kolmanovsky | Theory and computation of disturbance invariant sets for discretetime linear systems[END_REF]. Of particular interest is the so-called minimal Robust Positively Invariant (mRPI) set. It is defined as the smallest invariant set for a given disturbance set [START_REF] Rakovic | Invariant approximations of the minimal robust positively invariant set[END_REF]). It corresponds to the limit set of state trajectories for any sequence of disturbances. Characterization of the controllable region can also be addressed by set theoretic methods [START_REF] Blanchini | Set invariance in control[END_REF]; [START_REF] Mayne | Robust model predictive control of constrained linear systems with bounded disturbances[END_REF]). The set of interest for such controllability analysis is the largest invariant set respecting the constraints, denoted Maximal Robustly Positively Invariant (MRPI) set.

Previous work has focused on the joint synthesis of control laws and associated invariant sets tailored to state or input constraints [START_REF] Corradini | Sliding-mode control of discrete-time linear plants with input saturation: application to a twin-rotor system[END_REF]; [START_REF] Nguyen | Constrained control for uncertain systems: an interpolation based control approach[END_REF]; [START_REF] Tahir | Low-complexity polytopic invariant sets for linear systems subject to norm-bounded uncertainty[END_REF]; [START_REF] Rakovic | Optimized robust control invariance for linear discrete-time systems: Theoretical foundations[END_REF]; [START_REF] Michel | Invariant sets for discrete-time constrained linear systems using sliding mode approach[END_REF]). In [START_REF] Rakovic | Optimized robust control invariance for linear discrete-time systems: Theoretical foundations[END_REF], a characterization of families of robust control invariant sets, based on outer approximations of the mRPI set, is proposed. This characterization can be used to establish optimized invariant sets regarding the state and input constraints. The control design in [START_REF] Michel | Invariant sets for discrete-time constrained linear systems using sliding mode approach[END_REF] considers bounded matched additive disturbance and adopts a sliding mode strategy. The resulting control law is the linear feedback gain minimizing the mRPI projection in a predefined direction.

In this paper we extend the linear control law and associated invariant set design strategy of [START_REF] Michel | Invariant sets for discrete-time constrained linear systems using sliding mode approach[END_REF] to a larger class of state constraints, and we account for input constraints. The impact of the disturbances around the nominal equilibrium is further mitigated by relaxing the linear control structure, allowing for smaller invariant sets in the direction of the state constraints. An interpolationbased control design is then proposed to enlarge the controllable region.

The paper is organized as follows. Section 2 presents the class of system studied and important definitions. Section 3 introduces results on the design of invariant set tailored to the state constraints. Section 4 proposes an interpolation based method to enlarge the controllable region. Section 5 gives illustrative examples of the results. Finally, Section 6 draws conclusion and discusses perspectives.

Notation: For a positive integer p, define I p = {1, ..., p}.

For a vector

h ∈ R n , denote h i its i th element, de- fine ||h|| ∞ = max|h i |, i ∈ I n , and |h| = [|h 1 | ... |h n |] .
For two vectors x and y, x ≤ y (x < y) denotes the element-wise (strict) inequalities between their components. Define 1 p the vector of ones of dimension p. The i th power of a matrix A is denoted A i . The i th line of a matrix A is denoted A i . Define the set of invertible matrices

G n = {A ∈ R n×n | det(A) = 0}. The set of Schur matrices of dimension n is denoted C n . For a matrix A ∈ R m×n and a set X ⊆ R n , de- fine the set AX = {y ∈ R m | y = Ax, x ∈ X }. Given two sets A, B, define A ⊕ B = {a + b | a ∈ A, b ∈ B} and A B = {x | {x} ⊕ B ⊆ A}. The boundary of a set A is denoted ∂A.

PRELIMINARIES

Consider the following discrete-time linear time-invariant system

x + = Ax + B(u + w), B = 0 ⊥ n-m,m I m (1) where x ∈ R n is the state, u ∈ R m is the input, w ∈ W ⊆ R m is
an unknown bounded disturbance, and we assume that m < n. Note that any system x + = Āx + B(u + w) with rank( B) = m can be written as (1) with a linear change of coordinates. The system (1) is subject to the state and input constraints

x

∈ X = {x ∈ R n | |Hx| ≤ 1 p } , u ∈ U, (2)
where H ∈ R p×n , m ≤ p. The sets U and W are bounded polytopes containing the origin in their interior. This paper focuses on the stabilization of (1) to a neighborhood of the origin, characterized in terms of invariant set, along with the characterization of the controllable region.

The following definitions are based on invariant set theory [START_REF] Blanchini | Set invariance in control[END_REF]; [START_REF] Kolmanovsky | Theory and computation of disturbance invariant sets for discretetime linear systems[END_REF]). Definition 1. The set Z is said to be Robustly Controlled positively Invariant (RCI) for the system (1) and constraint set (X , U, W) if Z ⊆ X , and ∀x ∈ Z there exists u ∈ U such that Ax + B(u + w) ∈ Z, ∀w ∈ W.

In the following, an RCI set will refer to an RCI set for the system (1) and constraint set (X , U, W).

Given a state feedback control law

ν : R n → R m , we define the set X ν = {x ∈ X | ν(x) ∈ U} . Definition 2. A set Z ⊆ R n is said Robustly Positively Invariant (RPI) for the system x + = Ax + B(ν(x) + w) and constraint set (X ν , W), if Z ⊆ X ν , and ∀x ∈ Z, Ax + B(ν(x) + w) ∈ Z, ∀w ∈ W.
Remark 1. Note that an RPI set for the system x + = Ax+ Bν(x) + Bw and constraint set (X ν , W) is an RCI set. Likewise, from any RCI set Z it is possible to define a state feedback ν : Z → U such that Z is an RPI set for the system x + = Ax + Bν(x) + Bw and constraint set (X ν , W) (see [START_REF] Rakovic | Optimized robust control invariance for linear discrete-time systems: Theoretical foundations[END_REF]).

The following definitions consider a linear state feedback law ν(x) = Kx, and we define the polytopic set X K = {x ∈ X | Kx ∈ U} . Definition 3. The Maximal Robustly Positively Invariant (MRPI) set for the system x + = (A + BK)x + Bw and constraint set (X K , W) is defined as the RPI set containing all the RPI sets, denoted here O ∞ (K). Definition 4. The minimal Robust Positively Invariant (mRPI) set for the system x + = (A + BK)x + Bw and constraint set (X K , W) is defined as the RPI set contained in any closed RPI set.

If A + BK is Schur, the mRPI for the system x + = (A + BK)x + Bw and constraint set (R n , W) exists, is unique, compact and contains the origin in its interior. Moreover, it is given by the following infinite Minkowski sum

Z ∞ (K) = ∞ i=0 (A + BK) i BW.
An RPI for the system

x + = (A + BK)x + Bw and constraint set (X ν , W) exists if and only if Z ∞ (K) ⊆ X K . Remark 2.
In general, we do not have an explicit characterization of the set Z ∞ (K). For computational purposes, polytopic outer approximations of this set are sought [START_REF] Olaru | Positive invariant sets for fault tolerant multisensor control schemes[END_REF]; [START_REF] Rakovic | Invariant approximations of the minimal robust positively invariant set[END_REF]).

The local behavior around the origin can be characterized in terms of RCI sets, or RPI sets and their associated control law. In this paper, we want to design a local control law that mitigates the impact of the disturbances on the state constraints satisfaction. Hence, our goal is to design a control law and an associated RPI set, or an RCI set, that is minimal in the direction of the state constraints. To this local control strategy we add an interpolation-based control design to enlarge the controllable region.

A measure to evaluate the minimality of invariant sets with regards to the state constraints is introduced in the following section.

INVARIANT SET DESIGN

The criterion for the design of RCI sets Z is the minimization of

h(Z, H) = max x∈Z ||Hx|| ∞ .
(3) Indeed, Z accounts for the impact of the disturbance, and H characterizes the direction of the state constraints. However, we do not have an explicit characterization of all the RCI sets for the system (1). The proposed approach is to first minimize (3) among mRPI obtained with linear control laws, which is a choice for the computation of RPI sets using existing methods [START_REF] Olaru | Positive invariant sets for fault tolerant multisensor control schemes[END_REF]; [START_REF] Rakovic | Invariant approximations of the minimal robust positively invariant set[END_REF]). The linear control structure is then relaxed to construct a decreasing sequence of RCI sets starting from this mRPI.

The computation of a feedback gain leading to an mRPI minimizing (3) is presented below and a strategy to further improve the solution by relaxing the linear control law structure is presented in Section 3.2.

Invariant set design using linear state feedback

We now briefly recall the results in [START_REF] Michel | Invariant sets for discrete-time constrained linear systems using sliding mode approach[END_REF] for the minimization of ( 3) with ( 1)-( 2), p = m and U = R m . The design method allows to compute the linear control law ν(x) = Kx whose mRPI set Z ∞ (K) minimizes (3) under the assumptions that the matrix

H = [H B ⊥ H B ] satisfies H B ∈ G m .
In this paper, we propose a strategy that extends the approach for the case p > m.

Let us consider the matrices H σi ∈ R m×n , i ∈ {1, ..., p m } as the matrices obtained from the combination of m distinct rows out of the p rows of H. Consider the partition of those matrices, H σi = [H σi,B ⊥ H σi,B ], and define the set

H = H σi , i ∈ {1, ..., p m } | H σi,B ∈ G m .
From every matrix H σi ∈ H we compute the linear control law ν σi (x) = K σi x with the method presented in [START_REF] Michel | Invariant sets for discrete-time constrained linear systems using sliding mode approach[END_REF]

that minimizes h(Z, H σi ) = max x∈Z ||H σi x|| ∞ . ( 4
)
Define the set

K = K σi , i ∈ 1, ..., p m | H σi ∈ H,K σi Z ∞ (K σi ) ⊆ U
This set contains the linear feedback gains K σi obtained from the matrices H σi ∈ H, and such that Z ∞ (K σi ) is an RPI set for the system (1) and constraint set (X , U, W).

If the set K is non-empty, we chose the element minimizing (3), that is

K = arg min Kσ i ∈K max x∈Z∞(Kσ i ) ||Hx|| ∞ . ( 5
)
Using these elements we are able to state the following result.

Proposition 1. If Z ∞ (K) ⊆ X , then robust asymptotic stability of the set Z ∞ (K) is achieved with a region of attraction O ∞ (K). Additionally, the finite determination of O ∞ (K) is guaranteed.
The strategy presented here allows to take the state constraints into account in the design of a linear feedback gain and construct the associated mRPI in a direct manner by exploiting the matched properties of the disturbance. If the set K is empty, alternative design strategies based on the complete characterization of the RCI sets taking into account input constraints are to be sought [START_REF] Nguyen | Constrained control for uncertain systems: an interpolation based control approach[END_REF]; [START_REF] Rakovic | Optimized robust control invariance for linear discrete-time systems: Theoretical foundations[END_REF]; [START_REF] Tahir | Low-complexity polytopic invariant sets for linear systems subject to norm-bounded uncertainty[END_REF]).

In the next section we propose to improve the solution proposed in this section by relaxing the linear control structure and allowing for nonlinear control policies.

Refinement of RCI sets with nonlinear control laws

In the previous section we imposed a linear structure to the control law in the design of an RPI set. We now propose an optimization-based method to obtain a decreasing sequence of RCI sets with nonlinear control policies starting from a polytopic RCI set.

Let Ω 0 be a polytopic RCI set. We consider the control law ν 0 : Ω 0 → U :

ν 0 (x) = arg minimize u α subject to Ax + Bu ∈ Ω 0 BW (6) H(Ax + Bu) ∈ αH(Ω 0 BW) u ∈ U (7) 0 ≤ α ≤ 1 (8)
which, thanks to ( 6), (7), and (8), satisfies ∀x ∈ Ω 0 , Ax + Bν 0 (x) ∈ Ω 0 BW, ν 0 (x) ∈ U. The above definition of ν 0 seeks to minimize the scaling factor α in the direction of the state constraints defined by the matrix H as in (2). From the definition of an RCI set, the feasible domain of the above optimization problem is guaranteed to be non-empty. Note that the above optimization problem is convex (convex constraints and linear cost function).

We then define the set Ω 1 as

Ω 1 = ConvexHull {Av + Bν 0 (v), v ∈ V(Ω 0 )} ⊕ BW. By construction, the set Ω 1 is polytopic, satisfies Ω 1 ⊆ Ω 0 ,
and is an RPI set for the system x + = Ax + Bν 0 (x) + Bw and constraint set (X ν0 , W). Remark 3. Note that the image set, namely

{z ∈ R n | z = Ax + Bν 0 (x) + Bw, x ∈ Ω 0 , w ∈ W} might not be convex.
Likewise, we can define a sequence of polytopic RCI sets Ω i , i ∈ N, as

Ω i+1 = ConvexHull {Av + Bν i (v), v ∈ V(Ω i )}⊕BW, i ∈ N, where ν i (x) = arg minimize u α subject to Ax + Bu ∈ Ω i BW H(Ax + Bu) ∈ αH(Ω i BW) u ∈ U 0 ≤ α ≤ 1.
By construction, we have ∀i ∈ N, ∀j ∈ N, Ω i+j ⊆ Ω i , thus the objective (3) decreases (not strictly) as i increases.

Let k ∈ N, and let Ω = Ω k . Consider the following control law ν : Ω 0 → U:

ν(x) = ν k (x), x ∈ Ω k , (9a) ν(x) = ν i (x), x ∈ Ω i \Ω i+1 , i ∈ {0, ..., k -1}, (9b) ν(x) = ν 0 (x), x ∈ Ω 0 . ( 9c
)
For all x ∈ Ω 0 , finite time convergence to Ω is guaranteed.

Indeed, if x ∈ Ω i , i ∈ I k-1 , x + = Ax + Bν(x) + Bw ∈ Ω i+1 , ∀w ∈ W.
We have presented a method to construct, starting from a polytopic RCI set, a decreasing sequence of polytopic RCI sets that aims at minimizing (3).

In the following section we define the control law ν(x) outside of the set Ω 0 using interpolation-based methods to extend the controllable region.

ENLARGEMENT OF THE CONTROLLABLE REGION

The previous section focused on the behavior of the system in a neighborhood around the origin. The proposed control law is defined locally. We now propose a method to enlarge the controllable region using interpolation-based control.

Let K be the stabilizing gain as given in ( 5), Ω 0 be a polytopic outer approximation of the mRPI Z ∞ (K), and Ω = Ω k for a given k ∈ N, the k th element of the decreasing polytopic RCI sets sequence starting from Ω 0 as defined in Section 3.2.

A first step to enlarge the basin of attraction is to define the control law on the set O ∞ (K)\Ω 0 as ν(x) = Kx, x ∈ O ∞ (K)\Ω 0 .

(10) Indeed, any element of O ∞ (K)\Ω 0 is robustly steered to Ω 0 with the linear control law u = Kx.

The definition of the control law outside of O ∞ (K) proposed here relies on the existence of L-1 stabilizing control laws u j (x), j ∈ {2, ..., L} and associated RPI sets X j ⊆ X , j ∈ {2, ..., L}. That is ∀j ∈ {2, ..., L}, ∀x ∈ X j , u j (x) ∈ U, Ax + B(u j (x) + w) ∈ X j , ∀w ∈ W. We denote u 1 (x) the control law given by ( 9) and ( 10), and X 1 = O ∞ (K). Remark 4. The sets X j , j = {2, ..., L} are assumed to be convex and compact. This assumption is not restrictive provided Conv{X j } is an admissible convex RPI set.

Several methods to design the pairs u j (x), X j exist in the literature. Among those, we can cite • an LMI-based method to compute the invariant ellipsoid E(x 0 ), and the associated feedback gain u = K x0 x, that contains the most important extension on a direction defined by a reference point [START_REF] Nguyen | Constrained control for uncertain systems: an interpolation based control approach[END_REF]). This is of particular interest to enlarge the basin of attraction in specific directions. • Tube-based Model Predictive Control [START_REF] Mayne | Robust output feedback model predictive control of constrained linear systems[END_REF]).

Let us now define X ch = Conv ({X j , j ∈ I L }) .

Any point x ∈ X ch can be written x = L j=1 λ j x j , with L j=1 λ j = 1, λ j ≥ 0, x j ∈ X j , ∀j ∈ I L . Remark 5. The above expression of x is not unique.

By denoting xj = λ j x j , we have x = L j=1 xj and xj ∈ λ j X j . To perform a selection among the feasible λ j and xj at each time-step, we minimize online the following linear cost function subject to convex constraints

minimize λj ,xj ,j∈I L -λ 1 (11) subject to x = L j=1 xj xj ∈ λ j X j , ∀j ∈ I L λ j ≥ 0, ∀j ∈ I L L j=1 λ j = 1
Let us denote (x * j (x), λ * j (x)), j ∈ I L the solution of (11) for the state x, and define for all j ∈ I L ,

x * j (x) = x * j (x) λ * j (x) , if λ * j = 0,
x * j (x) = 0, if λ * j = 0. The dependency on x will be dropped for clarity purpose. We use this selection to define the control law ν :

X ch → U, ν(x) = L j=1 λ * j u j (x * j ). (12)
Note that ∀x ∈ X 1 , ν(x) = u 1 (x). We have the following result regarding the above control law. Proposition 2. The set X ch is an RPI set for the system x + = Ax + Bν(x) + Bw and constraint set (X ν , W).

Proof. Let x ∈ X ch and w ∈ W. We have

∀j ∈ I L , u j (x * j ) ∈ U, x * + j = Ax * j + Bu j (x * j ) + Bw ∈ X j . Moreover, x + satisfies x + = L j=1 λ * j Ax * j + Bu j (x * j ) + Bw = L j=1 λ * j x * + j . ( 13
)
Since the set U is convex, and by definition of the set X ch , we have ν(x) ∈ U, x + ∈ X ch . 2

In view of the stability analysis for the closed-loop system, we introduce the following positive definite function:

V (x) = 1 -λ * 1 (x).
Based on the constraints on the interpolation factors we have, ∀x ∈ X ch , 0 ≤ V (x) ≤ 1, and V (x) = 0 if and only if x ∈ X 1 . Proposition 3. The control law (12) ensures that the closed-loop system is robustly stable in the sense of Lyapunov (non-increase along the system trajectories) for all initial conditions x ∈ X ch .

Proof. From (13), ∀w ∈ W, the pairs (λ * j x * + j , λ * j ), j ∈ I L satisfy the constraints of the optimization problem (11) for the state x + .

Hence, ∀x ∈ X ch , ∀w ∈ W, V (x + ) ≤ 1 -λ * 1 (x) = V (x) 2 Let us introduce the following definition. Definition 5. (Robust Contractivity) A set S is α robustly contractive for the closed-loop system x + = f (x, w), w ∈ W if there exists 0 ≤ α < 1 such that ∀x ∈ S, ∀w ∈ W, x + ∈ αS.

The following assumption will be considered in view of the convergence analysis. Assumption 1. The sets X j , j ∈ I L are respectively α j robustly contractive for the closed-loop systems

x + = Ax+ B(u j (x) + w), w ∈ W.
Let us define α = max({α j , j ∈ I L }) in view of the following result. Proposition 4. The set X ch is α robustly contractive for the closed-loop system x + = Ax + Bν(x) + Bw, w ∈ W with ν(x) defined in (12) and under the conditions of the Assumption 1.

Proof. Let x ∈ X ch . From Assumption 1, we have, ∀j ∈ I L , ∀w ∈ W, x * + j = Ax * j + B(u j (x * j ) + w) ∈ α j X j ⊆ αX j . Hence, x + = L j=1 λ * j x * + j ∈ αX ch . 2 Proposition 5. The control law (12) ensures that the set X 1 is robustly asymptotically stable for all initial conditions x ∈ X ch .

Proof. First, let us prove that if V (x) = 1 then x ∈ ∂X ch .

Let us assume that x ∈ ∂X ch . Then, ∃ > 0 such that (1+ )x ∈ X ch . Moreover, X 1 has a non-empty interior, hence ∃δ > 0 such that δx ∈ X 1 .

Considering γ = min( , δ), we have concomitantly (1 + γ)x ∈ X ch , γx ∈ X 1 .

If γ ≥ 1, then δ ≥ 1 and it follows x ∈ X 1 , which leads to V (x) = 0. Else, if γ < 1 and we can rewrite x as x = (1 -γ)((1 + γ)x) + γ(γx), where (1 + γ)x ∈ X ch , γx ∈ X 1 , 0 < (1 -γ) < 1 and 0 < γ < 1. Hence we get V (x) ≤ 1 -γ < 1. We conclude that if V (x) = 1 then x ∈ ∂X ch .

Let w ∈ W. To prove robust asymptotic stability of the set X 1 , we consider three cases regarding the value of V (x).

Case 1: V (x) = 1. From Proposition 4, we have x + ∈ αX ch . Thus, V (x + ) < 1 = V (x).

Case 2: 0 < V (x) < 1. We have λ * 1 (x) > 0. Given that the set X 1 is α 1 robustly contractive, x * + 1 ∈ α 1 X 1 . Moreover, X 1 has an non-empty interior, hence ∃ > 0 such that x * + 1 + (x + -x * + 1 ) ∈ X 1 . Note that if ≥ 1, x + ∈ X 1 and thus V (x + ) = 0. Else, we denote

z 1 = x * + 1 + (x + -x * + 1 ) ∈ X 1 . ( 14
)
This leads to

x * + 1 = z 1 -x + 1 - . We can rewrite x + asx + = λ * 1 z 1 -x + 1 - + L j=2 λ * j x * + j . Hence, x + (1 + λ * 1 1 - ) = λ * 1 z 1 1 - + L j=2 λ * j x * + j
.This is equivalent to

x + = λ * 1 z 1 1 -(1 -λ * 1 ) + L j=2 λ * j (1 + λ * 1 1 - ) x * + j . From 0 < < 1, we have λ * 1 > λ * 1 1 -(1 -λ * 1 ) > 0.
Moreover, we can show that

λ * 1 1 -(1 -λ * 1 ) + L j=2 λ * j (1 + λ * 1 1 - ) = 1 and ∀j ∈ I L , λ * j (1 + λ * 1 1 - ) ≥ 0. This proves V (x + ) ≤ 1 - λ * 1 1 -(1 -λ * 1 ) < 1 -λ * 1 = V (x).
Case 3: V (x) = 0. The control action is given by ν(x) = u 1 (x) and it guarantees x + ∈ X 1 . Hence, V (x + ) = 0.

This proves robust asymptotic stability of the set X 1 for any initial condition x ∈ X ch . 2

We have proposed a design strategy to enlarge the controllability of the local control law defined in the previous section. Convergence properties have been established with regards to different assumptions on the sets considered for the interpolation-based control strategy.

SIMULATION RESULTS

The results presented in Section 3 and 4 are now illustrated. Consider the following system, constraints and disturbance set

x+ = Ax + B(u + w), A = 1 1 0 1 , B = 0 1 , X = x ∈ R 2 | |Hx| ≤ 1 3 , H = 0.375 0.25 0.1786 0.357 -0.25 0.25 , U = {u ∈ R | |u| ≤ 1.5} , W = {w ∈ R | |w| ≤ 0.
5} . In this exemple, p = 3, n = 2, and m = 1. The 1 × 3 submatrices of H verifying H ∈ H are H i , i = 1, 2, 3. We use the results in [START_REF] Michel | Invariant sets for discrete-time constrained linear systems using sliding mode approach[END_REF] to obtain the associated gains

K 1 = [-0.9 -1.9] , K 2 = [-0.5 -1.5] , K 3 = [-1.5 -2.5] .
In this scenario, it is possible to have an explicit representation of the sets Z ∞ (K i ) given the eigenstructure of the matrices A + BK i and the dimensions of the problem. We represent these sets and the state constraints in Figure 1

. Note that Z ∞ (K i ) ⊆ X , for all i ∈ {1, 2, 3}. We have K 1 Z ∞ (K 1 ) = [-1.2 ; 1.2] , K 2 Z ∞ (K 2 ) = [-1 ; 1] , K 3 Z ∞ (K 3 ) = [-3.5 ; 3.5] . For Z ∞ (K i ) to be an RPI set, it has to satisfy Z ∞ (K i ) ⊆ X and K i Z ∞ (K i ) ⊆ U.
Hence, the gain K 3 is not admissible. Moreover, we have

h(Z ∞ (K 1 ), H) = 0.44, h(Z ∞ (K 2 ), H) = 0.5.
The set Z ∞ (K 1 ) minimizes (3). Due to the dimension of the problem and the proposed approach, the refinement proposed Section 3 does not reduce the invariant set

(Ω 1 = Ω 0 = Z ∞ (K 1 )
). The MRPI of the feedback gains K 1 and K 2 are presented in Figure 2.

The method proposed in Section 4 to enlarge the controllable region O ∞ (K 1 ) = X 1 of the controller u 1 (x) = K 1 x has been tested in simulation. The control laws u j , j = 2, 3, 4 and the associated RPI sets X j , j = {2, 3, 4} have been obtained using Tube-Based MPC as presented in [START_REF] Mayne | Robust model predictive control of constrained linear systems with bounded disturbances[END_REF] with K tube,1 = K 2 , K tube,2 = [-0.61 -1.61] , K tube,3 = [-0.58 -1.55] , and a prediction horizon N = 10. The weight matrices Q, R, and P as defined in [START_REF] Mayne | Robust model predictive control of constrained linear systems with bounded disturbances[END_REF] do not impact the region of attraction of the tube-based MPC controllers. We also consider X 5 = O ∞ (K 2 ) and u 5 (x) = K 2 x.

The set X ch = Conv(X i , i = 1, ..., 5) can be seen in

CONCLUSION

We have proposed a control law for discrete-time linear systems subject to matched disturbances and input and state constraints. The proposed method allows to mitigate the impact of the disturbances in the direction of the state constraints in a neighborhood of the origin. The effect of the disturbances is assessed through invariant set. A first approach that imposes a linear structure to the control law is proposed. The control structure is then relaxed to further mitigate the impact of the disturbance on state constraints satisfaction, leading to smaller invariant sets in the constraints direction. To this local control strategy we add an interpolation-based control design to enlarge the controllable region.

  Figure 3. Trajectories emanating from ∂X ch and converging to Z ∞ (K 1 ) are represented in Figure 4.

Fig. 1 .

 1 Fig. 1. Z ∞ (K i ) for K 1 (red), K 2 (blue), and K 3 (yellow),and the state constraints X (black).

Fig. 2 .

 2 Fig. 2. The MRPI O ∞ (K i ) and the mRPI Z ∞ (K i ) for K 1 (left), and K 2 (right).

Fig. 3 .

 3 Fig. 3. The enlarged controllable region X ch (grey) and the initial MRPI O ∞ (K 1 ) (red).

Fig. 4 .

 4 Fig.4. The enlarged controllable region X ch (grey), the mRPI Z ∞ (K 1 ) (red), and trajectories initialized on several vertices of X ch .