Sharp worst-case evaluation complexity bounds for arbitrary-order
nonconvex optimization with inexpensive constraints
C. Cartis, N. I. M. Gould and Ph. L. Toint
3 XI 2018
We provide sharp worst-case evaluation complexity bounds for nonconvex
minimization problems with general inexpensive constraints, i.e.\ problems
where the cost of evaluating/enforcing of the (possibly nonconvex or even
disconnected) constraints, if any, is negligible compared to that of
evaluating the objective function. These bounds unify, extend or improve all
known upper and lower complexity bounds for unconstrained and
convexly-constrained problems. It is shown that, given an accuracy level
$\epsilon$, a degree of highest available Lipschitz continuous derivatives $p$
and a desired optimality order $q$ between one and $p$, a conceptual
regularization algorithm requires no more than
$O(\epsilon^{-\frac{p+1}{p-q+1}})$ evaluations of the objective function and
its derivatives to compute a suitably approximate $q$-th order minimizer. With
an appropriate choice of the regularization, a similar result also holds if
the $p$-th derivative is merely H\"{o}lder rather than Lipschitz
continuous. We provide an example that shows that the above complexity bound
is sharp for unconstrained and a wide class of constrained problems; we also
give reasons for the optimality of regularization methods from a worst-case
complexity point of view, within a large class of algorithms that use the same
derivative information.