Mickaël Rivier

Pietro Marco Congedo

Surrogate-Assisted Bounding-Box Approach for Optimization Problems with Tunable Objectives Fidelity

Keywords: Multi-objective optimization, Uncertainty-based optimization, Error Bounding-Boxes, Tunable fidelity, Surrogate-assisting strategy Optimisation multi-objectif, Optimisation sous incertitudes, Boîtes d'erreur conservatives, Fidélité adaptable, Assistance par modèle de substitution

In this work, we present a novel framework to perform multi-objective optimization when considering expensive objective functions computed with tunable fidelity. This case is typical in many engineering optimization problems, for example with simulators relying on Monte Carlo or on iterative solvers. The objectives can only be estimated, with an accuracy depending on the computational resources allocated by the user. We propose here a heuristic for allocating the resources efficiently to recover an accurate Pareto front at low computational cost. The approach is independent from the choice of the optimizer and overall very flexible for the user. The framework is based on the concept of Bounding-Box, where the estimation error can be regarded with the abstraction of an interval (in one-dimensional problems) or a product of intervals (in multi-dimensional problems) around the estimated value, naturally allowing the computation of an approximated Pareto front. This approach is then supplemented by the construction of a surrogate model on the estimated objective values. We first study the convergence of the approximated Pareto Front toward the true continuous one under some hypotheses. Secondly, a numerical algorithm is proposed and tested on several numerical test-cases.

Introduction

A key ingredient in any optimization method is the evaluation of the objective functions, which provides the metric to discriminate a good and feasible design, according to a set of objectives and constraints. In many real applications, the evaluation of the objective functions can be affected by a source of uncertainty, noise or error. A possible classification is presented in [START_REF] Yaochu | Evolutionary optimization in uncertain environments-a survey[END_REF], where four classes are identified: (i) noise, caused for example by sensor measurements or random simulations, (ii) uncertainty for robustness (or reliability) analysis, where the model/numerical method used to compute the objective functions includes stochastic variables, (iii) approximation error due to an approximate model of the exact objective functions and (iv) time-varying functions.

We focus here on a type of approximation error, which can, for example, arise in iterative or sampling-based computations. The exact objective values are the limits, which are estimated at a tunable cost and fidelity. A tunable fidelity does not mean that the user chooses a priori the fidelity of each objective, but rather that there is a way of increasing the fidelity of the blackbox computation at a given design. We consider all objectives to result from a single expensive solver, all objectives are then refined simultaneously each time the fidelity is increased. Ref. [START_REF] Picheny | Noisy Expected Improvement and on-line computation time allocation for the optimization of simulators with tunable fidelity[END_REF] introduced the idea of tunable fidelity and proposed an automated allocation strategy for mono-objective kriging-based optimizations.

The scope of the study presented here is to formulate a framework permitting to solve a multi-objective optimization efficiently with tunable objectives fidelity, independently from the choice of the optimizer. We target optimization problems linked to the resolution of an iterative solver. A non-exhaustive list includes the Gauss-Seidel method, Newton method, segregated approach, additive Schwarz technique, or computation of a sampling-based objective. The later notably covers uncertainty-based optimization, where the objectives are statistics approximated with Monte Carlo approaches, and more generally any optimization of expensive integrands [START_REF] Toscano-Palmerin | Bayesian optimization with expensive integrands[END_REF]. Note that the use of the concept of Pareto dominance limits the applicability of the proposed method to multi-objective optimization problems with two-three objectives. Many-objectives problems (more than three objectives) require dedicated techniques to discriminate between all non-dominated designs (see e.g. [START_REF] Ishibuchi | Evolutionary many-objective optimization: A short review[END_REF]).

Several techniques have been developed to cope with noise in objective values in the context of stochastic search algorithms. Review papers [START_REF] Yaochu | Evolutionary optimization in uncertain environments-a survey[END_REF][START_REF] Chen | Handling Uncertainties in Evolutionary Multi-Objective Optimization[END_REF] depicted the main methods to deal with uncertainties in an Evolutionary Algorithm (EA) environment, namely averaging, robust index selection or robustness measures. A robustness measure can be seen as a new fitness assessment, as in [START_REF] Barrico | Robustness analysis in multi-objective optimization using a degree of robustness concept[END_REF], or as an additional robustness index objective in [START_REF] Li | A multi-objective genetic algorithm for robust design optimization[END_REF]. Deb et al [START_REF] Deb | Introducing robustness in multi-objective optimization[END_REF] introduced two concepts of robustness, revising the objective function or applying an additional constraint on the problem. The main strategy to account for uncertainty on the objective functions is to use a probabilistic ranking of the individuals. The Stochastic Pareto Genetic Algorithm, developed in [START_REF] Eskandari | Handling uncertainty in evolutionary multiobjective optimization: Spga[END_REF], computes probabilistic dominations between individual, assuming normal distributions, and uses them for ranking. Hughes [START_REF] Hughes | Evolutionary Multi-objective Ranking with Uncertainty and Noise[END_REF] also assumes normal distributions and proposes a probabilistic extension of the Non-dominated Sorting Genetic Algorithm ranking. This work was then supplemented by [START_REF] Fieldsend | Multi-objective optimisation in the presence of uncertainty[END_REF] with a Bayesian learning of the variances of input noises. Teich [START_REF] Teich | Pareto-Front Exploration with Uncertain Objectives[END_REF] followed an idea similar to [START_REF] Hughes | Evolutionary Multi-objective Ranking with Uncertainty and Noise[END_REF] but with uniform distributions of the objective values. Other heuristics like Simulated Annealing and Pure Random Search have been developed in this context in [START_REF] David | Approximate implementations of pure random search in the presence of noise[END_REF] and [START_REF] Gutjahr | Simulated annealing for noisy cost functions[END_REF]. Model-based approaches have been applied to noisy optimization problems in [START_REF] Žilinskas | On similarities between two models of global optimization: statistical models and radial basis functions[END_REF]. Non-probabilistic interval uncertainties have been tackled through new dominance criteria in [START_REF] Gong | Evolutionary algorithms for multi-objective optimization problems with interval parameters[END_REF][START_REF] Limbourg | An optimization algorithm for imprecise multi-objective problem functions[END_REF], or with a worst case methodology in [START_REF] Soares | Interval robust multi-objective evolutionary algorithm[END_REF]. Epistemic uncertainties have also been treated by means of evidence theory in [START_REF] Du | Unified uncertainty analysis by the first order reliability method[END_REF][START_REF] Limbourg | Multi-objective Optimization of Problems with Epistemic Uncertainty[END_REF].

In the review of Mlakar et al. [START_REF] Mlakar | Comparing solutions under uncertainty in multiobjective optimization[END_REF], several techniques of optimization with approximated values have been compared. The authors introduce the concept of Bounding-Boxes, with an error regarded with the abstraction of an interval (in one-dimensional problems) or a product of intervals (in multi-dimensional problems) around the estimated value. They also introduce an extended concept of the Pareto dominance rule. In Fusi et al. [START_REF] Fusi | An adaptive strategy on the error of the objective functions for uncertainty-based derivative-free optimization[END_REF], these concepts have been used for online resource allocation in the context of robust and reliability-based optimization, where the objective functions are statistics of a quantity of interest. The Bounding-Box approach allows to tune the fidelity of the statistics computation depending on the closeness to the Pareto front.

The first contribution of this paper relies on providing some mathematical evidence about the convergence of the Bounding-Box approach for multi-objective optimization problem with adaptively tuned objective values. The work [START_REF] Fusi | An adaptive strategy on the error of the objective functions for uncertainty-based derivative-free optimization[END_REF] revealed that while substantial gains can be obtained in the early stages of the optimization, the convergence of the optimizer toward the Pareto front lessen the efficiency of the Bounding-Box approach. This behavior is due to the increasing number of efficient designs when the optimizer finds the optimal area.

For curing this issue, as a second contribution, we couple the Bounding-Box approach with a Surrogate-Assisting strategy. This should further reduce the computational cost, notably during the last iterations of the optimization process. In practice, the Bounding-Box approach can quickly drive the optimizer toward the Pareto optimal area, where the Surrogate-Assisting model could permit to increase the accuracy locally. Such acceleration strategies using surrogate models have been studied in the optimization context in [START_REF] Torzcon | Using approximations to accelerate engineering design optimization[END_REF], and notably within the Evolutionary Strategies ( [START_REF] Yaochu Jin | A framework for evolutionary optimization with approximate fitness functions[END_REF][START_REF] Yaochu | Surrogate-assisted evolutionary computation: Recent advances and future challenges[END_REF][START_REF] Emmerich | Metamodel-Assisted Evolution Strategies[END_REF][START_REF] Emmerich | Single-and multiobjective evolutionary optimization assisted by gaussian random field metamodels[END_REF][START_REF] Buche | Accelerating evolutionary algorithms with gaussian process fitness function models[END_REF]).

The aim of this paper is to introduce a framework called SABBa (Surrogate-Assisted Bounding-Box approach), and to provide mathematical and numerical evidence about its convergence properties. After explaining the strategy in Section 2, convergence of the Pareto front approximations is mathematically analyzed under several assumptions in Section 3. Then, the general pseudoalgorithm of the framework is presented in Section 4 and three analytical test-cases are fully analyzed in Section 5. Finally, conclusive remarks and future works are given in Section 6.

