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

Résultats de recherche: Papier de travailArticle de travail

3 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
ÉditeurArxiv
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

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 -