390036 UK VGSCO Derivate-Free Optimization: Basic Principles and State of the Art (2017W)

This course deals with the numerical solution of Optimization problems involving functions for which derivatives are unavailable, available at a prohibitive cost, or subject to noise --- as may be the case when function evaluations result from computing simulation or laboratorial observation.

In the field of Derivative-Free Optimization (DFO) one studies the development, analysis, and implementation of algorithms for such type of problems. A successful application of such algorithms requires them to be efficient (in the sense of taking a moderate number of function evaluations) and rigorous (meaning not too far from an algorithmic structure for which one can prove something meaningful under reasonable assumptions).

In this course we will describe the building blocks over which DFO algorithms are based and pass the intuition that helps understanding why are they globally convergent (meaning convergent to stationarity independently of the starting point). In some cases it is possible to develop worst case complexity bounds in terms of the number of iterations or function evaluations to reach some level of stationarity. Such global rates complement existing analyses of global convergence by providing additional insight and comparisons.

We will essentially focus on two well-known classes of methods, direct-search methods and model-based (trust-region type) algorithms. While the former are typically less efficient, they are better tailored to non-smooth and constrained settings due to their directional nature.

We will however try to bridge over other methodologies (like convex and sparse optimization, surrogate modeling, evolutionary optimization, multi-objective optimization, global optimization), as time permits, but always from the point of view of DFO.