Lower bound on complexity of optimization of continuous functions

DOI10.1016/j.jco.2003.06.004zbMath1109.90082OpenAlexW2039467763MaRDI QIDQ1888381

James M. Calvin

Publication date: 23 November 2004

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

Full work available at URL: https://doi.org/10.1016/j.jco.2003.06.004

zbMATH Keywords

Wiener measureGlobal optimizationAverage case complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Brownian motion (60J65)

Related Items (5)

A lower bound on complexity of optimization on the Wiener space ⋮ On the minimum of a conditioned Brownian bridge ⋮ Optimal algorithms for global optimization in case of unknown Lipschitz constant ⋮ Adaptive quantile computation for Brownian bridge in change-point analysis ⋮ One-dimensional global optimization for observations with noise

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deterministic and stochastic error bounds in numerical analysis
• Average-case analysis of numerical problems
• Discretization error in simulation of one-dimensional reflecting Brownian motion
• Approximation and optimization on the Wiener space
• Path Decomposition and Continuity of Local Time for One-Dimensional Diffusions, I
• The joint density of the maximum and its location for a Wiener process with drift
• Average-Case Optimality of a Hybrid Secant-Bisection Method
• Sequential Minimax Search for a Maximum
• INEQUALITIES FOR THE NORMAL INTEGRAL INCLUDING A NEW CONTINUED FRACTION
• A one-dimensional optimization algorithm and its convergence rate under the Wiener measure

This page was built for publication: Lower bound on complexity of optimization of continuous functions