  We propose and analyze a model-based derivative-free (DFO) algorithm for
solving bound-constrained optimization problems where the objective function is
the composition of a smooth function and a vector of black-box functions. We
assume that the black-box functions are smooth and the evaluation of them is
the computational bottleneck of the algorithm. The distinguishing feature of
our algorithm is the use of approximate function values at interpolation points
which can be obtained by an application-specific surrogate model that is cheap
to evaluate. As an example, we consider the situation in which a sequence of
related optimization problems is solved and present a regression-based
approximation scheme that uses function values that were evaluated when solving
prior problem instances. In addition, we propose and analyze a new algorithm
for obtaining interpolation points that handles unrelaxable bound constraints.
Our numerical results show that our algorithm outperforms a state-of-the-art
DFO algorithm for solving a least-squares problem from a chemical engineering
application when a history of black-box function evaluations is available.
