A Sequential Quadratic Programming Algorithm for Equality-Constrained Optimization without Derivatives

Abstract

In this paper, we present a new model-based trust-region derivative-free optimization algorithm which can handle nonlinear equality constraints by applying a sequential quadratic programming (SQP) approach. The SQP methodology is one of the best known and most efficient frameworks to solve equality-constrained optimization problems in gradient-based optimization. Our derivative-free optimization (DFO) algorithm constructs local polynomial interpolation-based models of the objective and constraint functions and computes steps by solving QP sub-problems inside a region using the standard trust-region methodology. As it is crucial for such model-based methods to maintain a good geometry of the set of interpolation points, our algorithm exploits a self-correcting property of the interpolation set geometry. To deal with the trust-region constraint which is intrinsic to the approach of self-correcting geometry, the method of Byrd and Omojokun is applied. Numerical experiments are carried out on a set of test problems from the CUTEr library and on a simulation-based engineering design problem.