Algorithms and Complexity for Global Optimization

New Jersey Institute Of Technology, Newark NJ

Investigators

Abstract

This grant provides funding for the development of numerical algorithms for approximating the global optimum of performance measures that can have many local optima. The approach is based on modeling the unknown performance measure as a random function, and then developing deterministic algorithms that minimize the average approximation error. The research will comprise two main components. The first component will be to construct algorithms for different types of available information and different classes of objective functions, including continuous functions with various orders of differentiability. The types of information will include: exact function evaluations, derivative evaluations, and function evaluations corrupted by random noise. The second part of the research will be to determine complexity bounds. For a given problem setting, for example continuous functions with exact function evaluations, the investigator will establish bounds on the smallest average error that can be attained with any algorithm. If successful, the algorithms developed in this project will be useful for two main types of problems. The first application is to the optimization of complex systems with continuous parameters where the system performance can be evaluated exactly and assumptions such as unimodality or convexity of the performance measure are not warranted. Such problems include optimizing groundwater contamination treatment plans and molecular geometry optimization. The second class of problems is the optimization of systems where the performance can only be observed corrupted by random noise. Such situations arise, for example, when the performance of the system being studied can only be estimated using a stochastic discrete-event simulation. In both cases the complexity bounds will indicate if a problem is tractable and provide guidance on how near to optimal a given algorithm is.