Minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity

Résultats de recherche: Papier de travailArticle de travail

2 Downloads (Pure)

Résumé

An adaptive regularization algorithm using inexact function and derivatives evaluations is proposed for the solution of composite nonsmooth nonconvex optimization. It is shown that this algorithm needs at most O(|log(epsilon)| epsilon^{-2}) evaluations of the problem's functions and their derivatives for finding an $\epsilon$-approximate first-order stationary point. This complexity bound therefore generalizes that provided by [Bellavia, Gurioli, Morini and Toint, 2018] for inexact methods for smooth nonconvex problems, and is within a factor |log(epsilon)| of the optimal bound known for smooth and nonsmooth nonconvex minimization with exact evaluations. A practically more restrictive variant of the algorithm with worst-case complexity O(|log(epsilon)|+epsilon^{-2}) is also presented.
langue originaleAnglais
EditeurArxiv
Nombre de pages19
Volume1902.10406
étatPublié - févr. 2019

Empreinte digitale

Derivatives
Evaluation
Adaptive algorithms
Nonconvex Minimization
Inexact Methods
Derivative
Nonsmooth Optimization
Optimal Bound
Nonconvex Optimization
Nonconvex Problems
Stationary point
Regularization
Composite materials
Composite
First-order
Generalise

mots-clés

    Citer ceci

    @techreport{47f1e6158a904bdd807e32cd49ffaac4,
    title = "Minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity",
    abstract = "An adaptive regularization algorithm using inexact function and derivatives evaluations is proposed for the solution of composite nonsmooth nonconvex optimization. It is shown that this algorithm needs at most O(|log(epsilon)| epsilon^{-2}) evaluations of the problem's functions and their derivatives for finding an $\epsilon$-approximate first-order stationary point. This complexity bound therefore generalizes that provided by [Bellavia, Gurioli, Morini and Toint, 2018] for inexact methods for smooth nonconvex problems, and is within a factor |log(epsilon)| of the optimal bound known for smooth and nonsmooth nonconvex minimization with exact evaluations. A practically more restrictive variant of the algorithm with worst-case complexity O(|log(epsilon)|+epsilon^{-2}) is also presented.",
    keywords = "evaluation complexity, nonsmooth problems, nonconvex optimization, inexact evaluations, composite functions",
    author = "Serge Gratton and Ehouarn Simon and Philippe Toint",
    year = "2019",
    month = "2",
    language = "English",
    volume = "1902.10406",
    publisher = "Arxiv",
    type = "WorkingPaper",
    institution = "Arxiv",

    }

    Minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity. / Gratton, Serge; Simon, Ehouarn; Toint, Philippe.

    Arxiv, 2019.

    Résultats de recherche: Papier de travailArticle de travail

    TY - UNPB

    T1 - Minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity

    AU - Gratton, Serge

    AU - Simon, Ehouarn

    AU - Toint, Philippe

    PY - 2019/2

    Y1 - 2019/2

    N2 - An adaptive regularization algorithm using inexact function and derivatives evaluations is proposed for the solution of composite nonsmooth nonconvex optimization. It is shown that this algorithm needs at most O(|log(epsilon)| epsilon^{-2}) evaluations of the problem's functions and their derivatives for finding an $\epsilon$-approximate first-order stationary point. This complexity bound therefore generalizes that provided by [Bellavia, Gurioli, Morini and Toint, 2018] for inexact methods for smooth nonconvex problems, and is within a factor |log(epsilon)| of the optimal bound known for smooth and nonsmooth nonconvex minimization with exact evaluations. A practically more restrictive variant of the algorithm with worst-case complexity O(|log(epsilon)|+epsilon^{-2}) is also presented.

    AB - An adaptive regularization algorithm using inexact function and derivatives evaluations is proposed for the solution of composite nonsmooth nonconvex optimization. It is shown that this algorithm needs at most O(|log(epsilon)| epsilon^{-2}) evaluations of the problem's functions and their derivatives for finding an $\epsilon$-approximate first-order stationary point. This complexity bound therefore generalizes that provided by [Bellavia, Gurioli, Morini and Toint, 2018] for inexact methods for smooth nonconvex problems, and is within a factor |log(epsilon)| of the optimal bound known for smooth and nonsmooth nonconvex minimization with exact evaluations. A practically more restrictive variant of the algorithm with worst-case complexity O(|log(epsilon)|+epsilon^{-2}) is also presented.

    KW - evaluation complexity

    KW - nonsmooth problems

    KW - nonconvex optimization

    KW - inexact evaluations

    KW - composite functions

    M3 - Working paper

    VL - 1902.10406

    BT - Minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity

    PB - Arxiv

    ER -