Since the seminal paper by Vavasis [21] on the complexity of finding first-order critical points in unconstrained nonlinear optimization was published 25 years ago, the question of the optimal worst-case complexity of optimization methods has been of interest to mathematicians and also, because of its strong connection with deep learning, to computer scientists. Of late, there has been a growing interest in this research field, both for convex and nonconvex problems. This paper focusses on the latter class and follows a now subtantialtrend of research where bounds on the worst-case evaluation complexity (or oracle complexity) of obtaining first- and (more rarely) second-order-necessary minimizersfor nonlinear nonconvex unconstrained optimization problems [21, 17, 14, 19, 5]. These papers all provide upper evaluation complexity bounds: they show that, to obtain an -approximate first-order-necessary minimizer (for unconstrained problem, this is a point at which the gradient of the objective function is less than ) evaluations of the objective functionif a model involving first derivatives is used, and ) evaluations are needed if using second derivatives is permitted. This result was extended to convexly-constrained problems in [6]. A broader framework allowing the use of Taylor series of degree p was more recently proposed in [2], in which case the worst-case evaluation complexity bound for order-necessary unconstrained minimizer is shown to be ), thereby generalizing the previous results for this case. Complexity for obtaining -approximate second-order-necessary unconstrained minimizers was considered in [19, 5], where a bound of ) evaluations was proved to obtain an -second-order-necessary minimizer using a Taylor’s model of degree two, and a bound of ) evaluations was shown in [8] for the case where a Taylor model of degree p is used. Defining q-th-order-necessary minimizers for q > 2 was considered in [11], where the difficulty of stating and verifying necessary optimality was discussed. In particular, it was concluded in this latter reference that defining and computing -approximate q-th-order-necessary minimizers for q > 2 is likely to remain elusive, essentially because of the nonlinearity and lack of continuity of the kernels of the derivatives involved. A more general Taylor-based definition of optimality was introduced instead, which allowed to show an upper bound of ) on evaluation complexity for convexly-constrained problems, in particular improving on the bound of ) stated in [1] for the case p = q = 3.

The unconstrained and convexly-constrained cases where the assumption of Lipschitz continuity is replaced by the weaker -H¨older continuity (1]) have also been studied for

q = 1 in [18, 7, 9]. These references show that ) evaluations are needed for obtaining an -first-order-necessary minimizer.

While upper complexity bounds are important as they provide a handle on the intrinsic difficulty of the considered problem, they do so at the condition of not being overly pessimistic. To address this last point, lower bounds on the evaluation complexity of unconstrained nonconvex optimization problems and methods were derived in [4, 17] and [12], where it was shown that the known upper complexity bounds are sharp (irrespective of problem’s dimension) for most known methods using Taylor’s models of degree one or two. That is to say that there are examples for which the complexity order predicted by the upper bound is actually achieved. More recently, Carmon et al. [3] provided an elaborate construction showing that at least

a multiple of function evaluations may be needed to obtain an -first-order-necessary unconstrained minimizer where derivatives of order at most p are used. This result, which matches in order the upper bound of [2], covers a very wide class of potential optimization methodsbut has the drawback of being only valid for problems whose dimension essentially exceeds the number of iterations needed, which can be very large and quickly grows when tends to zero.

Contributions. The present paper aims at unifying and generalizing all the above results in a single framework, providing, for problems with inexpensive or no constraints, provably optimal evaluation complexity bounds for arbitrary optimality order, all relevant model degrees and levels of smoothness of the objective function. By “inexpensive constraints”, we mean general set constraints whose enforcement and evaluationcost is negligible compared to the cost of evaluating the objective function. As a consequence, the evaluation complexity for such problems is meaningfully captured by focusing of the number of evaluations of this latter function. This class of minimization problems contains important cases such as bound-constrained problems and convexly-constrained problems (when the projection onto the feasible set is inexpensive), but also allows possibly nonconvex or even disconnected feasible sets.

