Virginia Torczon and Michael Trosset
Optimization problems that arise in engineering design are often characterized by several features that hinder the use of standard nonlinear optimization techniques. Foremost among these features is that the functions used to define the engineering optimization problem usually require the solution of differential equations, a process which is itself computationally intensive. Within a standard nonlinear optimization algorithm, the solution of these differential equations is required for each iteration of the algorithm. To mitigate such expense, an attractive alternative is to replace the computationally intensive objective with a less expensive surrogate.
In conformance with engineering practice, we draw a crucial distinction between surrogate models and surrogate approximations. Surrogate models are auxiliary simulations that are less physically faithful, but also less computationally expensive, than the expensive simulation that is regarded as ``truth.'' An instructive example is the use of an equivalent-plate analysis method in lieu of a finite element analysis, e.g. to analyze a wing-box of a high-speed civil transport. Surrogate models exist independently of the expensive simulation and can provide new information about the physical phenomenon of interest without requiring additional runs of the expensive simulation.
Surrogate approximations are algebraic summaries obtained from previous runs of the expensive simulation. Examples include the low-order polynomials favored in response surface methodology (RSM) and the kriging estimates employed in the design and analysis of computer experiments (DACE). Once the approximation has been constructed, it is typically inexpensive to evaluate.
When surrogates are available, be they models or approximations, the optimizer hopes to use them to facilitate the search for a solution to the engineering optimization problem. Our ultimate goal is to design robust optimization algorithms, but we would like to do so in ways that allow us to make effective use of the information that good surrogates can provide. Toward this end, we adopt the perspective that the surrogate can be used to accelerate the optimization technique by exploiting the trends that such surrogates tend to identify. We do not worry about accuracy in the surrogate until it becomes clear either that the optimization technique is in the neighborhood of a minimizer or that the surrogate is not doing a sufficiently good job of identifying trends in the objective.
We consider a methodology that constructs a sequence of approximations to the objective. We concentrate on approaches such as DACE, that krige known values of the objective, but our general strategy is also amenable to other classes of approximations. We make use of pattern search techniques to handle the optimization, though other approaches are possible. We choose pattern search techniques because they can be easily amended to exploit surrogates, can handle functions that are nondifferentiable or for which derivatives are difficult or too expensive to attain, and can be easily adapted to either a parallel or distributed computing environment. Pattern search methods also are less likely to be trapped by non-global minimizers than are traditional nonlinear optimization algorithms. Furthermore, recent analysis extends their applicability to optimization problems with general nonlinear constraints.
Our approach synthesizes recent ideas from both the numerical optimization and the computer experiments literature. Given a limited budget of expensive function evaluations that are to be used to solve an engineering optimization problem, we consider how to manage the trade-off between the expense of approximation and the expense of optimization. We believe that one should invest only a modest proportion of the original budget in constructing the initial approximation and that one should use the optimization procedure to help decide when and where further sampling should occur.
An obvious concern is the relation between the upper bound on the number of expensive function evaluations allowed, which we will call V, and the dimension n of the problem to be solved. When V is large relative to n, say n = 10 and V = 5000, then the expense of function evaluation is not necessarily an issue and we are content to rely on traditional optimization techniques. When V is not large relative to n, say n = 10 and V = 20, then the emphasis must be on trying to construct a simple approximation from what little information one has about the objective--there can be no hope of successfully applying an iterative optimization technique to the problem. (If V is less than n, then the methodologies we consider are inappropriate.) We are concerned with intermediate situations.
Our experience shows that managing approximations, which should be updated as optimization progresses, engenders a somewhat different set of issues than managing models, each of which remains static as optimization progresses. Earlier related work did not envisions the sequential updating of a surrogate approximation, yet this sequential updating has proved to be the defining characteristic of much of our current research. We now understand that the sequential updating of surrogate approximations may create difficulties that are not encountered when either conventional optimization or the construction of the approximation are employed separately. Furthermore, the introduction of general constraints (as opposed to the special case of bound constraints), complicates not only the optimization, but also the construction of approximations.
We will conclude by discussing some of the issues that remain to be addressed. Currently, we advocate the introduction of merit functions that explicitly recognize the desirability of improving the current approximation to the expensive simulation. We also include suggestions for addressing the ill-conditioning that plagues kriging approximations constructed from sequential designs generated by optimization algorithms. In addition, we propose methods for obtaining space-filling designs for nonrectangular regions and propose pattern search algorithms for such regions. Ultimately, we wish to develop techniques for handling problems in which the constraints are implicitly defined by expensive simulations, but our investigation to date has focussed on problems for which the constraints are defined by algebraic expressions.
Up:
Title Page: