Adaptive approximation of the minimum of Brownian motion

DOI10.1016/J.JCO.2016.11.002zbMATH Open1358.65012arXiv1601.01276OpenAlexW2962694399MaRDI QIDQ511112FDOQ511112

Mario Hefter, James M. Calvin, André Herzwurm

Publication date: 14 February 2017

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

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.

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)

Cites Work

• The joint density of the maximum and its location for a Wiener process with drift
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Discretization error in simulation of one-dimensional reflecting Brownian motion
• Title not available (Why is that?)
• Deterministic and stochastic error bounds in numerical analysis
• Average-case analysis of numerical problems
• Title not available (Why is that?)
• A versatile stochastic model of a function of unknown and time varying form
• Global optimization
• Title not available (Why is that?)
• The SDE solved by local times of a Brownian excursion or bridge derived from the height profile of a random tree or forest
• Approximation and optimization on the Wiener space
• Decomposing the Brownian path
• A lower bound on complexity of optimization on the Wiener space
• Axiomatic characterization of a global optimization algorithm and investigation of its search strategy
• Average performance of a class of adaptive algorithms for global optimization
• Average-Case Optimality of a Hybrid Secant-Bisection Method
• Title not available (Why is that?)
• Title not available (Why is that?)
• A one-dimensional optimization algorithm and its convergence rate under the Wiener measure

Cited In (4)

• On efficiency of a single variable bi-objective optimization algorithm
• Strong convergence rates for Cox-Ingersoll-Ross processes -- full parameter range
• Adaptive quantile computation for Brownian bridge in change-point analysis
• Lower error bounds for strong approximation of scalar SDEs with non-Lipschitzian coefficients

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)