In order to achieve these objectives, we first revisit the Taylor-based optimality measure of [11] and define (-th-order-necessary minimizers, a notion extending the standard and -second-order cases to arbitrary orders. We then present a conceptual regularization algorithm using degree p models and show that this algorithm requires at most evaluations of f and its derivatives to find such an (-th-order-necessary minimizer when the p-th derivative of f is assumed to be -H¨older continuous. (If the p-th derivative is assumed to be Lispchitz continuous, the bound becomes ).) This bound matches the best known lower bounds for first- and second-order, and improves on the bound in given by [11]. We then show that this bound is sharp in order for unconstrained problems with Lipschitz continuous p-th derivative by completing and extending the result of [3] in two ways. The first is to show that the lower worst-case bound of order evaluations for obtaining a first-order-necessary minimizer using at most p derivatives is also valid for problems of every dimension, and the second is to show that this bound can be generalized to a multiple of for obtaining a q-th-order-necessary minimizer of any order q. In particular, this result matches in order the upper bound obtained in the first part of the paper and subsumes or improves known lower bounds for first- and second-order-necessary minimizers. While our lower bounds are derived for regularization algorithms applied to unconstrained problems, we also indicate that they may be extended to a much wider class of minimization methods and to a significant class of constrained problems.

The paper is organized as follows. Section 2 introduces the (possibly constrained) minimization problem of interest and the concept of ()-approximate q-th-order-necessary minimizers. It also presents a variant of the Adaptive Regularization algorithm using degree p Taylor’s models (ARp) whose purpose is to find such minimizers. Section 3 then provides an upper bound on the evaluation complexity for the ARp algorithm to achieve this task. Section 4 then discusses specialization of this result to the case where -approximate second-order-necessary minimizers are sought. The complexity upper bound of Section 3 is then proved to be sharp in Section 5 for the Lipschitz-continuous cases where the feasible set contains a ray. Some conclusions are finally presented in Section 6.

Notation. Throughout the paper, denotes the standard Euclidean norm of a vector . For a symmetric tensor ] is the result of applying S to the vectors is the result of applying S to p copies of the vector v and

(where the second equality results from Theorem 2.1 in [23]) is the associated induced norm for such tensors. If are tensors, is their tensor product and product of times with itself. For a real, sufficiently differentiable univariate function denotes its i-th derivative and is a synonym for f. For an integer k and a real 1], we define () (this coincides with the standard factorial if = 1). As is usual, we also define 0! = 1. If M is a symmetric matrix, left-most eigenvalue. If is a real, denote the smallest integer not smaller than and the largest integer not exceeding , respectively. Finally globmin) denotes the smallest value of

Given 1, this paper considers the set-constrained optimization problem

where we assume that is closed and nonempty, and where that:

• f is p-times continuously differentiable,

• f is bounded below by

• the p-th derivative tensor of f at x is globally H¨older continuous, that is, there exist constants 1] such that, for all

Observe that convexity or even connectedness of F is not requested. Observe also that the more usual case of = 1. We note that our assumption covers the continuous range of objective function’s smoothness from H¨older continuous gradients to Lipschitz continuous p-th derivatives. In what follows, we assume that

If ) is the standard p-th degree Taylor’s expansion of f about x computed for the increment s, that is

(2.2) provides crucial approximation bounds, whose proof can be found in the appendix.

and

which can be interpreted as the

shown in [11] that ) is a proper generalization of well-known unconstrained optimality measures for low orders, in that, for

At variance with other optimality measures, ) is well-defined for any order varies continuously when x varies continuoulsy in F. The role of the “optimality radius” in (2.6) merits some discussion. While the choice of = 1 is adequate for retrieving known optimality conditions in the unconstrained case for j = 1, j = 2 provided j = 3 provided additionnaly ) is positive semi-definite (as we have just seen), important in other cases. Corollary 3.6 in [11] indicates that, when F is convex, q-th-order necessary “path-based” optimality conditions hold if

The limit for 0 is necessary to capture the notion of local minimizer for (2.1). However, considering ) for non-vanishing has substantial advantages from the point of view of optimization: while it may fail to indicate that x is a local minimizer, it does so only by providing a direction leading to values of f below f(x), thereby helping to avoid local but non-global approximate solutions. We refer the reader to [11] for a further discussion, but conclude that considering fixed has strong advantages when solving (2.1).

A special case is when x is an isolated feasible point, that is a point which is the sole intersection between F and any sufficiently small neighbourhood of x. Such a point is clearly a local minimizer, and this is reflected by the fact that ) = 0 for any f, any q and any sufficiently small

The main drawback of using ) is, of course, that its computation requires the global minimization of ) in the intersection of the ball of radius . We are not aware of an easy way to do this in general1, which is why our analysis remains of an essentially theoretical nature, as was the case for [11]. Note however that, albeit potentially very difficult, solving this global minimization problem does not involve calculating the value of f or of any of its derivatives. In that sense, this drawback is thus irrelevant for the worst-case evaluation complexity which solely focuses on these evaluations.

