On average complexity of global optimization problems

On average complexity of global optimization problems

0.00 Avg rating0 Votes
Article ID: iaor19931512
Country: Netherlands
Volume: 57
Issue: 2
Start Page Number: 313
End Page Number: 324
Publication Date: Nov 1992
Journal: Mathematical Programming
Authors:
Keywords: computational analysis, programming: nonlinear
Abstract:

The average case complexity of global optimization problems is discussed. The average complexity roughly means 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. It is stressed 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, it is not known how much easier global optimization becomes when the average case approach is utilized.

Reviews

Required fields are marked *. Your email address will not be published.