Overview of the SABBa framework

A multi-objective optimization problem can be stated as minimize/maximize: f (x) by changing:

x ∈ X (1)
where the m ≤ 3 objective functions are collected in a vector f ∈ R m and x ∈ X are the n design variables included in the design domain X ⊂ R n .

In this work, we assume that the objective functions f cannot be computed exactly, but only estimated. The associated error can be reduced through additional computational burden. These estimated objective values are denoted as f l (x) and associated to the error ε l (x), so that

f l (x) = f (x) -ε l (x).
Here the tilda refers to the approximation intrinsic to the objectives computation, which accuracy depends on the level of fidelity l. This work aims at formulating an adaptive strategy for choosing an optimal l for each visited x. Note then that l varies with respect to x, i.e. l(x). In the following, we decide to indicate the level of fidelity simply l and not l(x) to shorten the notation.

This section illustrates the SABBa framework, based on the coupling between the Bounding-Box approach and the Surrogate-Assisting strategy. The Bounding-Box approach rely on the definitions of Bounding-Boxes and the associated Pareto dominance, given in Sections 2.1 and Inria 2.2, respectively. This approach and the Surrogate-Assisting strategy are then described in Section 2.3 and 2.4. The flowchart of the framework is also illustrated.

Definition of a Bounding-Box in a multi-objective problem

As stated above, the objective functions are intrinsically subject to an error ε l (x), correlated with the level of fidelity l. We denote with ε l (x) a conservative estimation of this error, so that 1) is called a Box. It is denoted as B f l , ε l using the notation presented in the following Definition 1.

|ε l (x)| ≤ ε l (x), i.e. f ∈ f l -ε l , f l + ε l . This m-dimensional interval containing f (represented in Figure
f ε l 1 ε l 2 ε l 1 ε l 2 f l B f l , ε l
B(a, r) = b ∈ R m | b ∈ [a -r, a + r] ∈ ℘(R m ) ∀(a, r) ∈ R m × R m + ,
and with ℘(R m ) the power set of R m .

Remarks

• B(a, 0) ≡ a.

• To lighten the notation, with f : X → R m , we set:

B f (x, r) ≡ B f (x), r , ∀(x, r) ∈ X × R m .

Pareto dominance

In multi-objective optimization, objective functions are usually naturally conflicting, producing a set of trade-off optima. These designs are said Pareto-optimal and the ensemble is called the Pareto front. They are non-dominated according to the following Pareto dominance rule: ∀j ∈ 1, m , the symbol ± (implicitly ± j ) indicates the goal in the j th dimension: ± = + for minimization, -for maximization.

Definition 3. For two designs x, y ∈ X , where X is the design space, and f the objective functions, we introduce the following notations:

x f y ⇐⇒ f (x) f (y), x f y ⇐⇒ f (x) f (y), x f ∼ y ⇐⇒ f (x) ∼ f (y).
Remark Note that the objective functions appear explicitly in the above notation.

Definition 4. A design x ∈ X is said to be non-dominated (or efficient) regarding a set A ⊆ X if and only if:

y ∈ A, y f x.
Then, x is said to be Pareto-optimal iff x is non-dominated regarding X .

In this work, f is assumed to be unknown. Only the estimated value f l and its conservative error ε l can be computed, with f ∈ B f l , ε l . A new dominance criterion is then introduced.

Following [START_REF] Mlakar | Comparing solutions under uncertainty in multiobjective optimization[END_REF] and [START_REF] Fusi | An adaptive strategy on the error of the objective functions for uncertainty-based derivative-free optimization[END_REF], this dominance is denoted by Boxed Pareto dominance. Intuitively, a box B(a, r) dominates another box B(b, r ) if and only if any point of B(a, r) dominates (in the classical way) every point of B(b, r ). This can also be interpreted as a classical dominance rule between the least performing point of B(a, r) and the most performing one of B(b, r ). Definition 5. Boxed Pareto dominance. For two boxes B(a, r), B(b, r

) ∈ ℘(R m ) 2 , B(a, r) B B(b, r ) ⇐⇒ ∀j ∈ 1, m , ±a j + r j ≤ ±b j -r j and ∃j ∈ 1, m , ±a j + r j < ±b j -r j , B(a, r) B B(b, r ) ⇐⇒ ∀j ∈ 1, m , ±a j + r j < ±b j -r j , B(a, r) ∼ B B(b, r ) ⇐⇒ B(a, r) B B(b, r ) and B(b, r ) B B(a, r).
The following equivalence is verified:

∀a, b ∈ R m , B(a, 0) B B(b, 0) ⇐⇒ a b, (2)
which traduces the consistency between the two domination rules when the size of the box tends to zero.

Inria

Remark It can be noted that the relation between B(a, r) and B(b, r ) is the same as between B(a, r ) and B(b, r).

Bounding-Box approach

The Bounding-Box approach proposed in [START_REF] Fusi | An adaptive strategy on the error of the objective functions for uncertainty-based derivative-free optimization[END_REF] is a strategy permitting to choose for each design a fidelity level l to compute the fitness function. It aims at optimizing the trade-off between accuracy and computational cost and relies on the Boxed Pareto dominance rule defined above. The steps are the following:

a) The chosen optimization algorithm provides a new design x (Note that there may be an ensemble of designs if using for example evolutionary algorithms);

b) The objectives are estimated at x with low-fidelity (l=0) to get the associated box B f 0 (x), ε 0 (x) ; c) This box is then compared to all the other boxes using the Boxed Pareto dominance. If dominated, this box is not refined; d) Otherwise, the fidelity l(x) is increased and the box is updated to B f l (x), ε l (x) with the newly computed values f l (x) and ε l (x). This procedure is repeated as long as ε l (x) ≤ s 2 , where s 2 is a threshold fixed by the user. In the multi-objective case, s 2 is a vector and the inequality holds for all dimensions; e) After each refinement, the box is compared to the others using the Boxed Pareto dominance.

If either the box gets dominated or ε l (x) ≤ s 2 , it is no longer refined;

f) The value returned to the optimizer is the center of the box, i.e. f l (x).

Remarks

• When dealing with multiple new designs, for example with evolutionary algorithm, refinements (step d) are performed sequentially, one box at a time. This allows to check for domination at each refinement to avoid fidelity increases. This behavior is formally defined in Definition 10.

• Note that in principle, the inequality in step d) must not hold for all dimensions. Notably, when the objective functions are evaluated with different solvers, increasing the fidelity on one solver would not impact at all the fidelity of the objective functions assessed with another solver. As a consequence, each inequality should apply only to the set of objective functions evaluated with the same solver. As an underlying assumption, the scope of this paper is to handle one expensive solver, where the outcome of the simulation provides all the objective functions. For this reason, we consider the inequality to hold for all dimensions.

• Concerning the choice of s 2 , each component is written as

s 2 k = s2 k × h k , where h k is equal to: h k = max i f l k (x i ) -min i f l k (x i ) ,
given a set of estimations x i , f l (x i ) i . The choice in terms of the threshold is then made on the normalized parameter s2 k , which represents a percentage of the range covered by the objectives on the evaluated designs, updated at each iteration. These ranges are initialized with the first estimations f 0 (x i ) i on an initial set of designs. In the following, the value of s2 is given with a percent sign to recall this procedure. This strategy is part of the flowchart (Fig. 3), and the blue color of the "Bounding-Box approach" box indicates the significant computational cost associated to the objectives estimation. This approach gives an efficient heuristic to allocate the estimation fidelity in order to i) ensure a high-fidelity computation of the Pareto front and ii) minimize the associated computational cost.

Surrogate-assisting strategy

In [START_REF] Fusi | An adaptive strategy on the error of the objective functions for uncertainty-based derivative-free optimization[END_REF], the recursive Bounding-Box approach shows very good parsimony only during the first optimization iterations. Afterwards, most visited designs are located close to the Pareto front and require high-fidelity computations. In consequence, the strategy ends up behaving like a classical nested optimization.

For this reason, the Bounding-Box approach is coupled with a Surrogate-Assisting (SA) strategy. We propose here to build a surrogate model of the estimated objectives f l (x). This surrogate model is built on all previously estimated objectives f l (x i ) the optimizer. Else, the Bounding-Box approach is applied, and the associated box is computed and refined. Again, if s 1 is multidimensional, inequality must hold for all dimensions. The SA model is updated with the knowledge of the newly computed box at each optimization iteration t. The value f opt (x) returned to the optimizer depends then on the value of the surrogate error compared to a user-defined threshold s 1 . The choice of s 1 follows the same procedure as for s 2 (presented in Section 2.3). Namely, for each objective k, a normalized value

s1 k = s 1 k h k is provided by the user, with h k = max i f l k (x i ) -min i f l k (x i ) . In summary, f opt (x) = f t SA (x) if ε t SA (x) ≤ s 1 = s1 × h f l (x) else . (3)
The SA strategy and its coupling to the Bounding-Box approach are depicted in Figure 3, where the flowchart summarizes the behavior of the framework:

Optimization process

Objectives approximation

Surrogate model