Observe now that, if we were to relax the first-order condition ) = 0 for uncon- strained problems to and, at the same time, relax the second-order condition to, we then deduce that

A natural generalization of this observation is to define an (necessary minimizer of f as a point x such that

where

Because (2.12) is a new way to look at approximate optimality and is crucial for the rest of this paper, it is worthwhile to motivate and discuss it further.

1. When = 0, (2.12) implies that the complicated path-based necessary optimality conditions derived in [11] do hold. This results from the fact that these latter conditions merely express that the Taylor’s model of order q cannot decrease close enough to x along any feasible polynomial path emanating from x, which is clearly the case if x is a global minimizer of the same models in the intersection of the feasible set and a ball of radius centered at x. By continuity, these path-based conditions must therefore hold in the limit under (2.12) when tends to zero. The role of (2.12) as a condition for approximate minimization is thus coherent and consistent with known necessary conditions.

2. Inspired by (2.10), the stronger approximate optimality condition

was used in [11] instead of (2.12). Our main reason to prefer (2.12) is the following. Observe that (2.14) implies in particular that , which in turn im- plies, for small enough for the first-order term to dominate, that the unconstrained case (for example), this requires , imposing an inordinate level of first-order optimality, much stronger than the standard condition . No such difficulty arises with (2.12) because the right-hand side of the condition involves all powers of , which is not the case of the right-hand side of (2.14). Note however that the vital continuity properties of are not affected by the choice of the right-hand side, and are thus inherited by (2.12).

3. For given 1], (2.12) does not imply that although the violation of this condition tends to zero with . This slight blemish can be cured by requiring that instead of (2.12), but we claim that the benefit of this stronger definition is outweighted by the need to perform 1 additional constrained global minimizations, and therefore focus our exposition to the case using the simpler (2.12).

In order to further justify (2.12), we now make more explicit the “minimizing guarantees” provided by this approximate optimality condition, by formulating a result analogous to Theorem 3.7 in [11]. This result gives a lower bound on the value of f(x) in the feasible neighbourhood of an ()-approximate q-th-order-necessary minimizer.

In order to find ()-approximate q-th-order-necessary minimizers, we consider applying a variant of the ARp algorithm to (2.1). This algorithm, described as Algorithm 2.1 on the following page, is of the regularization type in that, at each iterate is computed which approximately minimizes (in a sense defined below) the model

subject to in an integer such that is a “regularization parameter”.

A few comments are useful at this stage.

1. Since by (2.22), we have that ) is bounded below as a function of s and the existence of a constrained global minimizer is guaranteed.

2. Step 2 requires, that, for = 0, we also compute This is easy for orders one and two. If q = 1, the formula for a global minimizer is analytic and

always acceptable. The situation is similar for q = 2, where can be assessed using a trust-region method whose radius is = 1 (more details are provided at the end of Section 3). The task is more difficult for higher orders where one may have to rely on the arguments of Lemma 2.5 below, or use different subproblems with decreasing values of . However, none of these computations involve the evaluation of f or its derivatives, and therefore the evaluation complexity bound discussed in this paper is unaffected.

3. That one needs to consider the second case in Step 2 (where no step exists satisfying (2.18) – (2.20)) can be seen by examining the following one-dimensional example. Let = 1, and suppose that = 4! = 24. Then and the origin is a global minimizer of the model (and a local minimizer of 1, yielding that . Thus, Step 1 with = 1 has failed to identify that termination was possible. In addition, we see that, at variance with the cases q = 1 and q = 2, a global minimizer of the model (2.16) may not, for global minimizer of its q-th order Taylor’s expansion in the intersection of F and a ball of arbitrary radius: we may have to restrict this radius (to in our example) for this important property to hold (see Lemma 2.5 below).

4. If (2.19) holds, the possibly expensive computation of ) in (2.20) is unnecessary and may be chosen arbitrarily in (0, 1].

5. We assume the availability of a feasible starting point, which is without loss of generality for inexpensive constraints.

6. Before termination, each successful iteration requires the evaluation of f and its first p derivative tensors, while only the evaluation of f is needed at unsuccessful ones.

7. The mechanism of the algorithm ensures the non-increasing nature of the sequence

Iterations for which (and hence ) are called “successful” and we denote by the index set of all successful iterations between 0 and k. We immediately observe that the total number of iterations (successful or not) can be bounded as a function of the number of successful ones (and include a proof in the appendix).

