Résumé
High-order optimality conditions for convexly constrained nonlinear optimization problems are analysed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order ϵ-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that if derivatives of the objective function up to order q≥ 1 can be evaluated and are Lipschitz continuous, then this algorithm applied to the convexly constrained problem needs at most O(ϵ - ( q + 1 )) evaluations of f and its derivatives to compute an ϵ-approximate qth-order critical point. This provides the first evaluation complexity result for critical points of arbitrary order in nonlinear optimization. An example is discussed, showing that the obtained evaluation complexity bounds are essentially sharp.
| langue originale | Anglais |
|---|---|
| Pages (de - à) | 1073-1107 |
| Nombre de pages | 35 |
| journal | Foundations of Computational Mathematics |
| Volume | 18 |
| Numéro de publication | 5 |
| Les DOIs | |
| état | Publié - 1 oct. 2018 |
Empreinte digitale
Citer ceci
}
Second-order optimality and beyond : Characterization and Evaluation Complexity in Convexly Constrained Nonlinear Optimization. / Cartis, Coralia; Gould, Nicholas I M; Toint, Philippe.
Dans: Foundations of Computational Mathematics, Vol 18, Numéro 5, 01.10.2018, p. 1073-1107.Résultats de recherche: Contribution à un journal/une revue › Article
TY - JOUR
T1 - Second-order optimality and beyond
T2 - Characterization and Evaluation Complexity in Convexly Constrained Nonlinear Optimization
AU - Cartis, Coralia
AU - Gould, Nicholas I M
AU - Toint, Philippe
PY - 2018/10/1
Y1 - 2018/10/1
N2 - High-order optimality conditions for convexly constrained nonlinear optimization problems are analysed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order ϵ-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that if derivatives of the objective function up to order q≥ 1 can be evaluated and are Lipschitz continuous, then this algorithm applied to the convexly constrained problem needs at most O(ϵ - ( q + 1 )) evaluations of f and its derivatives to compute an ϵ-approximate qth-order critical point. This provides the first evaluation complexity result for critical points of arbitrary order in nonlinear optimization. An example is discussed, showing that the obtained evaluation complexity bounds are essentially sharp.
AB - High-order optimality conditions for convexly constrained nonlinear optimization problems are analysed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order ϵ-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that if derivatives of the objective function up to order q≥ 1 can be evaluated and are Lipschitz continuous, then this algorithm applied to the convexly constrained problem needs at most O(ϵ - ( q + 1 )) evaluations of f and its derivatives to compute an ϵ-approximate qth-order critical point. This provides the first evaluation complexity result for critical points of arbitrary order in nonlinear optimization. An example is discussed, showing that the obtained evaluation complexity bounds are essentially sharp.
KW - Complexity theory
KW - optimality conditions
KW - nonlinear optimization
UR - http://www.scopus.com/inward/record.url?scp=85028973317&partnerID=8YFLogxK
U2 - 10.1007/s10208-017-9363-y
DO - 10.1007/s10208-017-9363-y
M3 - Article
VL - 18
SP - 1073
EP - 1107
JO - Foundations of Computational Mathematics
JF - Foundations of Computational Mathematics
SN - 1615-3375
IS - 5
ER -