Evaluation Complexity Bounds for Smooth Constrained Nonlinear Optimization Using Scaled KKT Conditions and High-Order Models

Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of O(𝜖 −3∕2) proved by Cartis et al. (IMA J Numer Anal 32:1662–1695, 2012) for computing an 𝜖-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(𝜖 −(p+1)∕p) evaluations whenever derivatives of order p are available. It is also shown that the bound of O ( 𝜖 P − 1 ∕ 2 𝜖 D − 3 ∕ 2 ) $$O(\epsilon _{\mbox{ P}}^{-1/2}\epsilon _{\mbox{ D}}^{-3/2})$$ evaluations (𝜖 P and 𝜖 D being primal and dual accuracy thresholds) suggested by Cartis et al. (SIAM J. Numer. Anal. 53:836–851, 2015) for the general nonconvex case involving both equality and inequality constraints can be generalized to yield a bound of O ( 𝜖 P − 1 ∕ p 𝜖 D − ( p + 1 ) ∕ p ) $$O(\epsilon _{\mbox{ P}}^{-1/p}\epsilon _{\mbox{ D}}^{-(p+1)/p})$$ evaluations under similarly weakened assumptions.