Lower bound on complexity of optimization of continuous functions

James M. Calvin

doi:10.1016/j.jco.2003.06.004

Lower bound on complexity of optimization of continuous functions

James M. Calvin

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

8 Scopus citations

Abstract

This paper considers the problem of approximating the minimum of a continuous function using a fixed number of sequentially selected function evaluations. A lower bound on the complexity is established by analyzing the average case for the Brownian bridge.

Original language	English (US)
Pages (from-to)	773-795
Number of pages	23
Journal	Journal of Complexity
Volume	20
Issue number	5
DOIs	https://doi.org/10.1016/j.jco.2003.06.004
State	Published - Oct 2004
Externally published	Yes

All Science Journal Classification (ASJC) codes

Algebra and Number Theory
Statistics and Probability
Numerical Analysis
General Mathematics
Control and Optimization
Applied Mathematics

Keywords

Average case complexity
Global optimization
Wiener measure

Access to Document

10.1016/j.jco.2003.06.004

Cite this

@article{3048dc03e9d645aba91d03ea2d58d02a,

title = "Lower bound on complexity of optimization of continuous functions",

abstract = "This paper considers the problem of approximating the minimum of a continuous function using a fixed number of sequentially selected function evaluations. A lower bound on the complexity is established by analyzing the average case for the Brownian bridge.",

keywords = "Average case complexity, Global optimization, Wiener measure",

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

note = "Funding Information: \$This work was supported in part by NSF grant DMI-9900117. E-mail address: [email protected].",

year = "2004",

month = oct,

doi = "10.1016/j.jco.2003.06.004",

language = "English (US)",

volume = "20",

pages = "773--795",

journal = "Journal of Complexity",

issn = "0885-064X",

publisher = "Academic Press Inc.",

number = "5",

}

TY - JOUR

T1 - Lower bound on complexity of optimization of continuous functions

AU - Calvin, James M.

N1 - Funding Information: $This work was supported in part by NSF grant DMI-9900117. E-mail address: [email protected].

PY - 2004/10

Y1 - 2004/10

N2 - This paper considers the problem of approximating the minimum of a continuous function using a fixed number of sequentially selected function evaluations. A lower bound on the complexity is established by analyzing the average case for the Brownian bridge.

AB - This paper considers the problem of approximating the minimum of a continuous function using a fixed number of sequentially selected function evaluations. A lower bound on the complexity is established by analyzing the average case for the Brownian bridge.

KW - Average case complexity

KW - Global optimization

KW - Wiener measure

UR - https://www.scopus.com/pages/publications/4444279251

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

U2 - 10.1016/j.jco.2003.06.004

DO - 10.1016/j.jco.2003.06.004

M3 - Article

AN - SCOPUS:4444279251

SN - 0885-064X

VL - 20

SP - 773

EP - 795

JO - Journal of Complexity

JF - Journal of Complexity

IS - 5

ER -

Lower bound on complexity of optimization of continuous functions

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this