Black-Box Optimization Via Global Optimization of Surrogate Models

In many practical scientific applications, there is a need to find optimal parameters without knowledge of the underlying functional form of what we are optimizing. Such problems, known as black-box optimization problems, commonly occur when there is an attempt to optimize over a simulation or to perform optimal experimental design. Though traditional derivative-free approaches such as genetic algorithms and Nelder-Mead simplex algorithms have been used for a long time, only in the last decade have there been attempts to systematically address such problems through mathematical programming ideas with an intent to ensure convergence and to solve larger problems. Comprehensive reviews of current methods to solve such problems are found in [1,2].

The specific problem we address is the minimization of a smooth, continuous, unconstrained objective function which is expensive to evaluate and has no inherent noise. Our aim then becomes to improve the quality of our solution with the least number of function evaluations. Toward this end, we first sample the function in a certain region at a relatively few number of points. Then, we build a surrogate model to uniquely interpolate the function at these points. Derivative-based approaches can now be used to minimize this surrogate model. To find progressively better points that approach a local minimum, this entire step is embedded in an iterative trust-region framework in which the algorithm terminates on the satisfaction of specific criteria.

Most trust-region algorithms solve the subproblem by finding a point that gives a sufficient decrease in the value of the objective. The novelty of our approach is that it takes advantage of the fact that our surrogate models are capable of capturing non-convexities of the the underlying objective function. As function evaluations are expensive, globally minimizing this surrogate model using deterministic global optimization techniques is considerably less expensive. We demonstrate that finding global minima of surrogates reduces the number of iterations of the overall algorithm to converge to a stationary point.

The algorithm is first applied to standard test problems from literature and compared against existing algorithms as proof-of-concept. We then consider problems of practical interest from the chemical engineering literature. We follow this with a discussion of the successes and the limitations of our approach.

[1] A. R. Conn, K. Scheinberg, and L. N. Vicente, Introduction to derivative-free optimization, MPS-SIAM Series on Optimization, SIAM, Philadelphia, 2009.

[2] L. M. Rios and N. V. Sahinidis,  Derivative-free optimization: A review of algorithms and comparison of software implementations, http://thales.cheme.cmu.edu/dfo/, 2011.