Ana Luísa Custódio

Youssef Diouane
email: youssef.diouane@isae-supaero.fr

Rohollah Garmanjani
email: rohollahgarmanjanir.garmanjani@fct.unl.pt

Elisa Riccietti

Worst-Case Complexity Bounds of Directional Direct-Search Methods for Multiobjective Optimization

Keywords: Multiobjective unconstrained optimization, Derivative-free optimization methods, Directional direct-search, Worst-case complexity, Nonconvex smooth optimization Mathematics Subject Classification 90C29, 90C30, 90C56, 90C60

Direct Multisearch is a well-established class of algorithms, suited for multiobjective derivative-free optimization. In this work, we analyze the worst-case complexity of this class of methods in its most general formulation for unconstrained optimization. Considering nonconvex smooth functions, we show that to drive a given criticality measure below a specific positive threshold, Direct Multisearch takes at most a number of iterations proportional to the square of the inverse of the threshold, raised to the number of components of the objective function. This number is also proportional to the size of the set of linked sequences between the first unsuccessful iteration and the iteration immediately before the one where the criticality condition is satisfied. We then focus on a particular instance of Direct Multisearch, which considers a more strict criterion for accepting new nondominated points. In this case, we can establish a better worst-case complexity bound, simply proportional to the square of the inverse of the threshold, for driving the same criticality measure below the considered threshold.

Introduction

Multiobjective optimization is a challenging domain in nonlinear optimization [START_REF] Marler | Survey of multi-objective optimization methods for engineering[END_REF][START_REF] Ehrgott | Multicriteria Optimization[END_REF], when there are different conflicting objectives that need to be optimized. Difficulties Communicated by Xinmin Yang.

B Ana Luísa Custódio alcustodio@fct.unl.pt Extended author information available on the last page of the article increase if derivatives are not available, neither can be numerically approximated due to the associated computational cost or to the presence of noise [START_REF] Custódio | Recent developments in derivative-free multiobjective optimization[END_REF]. We are then in the domain of multiobjective derivative-free optimization, which often appears in problems where the objective function is evaluated through numerical simulation (for complementary information on single-objective derivative-free optimization methods, see [START_REF] Kolda | Optimization by direct search: new perspectives on some classical and modern methods[END_REF][START_REF] Conn | Introduction to Derivative-Free Optimization[END_REF][START_REF] Audet | Derivative-Free and Blackbox Optimization[END_REF]).

We are interested in establishing worst-case complexity (WCC) bounds for directional direct-search, a class of derivative-free optimization methods, when used for solving unconstrained multiobjective optimization problems. Each iteration of this class of algorithms can be divided into a search step and a poll step, being the former optional. In fact, the convergence properties of these methods rely on the procedure implemented in the poll step [START_REF] Custódio | Direct multisearch for multiobjective optimization[END_REF]. The objective function is evaluated at a finite set of points, corresponding to directions with good geometrical properties, scaled by a stepsize parameter. The decision of accepting or rejecting a new evaluated point is solely based on the objective function value, no model is built for the objective function, neither any attempt of estimating derivatives is considered [START_REF] Custódio | Direct multisearch for multiobjective optimization[END_REF]. The criterion for accepting a new evaluated point makes use of the partial order induced by the concept of Pareto dominance (cf. Definition 2.1).

In the last decades, there has been a growing interest in evaluating the performance of optimization algorithms in the worst-case scenario (see, for instance, [START_REF] Cartis | On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization[END_REF][START_REF] Dodangeh | Worst case complexity of direct search under convexity[END_REF][START_REF] Fliege | Complexity of gradient descent for multiobjective optimization[END_REF][START_REF] Garmanjani | Smoothing and worst-case complexity for direct-search methods in nonsmooth optimization[END_REF][START_REF] Grapiglia | On the convergence and worst-case complexity of trust-region and regularization methods for unconstrained optimization[END_REF][START_REF] Gratton | Direct search based on probabilistic descent[END_REF][START_REF] Konečný | Simple Complexity Analysis of Simplified Direct Search[END_REF][START_REF] Nesterov | Introductory Lectures on Convex Optimization[END_REF][START_REF] Vicente | Worst case complexity of direct search[END_REF]). Usually, the performance of an algorithm is measured by the number of iterations (or function evaluations) required to drive either some criticality measure below a given positive threshold or the function value below the threshold distance to the optimal function value.

In single-objective nonconvex smooth unconstrained optimization, Nesterov [15, Example 1.2.3] derived a WCC bound of O -2 for gradient descent algorithms. A similar bound has been achieved for trust-region [START_REF] Gratton | Recursive trust-region methods for multiscale nonlinear optimization[END_REF] and line-search [START_REF] Cartis | Worst-case evaluation complexity of non-monotone gradientrelated algorithms for unconstrained optimization[END_REF] methods. Nesterov and Polyak [START_REF] Nesterov | Cubic regularization of Newton method and its global performance[END_REF] investigated the use of cubic regularization techniques, and then Cartis et al. [START_REF] Cartis | Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function-and derivative-evaluation complexity[END_REF] proposed a generalization to an adaptive regularized framework using cubics. For the latter class of methods, by considering second-order algorithmic variants, this bound was improved to O -3/2 , including a derivative-free approach where derivatives are approximated by finite-differences [START_REF] Cartis | On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization[END_REF].