We also verify that the algorithm is well-defined in the sense that either a step satisfying (2.18)–(2.20) can always be found, or termination is justified. For unconstrained problems with , the first possibility directly results from the observation that given by (2.7)-(2.9) for ) can be made suitably small at a global minimizer of the model. The situation is more complicated for other cases. In order to clarify it, we first state a useful technical lemma, whose proof is in the appendix.

We now provide reasonable sufficient conditions for a nonzero step and an optimality radius to satisfy (2.18)–(2.20).

be the global minimizer of the model Since (0), we have that = 0. By Taylor’s theorem, we have that, for all d,

(2.27) Since = 0, we may then choose such that, for every

where the last inequality follows from (2.13). Continuity of and its derivatives and the inequality (0) then imply that there exists a neighbourhood of that (2.18) holds and

for all s in this neighbourhood and all . This yields that, for all such s with

As can be seen in the proof of this lemma, may need to be small if any of the tensors

for has a large norm. This may occur in particular if close to zero, as is shown by the last term in the left-hand side of (2.28). We also note that (2.20) obviously holds for is an isolated feasible point. It now remains to verify that it is justified to terminate in Step 2 when no suitable nonzero step can be found.

Lemma 2.6 Suppose that the algorithm terminates in Step 2 of iteration Then there exists a 1] such that (2.12) holds for approximate qth-order-necessary minimizer.

Proof. Given Lemma 2.5, if the algorithm terminates within Step 2, it must be because every global minimizer ) under the constraints is such that (0). In that case, = 0 is one such global minimizer and we have that, for all d,

We may now choose 1] small enough to ensure that, for all

Observe that, in this proof, we could have chosen small enough to ensure

instead of (2.29), yielding ), which is a stronger necessary optimality condition than (2.12). Together, Lemmas 2.5 and 2.6 ensure that Algorithm 2.1 is well-defined.

The proofs of the following two lemmas are very similar to corresponding results in [2] and hence we again defer them to the appendix (but still include them for completeness, as the algorithm has changed).

We are now in position to prove the crucial lower bound on the step length.

Let the global minimum in the definition of ) be achieved at Since 0, we have from (2.6) that

Then, successively using (2.6) for , the triangle inequality, (2.16), (1.1) and (2.25), we deduce that

(3.6) Now, since , and using (2.6) for

The bound given by this lemma is another indication that choosing of the order of L (when this is known a priori) makes sense.

We now combine all the above results to deduce an upper bound on the maximum number of successful iterations, from which a final complexity bound immediately follows.

where we used (2.21), (3.1) and (2.22). Moreover we deduce from (3.9), (3.3) and (3.2) that

until termination. The desired bound on the number of successful iterations follows from combining (3.11). Lemma 2.3 is then invoked to compute the upper bound on the total number of iterations.

In particular, if the p-th derivative of f is assumed to be globally Lipschitz rather than merely H¨older continuous (i.e. if = 1), the bound (3.8) on the maximum number of evaluations becomes

where

This worst-case evaluation bound generalizes known bounds for q = 1 (see [2]) or q = 2 (see[8]) and significantly improve upon the bounds in ) given by [11] for a more stringent termination rule. It also extends the results obtained in [6] for convexly-constrained problems with q = 1 by allowing the significantly broader class of inexpensive constraints.

We also note that it is possible to weaken the assumption that must satisfy the H¨older inequality (2.2) for every (as required in the beginning of Section 2). The weakest possible smoothness assumption is to require that (2.2) holds only for points belonging to the same segment of the “path of iterates” ] (this is necessary for the proof of Lemma 2.1). As this path joining feasible iterates may be hard to predict a priori, one may instead use the monotonic character of Algorithm 2.1 and require (2.2) to hold for all x, y in the intersection of F with the level set . Again, it may be hard to determine this set and to ensure that it contains the path of iterates, and one may then resort to requiring (2.2) to hold in the whole of F, which must then be convex to ensure the desired H¨older property on every segment [

We now discuss the particular and much-studied case where second-order minimizers are sought for unconstrained problems with Lipschitz continuous Hessians (that is = 1). As we now show, a specialization of Algorithm 2.1 to this case is very close (but not identical) to well-known methods. Let us consider Step 1 first. The computation of ) then reduce to

which amounts to solving a standard trust-region subproblem with radius (see [13]). Hence verifying (4.1) or testing the more usual approximate second-order criterion

have very similar numerical costs (remember that finding the leftmost eigenvalue of the Hessian is the same as finding the global minimizer of the associated Rayleigh quotient). If we now turn to the computation of in Step 2, Algorithm 2.1 then computes such a step by attempting to minimize the model

