Adaptive approximation of the minimum of Brownian motion

DOI10.1016/J.JCO.2016.11.002MaRDI QIDQ511112zbMATH OpenOpenAlexFDO

Authors James M. Calvin, Mario Hefter, André Herzwurm

Publication date 14 February 2017

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.01276

zbMATH Keywords

global optimizationBrownian motionadaptive algorithmpathwise approximation

Mathematics Subject Classification ID

Brownian motion (60J65)

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.

Recommendations

• scientific article; zbMATH DE number 953012
• A one-dimensional optimization algorithm and its convergence rate under the Wiener measure
• On the minimum of a conditioned Brownian bridge
• An adaptive univariate global optimization algorithm and its convergence rate under the Wiener measure
• Optimal random non-adaptive algorithm for global optimization of Brownian motion

Cites work

• scientific article; zbMATH DE number 1817636 (Why is no real title available?)
• scientific article; zbMATH DE number 4078444 (Why is no real title available?)
• scientific article; zbMATH DE number 51724 (Why is no real title available?)
• scientific article; zbMATH DE number 193625 (Why is no real title available?)
• scientific article; zbMATH DE number 1245556 (Why is no real title available?)
• scientific article; zbMATH DE number 782652 (Why is no real title available?)
• A lower bound on complexity of optimization on the Wiener space
• A one-dimensional optimization algorithm and its convergence rate under the Wiener measure
• A versatile stochastic model of a function of unknown and time varying form
• An adaptive univariate global optimization algorithm and its convergence rate under the Wiener measure
• Approximation and optimization on the Wiener space
• Average performance of a class of adaptive algorithms for global optimization
• Average-Case Optimality of a Hybrid Secant-Bisection Method
• Average-case analysis of numerical problems
• Axiomatic characterization of a global optimization algorithm and investigation of its search strategy
• Decomposing the Brownian path
• Deterministic and stochastic error bounds in numerical analysis
• Discretization error in simulation of one-dimensional reflecting Brownian motion
• Global optimization
• Investigation of examples of e-education environment for scientific collaboration and distance graduate studies. II.
• The SDE solved by local times of a Brownian excursion or bridge derived from the height profile of a random tree or forest
• The joint density of the maximum and its location for a Wiener process with drift

Cited in

(6)

• Lower error bounds for strong approximation of scalar SDEs with non-Lipschitzian coefficients
• On efficiency of a single variable bi-objective optimization algorithm
• Adaptive quantile computation for Brownian bridge in change-point analysis
• On the expected uniform error of Brownian motion approximated by the Lévy-Ciesielski construction
• On the minimum of a conditioned Brownian bridge
• Strong convergence rates for Cox-Ingersoll-Ross processes -- full parameter range

This page was built for publication: Adaptive approximation of the minimum of Brownian motion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q511112)