Strong Evaluation Complexity Bounds for Arbitrary-Order
       Optimization of Nonconvex Nonsmooth Composite Functions

            C. Cartis, N. Gould and Ph. L. Toint
                          January 2020

Abstract.
We introduce the concept of strong high-order approximate minimizers for
nonconvex optimization problems. These apply in both standard smooth and
composite non-smooth settings, and additionally allow convex or inexpensive
constraints. An adaptive regularization algorithm is then proposed to find such
approximate minimizers. Under suitable Lipschitz continuity
assumptions, whenever the feasible set is convex,  it is shown that using a
model of degree p, this algorithm will find a strong
approximate q-th-order minimizer in at most

   O( max_{1 \leq j \leq q}\epsilon_j^{-(p+1)/(p-j+1)} )

evaluations of the problem’s functions and their derivatives, where
\epsilon_j is the j-th order accuracy tolerance; this bound applies when
either q = 1 or the problem is not composite with q \leq 2. For general
non-composite problems,  even when  the feasible set is nonconvex, the bound
becomes

   O( max_{1 \leq j \leq q}\epsilon_j^{-q(p+1)/p} )

evaluations. If the problem is composite, and either q > 1 or the
feasible set is not convex, the bound is then

   O( max_{1 \leq j \leq q}\epsilon_j^{-(q+1)} )

evaluations. These results not only provide, to our knowledge, the first known
bound for (unconstrained or inexpensively-constrained) composite problems for
optimality orders exceeding one, but also give the first sharp bounds for
high-order strong approximate q-th order minimizers of standard
(unconstrained and inexpensively constrained) smooth problems, thereby
complementing known results for weak minimizers.