as has already been proposed before for general p [2, 8]. Moreover, the failure of (2.12) in Step 1 is enough, when 2, to guarantee the existence of nonzero global minimizers of ), and thus to ensure that a nonzero is possible. The approximate model minimization is stopped as soon as (2.19) or (2.20) holds, the latter then reducing to checking that

for some 1]. For each potential 1] requires solving (possibly approximately)

While this could be acceptable without affecting the overall evaluation complexity of the algorithm, a simpler alternative is available for q = 2. We may consider terminating the model minimization when either (2.19) holds, or

The inequality is guaranteed to hold when is close enough to , a global minimizer of the model ), since then ) is positive semi definite, and then d = 0 provides the global minimizer of the second-order Taylor model of Verifying (4.5) only requires at most one trust-region calculation for each potential step and ensures (4.4) with = 1, making the choice = 1 acceptable. The cost this technique is comparable to that that proposed in [8] where an eigenvalue computation is required for each potential step. Combining these observations, Algorithm 2.1 then becomes Algorithm 4.1.

If p = q = 2, computing in Step 2 amounts to approximately minimizing the now well-known cubic model of [15, 19, 22, 5]. In addition, if is the exact global minimizer of this model, the above argument shows that (4.5) automatically holds at and checking this inequality by solving a trust-region subproblem is thus unnecessary. The only difference between our proposed algorithm and the more usual cubic regularization (ARC) method with exact global minimization is that the latter would check (4.2) for termination, while the algorithm presented here would instead check (4.1) with = 1 by solving a trust-region subproblem. As observed above, both techniques have comparable numerical cost.

The bound (3.12) then ensures that Algorithm 4.1 terminates in at most

uations of f, its gradient and Hessian. This algorithm thus sharesthe upper complexity bounds stated in [8] for general p with different values of fpr fisrt- and second-order, and in [19, 5] for p = 2.

We now intend to show that the upper bound on evaluation complexity of Theorem 3.4 is tight in terms of the order given for unconstrained and a broad class of constrained problems with Lipschitz continuous p-th derivative (i.e. ). This objective is attained by defining a variant of the high-degree Hermite interpolation technique developed in [11], and then using this technique to build, for any number p of available derivatives of the objective function and any optimality order q, an unconstrained univariate example of suitably slow convergence (i.e. for which the order in given by (3.12) is achieved). This example is then embedded in higher dimensions to provide general lower bounds.

5.1 High-degree univariate Hermite interpolation

We start by investigating some useful properties of Hermite interpolation. Let us assume that we wish to construct a univariate Hermite interpolant of degree 2(p + 1) of the form

on the interval [0, s] satisfying the 2(p + 1) conditions

where are given. The values of the coefficients may then be obtained by

(5.3) where

with is the matrix whose (i, j)-th entry is , which only depends on p. It was show in [11, Appendix] that is nonsingular. Therefore

We therefore deduce that, for any

The mean-value theorem then implies that, for any 0 [0, s],

This development thus leads us to the following conclusion.

Observe that (5.5) is identical to (2.5) when = 1. This means that the conditions of Theorem 5.1 automatically hold if the interpolation data is itself extracted from a function having a Lipschitz continuous p-th derivative.

Applying the above results to several interpolation intervals then yields the existence of a smooth Hermite interpolant.

Proof. We first use Theorem 5.1 to define a Hermite interpolant ) of the form (5.1) on each interval [, and then set

and where are chosen sufficiently large to ensure that (5.6) also holds on intervals -1 and . We next set

5.2 Slow convergence to (ǫ,δ)-approximate q-th-order-necessary minimizers

We now consider an unconstrained univariate instance of problem (2.1). Our aim is first to show that, for each choice of , there exists an objective function f for problem (2.1) with = 1) such that obtaining an ()-approximate q-th-order-necessary minimizer may require at least

evaluations of the objective function and its derivatives using Algorithm 2.1, matching, in order of 1], the upper bound (3.12). Our development follows the broad outline of [12] but extends it to approximate minimizers of arbitrary order. Given a model degree an optimality order , we first define the sequences

by

as well as

and

Thus

and, assuming = 1 for all k (we verify below that this is acceptable),

We also set (we again verify below that is acceptable). Note that

