Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

Author: 

Cartis, C
Gould, N
Toint, P

Publication Date: 

1 January 2019

Journal: 

Approximation and Optimization: Algorithms, Complexity and Applications

Last Updated: 

2020-01-21T15:08:28.14+00:00

Volume: 

145

DOI: 

10.1007/978-3-030-12767-1

abstract: 

Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of O(∈−3/2) proved by Cartis, Gould and Toint (IMAJNA 32(4) 2012, pp.1662-1695) 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) evaluations (∈P and ∈D 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(∈P−1/p ∈D−(p+1)/p) evaluations under similarly weakened assumptions

Symplectic id: 

951522

Submitted to ORA: 

Not Submitted

Publication Type: 

Journal Article

ISBN-13: 

9783030127671