Second-order optimality and beyond: characterization and evaluation complexity in nonconvex convexly-constrained optimization

Coralia Cartis, Nicholas I M Gould, Philippe Toint

Résultats de recherche: Contribution à un journal/une revueArticle

Résumé

High-order optimality conditions for convexly-constrained nonlinear
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.
langueAnglais
journalFoundations of Computational Mathematics
étatAccepté/sous presse - 28 mai 2017

Empreinte digitale

Nonconvex Optimization
Constrained Optimization
Optimality
Evaluation
Constrained optimization
Derivatives
Critical point
Nonlinear Optimization
Higher Order
Derivative
Arbitrary
Trust Region Algorithm
Order Conditions
Criticality
Optimality Conditions
Lipschitz
Nonlinear Problem
Optimization Problem

mots-clés

    Citer ceci

    @article{bd6f0a4f1ea04f118480bfabe0e76c6a,
    title = "Second-order optimality and beyond: characterization and evaluation complexity in nonconvex convexly-constrained optimization",
    abstract = "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.",
    keywords = "Complexity theory, optimality conditions, nonlinear optimization",
    author = "Coralia Cartis and Gould, {Nicholas I M} and Philippe Toint",
    year = "2017",
    month = "5",
    day = "28",
    language = "English",
    journal = "Foundations of Computational Mathematics",
    issn = "1615-3375",
    publisher = "Springer New York",

    }

    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 revueArticle

    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 -