A One-Dimensional Optimization Algorithm and Its Convergence Rate under the Wiener Measure

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

In this paper we describe an adaptive algorithm for approximating the global minimum of a continuous function on the unit interval, motivated by viewing the function as a sample path of a Wiener process. It operates by choosing the next observation point to maximize the probability that the objective function has a value at that point lower than an adaptively chosen threshold. The error converges to zero for any continuous function. Under the Wiener measure, the error converges to zero at rate e-nδn, where {δn} (a parameter of the algorithm) is a positive sequence converging to zero at an arbitrarily slow rate.

Original languageEnglish (US)
Pages (from-to)306-344
Number of pages39
JournalJournal of Complexity
Volume17
Issue number2
DOIs
StatePublished - Jun 2001

All Science Journal Classification (ASJC) codes

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

Keywords

  • Wiener measure; global optimization

Fingerprint Dive into the research topics of 'A One-Dimensional Optimization Algorithm and Its Convergence Rate under the Wiener Measure'. Together they form a unique fingerprint.

Cite this