Lower bound on complexity of optimization of continuous functions

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


This paper considers the problem of approximating the minimum of a continuous function using a fixed number of sequentially selected function evaluations. A lower bound on the complexity is established by analyzing the average case for the Brownian bridge.

Original languageEnglish (US)
Pages (from-to)773-795
Number of pages23
JournalJournal of Complexity
Issue number5
StatePublished - Oct 2004
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Statistics and Probability
  • Numerical Analysis
  • General Mathematics
  • Control and Optimization
  • Applied Mathematics


  • Average case complexity
  • Global optimization
  • Wiener measure


Dive into the research topics of 'Lower bound on complexity of optimization of continuous functions'. Together they form a unique fingerprint.

Cite this