Average Complexity of Global Optimization

9500173 Calvin One of the objectives of this research is to compare different algorithms for global optimization problems using an average performance criteria. Several classes of functions are considered, including smooth functions and non-differentiable continuous functions. The set of functions is endowed with a probability measure and the expected performance with respect to the given probability distribution of different algorithms are compared. This average performance can be traded off with the computational requirements of the algorithms. A range of algorithms is considered, from simple ones that choose the observations on a fixed grid of points to complex methods that choose each site to maximize some functional of all previous observations. A second objective of the research is to develop efficient algorithms for global optimization, where efficiency is measured in terms of average performance. The outcome of this research will serve several purposes. First, it will fill a void in global optimization studies. The void is the proliferation of algorithms with no systematic methods of assessing their performance quality. This research will provide a characterization of global optimization algorithms. Second, the knowledge gained from the results of the algorithmic performance quality will help identify areas where additional work is needed. Third, by benchmarking the algorithms, the current state of research advancement in global optimization can be characterized. This characterization is necessary in projecting future research directions in the area. Fourth, the research will also help to validate and invalidate some of the assumptions made in developing global optimization algorithms. Finally, the outcome of the research will provide some insights in choosing the techniques and algorithms to solve problems with certain structures and characteristics. The insights gained can translate into savings in time and resources by researchers from better problem understanding and savings in time and cost due to misapplications of algorithms. .