(and (2.12) fails at

(and (2.12) holds at ). It is easy to verify using (5.11) that the model (2.16) is then globally minimized for

Hence this step satisfies (2.19) if we choose = 1. Because of this fact, we are free to choose arbitrarily in (0, 1] and we choose = 1. Thus, provided we make the choice ensuring (5.12) for k = 0 , the value = 1 is admissible for all k. The step (5.15) yields that

where

Thus (0) and (2.18) holds. We then define

which provides the identity

(ensuring that iteration k is successful because = 1 in (2.21) and thus that our choice of a constant is acceptable). In addition, using (5.18), (5.13), (5.17), the equality the inequality from (5.7) gives that, for

We also set

Then (5.19) and (2.16) give that

Now note that, using (5.11) and the first equality in (5.15),

where is the standard indicator function. We may now verify that, for

while, for j = q, we have that

Combining (5.21), (5.22), (5.23) and (5.24), we deduce that (5.6) holds with We may thus apply Theorem 5.2 with = 1, and deduce the existence of a p times continuously differentiable function f from IR to IR with Lipschitz continuous derivatives of order 0 to p which interpolates the and . Moreover, (5.20) and Theorem 5.2 imply that the range of f only depends on p and q. In addition, (5.19) ensures that every iteration is successful and thus, because of (2.22), that the value ! may be used at all iterations.

This argument allows us to state the following lower bound on the complexity of the regularization algorithm using a p-th degree model.

This implies the following important consequence for higher dimensional problems.

Proof. The first conclusion directly follows from Lemma 5.3 since it is always possible to include the unimodal example as an independent component of a multivariate one.

The second conclusion follows from the observation that our univariate example of slow convergence is only defined on IR(even if Theorem 5.2 provides an extension to the complete real line). As a consequence, it may be used on any feasible ray.

We now make a few observations.

1. Theorem 5.4 generalizes to arbitrary q the bound obtained in [3] for the case q = 1 and also shows that, at variance with the result derived in this reference, the generalized bound applies for arbitrary problem’s dimension, but depends on

2. For simplicity, we have chosen, in the above example, to minimize the model globally at every iteration, but we might consider other pairs (). A similar example of slow convergence may in fact be constructed along the lines used abovesequence of acceptablemodel reducing steps and associated optimality radii (in the sense of Lemma 2.5), provided the optimality radii remain bounded away from zero. This means that our example of slow convergence applies not only to Algorithm 2.1 but also to a much broader class of minimization methods. Moreover, it is also possible to weaken the constraints on the step further by relaxing (5.19) and only insisting on acceptable decrease of the objective function value in Step 3 of the algorithm.

In [3], the authors derive their upper bound for q = 1 for the general class of “zero-preserving” algorithms, which are algorithms that “never explore (from ) coordinates which appear not to affect the function”, that is directions d along which is constant. This property is obviously shared by Algorithm 2.1 because it attempts to reduce the Taylors’ expansion of f around the current iterate (the presence of the isotropic regularization term is irrelevant for this).

3. Our example does not apply, for instance, to a linesearch method using global univariate minimization in a direction of search computed from the Taylor’s expansion of f, which

is another zero-preserving method. Note however that this method, just as every other linesearch method (including possibly randomized coordinate searches), is bound to fail when attempting to compute approximate minimizers of order beyond three, because the Taylor’s expansion at a non-optimal point then needs no longer decrease along lines. This is demonstrated by the following old example [16, 20]. Let

Then f(0, 0) = 0 and the origin is not a minimizer since f decreases along the arc . Yet the origin is the global minimizer along every line passing through the origin, preventing any linesearch method to progress away from (0, 0).

Let us now consider an alternative unconstrained minimization method which would attempt to reduce the unregularized model (that is (2.16) with = 0) in order to find an unconstrained first-order minimizer. It is easy to see that if one chooses

the same reasoning as above yields that the largest obtainable decrease with this model occurs at

and is given by

This then implies that at least a multiple of evaluations may be needed to find approximate first-order-necessary minimizers, which is worse than the bound in holding for the regularized algorithm. This is consistent with the known lower ) bound for first-order points that holds for the (unregularized) Newton method (and hence the trust-region method), both of which use p = 2. Adding the regularization term thus not only provides a mechanism to limit the stepsize and make the step well-defined when ) is unbounded below, but also amounts to increasing the ’useful degree’ of the model by one, improving the worst-case complexity bound. Summing up the above discussion, we conclude that an example of slow convergence requiring at least (5.25) evaluations can be built for any method whose steps decrease the regularized () or unregularized (= 0) model (2.16) and whose approximate local optimality can be measured by (2.20) for some constant = 1 (which we can always enforce by adapting and (5.9)). For orders up to two, this includes most variants of steepestdescent and Newton’s methods including those globalized with regularization, trust-region, a linesearch or a mixture of these (see [12] for a discussion). General linesearch methods are excluded for high-order optimization as they may fail to converge to approximate minimizers of order four and beyond. Finally, one may wonder at what would happen if, for the interpolation data (5.9)-(5.10), the model

