| Fueled by a growing number of applications in science and engineering, the development of derivative-free optimization algorithms has long been studied and found renewed interest. The problem addressed is the optimization of a deterministic function f : Rn→ R over a domain of interest that possibly includes constraints g(x) ≤ 0, with g : Rn→ Rm . We assume that the derivatives of f and g are neither symbolically available nor numerically computable, and that bounds, such as Lipschitz constants, for the derivatives of f and g are also unavailable.;In this thesis, we begin by presenting a comprehensive list of available methods and software and performing an extensive computational study that compares the solvers over a publicly available problem set. Then, we develop Model and Search (M&S), a new local search algorithm for derivative-free optimization. M&S performs a local search from a given point. The search is guided by identifying descent directions from a quadratic model fitted around the best known point, while using information from other evaluated points. We prove that M&S enjoys global convergence to a stationary point. We also propose a new global search algorithm for derivative-free optimization problems, in particular the Branch and Model (B&M) algorithm that is based on modeling the function of interest around each evaluated point by using information from other nearby evaluated points. Algorithm B&M is shown to perform a dense search and thus converge to a global minimum. While oriented towards a global search, B&M relies on the M&S algorithm for occasional local searches. Finally, we present an application of derivative-free solvers, including B&M, to the protein-ligand docking problem. Results show that B&M delivers satisfactory ligand conformations, even outperforming the state-of-the-art protein docking software AutoDock. |
