A lower bound on convergence rates of nonadaptive algorithms for univariate optimization with noise

James M. Calvin

doi:10.1007/s10898-010-9530-z

A lower bound on convergence rates of nonadaptive algorithms for univariate optimization with noise

Research output: Contribution to journal › Article › peer-review

Abstract

This paper considers complexity bounds for the problem of approximating the global minimum of a univariate function when the function evaluations are corrupted by random noise. We take an average-case point of view, where the objective function is taken to be a sample function of a Wiener process and the noise is independent Gaussian. Previous papers have bounded the convergence rates of some nonadaptive algorithms. We establish a lower bound on the convergence rate of any nonadaptive algorithm.

Original language	English (US)
Pages (from-to)	17-27
Number of pages	11
Journal	Journal of Global Optimization
Volume	48
Issue number	1
DOIs	https://doi.org/10.1007/s10898-010-9530-z
State	Published - Sep 2010
Externally published	Yes

All Science Journal Classification (ASJC) codes

Control and Optimization
Applied Mathematics
Business, Management and Accounting (miscellaneous)
Computer Science Applications
Management Science and Operations Research

Keywords

Global optimization
Noisy information
Wiener process

Access to Document

10.1007/s10898-010-9530-z

Cite this

@article{766d804ab93b4020866ced177d10c066,

title = "A lower bound on convergence rates of nonadaptive algorithms for univariate optimization with noise",

abstract = "This paper considers complexity bounds for the problem of approximating the global minimum of a univariate function when the function evaluations are corrupted by random noise. We take an average-case point of view, where the objective function is taken to be a sample function of a Wiener process and the noise is independent Gaussian. Previous papers have bounded the convergence rates of some nonadaptive algorithms. We establish a lower bound on the convergence rate of any nonadaptive algorithm.",

keywords = "Global optimization, Noisy information, Wiener process",

author = "Calvin, {James M.}",

note = "Funding Information: Acknowledgments This material is based upon work supported by the National Science Foundation under grant CMMI-0825381.",

year = "2010",

month = sep,

doi = "10.1007/s10898-010-9530-z",

language = "English (US)",

volume = "48",

pages = "17--27",

journal = "Journal of Global Optimization",

issn = "0925-5001",

publisher = "Springer Netherlands",

number = "1",

}

TY - JOUR

T1 - A lower bound on convergence rates of nonadaptive algorithms for univariate optimization with noise

AU - Calvin, James M.

N1 - Funding Information: Acknowledgments This material is based upon work supported by the National Science Foundation under grant CMMI-0825381.

PY - 2010/9

Y1 - 2010/9

N2 - This paper considers complexity bounds for the problem of approximating the global minimum of a univariate function when the function evaluations are corrupted by random noise. We take an average-case point of view, where the objective function is taken to be a sample function of a Wiener process and the noise is independent Gaussian. Previous papers have bounded the convergence rates of some nonadaptive algorithms. We establish a lower bound on the convergence rate of any nonadaptive algorithm.

AB - This paper considers complexity bounds for the problem of approximating the global minimum of a univariate function when the function evaluations are corrupted by random noise. We take an average-case point of view, where the objective function is taken to be a sample function of a Wiener process and the noise is independent Gaussian. Previous papers have bounded the convergence rates of some nonadaptive algorithms. We establish a lower bound on the convergence rate of any nonadaptive algorithm.

KW - Global optimization

KW - Noisy information

KW - Wiener process

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

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

U2 - 10.1007/s10898-010-9530-z

DO - 10.1007/s10898-010-9530-z

M3 - Article

AN - SCOPUS:77955516177

SN - 0925-5001

VL - 48

SP - 17

EP - 27

JO - Journal of Global Optimization

JF - Journal of Global Optimization

IS - 1

ER -

A lower bound on convergence rates of nonadaptive algorithms for univariate optimization with noise

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this