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

✍ Scribed by James M. Calvin

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 258 KB
• Volume: 17
• Category: Article
• ISSN: 0885-064X
• DOI: 10.1006/jcom.2001.0574

✦ Synopsis

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.