Evaluation complexity bounds for smooth constrained nonlinear
optimization using scaled KKT conditions and high-order models
C. Cartis, N. I. M. Gould~and Ph. L. Toint
Report NAXYS-11-2015
Evaluation complexity for convexly constrained optimization is considered and
it is shown first that the complexity bound of O(\epsilon^{-3/2}) proved by
Cartis, Gould and Toint (IMAJNA 32(4) 2012, pp.1662-1695) for computing an
\epsilon-approximate first-order critical point can be obtained under
significantly weaker assumptions. Moreover, the result is generalized to the
case where high-order derivatives are used, resulting in a bound of
O(\epsilon^{-(p+1)/p}) evaluations whenever derivatives of order $p$ are
available. It is also shown that the bound of O(\ep^{-1/2}\ed^{-3/2})
evaluations (\ep$and \ed being primal and dual accuracy thresholds)
suggested by Cartis, Gould and Toint (SINUM, 53(2), 2015, pp.836-851) for the
general nonconvex case involving both equality and inequality constraints can
be generalized to yield a bound of O(\ep^{-1/p}\ed^{-(p+1)/p}) evaluations
under similarly weakened assumptions.