f l d (x) x f OBJ (x) = f k min (x) f OBJ (x) = f l d (x) f k min (x)

Mathematical analysis of the proposed approach

The goal of this section is to provide some proofs of convergence of the proposed strategy. In particular, first, we show how the designs produced with the Bounding-Box approach converge towards the exact Pareto-optimal area under some assumptions. Then, we illustrate the convergence of the method also when coupled with a Surrogate-Assisting strategy.

Bounding-Box definition and convergence analysis

Based on the Pareto dominance defined in the preceding section, the following Pareto-optimal sets are introduced. The set P represents the true continuous Pareto front of the problem. Its discrete counterpart is labeled as P. Finally, we indicate with P B the set of Pareto-optimal boxes. Here, the tilda refers to the approximation arising from the discrete representation of the sets.

Definition 6. With A ⊂ R m , designs a i ∈ R m and boxes B i ∈ ℘(R m ): P A = a ∈ A | b ∈ A, b a , P a i N i=1 = a i , i ∈ 1, N | j ∈ 1, N , a j a i , P B B i N i=1 = B i , i ∈ 1, N | j ∈ 1, N , B j B B i .

RR n°9155

Ordinarily, A is simply f (X ) and P(f (X )) can simplify to P, i.e. the Pareto front of the problem. On the contrary, the discrete P always refers to a given set of designs.

Definition 7. With f the objective functions, X the design space, x i ∈ X and r i ∈ R m , let us define

X f P = x ∈ X | f (x) ∈ P , X f P x i N i=1 = x i , i ∈ 1, N f (x i ) ∈ P f (x i ) N i=1
,

X f P B x i , r i N i=1 = x i , i ∈ 1, N B f (x i , r i ) ∈ P B B f (x i , r i ) N i=1
Practically, X f P , X f P and

X f P B
represent the ensemble of design coordinates associated with P, P and P B , respectively.

Remark X f P B x i , r i N i=1
can be explicitly defined as follows:

x i ∈ X f P B x i , r i N i=1 ⇐⇒ ∀k ∈ 1, N , ∃j ∈ 1, m , ±f j (x i ) -r ij < ±f j (x k ) + r kj . (4) Proposition 1. Note that ∀ x i , r i N i=1 ∈ X × R m N , X f P x i N i=1 ⊆ x i N i=1 and X f P B x i , r i N i=1 ⊆ x i N i=1 .
The proof is provided in A.

Note that the inclusion becomes strict whenever a design does not satisfy the non-domination condition.

Two other sets are introduced, P c and P c , which represent the continuous extension of P and P, respectively. These sets contain all the dominated but not strictly dominated points of R m with respect to P and P. Definition 8. With A ⊂ R m and ∀i, a i ∈ R m , let us define P c and P c , as follows

P c (A) = P(A) ∪ b ∈ R m | ∃z ∈ P(A), z b & z ∈ P(A), z b , P c a i N i=1 = P a i N i=1 ∪ b ∈ R m ∃z ∈ P a i N i=1 , z P b & z ∈ P a i N i=1 , z P b .
Usually, as for Def. 6, A ≡ f (X ) and P c (A) is denoted by P c .

Mathematical formulation for error-based boxes

As stated in Section 2, the proposed framework is developed in the context of estimated objective functions with tunable fidelity. The goal of this section is to provide some definitions and to introduce the so-called Bounding-Box recursive strategy.

Definition 9. An error is assumed on the computation of each objective function f j . The estimated value f l j (x) with fidelity l differs from f j (x) by an additive error, as follows:

∀x ∈ X , ∀j ∈ 1, m , f j (x) = f l j (x) + ε l j (x).

Inria

Remark Let us recall here that l implicitly refers to l(x). The fidelity used for computing the objective functions can differ from one x to another. The aim of this work is to compute objective functions with high accuracy (high values of l) only for efficient designs.

Assumption 1. We assume that a conservative error ε l can be computed on f l , meaning that:

∀x ∈ X , ∀j ∈ 1, m , |ε l j (x)| ≤ ε l j (x). Then, ∀x ∈ X , f (x) ∈ B f l x, |ε l (x)| ⊆ B f l x, ε l (x) .
This assumption will be necessary for strictly demonstrating the convergence of the proposed approach.

The estimation f l can be refined by increasing the fidelity l. The conservative error is then assumed to converge to zero. Assumption 2. No constraint is imposed on the monotony of ε l l∈N+ but it is assumed in the following that:

∀j ∈ 1, m , lim l→+∞ ε l j = 0.
Note that the computational cost increases with the fidelity. In this work, the fidelity l is tuned adaptively for each design x. Hence, we consider the fidelity l as a strictly increasing sequence at each x during the optimization process. At each refinement iteration, the fidelity of one estimation f l (x) is increased. The iteration is denoted with the subscript k. Hence, after k refinements, the fidelity at a given x is l k and the estimated objectives value is

f l k (x).
The output of interest is X f P . The proposed strategy should allow for an accurate discrete approximation of this set based on estimations f l k with sequentially tuned fidelity l k . To this extent, the classical and recursive approaches are presented. The later has been developed in [START_REF] Fusi | An adaptive strategy on the error of the objective functions for uncertainty-based derivative-free optimization[END_REF]. Note that the following development is written in the design space, but can easily be transposed to the objective space. Definition 10. For any x i N i=1 ∈ X N , f the objective functions and f l k the approximations with sequentially tuned fidelity l k and conservative error ε l k , with N k k∈N+ a decreasing sequence and N 0 = N , let us introduce ∀k ∈ N + the following sequences, initialized by X f ,0

P = x i N i=1 . Classical: X f ,k+1 P = X f l k P B X f ,0 Pi , ε l k X f ,0 Pi N i=1 , Recursive: X f ,k+1 P = X f l k P B X f ,k Pi , ε l k X f ,k Pi N k i=1 . (5)
X f ,k P refers to the approximation of X f P at the k th refinement iteration, using f l k instead of f . It represents the Pareto-optimal set associated to a given set of fidelities l k (x i ) i .

Remark In the following, by default, X f ,k P will refer to the recursive strategy. The classical approach refers to a double-loop or nested optimization, where the objective functions are estimated with increasing fidelity on the whole design set X f ,0 P with size N . As raised in Assumption 2, the most time-consuming step is the decrease of the conservative error ε l through higher fidelity computations. In the recursive Bounding-Box refinement strategy, Proposition 1 gives that ∀k

∈ N + , X f ,k P ⊆ X f ,k-1 P ⊆ ... ⊆ X f ,0
P . Any unsatisfied non-domination condition implies a strict inclusion between two sets of the sequence. Hence, whenever a box gets dominated, the size N k = Card X f ,k P of the set of interest is decreased. The fidelity increased is then performed only on N k ≤ N designs.

The next section is devoted to the convergence of the recursive set sequence.

Convergence analysis

This section aims to demonstrate that the sequence X f ,k P k∈N+ theoretically converges to the real Pareto-optimal set. More precisely, the goal is to demonstrate the convergence of the continuous approximated Pareto front P c built on the approximated objectives f l k X f ,k P toward the real continuous front P c .

To this extent, another assumption is needed.

Assumption 3. For a given multi-objective optimization, it is assumed that:

∀y ∈ X f P , ∃D ⊆ X so that y ∈ D, D = ∅ and ∀j ∈ 1, m , f j ∈ C 0 (D).
Let D(y) be a set satisfying the previous condition for a given y ∈ X .

∀ ∈ R * + , ∃M ∈ N + , ∀y ∈ X f P , ∃k ∈ 1, m , x k ∈ D(y), x k -y ≤ .
In practice, it states that the optimizer converges toward the whole Pareto front and discretely covers the integrity of X f P . In addition, there exists a non-empty part of X around each efficient design in which all f j are continuous.

These assumptions simulate a "well-behaving" optimizer. In this context, the impact of the proposed strategy on the convergence can be studied.

Remarks

The following relation is trivial:

X f P X f P x i N i=1 = X f P x i N i=1 .
More generally, ∀S s.t.

X f P x i N i=1 ⊆ S ⊆ x i N i=1 , X f P S = X f P x i N i=1 . (6)
This can be transposed for P in the objective space.

Proposition 2. ∀y ∈ x i N i=1 , y / ∈ X f P x i N i=1 ⇐⇒ ∃y ∈ X f P x i N i=1 , y y. The proof is given in B. Lemma 1. ∀ x i , ε(x i ) N i=1 ∈ X × R m N , X f P x i N i=1 ⊆ X f P B x i , ε(x i ) N i=1 .
The proof is given in C.

Proposition 2 simply formalizes that there is at least one dominant design in a given set of points. Lemma 1 shows the robustness of the boxed dominance. All truly efficient design are also efficient in the Boxed Pareto dominance sense.

A novelty of this paper compared to Fusi's Bounding-Box approach in [START_REF] Fusi | An adaptive strategy on the error of the objective functions for uncertainty-based derivative-free optimization[END_REF] is the choice of an accuracy threshold for the estimation of the objective functions. In [START_REF] Fusi | An adaptive strategy on the error of the objective functions for uncertainty-based derivative-free optimization[END_REF], exact (or very refined) estimations are computed for non-dominated designs. Here, non-dominated boxes are only refined up to a given user-defined threshold.

