Second-order optimality and beyond: 
          characterization and evaluation complexity 
         in nonconvex convexly-constrained optimization

          C. Cartis, N. I. M. Gould and Ph. L. Toint

                   Report NAXYS-06-2016

Abstract.
High-order optimality conditions for convexly-constrained nonlinear
optimization problems are analyzed. A corresponding (expensive) measure of
criticality for arbitrary order is proposed and extended to define high-order
$\epsilon$-approximate critical points. This new measure is then used within a
conceptual trust-region algorithm to show that, if derivatives of the
objective function up to order $q \geq 1$ can be evaluated and are Lipschitz
continuous, then this algorithm applied to the convexly constrained problem
needs at most $O(\epsilon^{-(q+1)})$ evaluations of $f$ and its derivatives to
compute an $\epsilon$-approximate $q$-th order critical point. This provides
the first evaluation complexity result for critical points of arbitrary order
in nonlinear optimization. An example is discussed showing that the
obtained evaluation complexity bounds are essentially sharp.