A Derivative-Free Algorithm for Linearly Constrained Optimization Problems

Abstract

Derivative-free optimization is an active area of research, because there are many practical problems for which the derivatives are not available, and it may still be desirable to carry out optimization. The main motivation for the study of such problems is the high demand for the solution for such problems. In this thesis a new derivative-free algorithm has been developed, named LCOBYQA. The main aim of this algorithm is to nd a minimum x? 2 Rn of a nonlinear objective subject to linearly inequality constraints. The algorithm is based on the trust region method, and uses well known techniques such as the active set version of truncated conjugate gradient method, multivariate Lagrange polynomial interpolation, and QR factorization. Each iteration of the algorithm constructs a quadratic approximation (model) of the objective function that satis es interpolation conditions and leaves some freedom in the model, taken up by minimizing the Frobenius norm of the change of the second derivative of the model. A typical iteration of the algorithm generates a new vector of variables either by minimizing the quadratic model subject to the given constraints and the trust region bound, or by a procedure that should improve the accuracy of the model. Numerical results show that LCOBYQA works well and is so competing against available model-based derivative-free algorithms, such as CONDOR, COBYLA, UOBYQA, NEWUOA and DFO. Under certain conditions LCOBYQA is observed to work extremmely and amazingly fast, leaving an open further investigation to be considered.