SQPDFO - a Trust-Region Based Algorithm for Generally-Constrained Derivative-Free Optimization

Abstract

Derivative-free optimization is a specific branch of mathematical optimization where first and higher order derivatives of the objective function of the optimization problem are not available, too expensive to compute or too inexact to be used. Such problems do arise in many application areas, e.g. in engineering design optimization, wastewater treatment and quantum chemical processes. As only function value information and no derivative information is available, SQPDFO applies different sampling techniques to build local interpolation models of the objective and constraint functions and uses a self-correcting error technique (Scheinberg and Toint) which guarantees the quality of these models and their derivatives during the optimization process. Throughout the optimization process, first and second order derivatives of these models are used. SQPDFO can handle nonlinear and linear equality and inequality constraints and simple bounds on the variables. It is based on the SQP (Sequential Quadratic Programming) method which solves a sequence of optimization subproblems, each of which optimizes a quadratic program of the original optimization problem. Inequality constraints are carefully handled by slack variables which are not included in the local models to not unnecessarily increase the size of the interpolation matrix. We will present numerical results on a large set of academic test problems from the well-known optimization library CUTEst showing the good performance of the implementation of SQPDFO. Furthermore, we extended the code to run in parallel and several function evaluations can be used in each iteration. This was especially useful when applying SQPDFO to a multidisciplinary DLR research shape design problem of an entire airplane. As one complete function evaluation of the top-level optimization problem can take up to 56 hours, a code which needs a minimum number of iterations is crucial. We will show how SQPDFO is able to find good solutions within a very small number of iterations.