Inria

Theorem 1. For any initial set X f ,0

P = x i N i=1 ∈ X N , approximation sequence f l k
k∈N+ and conservative error set sequence ε l k k∈N+ , the robustness is verified ∀k ∈ N + , i.e.:

X f P x i N i=1 ⊆ X f ,k P . ( 7
)
The proof is given in D.

This first theorem extends the robust behavior presented in Lemma 1 to the recursive Bounding-Box strategy introduced in Definition 10. We raised that this strategy allows to reduce the number of refinements, Theorem 1 also ensures that all Pareto-optimal designs are retained for high-fidelity estimation.

Using Assumption 3, the convergence of P c f l k X f ,k P toward the real continuous front P c can be proven, as follows.

Theorem 2. For any initial set X f ,0 P ∈ X N , approximation sequence f l k k∈N+ and conservative error set sequence ε l k k∈N+ , the following convergence is verified:

lim (N,k)→(+∞,+∞) d H P c f l k X f ,k P , P c = 0, (8)
with the classical Hausdorff distance denoted by d H .

The proof is given in E.

The continuity assumption brings preimage convergence. In this section, the convergence analysis has been carried out. It relies on several assumptions on the computability of conservative errors and the good behavior of both the optimizer and the objective functions. The recursive set sequence is the set of non-dominated designs, which cardinality decreases when boxes get dominated. Performing refinements only on this set brings significant cost reduction, notably during the exploration phase of the optimizer.

Contrarily to [START_REF] Fusi | An adaptive strategy on the error of the objective functions for uncertainty-based derivative-free optimization[END_REF], the accuracy of the efficient boxes is tuned with a user-defined threshold s 2 . The fidelity of the objectives estimation is adaptively increased until ε l (x i ) ≤ s 2 for all x i . In the multi-objective case, s 2 is a user-defined vector and the notation a ≤ b means ∀i, a i ≤ b i . This approach has been proven to be conservative, meaning that truly efficient designs are not discarded during the recursive set sequence refinement.

Surrogate-Assisting model

In this section, we study the coupling between the Bounding-Box approach and a Surrogate-Assisting (SA) strategy. The later should not impact the converge towards the true Pareto optima. We recall the notation introduced in Section 2.4.

The SA model predictive value at iteration t is denoted f t SA (x) and the known conservative error is

ε t SA (x) ≥ ε t SA (x) = f (x) -f t SA (x).
The value returned to the optimizer is f opt (x), that uses the SA model predictive value when accuracy s 1 is reached, and the converged Bounding-Box estimation otherwise, see Equation (3).

Remark Again, in the case of multiple objectives m > 1, the surrogate errors and the userdefined vector s 1 must be compared. They are both of size m and:

a ≤ b ⇐⇒ ∀i, a i ≤ b i . RR n°9155
Theorem 3. Given two user-defined thresholds s 1 and s 2 , the true discrete Pareto optima are included in the following boxed Pareto optima:

∀ x i N i=1 ∈ X N , X f P x i N i=1 ⊆ X fopt P B x i , r(x i ) N i=1 ,
where equality holds when s 1 = s 2 = 0. The half-width r depends on the use or not of the Surrogate-Assisting model:

r(x i ) = ε t SA (x i ) if ε t SA (x i ) ≤ s 1 ε l (x i ) else . ( 9
)
The proof is given in F.

Note that the surrogate model is iteratively refined throughout the optimization process. Hence, sequential optimization approaches will benefit the most from the Surrogate-Assisting strategy.

A sketch about the coupling is provided in Algorithm 1. Steps (a) to (c) will be detailed in Section 4.

Algorithm 1 Algorithm overview

1: while Optimization running do 2:

Read new designs 3:

if SA error below s 1 then 4:

(a) Use SA model to approximate objective functions Update the SA model 8:

end if 9: end while The Surrogate-Assisting strategy complements efficiently the Bounding-Box approach. If a pattern, linearity or simple behavior of the objective functions is detected, it can drastically reduce the overall optimization cost. The convergence of the coupled approach can be deduced from Theorems 2 and 3, by replacing N → +∞ with t → +∞ and k → +∞ with (s 1 , s 2 ) → (0, 0).

In the following, a numerical algorithm is proposed and applied to some analytical test-cases in order to validate the framework.

Algorithm of the framework

This section illustrates the numerical algorithm associated with the proposed framework.

As seen in the previous sections, two user-defined thresholds s 1 and s 2 have to be chosen. The value s 1 is compared to the surrogate error to determine whether the surrogate can be used or not. The threshold s 2 is compared to the error of the estimated objective functions, to decide whether higher higher-fidelity estimations are required.

Three design sets D, D new and D are introduced for Algorithm 2. The set D is initialized at the beginning of the algorithm. It contains all the non-dominated designs and is updated at each refinement of the objective functions. It corresponds to the current set of the recursive set sequence from Definition 10. The set D new represents the new designs at each optimization Inria iteration. It can contain several designs (e.g. with a genetic algorithm optimizer) or only one design (for sequential optimization). The set D contains the non-dominated designs of D new that were not computed with the SA strategy. This set is updated at each refinement and is reinitialized at each optimization iteration.

The main steps of Algorithm 2 are the following: i) in the subroutine compareDesignSA, if the surrogate error is below s 1 , the associated objective values are returned. A low-fidelity objective estimation is computed for the other designs and added to D ; ii) the inner while loop refines each design of D up to the s 2 threshold within the iterateRefinement subroutine and checks for new dominations at each iteration to discard boxes from D ; iii) finally, the surrogate is updated and new designs can be analyzed. Initialize D empty 8:

D , f 0 (D ), ε 0 (D ), f opt , r = compareDesignSA(D new , s 1 , s 2 , f t SA , ε t SA ) (Alg. 3) (a,b
f l k , ε l k = iterateRefinement(D , x r ) (Alg. 4) (c) 16:
for each x ∈ D do 17:

f opt (x) = f l k (x) 18: r(x) = ε l k (x) 19:
end for 20:

Compute D = X fopt,k P = X fopt P B X fopt,k-1 P , r X fopt,k-1 P 21: D = D ∩ D 22:
end while

23:

Compute updated f t SA and ε t SA 24: end while 25: Return D and B fopt D, r(D)

Remark In Algorithm 2, B fopt D i , r(D i ) Card(D) i=1
is simply written B fopt D, r(D) . The subroutine compareDesignSA (in Algorithm 3) takes as inputs the new designs, the thresholds and the current SA model. It returns the set of non-dominated designs that can be refined (not coming from SA approximation), the associated low-fidelity estimation of the objective functions and the coupled objective functions f opt with boxes size r.

For each new design, the error of the SA model is compared to the threshold s 1 . If the error is small enough (a), the objective functions are approximated with the surrogate. Otherwise (b), low-fidelity estimations are computed and the design is added to D . In practice, computation (b) is assumed to have a much higher cost than computation (a).

Algorithm 3 compareDesignSA(D new , s 1 , s 2 , f SA , ε SA ) 1: for each x ∈ D new do 2: if ε SA (x) ≤ s 1 then (a)
3:

f opt (x) = f SA (x) 4: r(x) = s 2 (x) + ε SA (x) 5: else (b) 6:
Compute f 0 (x) and ε 0 (x)

7:

f opt (x) = f 0 (x) 8: r(x) = ε 0 (x) 9: D = D ∪ x 10:
end if 11: end for 12: Return D , f 0 (D ), ε 0 (D ), f opt and r Then, iterateRefinement (in Algorithm 4) computes the new approximation f l k and its associated error for the chosen design x r . The fidelity l k associated to the design to refine x r is increased and the new estimation is computed. For all other designs, the fidelity is kept constant. We chose to refine the boxes one at a time to check for domination at each iteration.

Algorithm 4 iterateRefinement(D , x r ) 1: for each x ∈ D do 2: if x = x r then 3: l k (x) = l k-1 (x) + 1 4:
Compute higher-fidelity estimations f l k (x) and ε l k (x) (c)

l k (x) = l k-1 (x) 7:
end if 8: end for 9: Return f l k and ε l k

Test-cases and analysis

The proposed framework (SABBa) is an adaptive strategy for approximating the Pareto front of an optimization problem by tuning the fidelity of the objectives estimations according to their efficiency to significantly lower the computational burden.

In this section, we apply the framework to several analytical test-cases and analyse its performance. The aim here is to provide a proof-of-concept of the proposed framework on analytical test-cases, i.e. to study the asymptotic behavior of SABBa compared to Fusi's approach [START_REF] Fusi | An adaptive strategy on the error of the objective functions for uncertainty-based derivative-free optimization[END_REF] and the simple nested approach, that can be surrogate-assisted. For this reason, we do not choose any specific surrogate model, optimizer or multi-fidelity objective estimations, but we simulate them analytically. Note also that in this perspective, the point is not to assess the behavior of the framework concerning the dimensionality and complexity of the optimization problem, as these last ones impact the optimizer and the surrogate model, which are choices independent of the framework.

Inria

Section 5.1 illustrates how the multi-fidelity estimations, surrogate models, and the optimizer are estimated. The first test-case, treated in Section 5.2, is a classical bi-objective optimization. The second test-case illustrated in Section 5.3 highlights the increase of the computational cost raised in [START_REF] Fusi | An adaptive strategy on the error of the objective functions for uncertainty-based derivative-free optimization[END_REF] when the optimizer converges toward the Pareto front. It permits to emphasize the gains induced by the Surrogate-Assisting (SA) strategy. Finally, the robustness of SABBa to complex Pareto front is illustrated in a third test-case, presented in Section 5.4.

Tools

As stated above, the different tools (optimizer, surrogate model and multi-fidelity computations) are simulated analytically. For real applications, any existing method can be chosen.

Multi-fidelity computations

In this section, we deal with analytical test-cases. We add arbitrarily a noise on the real value, inversely proportional to the desired fidelity. In practice, the low-fidelity estimation costs one evaluation. Each refinement then increases this value by one. The first low-fidelity computation is performed as follows for each objective function f i :

ε noisei = max(f i ) -min(f i ) 4 + 6X 1 with X 1 ∼ U[0, 1], ε biasi = ε noisei X 2 with X 2 ∼ U[-1, 1], f 0 i = f i + ε biasi , ε 0 i = 2.ε noisei .
This estimation can then be refined with a given refinement factor r f > 1:

f l i = f i + f l-1 i - f i r f , ε l i = ε l-1 i r f .
Optimizer The optimization is performed with a sequence of Monte-Carlo samplings. At each iteration, the set of new designs is constituted by ten random designs. Convergence toward the optimal area can be enforced on the Monte Carlo samples. The effect of this convergence is studied in test-cases 2 and 3.

Surrogate model

Similarly to the multi-fidelity computations, the Surrogate-Assisting (SA) model f SA is an arbitrarily noisy evaluation of the objective functions. We consider a noise proportional to the distance d min to the closest training point. The noise is also proportional to the range covered by the objective functions. Practically, at a given optimization iteration t and for each dimension i:

t SAi = d min 1 Nx j max(x j ) -min(x j ) . max(f i ) -min(f i ) 2 , ε noisei = t SAi 2 X 1 with X 1 ∼ U[0, 1], ε biasi = ε noisei X 2 with X 2 ∼ U[-1, 1], f t SAi = f i + ε biasi .
To simulate the fact that the surrogate is built on noisy training data, and to be consistent at least on the Pareto front, we add a constant noise on the conservative errors, as follows:

ε t SAi = t SAi + s 2 .
In the following, the SABBa framework is compared to three different approaches: i) the nested classical approach (denoted by Class), i.e. non-recursive Bounding-Box approach defined in Def. 10, where each box is refined up to the threshold s 2 ; ii) the recursive approach, i.e. Fusi's Bounding-Box refinement strategy [START_REF] Fusi | An adaptive strategy on the error of the objective functions for uncertainty-based derivative-free optimization[END_REF], where only non-dominated boxes are refined to the threshold s 2 ; iii) a surrogate-assisted classical approach (denoted by Class-acc).

