Adaptive approximation of the minimum of Brownian motion

James M. Calvin; Mario Hefter; André Herzwurm

doi:10.1016/j.jco.2016.11.002

Adaptive approximation of the minimum of Brownian motion

James M. Calvin, Mario Hefter, André Herzwurm

Computer Science

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

10 Scopus citations

Abstract

We study the error in approximating the minimum of a Brownian motion on the unit interval based on finitely many point evaluations. We construct an algorithm that adaptively chooses the points at which to evaluate the Brownian path. In contrast to the 1/2 convergence rate of optimal nonadaptive algorithms, the proposed adaptive algorithm converges at an arbitrarily high polynomial rate.

Original language	English (US)
Pages (from-to)	17-37
Number of pages	21
Journal	Journal of Complexity
Volume	39
DOIs	https://doi.org/10.1016/j.jco.2016.11.002
State	Published - Apr 1 2017

All Science Journal Classification (ASJC) codes

Algebra and Number Theory
Statistics and Probability
Numerical Analysis
Mathematics(all)
Control and Optimization
Applied Mathematics

Keywords

Adaptive algorithm
Brownian motion
Global optimization
Pathwise approximation

Access to Document

10.1016/j.jco.2016.11.002

Cite this

@article{e673e5fcbe53435293cb535ac4e3bb33,

title = "Adaptive approximation of the minimum of Brownian motion",

abstract = "We study the error in approximating the minimum of a Brownian motion on the unit interval based on finitely many point evaluations. We construct an algorithm that adaptively chooses the points at which to evaluate the Brownian path. In contrast to the 1/2 convergence rate of optimal nonadaptive algorithms, the proposed adaptive algorithm converges at an arbitrarily high polynomial rate.",

keywords = "Adaptive algorithm, Brownian motion, Global optimization, Pathwise approximation",

author = "Calvin, {James M.} and Mario Hefter and Andr{\'e} Herzwurm",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier Inc.",

year = "2017",

month = apr,

day = "1",

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

language = "English (US)",

volume = "39",

pages = "17--37",

journal = "Journal of Complexity",

issn = "0885-064X",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Adaptive approximation of the minimum of Brownian motion

AU - Calvin, James M.

AU - Hefter, Mario

AU - Herzwurm, André

PY - 2017/4/1

Y1 - 2017/4/1

N2 - We study the error in approximating the minimum of a Brownian motion on the unit interval based on finitely many point evaluations. We construct an algorithm that adaptively chooses the points at which to evaluate the Brownian path. In contrast to the 1/2 convergence rate of optimal nonadaptive algorithms, the proposed adaptive algorithm converges at an arbitrarily high polynomial rate.

AB - We study the error in approximating the minimum of a Brownian motion on the unit interval based on finitely many point evaluations. We construct an algorithm that adaptively chooses the points at which to evaluate the Brownian path. In contrast to the 1/2 convergence rate of optimal nonadaptive algorithms, the proposed adaptive algorithm converges at an arbitrarily high polynomial rate.

KW - Adaptive algorithm

KW - Brownian motion

KW - Global optimization

KW - Pathwise approximation

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

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

U2 - 10.1016/j.jco.2016.11.002

DO - 10.1016/j.jco.2016.11.002

M3 - Article

AN - SCOPUS:85007549058

SN - 0885-064X

VL - 39

SP - 17

EP - 37

JO - Journal of Complexity

JF - Journal of Complexity

ER -

Adaptive approximation of the minimum of Brownian motion

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this