On average complexity of global optimization problems

G. W. Wasilkowski

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


We discuss the average case complexity of global optimization problems. By the average complexity, we roughly mean the amount of work needed to solve the problem with the expected error not exceeding a preassigned error demand. The expectation is taken with respect to a probability measure on a class F of objective functions. Since the distribution of the maximum, maxxf(x), is known only for a few nontrivial probability measures, the average case complexity of optimization is still unknown. Although only preliminary results are available, they indicate that on the average, optimization is not as hard as in the worst case setting. In particular, there are instances, where global optimization is intractable in the worst case, whereas it is tractable on the average. We stress, that the power of the average case approach is proven by exhibiting upper bounds on the average complexity, since the actual complexity is not known even for relatively simple instances of global optimization problems. Thus, we do not know how much easier global optimization becomes when the average case approach is utilized.

Original languageEnglish
Pages (from-to)313-324
Number of pages12
JournalMathematical Programming
Issue number1-3
StatePublished - May 1992

ASJC Scopus subject areas

  • Software
  • Mathematics (all)


Dive into the research topics of 'On average complexity of global optimization problems'. Together they form a unique fingerprint.

Cite this