TY - JOUR

T1 - On average complexity of global optimization problems

AU - Wasilkowski, G. W.

PY - 1992/5

Y1 - 1992/5

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=34249830589&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34249830589&partnerID=8YFLogxK

U2 - 10.1007/BF01581086

DO - 10.1007/BF01581086

M3 - Article

AN - SCOPUS:34249830589

SN - 0025-5610

VL - 57

SP - 313

EP - 324

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1-3

ER -