were used for some m > p + 1, resulting in a shorter step. The global model minimizer would then occur at and give an optimal model decrease equal to [. However, (5.6) would then fail for j = 0 and the argument leading to an example of slow convergence would break down.

For any optimality order 1, we have provided the concept of an ()-approximate q-th-order-necessary minimizer for the very general set-constrained problem (2.1). We have then proposed a conceptual regularization algorithm to find such approximate minimizers and have shown that, if -H¨older continuous, this algorithm requires at most evaluations of the objective function and its p first derivatives to terminate. When Lipschitz continuous, we have used an unconstrained univariate version of the problem to show that this bound is sharp in terms of the order in for any feasible set containing a ray and any problem dimension.

In view of the results in [7, 18], one may wonder at what would happen if the regularization power (i.e. the power of used in the last term of the model (2.16)) is allowed to differ from . The theory presented above must then be re-examined and the crucial point is whether a global upper bound on the regularization parameter can still be ensured as in Lemma 3.2. One easily verifies that this is the case for regularization powers ]. Arguments parallel to those presented above then yield an upper bound of ) evaluationsrecovering the bound given in Section 3.3 of [7] for q = 1. The situation is however more complicated (and beyond the scope of the present paper) for and the determination of a suitable general complexity upper bound for this latter case has not been formalized at this stage, but the analysis for q = 1 discussed in Section 3.2 of [7] suggests that an improvement of the bound for larger r is unlikely.

Although the results presented essentially solve the question of determining the optimal evaluation complexity for unconstrained problems and problems with general inexpensive constraints, some interesting issues remain open at this stage. A first such issue is whether an example of slow convergence for all 1) can be found for feasible domains not containing a ray. A second is to extend the general complexity theory for problems whose constraints are not inexpensive: the discussion in [10] indicates that this is a challenging research area.

[1] A. Anandkumar and R. Ge. Efficient approaches for escaping high-order saddle points in nonconvex optimization. Proceedings of the Machine Learning Society, 49:81–102, 2016.

[2] E. G. Birgin, J. L. Gardenghi, J. M. Mart´ınez, S. A. Santos, and Ph. L. Toint. Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. Mathematical Programming, Series A, 163(1):359–368, 2017.

[3] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. Lower bounds for finding stationary points I. arXiv:1710.11606, 2018.

[4] C. Cartis, N. I. M. Gould, and Ph. L. Toint. On the complexity of steepest descent, Newton’s and regularized Newton’s methods for nonconvex unconstrained optimization. SIAM Journal on Optimization, 20(6):2833–2852, 2010.

[5] C. Cartis, N. I. M. Gould, and Ph. L. Toint. Adaptive cubic overestimation methods for unconstrained optimization. Part II: worst-case function-evaluation complexity. Mathematical Programming, Series A, 130(2):295–319, 2011.

[6] C. Cartis, N. I. M. Gould, and Ph. L. Toint. An adaptive cubic regularization algorithm for nonconvex optimization with convex constraints and its function-evaluation complexity. IMA Journal of Numerical Analysis, 32(4):1662–1695, 2012.

[7] C. Cartis, N. I. M. Gould, and Ph. L. Toint. Universal regularization methods – varying the power, the smoothness and the accuracy. Technical Report naXys-7-2016, Namur Center for Complex Systems (naXys), University of Namur, Namur, Belgium, 2016.

[8] C. Cartis, N. I. M. Gould, and Ph. L. Toint. Improved second-order evaluation complexity for uncon- strained nonlinear optimization using high-order regularized models. arXiv:1708.04044, 2017.

[9] C. Cartis, N. I. M. Gould, and Ph. L. Toint. Worst-case evaluation complexity of regularization methods for smooth unconstrained optimization using H¨older continuous gradients. Optimization Methods and Software, 6(6):1273–1298, 2017.

[10] C. Cartis, N. I. M. Gould, and Ph. L. Toint. Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization. Journal of Complexity, (to appear), 2018.

[11] C. Cartis, N. I. M. Gould, and Ph. L. Toint. Second-order optimality and beyond: characterization and evaluation complexity in convexly-constrained nonlinear optimization. Foundations of Computational Mathematics, 18(5):1073–1107, 2018.

