Derivative-free bound-constrained optimization for solving structured problems with surrogate models

Abstract

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.

Keywords:

• Derivative-free optimization
• trust-region methods
• least squares

AMS Subject Classifications:

• 49M15
• 65K05
• 65K10
• 90C30
• 90C56

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

Frank E. Curtis was supported in part by National Science Foundation Grant [NSF CCF-2008484], and Shima Dezfulian and Andreas Wächter were suppored in part by Department of Energy Grant [ARPA-E DE-AR0001073] and National Science Foundation Grant [NSF DMS-2012410].

Notes on contributors

Frank E. Curtis

Frank E. Curtis, Professor in the Department of Industrial and Systems Engineering at Lehigh University, conducts research on the design and analysis of algorithms for solving continuous optimization problems. He is a recipient of the Lagrange Prize in Continuous Optimization, jointly awarded by SIAM and the Mathematical Optimization Society, and is a recipient of the INFORMS Computing Society Prize.

Shima Dezfulian

Shima Dezfulian is a Ph.D. student in the Department of Industrial Engineering and Management Sciences at Northwestern University. Her research interests include numerical optimization and machine learning.

Andreas Wächter

Andreas Wächter is a professor in the Department of Industrial Engineering and Management Sciences at Northwestern University. His research is in the design, analysis, and application of numerical optimization algorithms. He is a SIAM Fellow, and was awarded the 2011 Wilkinson Prize for Numerical Software and the 2009 INFORMS Computing Society Prize for his work on the open-source optimization package Ipopt.