In the context of single-objective derivative-free optimization, directional direct search was the first class of algorithms for which worst-case complexity bounds were established [START_REF] Vicente | Worst case complexity of direct search[END_REF]. The author considered the broad class of directional direct-search methods which use sufficient decrease as globalization strategy and established that this class of algorithms shares, in terms of , the worst-case complexity bound of steepest descent for the unconstrained minimization of a nonconvex smooth function. The complexity of directional direct-search methods for the optimization of convex smooth functions has been addressed in [START_REF] Dodangeh | Worst case complexity of direct search under convexity[END_REF]. The bound of O -2 has been improved to O -1 , which is identical, in terms of , to the one of steepest descent, under convexity. Complexity results have also been established for the nonsmooth case. In [START_REF] Garmanjani | Smoothing and worst-case complexity for direct-search methods in nonsmooth optimization[END_REF], a class of smoothing direct-search methods for the unconstrained optimization of nonsmooth functions was proposed and it was shown that the worst-case complexity of this procedure is roughly one order of magnitude worse than the one for directional direct-search or the steepest descent method, when applied to smooth functions. Other types of direct-search methods have been analyzed in the literature. A probabilistic descent directional direct-search algorithm has been proposed in [START_REF] Gratton | Direct search based on probabilistic descent[END_REF], which is characterized by the fact that poll directions only guarantee descent with a certain fixed probability. The authors establish a worst-case complexity bound of O -2 , which holds with a high probability. A restricted version of directional direct-search methods, where no stepsize increase is allowed, along with a worst-case complexity analysis has also been studied in [START_REF] Konečný | Simple Complexity Analysis of Simplified Direct Search[END_REF]. In [START_REF] Bergou | Stochastic three points method for unconstrained smooth optimization[END_REF], considering stepsizes independent from the results of each iteration, the authors propose and analyze a random derivative-free optimization algorithm which evaluates three points per iteration and enjoys a worst-case complexity bound of O -2 .

As for the worst-case complexity of derivative-based methods for solving unconstrained multiobjective optimization problems, it has been shown in [START_REF] Grapiglia | On the convergence and worst-case complexity of trust-region and regularization methods for unconstrained optimization[END_REF] that trust-region methods provide a worst-case complexity bound of O -2 . A similar bound has been derived in [START_REF] Fliege | Complexity of gradient descent for multiobjective optimization[END_REF] and improved to O -1 or O(log( -1 )), assuming convexity or strong convexity of the different objective function components. In [START_REF] Calderón | On high-order model regularization for multiobjective optimization[END_REF], complexity bounds have also been derived for p-order regularization methods, this time under a Hölder continuity assumption on the derivatives of the objective function components.

Regarding the WCC of multiobjective derivative-free optimization algorithms, a first work [START_REF] Žilinskas | On the worst-case optimal multi-objective global optimization[END_REF] showed that an optimal worst-case algorithm for Lipschitz functions can be reduced to the computation of centers of balls producing an uniform cover of the feasible region. A biobjective optimization algorithm for single variable, twice continuously differentiable functions was proposed and analyzed in [START_REF] Calvin | On efficiency of a single variable bi-objective optimization algorithm[END_REF]. The authors prove that after ∈ N function evaluations, the number of points that do not belong to the Pareto front is of O(log( ) 2 ).

In this work, we first establish a worst-case complexity bound for the original Direct Multisearch (DMS) [START_REF] Custódio | Direct multisearch for multiobjective optimization[END_REF] class of methods. We show that the DMS algorithm takes at most O |L( )| -2m iterations for driving a criticality measure below > 0, where |L( )| represents the cardinality of the set of linked sequences between the first unsuccessful iteration and the iteration immediately before the one where the criticality condition is satisfied. We then focus on a particular instance of this class of algorithms, which considers a more restrictive condition to accept new nondominated points. For that, we resort to the standard min-max formulation of the multiobjective optimization problem, which is widely used in the literature (e.g., see [START_REF] Villacorta | A trust-region method for unconstrained multiobjective problems with applications in satisficing processes[END_REF] and [START_REF] Grapiglia | On the convergence and worst-case complexity of trust-region and regularization methods for unconstrained optimization[END_REF]Sect. 4.2] for multiobjective trust-region methods or [START_REF] Marler | Survey of multi-objective optimization methods for engineering[END_REF] for additional references). We are able to establish that this particular instance of DMS enjoys a worst-case complexity bound of O -2 for driving the same criticality measure below > 0. This bound is identical, in terms of , to the one derived for multiobjective gradient descent [START_REF] Fliege | Complexity of gradient descent for multiobjective optimization[END_REF] and trust-region [START_REF] Grapiglia | On the convergence and worst-case complexity of trust-region and regularization methods for unconstrained optimization[END_REF] methods.

With regard to the strategy used to establish the WCC of the min-max formulation, we highlight that it is not equivalent to a straightforward application of the technique used for single-objective optimization to the scalar function obtained by considering the maximum of the components of the objective function. In particular, the analysis in [START_REF] Vicente | Worst case complexity of direct search[END_REF], which establishes the WCC of directional direct-search for single-objective optimization, relies on the differentiability of the objective function, which does not hold when a min-max formulation is considered. However, the analysis we propose takes into account the differentiability of the single components.

The remaining of the paper is organized as follows. In Sect. 2, we recall some known results on multiobjective optimization, which will be used throughout the paper. The complexity analysis of DMS in its most general form will be established in Sect. [START_REF] Custódio | Recent developments in derivative-free multiobjective optimization[END_REF]. Section 4 introduces the min-max formulation and establishes a worst-case complexity bound for it. Some conclusions are drawn in Sect. 5.

Preliminaries

Let us consider the unconstrained multiobjective derivative-free optimization problem, defined as

min F(x) := ( f 1 (x), . . . , f m (x)) s.t. x ∈ R n , ( 1
)
where m ≥ 2, and each f i : R n → R ∪ {+∞}, i ∈ I := {1, . . . , m} is a continuously differentiable function with Lipschitz continuous gradient. When solving a multiobjective optimization problem of type (1), the goal is to identify a local Pareto minimizer [START_REF] Fliege | Steepest descent methods for multicriteria optimization[END_REF], i.e., a point x * ∈ R n such that it does not exist another point x in a neighborhood N of x * that dominates x * , according to Definition 2.1.

Definition 2.1 (Pareto dominance)

We say that point x dominates point x * when F(x) ≺ F F(x * ), i.e., when

F(x * ) -F(x) ∈ R m + \{0}.
Point x * is then a local Pareto minimizer, if there is a neighborhood N of x * where x * is nondominated, meaning F(x) ⊀ F F(x * ) for all x ∈ N .

A necessary condition for x * ∈ R n to be a local Pareto minimizer is [START_REF] Fliege | Steepest descent methods for multicriteria optimization[END_REF]:

∀d ∈ R n , ∃i d ∈ I : ∇ f i d (x * ) d ≥ 0. (2)
A point satisfying (2) is called a Pareto critical point [START_REF] Fliege | Steepest descent methods for multicriteria optimization[END_REF]. We are then interested in finding Pareto critical points. In what comes next, • will denote the vector or matrix 2 -norm. Following [START_REF] Fliege | Steepest descent methods for multicriteria optimization[END_REF], to characterize Pareto critical points, we are going to use, for a given x ∈ R n , the function:

μ(x) := -min d ≤1 max i∈I ∇ f i (x) d. ( 3
)
Fliege and Svaiter [START_REF] Fliege | Steepest descent methods for multicriteria optimization[END_REF] showed how some properties of μ(x), as reported in the following lemma, relate to the concept of Pareto critical points. We denote by F(x) the solution set of (3).

Lemma 2.1 [START_REF] Fliege | Steepest descent methods for multicriteria optimization[END_REF]Lemma 3] For a given x ∈ R n , assume that, for all i ∈ I , the function f i is continuously differentiable at x and let μ(x) be defined as in [START_REF] Custódio | Recent developments in derivative-free multiobjective optimization[END_REF]. Then,

1. μ(x) ≥ 0; 2.
If x is a Pareto critical point of (1), then 0 ∈ F(x) and μ(x) = 0; 3. If x is not a Pareto critical point of (1), then μ(x) > 0 and for any d ∈ F(x) we have

∇ f j (x) d ≤ max i∈I ∇ f i (x) d < 0, ∀ j ∈ I ,
i.e., d is a descent direction of (1); 4. The function x → μ(x) is continuous;

5. If x k converges to x, d k ∈ F(x k ) and d k converges to d, then d ∈ F( x).
Function μ can then be used to provide information about Pareto criticality of a given point and plays a role similar to the one of the norm of the gradient in singleobjective optimization.

The following lemma describes the relationship between function μ and the norm of the gradient of the components of F. Lemma 2.2 For a given x ∈ R n and > 0, assume that, for all i ∈ I ,

∇ f i (x) is well defined. If μ(x) > , then ∇ f i (x) > , for all i ∈ I . Proof If μ(x) > , then min d ≤1 max i∈I ∇ f i (x) d < -.
As a consequence, it exists d such that d ≤ 1 and

max i∈I ∇ f i (x) d < -, that is, for all i ∈ I , we have -∇ f i (x) d > . Hence, as -∇ f i (x) d ≤ ∇ f i (x) d ≤ ∇ f i (x)
, the thesis follows.

In the following, we set μ k := μ(x k ), for all k ≥ 0.

Direct Multisearch

