Model-based derivative-free optimization methods and software

Abstract

This thesis studies derivative-free optimization (DFO), particularly model-based methods and software. These methods are motivated by optimization problems for which it is impossible or prohibitively expensive to access the first-order information of the objective function and possibly the constraint functions. Such problems frequently arise in engineering and industrial applications, and keep emerging due to recent advances in data science and machine learning. We first provide an overview of DFO and interpolation models for DFO methods. In addition, we show that an interpolation set employed by Powell for underdetermined quadratic interpolation is optimal in terms of well-poisedness. We then present PDFO, a package that we develop to provide both MATLAB and Python interfaces to Powell's model-based DFO solvers, namely COBYLA, UOBYQA, NEWUOA, BOBYQA, and LINCOA. They were implemented by Powell in Fortran 77, and hence, are becoming inaccessible to many users nowadays. PDFO provides user-friendly interfaces to these solvers, so that users do not need to deal with the Fortran code. In addition, it patches bugs in the original Fortran implementation. We also share some observations about the behavior of Powell's solvers. A major part of this thesis is devoted to the development of a new DFO method based on the sequential quadratic programming (SQP) method. Therefore, we first present an overview of the SQP method and provide some perspectives on its theory and practice. In particular, we show that the objective function of the SQP subproblem is a natural quadratic approximation of the original objective function in the tangent space of a surface. Moreover, we propose an extension of the Byrd-Omojokun approach for solving trust-region SQP subproblems with inequality constraints. This extension works quite well in our experiments. Finally, we elaborate on the development of our new DFO method, named COBYQA after Constrained Optimization BY Quadratic Approximations. This derivative-free trust-region SQP method is designed to tackle nonlinearly constrained optimization problems that admit equality and inequality constraints. An important feature of COBYQA is that it always respects bound constraints, if any, which is motivated by applications where the objective function is undefined when bounds are violated. COBYQA builds quadratic trust-region models based on the derivative-free symmetric Broyden update proposed by Powell. We provide a detailed description of COBYQA, including its subproblem solvers, and introduce its Python implementation. We expose extensive numerical experiments of COBYQA, showing evident advantages of COBYQA compared with Powell's DFO solvers. These experiments demonstrate that COBYQA is an excellent successor to COBYLA as a general-purpose DFO solver.