Abstract
This paper is a study of the complexity of optimization of continuous univariate functions using a fixed number of sequentially selected function evaluations. The complexity is studied in the average case under a conditioned Wiener measure. We show that to obtain an error of at most ε{lunate}, on the order of log log (1 / ε{lunate}) log (1 / ε{lunate}) function evaluations are required.
Original language | English (US) |
---|---|
Pages (from-to) | 132-139 |
Number of pages | 8 |
Journal | Theoretical Computer Science |
Volume | 383 |
Issue number | 2-3 |
DOIs | |
State | Published - Sep 18 2007 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)
Keywords
- Average-case complexity
- Global optimization
- Wiener measure