Direct Multisearch (DMS) was proposed in [START_REF] Custódio | Direct multisearch for multiobjective optimization[END_REF] and generalizes directional directsearch to multiobjective derivative-free optimization. It is a general class of methods that can encompass many algorithmic variants, depending, for instance, on the globalization strategy considered. In this work, we will require sufficient decrease for accepting new points, via the use of a forcing function ρ :]0, +∞[-→]0, +∞[. Following [START_REF] Kolda | Optimization by direct search: new perspectives on some classical and modern methods[END_REF], ρ is a continuous nondecreasing function, satisfying ρ(t)/t → 0 when t ↓ 0. We consider the typical forcing function ρ(t) = ct p , with p > 1, and c > 0.

DMS makes use of the strict partial order induced by the cone R m + . Let D(L) ⊂ R m be the image of the set of points dominated by a list of evaluated points L and let D(L; a) be the set of points whose distance in the ∞ -norm to D(L) is no larger than a > 0. Algorithm 1 corresponds to an instance of the original DMS [START_REF] Custódio | Direct multisearch for multiobjective optimization[END_REF] method, which uses a globalization strategy based on the imposition of a sufficient decrease condition.

Algorithm 1: DMS using sufficient decrease as globalization strategy.

Initialization

Choose

x 0 ∈ R n with f i (x 0 ) < +∞, ∀i ∈ I , α 0 > 0 an initial stepsize, 0 < β 1 ≤ β 2 <
1 the coefficients for stepsize contraction and γ ≥ 1 the coefficient for stepsize expansion. Let D be a set of positive spanning sets. Initialize the list of nondominated points and corresponding stepsize parameters L 0 = {(x 0 ; α 0 )}.

For k = 0, 1, 2, . . .

Selection of an iterate point:

Order the list L k according to some criteria and select the first item (x; α) ∈ L k as the current iterate and stepsize parameter (thus setting DMS declares an iteration as successful when there are modifications in the list of nondominated points, meaning that a new point x was accepted, such that

(x k ; α k ) = (x; α)).
F(x) / ∈ D(L; ρ(α))
, where α represents a stepsize parameter associated with the current iteration.

For analyzing the worst-case behavior of the algorithms presented in this paper, we will need the following assumptions with regard to the component functions in [START_REF] Marler | Survey of multi-objective optimization methods for engineering[END_REF].

F max := max{ f max 1 , . . . , f max m }. Assumption 3.3 The set {x ∈ R n : F(x) / ∈ D({x 0 })} is compact.
At an unsuccessful iteration of Algorithm 1, none of the components of the objective function is improved, since no new point is added to the list. However, the use of Pareto dominance to accept new points implies that successful iterations do not necessarily correspond to points that improve all components of the objective function. In fact, at some successful iterations, some of these components could increase the corresponding value. Nevertheless, at every successful iteration, the hypervolume (see Definition 3.1 or [START_REF] Zitzler | Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications[END_REF]) corresponding to the current list of nondominated points always increases. Definition 3.1 [3, Definition 5.2] The hypervolume indicator (or S-metric, from 'Size of space covered') for some (approximation) set A ⊂ R m and a reference point r ∈ R m that is dominated by all the points in A is defined as:

HI(A) := Vol{b ∈ R m : b ≤ r ∧ ∃a ∈ A : a ≤ b} = Vol a∈A [a, r ] .
The inequalities should be understood componentwise, Vol(•) denotes the Lebesgue measure of a m-dimensional set of points, and [a, r ] denotes the interval box with lower corner a and upper corner r .

Define F(L) as the image set of a list of points L, i.e., F(L) := {F(x) : (x, α) ∈ L}. We will consider r = ( f max 1 , . . . , f max m ), when computing a hypervolume. Lemma 3.1 quantifies the increase in the hypervolume, associated with successful iterations.

Lemma 3.1

In Algorithm 1, for a successful iteration k ≥ 0, we have

HI(F(L k+1 )) -HI(F(L k )) ≥ (ρ(α k )) m . Proof If k is a successful iteration, then L k+1 = L k . Let x ∈ L k+1 be such that x / ∈ L k . In this situation, F(x) / ∈ D(L k ; ρ(α k )). Thus, B ∞ (F(x), ρ(α k )) ∩ D(L k ) = ∅, where B ∞ (F(x), ρ(α k )) represents the ∞ ball centered at F(x), with radius ρ(α k ).
This means that at least a hypercube of volume ρ(α k ) m was added to the dominated region (the one belonging to F(x) + (R + 0 ) m ). Figure 1 illustrates the situation, where for a biobjective problem, at a successful iteration, the previous condition is satisfied as an equality. The initial list of nondominated points is formed by the two points represented by the dots. The point corresponding to the star, in the interior of the shaded region, was accepted as a new nondominated point, since it satisfies the sufficient decrease condition. Thus, the hypervolume corresponding to the new set of nondominated points has increased exactly in ρ(α k ) 2 .

As it is done in classical directional direct-search [START_REF] Kolda | Optimization by direct search: new perspectives on some classical and modern methods[END_REF], we assume that all positive spanning sets considered by the algorithm include bounded directions. In multiobjective optimization, the cone of descent directions for all components of the objective function can be as narrow as one would like (see Remark 3.1). So, we need to assume density of the directions at a given limit point, as it is considered in the convergence analysis of DMS [START_REF] Custódio | Direct multisearch for multiobjective optimization[END_REF]. The existence of at least one convergent refining subsequence is a direct consequence of Assumption 3.3 and the use of sufficient decrease for accepting new nondominated points. Refining directions are limits of normalized poll directions associated with the refining subsequence. Without loss of generality, we will assume that all the positive spanning sets considered have normalized directions. Assumption 3.4 Consider Algorithm 1 and let x * be the limit point of a convergent refining subsequence. Assume that the set of refining directions associated with x * is dense in the unit sphere.

We will make use of the following result, which establishes a relationship between the stepsize parameter at an unsuccessful iteration of a directional direct-search method and μ D k (x k ), an approximation to μ k = μ(x k ) which only considers the poll directions. Lemma 3.2 Let Assumption 3.1 hold. Let k be an unsuccessful iteration of Algorithm 1, D k be the positive spanning set considered, and α k > 0 be the corresponding stepsize. Define

μ D k (x) := - min d∈D k , d ≤1 max i∈I ∇ f i (x) d. ( 4
)
Then,

μ D k (x k ) ≤ L max 2 α k + ρ(α k ) α k . ( 5
)
Proof If iteration k is unsuccessful, then for each direction

d k ∈ D k there is an index i(d k ) ∈ I such that f i(d k ) (x k + α k d k ) ≥ f i(d k ) (x k ) -ρ(α k ).
Hence, for each direction

d k ∈ D k , 0 ≤ f i(d k ) (x k + α k d k ) -f i(d k ) (x k ) + ρ(α k ) = 1 0 ∇ f i(d k ) (x k + tα k d k ) α k d k dt + ρ(α k ) Adding -α k ∇ f i(d k ) (x k ) d k to both sides yields: -α k ∇ f i(d k ) (x k ) d k ≤ 1 0 ∇ f i(d k ) (x k + tα k d k ) α k d k -α k ∇ f i(d k ) (x k ) d k dt + ρ(α k ) ≤ α 2 k L max 2 d k 2 + ρ(α k ), so that -∇ f i(d k ) (x k ) d k ≤ α k L max 2 d k 2 + ρ(α k ) α k .
Then,

max i∈I ∇ f i (x k ) d k ≥ -α k L max 2 d k 2 - ρ(α k ) α k
This is true for all d k ∈ D k so the thesis holds.

Hereafter, we set μ D k := μ D k (x k ). In the current work, WCC bounds will be derived for driving μ D k below > 0. However, the goal is to establish bounds for having μ k ≤ . For this purpose, we consider Assumption 3.5. A somehow similar assumption has already been used within the context of trust-region derivative-free methods for multiobjective optimization (see [START_REF] Thomann | A trust-region algorithm for heteregeneous multiobjective optimization[END_REF]Assumption 4.8]). Assumption 3.5 There exists C 1 > 0 such that

|μ D k -μ k | ≤ C 1 μ D k , ∀k ≥ 0. ( 6
)
Remark 3.1 We note that Assumption 3.5 requires the nonnegativity of μ D k at every iteration, which may not hold. In such cases, additional directions could be added to the positive spanning sets considered as poll directions. Such procedure is supported by Assumption 3.4.

However, there are cases where Assumption 3.5 can be easily satisfied. Let us consider the following biobjective function:

F(x) := 1 2 x -c 1 2 , x -c 2 2 ,
where c 1 = (-1, 1) and c 2 = -c 1 . This is a biobjective version of a single-objective variant of the Dennis-Woods function [START_REF] Woods | Optimization on microcomputers: the Nelder-Mead simplex algorithm[END_REF] introduced in [START_REF] Kolda | Optimization by direct search: new perspectives on some classical and modern methods[END_REF] (see also [START_REF] Conn | Introduction to Derivative-Free Optimization[END_REF]). The singleobjective function has been used to show that coordinate search (which considers, at every iteration, the positive spanning set D k = [I -I ], where I represents the identity matrix) stalls at any point (a, a) , where a = 0 (see [START_REF] Kolda | Optimization by direct search: new perspectives on some classical and modern methods[END_REF][START_REF] Conn | Introduction to Derivative-Free Optimization[END_REF]). We will show that, for this biobjective problem, when considering the coordinate directions as positive spanning set, Assumption 3.5 holds for the majority of points in R 2 . When applying DMS, for simplicity, we drop the iteration index k and assume that the set of poll directions is