Test-case 1: The BNH problem

The first test-case deals with a bi-objective constrained problem, proposed by Binh and Korn (1997):

minimize: f (x) = 4x 2 1 + 4x 2 2 (x 1 -5) 2 + (x 2 -5) 2 subject to: (x 1 -5) 2 + x 2 2 ≤ 25 (x 1 -8) 2 + (x 2 + 3) 2 ≥ 7.7 by changing: (x 1 , x 2 ) ∈ [0, 5] × [0, 3] (10)
The acceptable design area and its counterpart in the objective space are represented in Fig. 4. The Pareto optimal set in the design space is represented by the thick black curve. New designs are chosen randomly in [0, 5] × [0, 3] under the optimization geometric constraints. In Figures 5 and6, the results in terms of optimal designs and objectives, for the classical and the recursive approaches are provided, respectively. This optimization is performed with 100 optimization iterations and s2 = (1%, 1%) T . This is simply written s2 = 1% as we chose to use the same threshold for both objectives. We recall that the normalized thresholds s1 and s2 are multiplied by the range covered by each objective to obtain the thresholds s 1 and s 2 , as defined in Section 2.3 and 2.4. Because of the low gradient around the optima, the non-dominated designs (in black) cover a quite wide area. Dominated designs and boxes are drawn in grey.

The approximated Pareto front of these two strategies are qualitatively very similar and both provided the same Pareto-optimal design area. However, a significant portion of the boxes are not refined up to s 2 in the recursive approach (Figure 6), thus reducing the number of function evaluations, and the computational cost of the optimization. In Figures 7 and8, the Surrogate-Assisting (SA) strategy is applied on the classical approach and the recursive (Fusi) approach, respectively. Figure 8 pictures the behavior of SABBa. The thresholds s2 = 1% and s1 = 1% are used (implicitly (1%, 1%) T ).

SA designs and boxes are drawn in dark grey when they are non-dominated and light grey otherwise. The non-dominated design area and the approximated Pareto front are similar to the fully-computed ones from Figure 5.

We directly compare the number of function evaluations needed for each strategy. Because the tools are analytically simulated, the number of function evaluations only allows for asymptotic comparison and should not be confronted to real applications. The results are reported in Figure 9a: • The recursive (Fusi [22]) strategy appears to be more parsimonious than the classical approach. It reduces the slope of the cost curve by a ratio that can be interpreted as the mean computational cost in the recursive strategy with regards to the full convergence cost.

Nearly half of the designs are non-dominated in this test-case. This high number of fully refined boxes implies limited computational gains. • The SA strategy is more and more effective throughout the optimization process. During the first iterations, the surrogate is not yet accurate and the slope is similar to non-assisted strategies. Later, surrogate-assisted strategies show significant cost reduction.

The influence of the user-defined thresholds s1 and s2 is also investigated.

Figure 9b pictures the substantial impact of s2 on the computational cost. This comes from the high number of high-fidelity boxes. Increasing the threshold implies higher accuracy for all these boxes and significantly rises the global cost. However, this threshold has a critical repercussion on the accuracy of the Pareto-optimal set. This is qualitatively drawn in Fig. 10.

Figures 9c and 9d

Test-case 2: The Triangle problem

This problem is a bi-objective unconstrained optimization:

minimize: f (x) = x1+x2 10 + |x 1 -x 2 | x1 5 + |x 2 -2| by changing: (x 1 , x 2 ) ∈ [0, 10] 2 (11)
The design space with the optimal set (represented with a thick black curve) and the objective space counterpart are represented in Fig. 11.

This small optimal area is well fit to study the behavior of SABBa when the optimizer converges toward the Pareto front. In practice, two variants are compared. At each iteration, 10 new random designs are given to SABBa: a) in X = [0, 10] × [0, 10]; b) in a domain X k converging toward [0, 2] × [0, 2] throughout the iteration, with X 0 = X .

We aim at replicating the slow-down of the recursive Bounding-Box approach raised in [START_REF] Fusi | An adaptive strategy on the error of the objective functions for uncertainty-based derivative-free optimization[END_REF], and at quantifying the impact of the SA strategy.

Test-case 2 a): No convergence of the designs

In this variant, new designs are chosen randomly within the [0, 10] 2 design space. The approximation of the Pareto front is very poor and highly inefficient, as one could expect. The result is pictured in Fig. 12. Here, new designs are randomly chosen in a domain that converges toward the optimal area. In practice, with j the optimization iteration, the new designs are drawn as follows, for i in {1, 2},

x i = X 2 + 8 exp - j 45 , with X ∼ U[0, 1].
This gives a better refinement of the Pareto front, as can be seen comparing Figs. 12 and 13. The number of function evaluations are compared in Fig. 14. As raised in [START_REF] Fusi | An adaptive strategy on the error of the objective functions for uncertainty-based derivative-free optimization[END_REF], the convergence toward the optimal area induces a decreasing impact of the recursive strategy. The slope of the associated cost curve (dashed) slowly relapses to the slope of the classical one (solid) in Fig. 14b. This is due to the increasing ratio of non-dominated designs.

SABBa relies on the SA strategy to ultimately bypass function evaluations in the optimal area. In Fig. 14b, both surrogate-assited strategies (Class-acc and SABBa) benefit from the convergence to reach their cost plateau faster. Despite the increasing slope of the Fusi strategy alone, SABBa takes advantage of the convergence by constructing a locally highly refined surrogate model in the optimal area. Fig. 14a can also be compared with Fig. 9a. Contrarily to the first test-case, Fig. 12 shows a small Pareto front. Many more boxes are dominated and the recursive strategy can generate higher computational gains.

Remark The increasing number of non-dominated design in the converging case also induces an increasing impact of the threshold s2 throughout the optimization process. This is depicted in Figure 15, that compares the converging and non-converging cases.

Test-case 3: The Kursawe problem

The Kursawe bi-objective optimization is performed here, in order to study the framework behavior on a more complex Pareto front shape. The problem is the following:

minimize: f (x) = 2 i=1 -10 exp -0.2 x 2 i + x 2 i+1 3 i=1 |x i | 0.8 + 5 sin(x 3 i ) by changing: (x 1 , x 2 , x 3 ) ∈ [-5, 5] 3 (12)
This problem is known to have a complex Pareto front with several discontinuities, associated with a small area of the design space. In the following, the convergence toward the optimal zone is forced, similarly to test-case 2 b). We aim at showing that the SABBa framework is not influenced by the complexity or dimensionality of the optimization problem. To tackle these issues, a suitable choice of the optimizer and the surrogate model is required.

