Improved second-order evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

Coralia Cartis, Nicholas I M Gould, Philippe Toint

Résultats de recherche: Papier de travailArticle de travail

Résumé

The unconstrained minimization of a sufficiently smooth objective function f(x) is considered, for which derivatives up to order p, p >= 2, are assumed to be available. An adaptive regularization algorithm is proposed that uses Taylor models of the objective of order p and that is guaranteed to find a first- and second-order critical point in at most O(max(\epsilon_1^{-(p+1)/p},\epsilon_2^{-(p+1)/(p-1)})) function and derivatives evaluations, where\epsilon_1 and \epsilon_2 >0 are prescribed first- and second-order optimality tolerances. Our approach extends the method in Birgin et al. (2016) to finding second-order critical points, and establishes the novel complexity bound for second-order criticality under identical problem assumptions as for first-order, namely, that the p-th derivative tensor is Lipschitz continuous and that f(x) is bounded from below. The evaluation-complexity bound for second-order criticality improves on all such known existing results.
langueAnglais
EditeurArxiv
Volume1708.04044
étatPublié - août 2017

Empreinte digitale

Function evaluation
Unconstrained Optimization
Adaptive algorithms
Nonlinear Optimization
Tensors
Higher Order
Derivatives
Evaluation
Criticality
Critical point
Unconstrained Minimization
Model
Evaluation Function
Lipschitz
Tolerance
Optimality
Regularization
Tensor
First-order
Derivative

mots-clés

    Citer ceci

    @techreport{70387628b18d4359a9e8a52d1e69eeea,
    title = "Improved second-order evaluation complexity for unconstrained nonlinear optimization using high-order regularized models",
    abstract = "The unconstrained minimization of a sufficiently smooth objective function f(x) is considered, for which derivatives up to order p, p >= 2, are assumed to be available. An adaptive regularization algorithm is proposed that uses Taylor models of the objective of order p and that is guaranteed to find a first- and second-order critical point in at most O(max(\epsilon_1^{-(p+1)/p},\epsilon_2^{-(p+1)/(p-1)})) function and derivatives evaluations, where\epsilon_1 and \epsilon_2 >0 are prescribed first- and second-order optimality tolerances. Our approach extends the method in Birgin et al. (2016) to finding second-order critical points, and establishes the novel complexity bound for second-order criticality under identical problem assumptions as for first-order, namely, that the p-th derivative tensor is Lipschitz continuous and that f(x) is bounded from below. The evaluation-complexity bound for second-order criticality improves on all such known existing results.",
    keywords = "Evaluation complexity, Nonlinear optimization, second-order methods",
    author = "Coralia Cartis and Gould, {Nicholas I M} and Philippe Toint",
    year = "2017",
    month = "8",
    language = "English",
    volume = "1708.04044",
    publisher = "Arxiv",
    type = "WorkingPaper",
    institution = "Arxiv",

    }

    Improved second-order evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. / Cartis, Coralia; Gould, Nicholas I M; Toint, Philippe.

    Arxiv, 2017.

    Résultats de recherche: Papier de travailArticle de travail

    TY - UNPB

    T1 - Improved second-order evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

    AU - Cartis,Coralia

    AU - Gould,Nicholas I M

    AU - Toint,Philippe

    PY - 2017/8

    Y1 - 2017/8

    N2 - The unconstrained minimization of a sufficiently smooth objective function f(x) is considered, for which derivatives up to order p, p >= 2, are assumed to be available. An adaptive regularization algorithm is proposed that uses Taylor models of the objective of order p and that is guaranteed to find a first- and second-order critical point in at most O(max(\epsilon_1^{-(p+1)/p},\epsilon_2^{-(p+1)/(p-1)})) function and derivatives evaluations, where\epsilon_1 and \epsilon_2 >0 are prescribed first- and second-order optimality tolerances. Our approach extends the method in Birgin et al. (2016) to finding second-order critical points, and establishes the novel complexity bound for second-order criticality under identical problem assumptions as for first-order, namely, that the p-th derivative tensor is Lipschitz continuous and that f(x) is bounded from below. The evaluation-complexity bound for second-order criticality improves on all such known existing results.

    AB - The unconstrained minimization of a sufficiently smooth objective function f(x) is considered, for which derivatives up to order p, p >= 2, are assumed to be available. An adaptive regularization algorithm is proposed that uses Taylor models of the objective of order p and that is guaranteed to find a first- and second-order critical point in at most O(max(\epsilon_1^{-(p+1)/p},\epsilon_2^{-(p+1)/(p-1)})) function and derivatives evaluations, where\epsilon_1 and \epsilon_2 >0 are prescribed first- and second-order optimality tolerances. Our approach extends the method in Birgin et al. (2016) to finding second-order critical points, and establishes the novel complexity bound for second-order criticality under identical problem assumptions as for first-order, namely, that the p-th derivative tensor is Lipschitz continuous and that f(x) is bounded from below. The evaluation-complexity bound for second-order criticality improves on all such known existing results.

    KW - Evaluation complexity

    KW - Nonlinear optimization

    KW - second-order methods

    M3 - Working paper

    VL - 1708.04044

    BT - Improved second-order evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

    PB - Arxiv

    ER -