[12] C. Cartis, N. I. M. Gould, and Ph. L. Toint. Worst-case evaluation complexity and optimality of second- order methods for nonconvex smooth optimization. To appear in the Proceedings of the 2018 International Conference of Mathematicians (ICM 2018), Rio de Janeiro, 2018.

[13] A. R. Conn, N. I. M. Gould, and Ph. L. Toint. Trust-Region Methods. MPS-SIAM Series on Optimization. SIAM, Philadelphia, USA, 2000.

[14] S. Gratton, A. Sartenaer, and Ph. L. Toint. Recursive trust-region methods for multiscale nonlinear optimization. SIAM Journal on Optimization, 19(1):414–444, 2008.

[15] A. Griewank. The modification of Newton’s method for unconstrained optimization by bounding cubic terms. Technical Report NA/12, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Cambridge, United Kingdom, 1981.

[16] H. Hancock. The Theory of Maxima and Minima. The Athenaeum Press, Ginn & Co, NewYork, USA, 1917. Available on line at https://archive.org/details/theoryofmaximami00hancroft.

[17] Yu. Nesterov. Introductory Lectures on Convex Optimization. Applied Optimization. Kluwer Academic Publishers, Dordrecht, The Netherlands, 2004.

[18] Yu. Nesterov and G. N. Grapiglia. Globally convergent second-order schemes for minimizing twice-differentiable functions. Technical Report CORE Discussion paper 2016/28, CORE, Catholic University of Louvain, Louvain-la-Neuve, Belgium, 2016.

[19] Yu. Nesterov and B. T. Polyak. Cubic regularization of Newton method and its global performance. Mathematical Programming, Series A, 108(1):177–205, 2006.

[20] G. Peano. Calcolo differenziale e principii di calcolo integrale. Fratelli Bocca, Roma, Italy, 1884.

[21] S. A. Vavasis. Black-box complexity of local minimization. SIAM Journal on Optimization, 3(1):60–80, 1993.

[22] M. Weiser, P. Deuflhard, and B. Erdmann. Affine conjugate adaptive Newton methods for nonlinear elastomechanics. Optimization Methods and Software, 22(3):413–431, 2007.

[23] X. Zhang, C. Ling, and L. Qi. The best rank-1 approximation of a symmetric tensor and related spherical optimization problems. SIAM Journal on Matrix Analysis, 33(3):806–821, 2012.

Proof of Lemma 2.1. We first establish the identity

To see this, integrating by parts, we have that

and thus, recursively, that

As in [11], consider the Taylor identity

involving a given univariate -th order Taylor approximation

expressed in terms of the value th derivatives . Then, picking ), for given , the identity (A.2), and the relationships ) give that

and thus from the definition of the tensor norm (1.1), the H¨older bound (2.2) and the identity (A.1) when k = p that

for all , which is the required (2.4).

,it follows from (A.2), the relationships

Then picking to maximize the absolute value of left-hand size of (A.3) and using the tensor norm (1.1), the H¨older bound (2.2) and the identity (A.1) when that

for all , which gives (2.5).

Proof of Lemma 2.3. The regularization parameter update (2.22) gives that, for each k,

where . Thus we deduce inductively that . We therefore obtain, using (2.23), that

which then implies that

since 1. The desired result (2.24) then follows from the equality the inequality 1 given by (2.17).

Proof of Lemma 2.4. We first observe that -th order tensor, whose norm is defined using (1.1). Moreover, using the relationships

defining

and proceeding by induction, we obtain that, for some

where the last equation uses the convention that = 0 for all j. Thus we may write

with

where we used the identity

to deduce the second equality. Now (A.6) gives that

It is then easy to see that the maximum in (1.1) is achieved for

with

Successively using this definition, (A.7), (A.8) (twice), the identity = 0 and (A.10) again, we then deduce that

Since from the first part of (A.4), we obtain that combined with (A.9) and (A.10), gives (2.25). We obtain (2.26) from (A.9) and (A.10), the observation that )! and (A.11) for

Proof of Lemma 3.1. (See [2, Lemma 2.1]) Observe that, because of (2.18) and (2.16),

which implies the desired bound. Note that = 0 as long as we can satisfy condition (2.18), and so (3.1) implies (2.21) is well defined.

Proof of Lemma 3.2. (See [2, Lemma 2.2]) Assume that

Using (2.4) and (3.1), we may then deduce that

and thus that . Then iteration k is very successful in that a consequence, the mechanism of the algorithm ensures that (3.2) holds.