Title | ||
---|---|---|
Evaluation complexity bounds for smooth constrained nonlinear optimisation using scaled KKT conditions, high-order models and the criticality measure $χ$. |
Abstract | ||
---|---|---|
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(epsilon_P^{-1/2}epsilon_D^{-3/2})$ evaluations ($epsilon_P$ and $epsilon_D$ being primal and dual accuracy thresholds) suggested by Cartis, Gould and Toint (SINUM, 2015) for the general nonconvex case involving both equality and inequality constraints can be generalized to a bound of $O(epsilon_P^{-1/p}epsilon_D^{-(p+1)/p})$ evaluations under similarly weakened assumptions. This paper is variant of a companion report (NTR-11-2015, University of Namur, Belgium) which uses a different first-order criticality measure to obtain the same complexity bounds. |
Year | Venue | Field |
---|---|---|
2017 | arXiv: Optimization and Control | Discrete mathematics,Mathematical optimization,Nonlinear system,Critical point (thermodynamics),Criticality,Karush–Kuhn–Tucker conditions,Mathematics,Constrained optimization |
DocType | Volume | Citations |
Journal | abs/1705.04895 | 1 |
PageRank | References | Authors |
0.35 | 3 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Coralia Cartis | 1 | 451 | 28.74 |
Nicholas I. M. Gould | 2 | 1445 | 123.86 |
Philippe L. Toint | 3 | 1397 | 127.90 |