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

Research output: Working paper

2 Downloads (Pure)

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.
Original languageEnglish
PublisherArxiv
Number of pages19
Volume1902.10406
Publication statusPublished - Feb 2019

Fingerprint

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

Keywords

  • evaluation complexity
  • nonsmooth problems
  • nonconvex optimization
  • inexact evaluations
  • composite functions

Cite this

@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",

}

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 -