Worst-case evaluation complexity of regularization methods for smooth unconstrained optimization using Hölder continuous gradients

Research output: Contribution to journalArticle

3 Downloads (Pure)

Abstract

The worst-case behaviour of a general class of regularization algorithms is considered in the case where only objective function values and associated gradient vectors are evaluated. Upper bounds are derived on the number of such evaluations that are needed for the algorithm to produce an approximate first-order critical point whose accuracy is within a user-defined threshold. The analysis covers the entire range of meaningful powers in the regularization term as well as in the Hölder exponent for the gradient. The resulting complexity bounds vary according to the regularization power and the assumed Hölder exponent, recovering known results when available.
Original languageEnglish
Pages (from-to)1273-1298
Number of pages26
JournalOptimization Methods and Software
Volume32
Issue number6
DOIs
Publication statusPublished - 2 Nov 2017

Fingerprint

Unconstrained Optimization
Regularization Method
Regularization
Gradient
Evaluation
Exponent
Gradient vector
Critical point
Objective function
Entire
Vary
Cover
Upper bound
First-order
Term
Range of data

Keywords

  • optimization
  • worst-case analysis
  • complexity theory
  • nonlinear optimisation
  • regularization methods
  • complexity analysis

Cite this

@article{bc81bf2815b64fa0b632a6fee775d459,
title = "Worst-case evaluation complexity of regularization methods for smooth unconstrained optimization using H{\"o}lder continuous gradients",
abstract = "The worst-case behaviour of a general class of regularization algorithms is considered in the case where only objective function values and associated gradient vectors are evaluated. Upper bounds are derived on the number of such evaluations that are needed for the algorithm to produce an approximate first-order critical point whose accuracy is within a user-defined threshold. The analysis covers the entire range of meaningful powers in the regularization term as well as in the H{\"o}lder exponent for the gradient. The resulting complexity bounds vary according to the regularization power and the assumed H{\"o}lder exponent, recovering known results when available.",
keywords = "optimization, worst-case analysis, complexity theory, nonlinear optimisation, regularization methods, complexity analysis",
author = "Philippe Toint",
year = "2017",
month = "11",
day = "2",
doi = "10.1080/10556788.2016.1268136",
language = "English",
volume = "32",
pages = "1273--1298",
journal = "Optimization Methods and Software",
issn = "1055-6788",
publisher = "Taylor & Francis",
number = "6",

}

TY - JOUR

T1 - Worst-case evaluation complexity of regularization methods for smooth unconstrained optimization using Hölder continuous gradients

AU - Toint, Philippe

PY - 2017/11/2

Y1 - 2017/11/2

N2 - The worst-case behaviour of a general class of regularization algorithms is considered in the case where only objective function values and associated gradient vectors are evaluated. Upper bounds are derived on the number of such evaluations that are needed for the algorithm to produce an approximate first-order critical point whose accuracy is within a user-defined threshold. The analysis covers the entire range of meaningful powers in the regularization term as well as in the Hölder exponent for the gradient. The resulting complexity bounds vary according to the regularization power and the assumed Hölder exponent, recovering known results when available.

AB - The worst-case behaviour of a general class of regularization algorithms is considered in the case where only objective function values and associated gradient vectors are evaluated. Upper bounds are derived on the number of such evaluations that are needed for the algorithm to produce an approximate first-order critical point whose accuracy is within a user-defined threshold. The analysis covers the entire range of meaningful powers in the regularization term as well as in the Hölder exponent for the gradient. The resulting complexity bounds vary according to the regularization power and the assumed Hölder exponent, recovering known results when available.

KW - optimization

KW - worst-case analysis

KW - complexity theory

KW - nonlinear optimisation

KW - regularization methods

KW - complexity analysis

UR - http://www.scopus.com/inward/record.url?scp=85017624210&partnerID=8YFLogxK

U2 - 10.1080/10556788.2016.1268136

DO - 10.1080/10556788.2016.1268136

M3 - Article

VL - 32

SP - 1273

EP - 1298

JO - Optimization Methods and Software

JF - Optimization Methods and Software

SN - 1055-6788

IS - 6

ER -