D = [I -I ]. Then, for any x ∈ R 2 , one has μ D (x) = -min{x 1 + 1, x 2 + 1, -x 1 + 1, -x 2 + 1}. Thus, as long as x belongs to B = {x ∈ R 2 : |x 1 | > 1 ∨ |x 2 | > 1}, μ D (x)
will be positive. On the other hand,

μ(x) = max d =1 min{-∇ f 1 (x) d, -∇ f 2 (x) d} ≤ min max d =1 -∇ f 1 (x) d, max d =1 -∇ f 2 (x) d
We will show that the assumption holds for all the points in B such that x 1 > 1 and x 2 > 1. For the other points in B a similar reasoning can be applied. If x 1 > 1 and x 2 > 1, one gets that μ D (x) = max{x 1 -1, x 2 -1} and μ(x) ≤ min μ 1 (x), μ 2 (x) , where

μ 1 (x) := (x 1 -1) (x 1 -1) 2 (x 1 -1) 2 + (x 2 + 1) 2 + (x 2 + 1) (x 2 + 1) 2 (x 1 -1) 2 + (x 2 + 1) 2 , μ 2 (x) := (x 1 + 1) (x 1 + 1) 2 (x 1 + 1) 2 + (x 2 -1) 2 + (x 2 -1) (x 2 -1) 2 (x 1 + 1) 2 + (x 2 -1) 2 .
Then, it holds

μ 1 (x) μ D (x) ≤ (x 1 -1) + (x 2 + 1) x 1 -1 ≤ x 1 + x 2 x 1 -1 , μ 2 (x) μ D (x) ≤ (x 1 + 1) + (x 2 -1) x 2 -1 ≤ x 1 + x 2 x 2 -1 .
Hence, in this case, inequality (6) holds with

C 1 ≥ max x 1 +x 2 x 1 -1 , x 1 +x 2 x 2 -1 -1. If
x is far from the border of B, this constant will assume reasonable values. For example, if we assume 2 ≤ x 1 , x 2 ≤ 5, then C 1 = 6.

Difficulties arise when x /

∈ B (in which case μ D ≤ 0) or when x is close to the border of B (which makes the constant C 1 large). In particular, if x = (a, a) and a → 0, the cone of descent directions will become as narrow as one would like. In such cases, it is advisable to rotate the set of polling directions. For example, to make sure that Assumption 3.5 holds at any point x = (a, a) with |a| < 1, a possibility would be to choose, for l ≥ 1, 2 l-1 maximal positive basis {R i D} 0≤i≤2 l-1 -1 , where

R i = cos(iθ) -sin(iθ) sin(iθ) cos(iθ) ,
with θ = π 2 l the angle between the generators of the cone of descent directions. Therefore, when a → 0 (or equivalently θ → 0), Assumption 3.5 is satisfied at the cost of increasing the number of function evaluations.

