Department of Mathematics,
Arizona State University
Thursday, February 4, 1999, 12:15 p.m. in GWC Room 510
A rigorous Framework for Optimization using Surrogates
Abstract
Methods that use computer simulations in engineering decision-making are growing in importance.
However, there still are many important problems for which existing methods are either
impractical or ad hoc. This work is part of a collaboration involving Rice, SANDIA Labs,
IBM Research, and Boeing Applied Research and Technology
to develop sound and effective techniques that combine
simulation and optimization to solve practical engineering problems.
We will consider here only bound constrained nonlinear optimization problems.
Of course they are wildly nonconvex, and some other key properties of our target problems are:
i) There are less than 100 decision variables.
ii) It is impractical to accurately approximate derivatives of the objective f.
iii) The routines that evaluate f(x) may fail for some feasible x at the same cost as when
they are successful.
iv) Each decision variable has a range of legal values, and values
outside that range can make the simulator fail.
v) The computation of f(x) is very expensive and the values obtained may have few correct
digits.
Although the number of decision variables is small, the total number of variables in the
problem usually is large. Typically, f(x) is expensive to evaluate because there are large
numbers of ancillary or system variables that must be determined for each choice of x before
f(x) can be evaluated. We will discuss an example in which x specifies a coupled set of
partial differential equations (PDEs) that must be solved in order to obtain dependent
system variables that are then used to evaluate f(x). The coupling of PDEs via some
iterative method, most often the notoriously unreliable successive substitution approach,
explains the third of our assumptions, since the method may run for many iterations and not
converge.
The second and third of our intrinsic assumptions make quasi-Newton methods difficult to
apply. Choosing a finite-difference step size to approximate derivatives is a difficult
and crucial part of getting a finite-difference quasi-Newton method to work. This difficulty
is compounded by the fact that we may not be able to compute the objective function value at
the step size selected.
The solution methods we analyze and test use inexpensive-to-evaluate approximations of expensive
analysis codes as surrogates or proxies in the optimization procedure. We will give
some computational results from a standard global optimization test problem and from a
low vibration Boeing helicopter rotor blade design problem which indicate
that the approximations do not need to be accurate to be effective surrogates.
The convergence analysis is independent of the accuracy of the approximations.
This is joint work with D. Moore.
For further information please contact:
mittelmann@asu.edu