The Pareto front associated to the problem is given in Fig. 16. It is highly discontinuous and should allow for a high impact of the recursive strategy as many designs are far from the Pareto front. The Pareto-optimal designs are represented in Fig. 16c in the [-5, 5] 3 domain and in Fig. 16d in a close-up view. These designs form complex disjoint sets and their approximations will be qualitatively compared to Fig. 16c. The SABBa framework is applied in the following with different thresholds. Fig. 17 gives the outputs obtained with a fine threshold. The results are highly comparable to Fig. 16, with only 28510 function evaluations over 48913 for the classical approach (gain = 42%). With larger thresholds, the optimal area is less accurately captured, as seen in Fig. 18a, and the associated approximated Pareto front is depicted with higher imprecision in Fig. 18b. Here, 8294 function evaluations were required (gain = 83%). With very coarse thresholds, the local optimal shape is not captured in Fig. 19. This however gives a first rough approximation of the optimal area with only a computational cost of 3546 evaluations (gain = 93%). The cost graphs are given in Fig. 20. Similarly to Figs. 14b and 15b, Figs. 20a and 20b reveal a decreasing impact of the recursive strategy alone and an increasing sensitivity to s2 throughout the optimization. Figure 20c and20d show that the computational cost associated to SABBa is here highly influenced by the threshold s1 , that controls the accuracy of the SA model.

SABBa yields a significant decrease in the computational cost. The user-defined thresholds heavily impact both the accuracy and the global computational cost. They should be chosen with care in real-life applications.

The efficiency of the SABBa framework is not directly correlated with the complexity of the optimization problem. The user should choose the most relevant optimization and surrogate modelling techniques for tackling high dimension, non-linearity or other difficulties. In this context, SABBa can bring consistent cost reduction through a fine allocation of the high-fidelity computations and robust use of the Surrogate-Assisting model.

Conclusive remarks

In this paper, we introduced a novel framework to efficiently deal with multi-objective (≤ 3) optimization problems with objective computations of tunable and refinable fidelity. This kind of problem could notably arise with iterative or sampling-based computations. The proposed strategy couples the recursive Bounding-Box approach for error-based objective functions developed in [START_REF] Fusi | An adaptive strategy on the error of the objective functions for uncertainty-based derivative-free optimization[END_REF] with a Surrogate-Assisting strategy that aims at bypassing function evaluations. The intuitive idea is to use the Bounding-Box approach to quickly converge toward the optimal area through low-fidelity computations of the non-efficient designs and to simultaneously build the Surrogate-Assisting model, which refinement is driven by the optimization process. We first provided a mathematical proof of the robustness of the framework and of its convergence under some assumptions. Then, a numerical validation was carried out, in order to validate the convergence, quantify the computational gains and make explicit the main behaviors of the strategy.

The framework appears to yield a consistent cost-reduction compared to the Fusi [START_REF] Fusi | An adaptive strategy on the error of the objective functions for uncertainty-based derivative-free optimization[END_REF] approach, which already performed better than the classical nested optimization approach. Accuracy of the outputs have been qualitatively analyzed with regards to the associated cost reduction. Finally, the influence of the user-defined thresholds has been investigated.

SABBa is based on several assumptions, such as the possibility to compute a conservative error approximation and the convergence of the optimization process. Plus, the objective estimation error is only represented through an uncorrelated bounded product of intervals. A high correlation in the objective space could have a momentous impact on the domination computation, and thus on the computational cost. The uncorrelated assumption usually overestimates the true variability. Note also that the assumption of bounded error is critical for the computation of conservative errors, that ensure a proper convergence of the framework. A Gaussian-distributed error, unbounded, could be treated within the proposed framework in two different manners. The most straightforward approach would be to relax the conservative assumption by truncating the Gaussian distributions. One could also propose Gaussian objective approximations instead of uniform boxes. This would however require the choice of a suitable Pareto dominance rule.

Finally, the behavior of the framework when dealing with a high number of parameters has not been treated here. One would expect the Surrogate-Assisting model to need more training data before convergence, thus slowing down the whole process. Note that up to tens of dimensions, this issue is expected to be tackled with an appropriate choice of the surrogate model (i.e. Automatic Relevance Determination or additive kernel for Gaussian processes). Furthermore, the choice of the threshold s 1 could be of particular importance and may allow to balance the computational burden with respect to the accuracy of the Pareto-optimal area. Future developments will be directed towards the application of the proposed framework to a problem of uncertainty-based multi-objective optimization in an engineering context and to the management of constraint functions.

A Proof 1

Proof. The proof here is trivial. By definition,

X f P x i N i=1 = x i , i ∈ 1, N | non-domination condition ⊆ x i , i ∈ 1, N ≡ x i N i=1 .
The same can be said for the boxed Pareto optima.

B Proof 2

Proof. For y / ∈ X f 6, which proves the first implication by contradiction. The second implication is immediate from the definition of X f P .

C Proof 3

Proof. By using the explicit definition of the Pareto front as in Equation 4, the proof is immediate as Assumption 1 gives ∀x ∈ X , ∀j ∈ 1, N , f j (x) ∈ f j (x) -ε j (x), f j (x) + ε j (x) . Hence,

∀x i ∈ X f P x i N i=1 :
∀k ∈ 1, N , ∃j ∈ 1, m , ±f j (x i ) < ± f j (x k ), ± f j (x i ) -ε j (x i ) < ± f j (x k ) + ε j (x k ).

Therefore, x i ∈ X f P B

x i , ε(x i ) N i=1 , which ends the proof.

Inria

Hence, we prove by contradiction that ∀a ∈ P c f X f ,k P , it follows that d ∞ a, P c f l k X f ,k P ≤ max (i,j)

ε l k j X f ,k
Pi . This statement holds also when inverting the Pareto front continuous sets (real and approximated), and this can proved in the same way. As a consequence, the Hausdorff distance can be written as follows:

d H P c f l k X f ,k P , P c f X f ,k P ≤ max (i,j) ε l k j X f ,k Pi .
Hence, Assumption 2 implies that:

lim k→∞ d H P c f l k X f ,k P , P c f X f ,k P = 0. ( 15
)
Let us focus now on the second part of the sum in Equation 14.

Of course, ∀a ∈ P c f X f ,k P , ∃a ∈ P c , so that a a (or a = a). Moreover, ∀b ∈ R m such that ∃a ∈ P, a b, Assumption 3 with Theorem 1 provides evidence that the recursive discrete efficient set converges toward the continuous real one and that this efficient set is included in X f ,k P . In other words, ∀k ∈ N, ∃M ∈ N * , ∃i ∈ 1, M , s.t.∀j ∈ 1, m , a j -f j X f ,k

F Proof 6

Proof. The proof is straightforward and comes from the following inequalities:

If ε t SA (x i ) > s 1 , f opt (x i ) -f (x i ) = f l (x i ) -f (x i ) ≤ ε l (x i ).
Else,

f opt (x i ) -f (x i ) = f t SA (x i ) -f (x i ) ≤ ε t SA (x i ) which comes from Equation 3.

Figure 1 :

 1 Figure 1: Bounding-Box approximation

Definition 2 .

 2 Pareto dominance. For two vectors a, b ∈ R m , a b (a dominates b) ⇐⇒ ∀j ∈ 1, m , ±a j ≤ ±b j and ∃j ∈ 1, m , ±a j < ±b j , a b (a strictly dominates b) ⇐⇒ ∀j ∈ 1, m , ±a j < ±b j , a ∼ b (a is indifferent to b) ⇐⇒ a b and b a.

Figure 2

 2 Figure 2 illustrates an example of the output produced by the Bounding-Box approach in the case of a bi-objective minimization problem. We observe that green dominated designs (in the top right of the figure) feature large boxes, while red non-dominated designs are associated with smaller boxes.This strategy is part of the flowchart (Fig.3), and the blue color of the "Bounding-Box approach" box indicates the significant computational cost associated to the objectives estimation. This approach gives an efficient heuristic to allocate the estimation fidelity in order to i) ensure a high-fidelity computation of the Pareto front and ii) minimize the associated computational cost.

Figure 2 :

 2 Figure 2: Bounding-Boxes refinement strategy for a bi-objective minimization problem

Figure 3 :

 3 Figure 3: Structure of the SABBa framework

  Compute and (c) refine the recursive set sequence up to s 2 7:

Algorithm 2 1 :s 1 and s 2 2 : 5 : 6 :

 21256 Detailed pseudo-algorithm of the framework Set Initialize D empty 3: t = 0 4: while Optimization running do Read new designs D new = x i N i=1 D = D ∪ D new 7:

  )

k = k + 1 14 :

 14 while max ε l (x) > s 2 , x ∈ D do 13: Select x r to refine in D 15:

Figure 4 :

 4 Figure 4: Test-case 1, a) acceptable design and Pareto optima (thick line), b) image in the objective space.

Inria

Figure 5 :

 5 Figure 5: Test-case 1, Class approach, non-dominated designs in black and dominated ones in grey: a) design space, b) objective space.