In the following theorem, we will derive a bound on the number of successful iterations required to drive μ k below a given small positive threshold. For each pair of indexes k 1 < k 2 , we will denote by U k 1 (k 2 ) and S k 1 (k 2 ) the set of unsuccessful and successful iterations from k 1 to k 2 , respectively. We will also denote by k 0 the index of the first unsuccessful iteration. We remark that the existence of such index is ensured by Assumption 3.2, from which one can prove that Algorithm 1 generates a sequence of iterates satisfying lim inf k→+∞ α k = 0 [START_REF] Custódio | Direct multisearch for multiobjective optimization[END_REF]. [START_REF] Marler | Survey of multi-objective optimization methods for engineering[END_REF], with the choice of forcing function ρ(t) = ct p , p > 1, c > 0. Let Assumptions 3.1, 3.2, and 3.5 hold. Let k 0 be the index of the first unsuccessful iteration. Given any ∈ ]0, 1[, assume that μ k 0 > and let j 1 be the first iteration after k 0 such that μ j 1 +1 ≤ . Then, to achieve

Theorem 3.1 Consider the application of Algorithm 1 to problem

μ j 1 +1 ≤ starting from k 0 , Algorithm 1 takes at most |S k 0 ( j 1 )| = O - pm min( p-1,1) successful iterations.
Proof Let us assume that μ k > , for k = k 0 , . . . , j 1 . Using Assumption 3.5 we have

< μ k = |μ k -μ D k | + μ D k ≤ (C 1 + 1)μ D k . ( 7
)
Hence, we obtain

μ D k > /(1 + C 1 ).
In view of Lemma 3.2, for an unsuccessful iteration k, we have

μ D k ≤ L max 2 α k + ρ(α k ) α k .
Thus,

1 + C 1 < L max 2 α k + ρ(α k ) α k ,
which then implies, when α k < 1,

< L 1 α min( p-1,1) k ,
where

L 1 = (1 + C 1 ) L max 2 + c . If α k ≥ 1, then α k > .
Hence, by combining the two cases (α k ≥ 1 and α k < 1) and having < 1, when k is an unsuccessful iteration, we have

α k > L 2 1 min( p-1,1) , ( 8
)
where

L 2 = min 1, L - 1 min( p-1,1) 1 .
Let k be a successful iteration and U k 0 (k) = {k 0 , k 1 , . . . , k u } with k u < k be the set of unsuccessful iterations from k 0 to k. From Lemma 3.1 and by the choice of forcing function,

HI(F(L k+1 )) -HI(F(L k u )) ≥ (k -k u )(c( min k u +1≤t≤k α t ) p ) m ≥ |S k u (k)|(cβ p 1 α p k ) m , for some 0 ≤ ≤ u.
Notice that the second inequality holds as it is possible to backtrack from any iteration t ∈ {k u + 1, . . . , k} to some previous unsuccessful k ∈ U k 0 (k) iteration and have

α t ≥ β 1 α k .
Thus, in view of [START_REF] Cartis | On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization[END_REF],

HI(F(L k+1 )) -HI(F(L k u )) ≥ |S k u (k)| cβ p 1 L p 2 p min( p-1,1) m .
By a similar reasoning, for 1 ≤ i ≤ u, we obtain

HI(F(L k i )) -HI(F(L k i-1 )) ≥ |S k i-1 (k i )| cβ p 1 L p 2 p min( p-1,1) m .
Therefore, using the two inequalities above for k = k 0 , . . . , j 1 , we obtain

HI(F(L j 1 +1 )) -HI(F(L k 0 )) ≥ |S k 0 ( j 1 )| cβ p 1 L p 2 p min( p-1,1) m . Since F max -F min m ≥ HI(F(L j 1 +1 )) -HI(F(L k 0 )), the proof is completed.
Now, in order to obtain a bound on the total number of iterations for driving μ k below a given threshold, it remains to find a bound on the number of unsuccessful iterations. For that, we will adapt the definition of linked sequences, introduced in [START_REF] Liuzzi | A derivative-free approach to constrained multiobjective nonsmooth optimization[END_REF]. Definition 3.3 Consider {L k } k∈N the sequence of sets of nondominated points generated by Algorithm 1. A linked sequence between iterations i and j (i < j) is a finite sequence {(x l k , α l k )} k∈{1,...,n l } of maximum length such that n l ≤ ji + 1, (x l k , α l k ) ∈ ∪ j r =i L r for all k ∈ {1, . . . , n l }, and for any k ∈ {2, . . . , n l } and r ∈ {i + 1, . . . , j}, the pair

(x l k , α l k ) ∈ L r is generated by (x l k-1 , α l k-1 ) ∈ L p , with i ≤ p < r .
Theorem 3.2 establishes a bound on the number of unsuccessful iterations required for driving μ k below a given threshold. Theorem 3.2 Let all the assumptions of Theorem 3.1 hold. Then, to achieve μ k ≤ starting from k 0 , Algorithm 1 takes at most

|U k 0 ( j 1 )| ≤ |L j 1 k 0 | ⎡ ⎢ ⎢ ⎢ ⎢ - log(γ ) log(β 2 ) |S k 0 ( j 1 )| - log(α l 1 ) log(β 2 ) + log β 1 L 2 1 min( p-1,1) log(β 2 ) ⎤ ⎥ ⎥ ⎥ ⎥
unsuccessful iterations, where α l 1 denotes the stepsize associated to one of the points in L k 0 and |L j 1 k 0 | the cardinality of the set of all linked sequences between k 0 and j 1 .

Proof Let {(x l k , α l k )} k∈{1,...,n l } be a linked sequence between k 0 and j 1 . Let S k 0 (n l ) and U k 0 (n l ) be, respectively, the set of successful and unsuccessful iterations in the sequence. Assume U k 0 (n l ) = ∅. Since, for any 1

≤ k < n l -1, either α l k+1 ≤ β 2 α l k (if the iteration is unsuccessful) or α l k+1 ≤ γ α l k (if the iteration is successful), we obtain by induction α l n l ≤ α l 1 γ |S k 0 (n l )| β |U k 0 (n l )| 2 , which, in turn, implies from log(β 2 ) < 0 |U k 0 (n l )| ≤ - log(γ ) log(β 2 ) |S k 0 (n l )| - log(α l 1 ) log(β 2 ) + log(α l n l ) log(β 2 ) .
From log(β 2 ) < 0 and the lower bound (8) on α k , we obtain

|U k 0 (n l )| ≤ - log(γ ) log(β 2 ) |S k 0 (n l )| - log(α l 1 ) log(β 2 ) + log β 1 L 2 1 min( p-1,1) log(β 2 )
.

The last inequality holds trivially when

U k 0 (n l ) = ∅. Let L j 1
k 0 denote the set of indexes of all linked sequences between k 0 and j 1 . Then,

|U k 0 ( j 1 )| ≤ l∈L j 1 k 0 |U k 0 (n l )| ≤ |L j 1 k 0 | max l∈L j 1 k 0 |U k 0 (n l )| ≤ |L j 1 k 0 | max l∈L j 1 k 0 ⎡ ⎢ ⎣- log(γ ) log(β 2 ) |S k 0 (n l )| - log(α l 1 ) log(β 2 ) + log β 1 L 2 1 min( p-1,1) log(β 2 ) ⎤ ⎥ ⎦ . Since n l ≤ j 1 -k 0 + 1, one has |S k 0 (n l )| ≤ |S k 0 ( j 1 )| for all l ∈ L j 1 k 0 . Thus, |U k 0 ( j 1 )| ≤ |L j 1 k 0 | ⎡ ⎢ ⎣- log(γ ) log(β 2 ) |S k 0 ( j 1 )| - log(α l 1 ) log(β 2 ) + log β 1 L 2 1 min( p-1,1) log(β 2 ) ⎤ ⎥ ⎦ .
In the previous bound, the size of the second term in the sum can be easily bounded. In fact, from Theorem 3.1 we know that there is a finite number of successful iterations, before driving μ below the given threshold. The increase in the stepsize can be controlled by setting γ = 1 or by considering an upper bound for the stepsize itself (see [START_REF] Dodangeh | Worst case complexity of direct search under convexity[END_REF]).

Combining Theorems 3.1 and 3.2, it can be seen that Algorithm 1 takes at most

O |L( )| - pm min( p-1,1)
iterations to bring μ k < for some k ≥ 0, where |L( )| represents the size of the set of linked sequences between the first unsuccessful iteration and the iteration immediately before the one where the criticality condition is satisfied. The best complexity bound is then derived by setting p = 2, which leads to the complexity bound of O |L( )| -2m . The WCC bounds of Algorithm 1 in terms of the number of function evaluations are established in the following corollary.

Remark 3.2

With regard to the number of function evaluations in Corollary 3.1, since the computational cost of evaluating each component of the objective function might not be the same, we have considered the computational cost of F and count the number of times that it is evaluated at each iteration, rather than counting separately the number of component functions evaluations.

One can see that the bound for DMS, in terms of , does not conform with the bound O -2 for the gradient descent derived in [START_REF] Fliege | Complexity of gradient descent for multiobjective optimization[END_REF] for problem [START_REF] Marler | Survey of multi-objective optimization methods for engineering[END_REF]. One of the main reasons behind this difference is the fact that DMS declares an iteration as successful if at least one of the components of the objective function could be improved sufficiently, whereas in [START_REF] Fliege | Complexity of gradient descent for multiobjective optimization[END_REF] the algorithm, which uses a backtracking approach for determining the right stepsize parameter, moves to a new point if all the components of the objective function could be improved sufficiently. It should also be noted that DMS will compute an approximation to a complete local Pareto front, whereas the multiobjective gradient descent algorithm finds a single Pareto critical point. This explains the dependence on |L( )| for the WCC bounds derived.

If a more demanding criterion is considered to accept new nondominated points, a complexity bound identical, in terms of , to the one derived in [START_REF] Fliege | Complexity of gradient descent for multiobjective optimization[END_REF] for the gradient descent can be established for DMS. In the next section, we will propose a directsearch framework, which corresponds to a particular instance of DMS, and presents a worst-case complexity bound of O n -2 , when considering the number of function evaluations.

A Min-Max Direct-Search Framework for Multiobjective Optimization

In this section, instead of considering problem (1) directly, we use a min-max formulation:

min x∈R n f (x) with f (x) := max i∈I f i (x).
Algorithm 2 considers a direct-search (DS) approach with a stricter criterion for accepting new nondominated points. In this case, rather than an approximation to the complete Pareto front, only one Pareto critical point will be computed for problem [START_REF] Marler | Survey of multi-objective optimization methods for engineering[END_REF]. For simplicity, the forcing function ρ(t) = c 2 t 2 , with c > 0, has been considered and the (optional) search step has not been included in the algorithmic description. However, the subsequent results could be established for a more general setting, such as the one of Algorithm 1, once that the strict condition for accepting new nondominated points is used.

Algorithm 2: Min-max DS for multiobjective optimization.

Initialization

Choose x 0 ∈ R n with f i (x 0 ) < +∞, ∀i ∈ I , α 0 > 0 an initial stepsize, 0 < β 1 ≤ β 2 < 1 the coefficients for stepsize contraction and γ ≥ 1 the coefficient for stepsize expansion. Let D be a set of positive spanning sets and c > 0 a constant used in the sufficient decrease condition. For k = 0, 1, 2, . . .

k + α k d : d ∈ D k }. If it exists d k ∈ D k such that f (x k + α k d k ) < f (x k ) - c 2 α 2 k ,
then declare the iteration as successful and set

x k+1 = x k + α k d k .
Otherwise, declare the iteration as unsuccessful and set x k+1 = x k .

2.

Stepsize parameter update: If the iteration was successful, then maintain or increase the corresponding stepsize parameter, by considering

α k+1 ∈ [α k , γ α k ].
Otherwise decrease the stepsize parameter, by choosing

α k+1 ∈ [β 1 α k , β 2 α k ].
Algorithm 2 can be regarded as a particular instance of Algorithm 1, where no search step is performed, the list L k is a singleton, corresponding to the current iterate

(f k 1 , f k 2 )
and stepsize parameter (x k ; α k ), with a particular choice of L trial as a subset of the set of computed nondominated points. Figure 2 illustrates the latter claim for a biobjective optimization problem. Consider

F(x k ) = ( f k 1 , f k 2 )
as the objective function value at the current iterate and ρ(α k ) as the current value of the forcing function. The shaded region corresponds to the image of the subset of nondominated points, from which a new iterate can be selected. This set is a subset of the corresponding set in Algorithm 1 (represented by the hatch-lined area). Such restriction leads to a better worst-case complexity bound, compared to the general formulation of DMS.

A result similar to Lemma 3.2 can be established for Algorithm 2.

Lemma 4.1 Under Assumption 3.1, suppose that the k-th iteration of Algorithm 2 is unsuccessful. Let D k be the positive spanning set considered, and α k > 0 be the corresponding stepsize. Then,

μ D k (x k ) ≤ 1 2 (L max + c) α k . Proof If iteration k is unsuccessful, then for all directions d k ∈ D k f (x k + α k d k ) ≥ f (x k ) - c 2 α 2 k .
Hence, there exists i(d k ) ∈ I such that

f i(d k ) (x k + α k d k ) ≥ f i(d k ) (x k ) - c 2 α 2 k .
The remainder of the proof is similar to the one of Lemma 3.2.

The following lemma states that the sequence ∞ k=0 α 2 k is finite, where {α k } k≥0 is generated by Algorithm 2. The proof is identical to the one of [START_REF] Gratton | Direct search based on probabilistic descent[END_REF]Lemma 4

∞ k=0 α 2 k ≤ Ω := γ 2 1 -β 2 2 γ -2 α 2 0 + 2 c ( f (x 0 ) -F min ) ,
where γ, β 2 , c are defined in Algorithm 2.

Proof We begin by proving that the series k∈S α 2 k is finite. To this end, recall that for every successful iteration, we have

f (x k ) -f (x k+1 ) ≥ c 2 α 2 k .
Moreover, denoting by S the set corresponding to the indexes of successful iterations, since the iterate does not change between two successful iterations, we also have for any K ≥ 0:

k∈S k≤K f (x k ) -f (x k+1 ) = k≤K f (x k ) -f (x k+1 ) = f (x 0 ) -f (x K +1 ) ≤ f (x 0 ) -F min ,
where the last inequality results from Assumption 3.2. As result, we obtain

f (x 0 ) -F min ≥ k∈S f (x k ) -f (x k+1 ) ≥ k∈S c 2 α 2 k . Thus, k∈S α 2 k ≤ 2 c ( f (x 0 ) -F min ) < ∞.
To analyze the full series, we consider the set S := {k 0 , k 1 , k 2 , . . . , }, where k i ≥ 0 is the index of the i-th successful iteration and k 0 = -1 is an artificial index corresponding to α -1 = γ -1 α 0 . With this notation, given the updating rules on α k , we have that

∞ k=0 α 2 k = ∞ i=0 k i+1 k=k i +1 α 2 k ≤ ∞ i=0 k i+1 k=k i +1 γ 2 β 2(k-k i -1) 2 α 2 k i ≤ γ 2 1 -β 2 2 ∞ i=0 α 2 k i .
We conclude by observing that

