Résumé
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 (Formula presented) evaluations whenever derivatives of order p are available. It is also shown that the bound of (Formula presented) 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 (Formula presented) evaluations under similarly weakened assumptions.
| langue originale | Anglais |
|---|---|
| titre | Springer Optimization and Its Applications |
| Sous-titre | Algorithms, Complexity and Applications |
| rédacteurs en chef | Iannis Demetriou, Panos Pardalos |
| Editeur | Springer Heidelberg |
| Chapitre | 1 |
| Pages | 5-26 |
| Nombre de pages | 22 |
| ISBN (Electronique) | 978-3-030-12766-4 |
| Les DOIs | |
| état | Publié - juin 2019 |
Série de publications
| Nom | Springer Optimization and Its Applications |
|---|---|
| Volume | 145 |
| ISSN (imprimé) | 1931-6828 |
| ISSN (Electronique) | 1931-6836 |
Empreinte digitale
Citer ceci
}
Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models. / Cartis, Coralia; Gould, Nicholas I M; Toint, Philippe.
Springer Optimization and Its Applications: Algorithms, Complexity and Applications. Ed. / Iannis Demetriou; Panos Pardalos. Springer Heidelberg, 2019. p. 5-26 (Springer Optimization and Its Applications; Vol 145).Résultats de recherche: Contribution dans un livre/un catalogue/un rapport/dans les actes d'une conférence › Chapitre
TY - CHAP
T1 - Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models
AU - Cartis, Coralia
AU - Gould, Nicholas I M
AU - Toint, Philippe
PY - 2019/6
Y1 - 2019/6
N2 - 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 (Formula presented) evaluations whenever derivatives of order p are available. It is also shown that the bound of (Formula presented) 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 (Formula presented) evaluations under similarly weakened assumptions.
AB - 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 (Formula presented) evaluations whenever derivatives of order p are available. It is also shown that the bound of (Formula presented) 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 (Formula presented) evaluations under similarly weakened assumptions.
KW - Complexity theory
KW - Nonlinear optimization
KW - scaled optimality conditions
UR - http://www.scopus.com/inward/record.url?scp=85065814036&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-12767-1_2
DO - 10.1007/978-3-030-12767-1_2
M3 - Chapter
T3 - Springer Optimization and Its Applications
SP - 5
EP - 26
BT - Springer Optimization and Its Applications
A2 - Demetriou, Iannis
A2 - Pardalos, Panos
PB - Springer Heidelberg
ER -