Abstract
The worst-case evaluation complexity of finding an approximate first-order critical point using gradient-related non-monotone methods for smooth non-convex and unconstrained problems is investigated. The analysis covers a practical linesearch implementation of these popular methods, allowing for an unknown number of evaluations of the objective function (and its gradient) per iteration. It is shown that this class of methods shares the known complexity properties of a simple steepest-descent scheme and that an approximate first-order critical point can be computed in at most (Formula presented.) function and gradient evaluations, where (Formula presented.) is the user-defined accuracy threshold on the gradient norm.
| Original language | English |
|---|---|
| Pages (from-to) | 1349-1361 |
| Number of pages | 13 |
| Journal | Optimization |
| Volume | 64 |
| Issue number | 5 |
| DOIs | |
| Publication status | Published - 4 May 2015 |
Fingerprint
Keywords
- evaluation complexity
- linesearch algorithms
- non-linear optimization
- non-monotone methods
- worst-case analysis
Cite this
}
Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained optimization. / Cartis, C.; Rodrigues Sampaio, Phillipe; Toint, Ph L.
In: Optimization, Vol. 64, No. 5, 04.05.2015, p. 1349-1361.Research output: Contribution to journal › Article
TY - JOUR
T1 - Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained optimization
AU - Cartis, C.
AU - Rodrigues Sampaio, Phillipe
AU - Toint, Ph L.
PY - 2015/5/4
Y1 - 2015/5/4
N2 - The worst-case evaluation complexity of finding an approximate first-order critical point using gradient-related non-monotone methods for smooth non-convex and unconstrained problems is investigated. The analysis covers a practical linesearch implementation of these popular methods, allowing for an unknown number of evaluations of the objective function (and its gradient) per iteration. It is shown that this class of methods shares the known complexity properties of a simple steepest-descent scheme and that an approximate first-order critical point can be computed in at most (Formula presented.) function and gradient evaluations, where (Formula presented.) is the user-defined accuracy threshold on the gradient norm.
AB - The worst-case evaluation complexity of finding an approximate first-order critical point using gradient-related non-monotone methods for smooth non-convex and unconstrained problems is investigated. The analysis covers a practical linesearch implementation of these popular methods, allowing for an unknown number of evaluations of the objective function (and its gradient) per iteration. It is shown that this class of methods shares the known complexity properties of a simple steepest-descent scheme and that an approximate first-order critical point can be computed in at most (Formula presented.) function and gradient evaluations, where (Formula presented.) is the user-defined accuracy threshold on the gradient norm.
KW - evaluation complexity
KW - linesearch algorithms
KW - non-linear optimization
KW - non-monotone methods
KW - worst-case analysis
UR - http://www.scopus.com/inward/record.url?scp=84924237792&partnerID=8YFLogxK
U2 - 10.1080/02331934.2013.869809
DO - 10.1080/02331934.2013.869809
M3 - Article
AN - SCOPUS:84924237792
VL - 64
SP - 1349
EP - 1361
JO - Optimization
JF - Optimization
SN - 0233-1934
IS - 5
ER -