Figure 6 :

 6 Figure 6: Test-case 1, Fusi approach, non-dominated designs in black and dominated one in grey: a) design space, b) objective space.

Figure 7 :

 7 Figure 7: Test-case 1, Class-acc approach, non-dominated interpolated designs added in dark grey, dominated interpolated designs in light grey. a) design space, b) objective space.

Figure 8 :

 8 Figure 8: Test-case 1, SABBa approach, non-dominated interpolated designs added in dark grey, dominated interpolated designs in light grey: a) design space, b) objective space.

  Figures 9c and 9d illustrate the momentous cost reduction that can be achieved with the SA strategy, at the expense of Pareto front accuracy. One should however be careful not to underestimate the surrogate error, e.g. when high local variations are not yet captured.The next test-case deals with an optimization problem with a smaller Pareto-optimal area.

Figure 9 :

 9 Figure 9: Test-case 1: a) number of function evaluations for each method of interest (s 1 = s2 = 0.01), b) Fusi's approach varying s2 , c) SABBa framework varying s1 with s2 = 0.01 ; d) varying both s1 and s2 .

Figure 10 :

 10 Figure 10: Impact of s2 : Outputs with s2 = 0.005 in a) design space and b) objective space; Outputs with s2 = 0.1 in c) design space and d) objective space.

Figure 11 :

 11 Figure 11: Test-case 2: a) acceptable design and Pareto optima (thick line), b) image in the objective space.

Inria

Figure 12 :

 12 Figure 12: Test-case 2: Classical approach, non-converging domain for new designs: a) design space, b) objective space.

Figure 13 :

 13 Figure 13: Test-case 2: Classical approach, converging domain for new designs: a) design space, b) objective space.

Figure 14 :

 14 Figure 14: Test-case 2: number of function evaluations depending on the strategy for a) the non-converging case, b) the converging case.

Figure 15 :

 15 Figure 15: Test-case 2: number of function evaluations (Fusi strategy) depending on s2 for a) the non-converging case, b) the converging case.

Inria

Figure 16 :

 16 Figure 16: Test-case 3: a) image in the objective space, b) associated Pareto front, c) Pareto optima in the design space, d) in a close-up view.

Figure 17 :

 17 Figure 17: Test-case 3: SABBa ouputs with fine thresholds in a) the design space, b) the objective space. Computational cost saving: 42%.

Figure 18 :

 18 Figure 18: Test-case 3: SABBa ouputs with moderate thresholds in a) the design space, b) the objective space. Computational cost saving: 83%.

Figure 19 :

 19 Figure 19: Test-case 3: SABBa ouputs with coarse thresholds in a) the design space, b) the objective space. Computational cost saving: 93%.

Figure 20 :

 20 Figure 20: Test-case 3: a) number of function evaluations for each method of interest (s 1 = s2 = 0.01), b) Fusi's approach varying s2 , c) SABBa framework varying s1 with s2 = 0.01 ; d) varying both s1 and s2 .

  Pi< a j -b j .Thus, ∀k ∈ N, ∃M ∈ N * , ∃i ∈ 1, M , f X f ,k Pi b.Hence, P c is always dominated by P c and any element dominated by P c is dominated by P c with a sufficient number of points. From Definition 8, it can be deduced that:lim N →∞ d H P c f X f ,k P , P c = 0.(16)Finally, by combining Equations 14, 15 and 16, it comes:lim (N,l)→(+∞,+∞) d H P c f l k X f ,kP, P c = 0, which ends the proof.

RR n°9155

N i=1, where N is the number of boxes computed so far, and is used as a substitute for f l in areas where the surrogate error is low enough. The Surrogate-Assisting model is recomputed at each optimization iteration. We denote then the Surrogate-Assisting model at each iteration as f t SA . During the last iterations, the surrogate model can be massively used, as the optimizer stabilizes in the optimal area. Practically, this approach should allow a faster densification of the approximated Pareto front.The unknown surrogate error between f t SA (x) and f (x) at iteration t is denoted by ε t SA (x). It is approximated by a conservative approximation ε t SA (x), so that ε t SA (x) ≥ |ε t SA (x)|. We assume in this paper that we can estimate this error ε t SA (x). For example, Bayesian regression approaches like Gaussian processes give a variability estimate of the surrogate model at each x. Because of the estimation noise on the training points x i , f l (x i ) on which the surrogate model is built, a regression model seems a priori more adequate than an interpolation.When the optimizer provides a new design x, the SA error ε t SA (x) is compared to a userdefined threshold s 1 . If ε t SA (x) ≤ s 1 , the predictive value of the surrogate f t SA (x) is returned to Inria

rue Honoré d'Estienne d'Orves Bâtiment Alan Turing Campus de l'École Polytechnique 91120 Palaiseau Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

D Proof 4

Proof. For proving this, mathematical induction can be used. Let us assume that ∃l ∈ N + , so that X f

, y ∈ X , so that y x. Hence, y ∈ X f ,k P ⊆ X , so that y x, and

which means that:

Finally, Lemma 1 gives

P , which ends the inductive step of the proof, yielding

P , therefore, the mathematical induction proves that the robustness inclusion is verified.

E Proof 5

Proof. The triangle inequality gives :

Now, let us suppose that ∃a ∈ P c f X f ,k

Pi . This means that P c f l k X f ,k P ∩ a, ε max = ∅ with ε max being the m-dimensional vector where each component is equal to max

• In the first case i), the dominance can be formulated as follows: ∃j ∈ 1, N , so that

, which is contradictory with Assumption 1.

• The second case ii) implies that ∃b ∈ P

Pi ∈ f X f ,k Pj , ε max , which contradicts again Assumption 1.


Kalil Bernardino
email: kalilbernardino@gmail.com

Jolanta Świergiel
email: swiergiel@ifmpan.poznan.pl

Jan Jadżyn

Laurent Bouteiller
email: laurent.bouteiller@upmc.fr

André Farias

André Farias De Moura

Bulkiness as a design element

Molecular systems with large macrodipoles are useful in numerous fields such as responsive materials (that display piezo-, pyro-or ferroelectricity), 1 directional electron 2 or ion transport (with membrane proteins 3 or synthetic transporters 4 ) or catalysis (where long-range macrodipoleion interactions can help stabilize reactive intermediates 5,6 ). In this context, supramolecular polymers (i.e., linear and reversible assemblies of monomers) are of particular interest because of their synthetic accessibility, tunability and responsiveness. 7 To create a large macrodipole by assembly of polar monomers, it is essential to obtain a rigid final assembly, and the overwhelming approach to enforce rigidity is to use multiple point attachments between the monomers, such as multiple hydrogen bonds in benzenetricarboxamides [8][9][10][11][12][13][14] or cyclohexane-tricarboxamides. 15,16 When the monomers are held by strong covalent bonds, steric hindrance between the repeat units is a straightforward approach to impart rigidity to the resulting polymer. 17,18 Although intermolecular steric hindrance can probably also be expected to favour rigidity in supramolecular polymers, this simple concept has been completely neglected, ‡ probably because of the obvious detrimental effect on the size of the assemblies. 19 However, we now demonstrate that increasing intermolecular steric interactions between the monomers can actually result in assemblies with a significantly larger dipole moment, because the effect on the size is more than compensated by the effect on the rigidity of the assemblies.

sym-Dialkyl ureas (Chart 1) dissolved in non-polar solvents self-associate as hydrogen-bonded chains, as a direct consequence of the trans-trans conformation of the ureido moiety. [20][21][22] The formation of such macrodipoles is responsible for an increased dielectric constant of the solution. 23 For a given molecule, it is well-known that selfassociation is favoured by an increase in concentration or by a decrease in temperature. 21 Moreover, increasing the size of the urea substituents disfavours the formation of the assemblies, and leads to shorter chains. 21 In particular, IR spectroscopy measurements show that bulky dialkyl urea MPHU forms chains that are two to three times shorter than reference diethyl urea DEU (Fig. S1 andS2). sym-Dialkyl ureas are characterized by a significant monomer dipole, and the ordered placement of the monomer dipoles along the chains is responsible for the build-up of a large macrodipole. 20 Therefore one would expect longer chains to yield larger macrodipoles and thus a higher static permittivity of the solution. 23 However, dielectric spectroscopy measurements show that a solution of the bulky dialkyl urea (MPHU) is more polar than a solution of the reference diethyl urea (DEU, which actually forms the longest chains) (Fig. 1). This unexpected effect is quite significant: the static permittivity of the MPHU solution is about 50% higher than the value measured for DEU (at a mole fraction x = 0.04 and a temperature of 25°C).

Chart 1

To investigate the reasons for this effect, the conformation and the macrodipole of the chains were probed by molecular dynamics simulations. Starting from a solution of randomly dispersed monomers in an explicit solvent box (urea mole fraction x = 0.01), spontaneous aggregation took place for both solutes. After equilibrium, the average chain size was 8.9 ± 1.4 for DEU and 1.4 ± 0.1 for MPHU (i.e., a larger fraction of MPHU molecules were in monomer state instead of forming chains). These figures agree qualitatively with the expected tendency of the monomers with the smallest substituents to form longer chains, but they are smaller than the values deduced from experiment (Fig. S2). This discrepancy can be due to the

