Résumé
optimization problems are analyzed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order $\epsilon$-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that, if derivatives of theobjective function up to order $q \geq 1$ can be evaluated and are Lipschitz continuous, then this algorithm applied to the convexly constrained problem needs at most $O(\epsilon^{-(q+1)})$ evaluations of $f$ and its derivatives to compute an $\epsilon$-approximate $q$-th 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 | Anglais |
|---|---|
| journal | Foundations of Computational Mathematics |
| état | Accepté/sous presse - 28 mai 2017 |
Empreinte digitale
mots-clés
Citer ceci
}
Second-order optimality and beyond : characterization and evaluation complexity in nonconvex convexly-constrained optimization. / Cartis, Coralia; Gould, Nicholas I M; Toint, Philippe.
Dans: Foundations of Computational Mathematics, 28.05.2017.Résultats de recherche: Contribution à un journal/une revue › Article
TY - JOUR
T1 - Second-order optimality and beyond
T2 - Foundations of Computational Mathematics
AU - Cartis,Coralia
AU - Gould,Nicholas I M
AU - Toint,Philippe
PY - 2017/5/28
Y1 - 2017/5/28
N2 - High-order optimality conditions for convexly-constrained nonlinearoptimization problems are analyzed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order $\epsilon$-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that, if derivatives of theobjective function up to order $q \geq 1$ can be evaluated and are Lipschitz continuous, then this algorithm applied to the convexly constrained problem needs at most $O(\epsilon^{-(q+1)})$ evaluations of $f$ and its derivatives to compute an $\epsilon$-approximate $q$-th 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 nonlinearoptimization problems are analyzed. A corresponding (expensive) measure of criticality for arbitrary order is proposed and extended to define high-order $\epsilon$-approximate critical points. This new measure is then used within a conceptual trust-region algorithm to show that, if derivatives of theobjective function up to order $q \geq 1$ can be evaluated and are Lipschitz continuous, then this algorithm applied to the convexly constrained problem needs at most $O(\epsilon^{-(q+1)})$ evaluations of $f$ and its derivatives to compute an $\epsilon$-approximate $q$-th 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
M3 - Article
JO - Foundations of Computational Mathematics
JF - Foundations of Computational Mathematics
SN - 1615-3375
ER -