∞ i=0 α 2 k i = γ -2 α 2 0 + k∈S α 2 k ≤ γ -2 α 2 0 + 2 c ( f (x 0 ) -F min ).
Finally, in the main result of this section, we will prove that Algorithm 2 takes at most O( -2 ) iterations for driving μ below > 0. Similarly to Algorithm 1, Algorithm 2 cannot be proven globally convergent to a Pareto critical point for an arbitrary choice of positive spanning sets as sets of poll directions, as one can easily present examples where the cone of descent directions, considering all components of the objective function, can be arbitrarily narrow (see Remark 3.1). where Ω is defined as in Lemma 4.2.

Proof If k = 0, the result trivially holds. Therefore, we assume in what follows that k > 0.

For any unsuccessful iteration of index k ≤ k , we have from Lemma 4.1 that

α 2 k ≥ 4μ 2 D k (L max + c) 2 . ( 9
)
Since μ k > , in view of ( 7), we have μ D k > /(C 1 + 1). Therefore, using (9), we have

α 2 k ≥ 4 2 (L max + c) 2 (C 1 + 1) 2 . ( 10
)
Considering the updating rules on the stepsize, for any successful iteration of index k ≥ k > j 1 , where j 1 is the index of the first unsuccessful iteration, there exists an index of an unsuccessful iteration j(k) ≤ k (with possibly j(k) = j 1 ) such that α k ≥ β 1 α j(k) . Putting this together with (10) yields:

∀k ∈ S, k ≥ k > j 1 , α 2 k ≥ 4β 2 1 2 (L max + c) 2 (C 1 + 1) 2 ,
where S denotes the set of successful iterations. Using now the result of Lemma 4.2, we have:

Ω ≥ ∞ k=0 α 2 k ≥ k ε k= j 1 +1 α 2 k ≥ (k ε -j 1 ) 4β 2 1 2 (L max + c) 2 (C 1 + 1) 2 .
Thus,

k ε -j 1 ≤ Ω(L max + c) 2 (C 1 + 1) 2 4β 2 1 -2 .
Since j 1 is the index of the first unsuccessful iteration, one can trivially show that j 1 ≤ 2 cα 2 0 f (x 0 ) -F min . Then, the thesis follows.

The previous theorem allows us to establish a WCC bound in terms of the number of function evaluations for Algorithm 2 (see also Remark 3.2).

Conclusions

In this work, we analyzed the worst-case complexity of some direct-search derivativefree algorithms for unconstrained multiobjective nonconvex smooth optimization problems. In the case of Direct Multisearch [START_REF] Custódio | Direct multisearch for multiobjective optimization[END_REF], we derived a complexity bound of O(|L( )| -2m ) for driving a criticality measure below > 0. We then proposed a min-max approach to the multiobjective derivative-free optimization problem, which proved to be a particular instance of Direct Multisearch, but presented a worst-case complexity bound of O( -2 ) for driving the same criticality measure below > 0. This result is identical, in terms of , to the one established in [START_REF] Fliege | Complexity of gradient descent for multiobjective optimization[END_REF] for gradient descent, considering the same class of problems. For the (strongly) convex case, where all the components of the objective function are (strongly) convex, it remains as an open question whether similar complexity bounds to those derived in [START_REF] Fliege | Complexity of gradient descent for multiobjective optimization[END_REF] could be established for the algorithms considered in this paper.

2 . 3 .

 23 Search step: Compute a finite set of points {z s } s∈S and evaluate F at each point in S. Compute L trial by removing all dominated points, using sufficient decrease, from L k ∪ {(z s ; α k ) : s ∈ S} and selecting a subset of the remaining nondominated points. If L trial = L k declare the iteration (and the search step) as successful, set L k+1 = L trial , and skip the poll step. Poll step: Choose a positive spanning set D k from the set D. Evaluate F at the poll points belonging to {x k + α k d : d ∈ D k }. Compute L trial by removing all dominated points, using sufficient decrease, from L k ∪ {(x k + α k d; α k ) : d ∈ D k } and selecting a subset of the remaining nondominated points. If L trial = L k declare the iteration (and the poll step) as successful and set L k+1 = L trial . Otherwise, declare the iteration (and the poll step) as unsuccessful and set L k+1 = L k .

Assumption 3 . 1

 31 For all i ∈ I , the function f i is continuously differentiable with Lipschitz continuous gradient with constant L i . Set L max = max i∈I L i . Assumption 3.2 For all i ∈ I , the function f i is lower and upper bounded in {x ∈ R n : F(x) / ∈ D({x 0 })}, with lower bound f min i and upper bound f max i . Let F min := min{ f min 1 , . . . , f min m } and

Fig. 1 Definition 3 . 2 A

 132 Fig. 1 Hypervolume increase at a successful iteration of Algorithm 1

Corollary 3 . 1

 31 Let all the assumptions of Theorem 3.1 hold. To achieve μ k < , Algorithm 1 takes at most O |L( )| -pm min( p-1,1) iterations (and O n|L( )| -pm min( p-1,1) function evaluations). When p = 2 this bound is O |L( )| -2m (and O n|L( )| -2m function evaluations).

1 .

 1 Poll step: Choose a positive spanning set D k from the set D. Evaluate F at the poll points belonging to {x

Fig. 2

 2 Fig. 2 Selecting a new nondominated point in the min-max direct-search framework

Theorem 4 . 1 ≤ 2 cα 2 0f 1

 4121 Let Assumptions 3.1, 3.2, and 3.5 hold. For ∈ ]0, 1[, let k be the first iteration index such that μ k +1 ≤ . Then,k (x 0 ) -F min + Ω(L max + c) 2 (C 1 +

Corollary 4 . 1

 41 Let all the assumptions of Theorem 4.1 hold. To achieve μ k < , Algorithm 2 takes at most O n -2 function evaluations.

  .1], but we include it for completeness. [13, Lemma 4.1] Under Assumption 3.2, the sequence of {α k } k≥0 generated by Algorithm 2 satisfies

	Lemma 4.2

Acknowledgements

The authors would like to thank the three anonymous referees, whose comments and suggestions much improved the quality of the paper. Funding support for Ana Luísa Custódio and Rohollah Garmanjani was provided by national funds through FCT-Fundação para a Ciência e a Tecnologia I. P., under the scope of Projects PTDC/MAT-APL/28400/2017 and UIDB/00297/2020. Support for Elisa Riccietti was provided by TOTAL E&P.

Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.