A lower bound on complexity of optimization under the r-fold integrated Wiener measure

James M. Calvin

doi:10.1016/j.jco.2010.10.006

A lower bound on complexity of optimization under the r-fold integrated Wiener measure

James M. Calvin

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

2 Scopus citations

Abstract

We consider the problem of approximating the global minimum of an r-times continuously differentiable function on the unit interval, based on sequentially chosen function and derivative evaluations. Using a probability model based on the r-fold integrated Wiener measure, we establish a lower bound on the expected number of function evaluations required to approximate the minimum to within ∈ on average.

Original language	English (US)
Pages (from-to)	404-416
Number of pages	13
Journal	Journal of Complexity
Volume	27
Issue number	3-4
DOIs	https://doi.org/10.1016/j.jco.2010.10.006
State	Published - 2011
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

Convergence
Optimization
Statistical models

Access to Document

10.1016/j.jco.2010.10.006

Cite this

@article{5a43db76e01e448798babc02a5ee6094,

title = "A lower bound on complexity of optimization under the r-fold integrated Wiener measure",

abstract = "We consider the problem of approximating the global minimum of an r-times continuously differentiable function on the unit interval, based on sequentially chosen function and derivative evaluations. Using a probability model based on the r-fold integrated Wiener measure, we establish a lower bound on the expected number of function evaluations required to approximate the minimum to within ∈ on average.",

keywords = "Convergence, Optimization, Statistical models",

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

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

year = "2011",

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

language = "English (US)",

volume = "27",

pages = "404--416",

journal = "Journal of Complexity",

issn = "0885-064X",

publisher = "Academic Press Inc.",

number = "3-4",

}

TY - JOUR

T1 - A lower bound on complexity of optimization under the r-fold integrated Wiener measure

AU - Calvin, James M.

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

PY - 2011

Y1 - 2011

N2 - We consider the problem of approximating the global minimum of an r-times continuously differentiable function on the unit interval, based on sequentially chosen function and derivative evaluations. Using a probability model based on the r-fold integrated Wiener measure, we establish a lower bound on the expected number of function evaluations required to approximate the minimum to within ∈ on average.

AB - We consider the problem of approximating the global minimum of an r-times continuously differentiable function on the unit interval, based on sequentially chosen function and derivative evaluations. Using a probability model based on the r-fold integrated Wiener measure, we establish a lower bound on the expected number of function evaluations required to approximate the minimum to within ∈ on average.

KW - Convergence

KW - Optimization

KW - Statistical models

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

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

U2 - 10.1016/j.jco.2010.10.006

DO - 10.1016/j.jco.2010.10.006

M3 - Article

AN - SCOPUS:79955068900

SN - 0885-064X

VL - 27

SP - 404

EP - 416

JO - Journal of Complexity

JF - Journal of Complexity

IS - 3-4

ER -

A lower bound on complexity of optimization under the r-fold integrated Wiener measure

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this