R N N R O H H R = C 2 H 5 CH 2 C 5 H 11 C 5 H 11 CH 3

DEU MPHU

limited size of the simulation system. § Besides the size of the chains, the most striking difference between both systems is the presence of cyclic structures in the case of DEU. Although cyclic supramolecular polymers are known to form when the repeat unit contains a flexible spacer, 24,25 to the best of our knowledge, there is no previous experimental or theoretical work suggesting the formation of cyclic structures for dialkyl urea supramolecular polymers. In the case of MPHU, due to the larger steric hindrance of alkyl groups, the formation of cyclic structures is apparently inhibited, at least for small chain sizes, and was not observed in our simulations. The average size of the hydrogenbonded chains is known to increase with the molar fraction (x) and decrease with the temperature (T). 21 See also Fig. S3 for the effect of temperature on the size of the assemblies.

It is instructive to look at some structures with the same chain size sampled from both simulations (and the corresponding macrodipole values) (Fig. 2). The average dipole moment of a monomer in our model is 4.4 D for DEU and 4.1 D for MPHU. In a hexamer, if the six units were perfectly aligned, the macrodipole would be 26.4 or 24.6 D, respectively. However, due to bends in the chain, the monomer dipoles can partially cancel each other out and the resulting macrodipole were actually smaller than these values. Noticeably, for DEU we can find both open and cyclic structures for N=6, and whenever a cycle is formed the dipoles of the monomers cancel each other out almost completely and the resulting macrodipole is even smaller than the dipole of a single monomer (Fig. 2, top). For MPHU, the formation of N=6 cycles is not possible due to the steric hindrance of the aliphatic chains. Taking the open structures into account, the more bended the structure, the smaller the macrodipole will be. As MPHU presents a greater resistance to deformations, the average macrodipole of MPHU chains, especially for N>3, is greater than for DEU chains of the same size. For larger chain sizes, the complexity of the chains increases and multiple bends can take place simultaneously, but this general remark is still valid. A more quantitative comparison between both solutes can be made by considering the distribution of all macrodipole values for various chain sizes (Fig. 3) instead of looking at the values for arbitrarily chosen structures. For N=4, both DEU and MPHU present a single population (i.e., no cycles) but the distribution for DEU is more spread, especially with a longer tail at small macrodipole values, due to its greater flexibility. For N=6, the formation of cycles takes place for DEU and the distribution of macrodipoles presents two populations. The main distribution has a maximum at ca. 20 D, and corresponds to open chains, whereas a minor population with macrodipoles smaller than 5 D corresponds to the cycles. There is no abrupt transition between both populations since DEU chains can be open and yet almost as bended as in a cycle. On the other hand, MPHU presents a single population for N=6, since the steric hindrance renders the chains too rigid to form cycles. This population also has a maximum at ca. 20 D but it is less spread than the one of DEU, especially on the small dipole side. In summary, both structural patterns must contribute to the different dielectric properties of the solutions of DEU and MPHU. Only DEU can form cycles with almost zero dipole moment, which have a very small contribution to the dielectric constant of the medium, while among open chains, those formed by DEU are more likely to bend into smaller macrodipole structures than those formed by MPHU.

The sampling for chains longer than 6 monomers was very limited for MPHU and hence only the results for DEU are shown in Fig. 3 for larger aggregates. For N>6, the formation of cycles is even more favourable and, despite the maximum of the open chain population being continuously displaced toward larger macrodipoles as the chain size increases, the distribution also becomes broader due to the increase in the possible number of conformations of the chain. This is an entropic effect: the perfect alignment of monomers that results in the largest macrodipole is only one among all possible conformational states of the chain and the total number of states increases as the chain becomes longer. Cycles were found even for chains as large as 30 DEU units, leading to a low macrodipole population within the overall distribution, although a clear separation between the "closed" and "open" chains populations was not discernible (Figures S4 and S5 in Supporting Information). The average macrodipoles for a chain of size N was computed and divided by N (Fig. 4) and corresponds to the average contribution of each repeat unit to the total dipole moment of a chain of size N. Despite the increase of the macrodipole with the chain size, the contribution per monomer decreases as N increases until it reaches some plateau, due to the partial cancellation of their individual dipoles. This plateau is reached only at ca. N=20 for DEU while for MPHU, due to the rigidity of the chains, it is reached already for N=3. For larger chains, the average contribution of each molecule is 1.4 D for DEU and 3.3 D for MPHU. For DEU, this value is more than 3 times lower than the monomer dipole moment (4.4 D). Even for MPHU the contribution per molecule is smaller than the monomer dipole moment (4.1 D), indicating some degree of disorder in the alignment of units, but much less than for DEU, for which the greater flexibility of the chains and the possibility of cycle formation leads to a greater decrease of the dipole moment as the chain increases. In conclusion, increasing the steric bulkiness of a monomer will certainly result in shorter supramolecular assemblies, but will also constrain their conformations. The macrodipole is a quantity that is affected by both effects, and we show that the latter can overwhelm the former. This fact should be taken into account while designing new supramolecular polymers with a large macrodipole for electric field responsiveness, transport phenomena or catalysis.

the research results reported within this paper. URL: http://sdumont.lncc.br.

Notes and references ‡ Intermolecular steric hindrance in supramolecular polymers has been exploited to avoid lateral aggregation 26 or to favour alternated copolymers from two monomers of differing bulkiness. 27 Steric hindrance is also well-known to allow internal conformational control of the monomers by constraining dihedral angles. 28,29 § In the case of DEU, the discrepancy is also due to the cyclic structures that were found in the simulations, but not taken into account in the modelling of the IR experimental data.

Fig. 1

 1 Fig. 1 Concentration (top) and temperature dependence (bottom) of the static permittivity of DEU and MPHU solutions in CCl4.The average size of the hydrogenbonded chains is known to increase with the molar fraction (x) and decrease with the temperature (T).21 See also Fig.S3for the effect of temperature on the size of the assemblies.

Fig. 2

 2 Fig. 2 Selected structures of hexamers formed in the simulations with the respective dipole moments in debye (D). Top: Cyclic structures of DEU; middle: open structures of DEU; bottom: open structures of MPHU. The urea groups are represented as van der Waals spheres while the aliphatic groups are represented as lines. Atoms: Silver -H, Cyan -C, Dark Blue -N, Red -O.

Fig. 3

 3 Fig. 3 Distribution of macrodipoles for selected cluster sizes for DEU (solid lines) and MPHU (dashed lines).

Fig. 4

 4 Fig. 4 Average macrodipole per monomer as a function of the polymer size (continuous black line). The dotted line is the average after the plateau is reached (N > 20 for DEU and N > 3 for MPHU). The horizontal bars stand for the value of the average ± the standard deviation. Top: DEU, bottom: MPHU. See also the analyses in different time windows of the simulation in Fig. S6, which demonstrated the convergence of the simulations and the significance of the data.

Acknowledgments

The authors are grateful to the Brazilian funding agencies CAPES, CNPq and FAPESP (process 2012/15147-4, 2013/07296-2 and 2017/12063-8) for financial support. AFM is grateful to MEC/PET for a fellowship. The authors acknowledge the National Laboratory for Scientific Computing (LNCC/MCTI, Brazil) for providing HPC resources of the SDumont supercomputer, which have contributed to


Mohsen Davoudkhani
email: mohsen.davoudkhani@inra.fr

Fabrice Mahé

Jean-Yves Dourmad

Alexandre Gohin

Eric Darrigrand

Florence Garcia-Launay

M Davoudkhani 𝟏

Economic optimization of

published or not. The documents may come

 Economic results of pig farming systems are highly variable and depend on the price of feeds, pig performance, and pork price.  Shipping strategy affects farm income since lightest pigs that don't reach the target weight at maximal fattening duration result in a lower payment.  Thus, feeding and shipping strategies are major levers for improvement. 1)Develop an optimization procedure that finds the best feeding and shipping strategies to maximize the profitability of the pigfattening unit.

2)Illustrate the potential of the model to improve profitability of the pig-fattening unit (20 batches of 400 pigs). The first phase The second phase  Means that do not share the same letter are significantly different (according to post-hoc Tukey Honestly Significant Difference (HSD) test at a 5% significance level). The objective is to optimize feeding and shipping strategies in order to maximize the average gross margin per fattened pig.

Scenarios



  The optimization procedure is suitable to compare different strategies and improve economic performances of the fattening-unit.  Accounting for more decision variables (i.e. feeding & shipping strategies) tends to improve profitability.  Further work will include the feed formulation problem to the whole optimization procedure and investigate :Possible synergies and/or trade-offs between economic and environmental objectives. A in the first phase (𝛼 1 )

  𝟐 , J.Y. DOURMAD 𝟏 , A. GOHIN 𝟑 , E. DARRIGRAND 𝟐 , F. GARCIA-LAUNAY 𝟏 Feed A % of feed A in the second phase (𝛼 2 ) Methodology (With I, index of pig)

  1 , 𝑥, 𝛼 2 , 𝑇𝑊, 𝑀𝑎𝑥 𝑑 Feeding strategy (% of feed A in the first (𝛼 1 ) and second (𝛼 2 ) phases and live weight at diet change (𝑥)