Derivative-Free Optimization Algorithms For Computationally Expensive Functions

Abstract

This thesis concerns the development and analysis of derivative-free optimization algorithms for simulation-based functions that are computationally expensive to evaluate.

The first contribution is the introduction of data profiles as a tool for analyzing the performance of derivative-free optimization solvers when constrained by a computational budget. Using these profiles, together with a convergence test that measures the decrease in function value, we find that on three different sets of test problems, a model-based solver performs better than the two direct search solvers tested.

The next contribution is a new model-based derivative-free algorithm, ORBIT, for unconstrained local optimization. A trust-region framework using interpolating Radial Basis Function (RBF) models is employed. RBF models allow ORBIT to interpolate nonlinear functions using fewer function evaluations than many of the polynomial models considered by present techniques. We provide an analysis of the approximation guarantees obtained by interpolating the function at a set of sufficiently affinely independent points. We detail necessary and sufficient conditions that an RBF model must obey to fit within our framework and prove that this framework allows for convergence to first-order critical points. We present numerical results on test problems as well as three application problems from environmental engineering to support ORBIT's effectiveness when relatively few function evaluations are available. The framework used by ORBIT is also extended to include other models, in particular undetermined interpolating quadratics. These quadratics are flexible in their ability to interpolate at dynamic numbers of previously evaluated points.

The third contribution is a new multistart global optimization algorithm, GORBIT, that takes advantage of the expensive function evaluations done in the course of both the global exploration and local refinement phases. We modify ORBIT to handle both bound constraints and external functional evaluations and use it as the local solver. For the global exploration phase, a new procedure for making maximum use of the information from previous evaluations, MIPE, is introduced. Numerical tests motivating our approach are presented and we illustrate using GORBIT on the problem of finding error-prone systems for Gaussian elimination.