DERIVATIVE FREE OPTIMIZATION (DFO) – OPTIMISATION SANS GRADIENT
Master Course, Mauritius, January 2018
Laurent Dumas (Versailles University, France)
Muhammad Zaid Dauhoo (University of
Optimization problems are encountered in many fields of engineering for which the associated cost function may be of various type : black box or explicit, with continuous or discrete variables, costly or not to compute, etc…
In many cases, the gradient of the cost function is not easy or even impossible to compute or it can exhibit many local minima leading to consider Derivative Free Optimization (DFO) methods.
After a recall on descent methods, this course deals with a large number of Derivative Free Optimization methods that have been recently developped, either local or global, deterministic or stochastic. It will be illustrated by various examples issued from industrial or medical fields.
Day 1 (5h) A RECALL ON DESCENT METHODS
Introdution, motivation (slides.pdf)
Recall on optimality conditions, with or without constraints
Descent methods (1st and 2nd order)
Day 2 (5h) DFO : STOCHASTIC METHODS (slides.pdf)
Simulated Annealing, Genetic Algorithm, Evolution Strategy, Particle Swarm Optimization
Day 3 : (5h) DFO : DIRECT AND TRUST REGION METHODS
Direct methods : Pattern Search, Nelder Mead
Trust region methods
Session 3 : DFO : DIRECT AND TRUST REGION METHODS
Descent methods (1st or 2nd order, two linesearch strategies): descente.sci
Evolution strategy: ES-rastrigin.sci
Particle Swarm Optimization: PSO-rastrigin.sci
Nelder Nead : NelderMead.sci
Trust region method (including the Lagrange interpolation in 2D) : Trust.zip (in Matlab)
- N. Gould, S. Leyffer, An introdution to algorithms for non linear optimization, online.
- Lecture notes (in french) Max Cerf (notes de cours)
- A presentation of Simulated Annealing: Interstices
- Description de la méthode CMAES : cmaesintro
- A review article on DFO : Journal Global Opt. 2013
- An article on the non convergence of Nelder Mead : SIAM J. Opt.1998
- A list of optimization test functions : http://www.sfu.ca/~ssurjano/optimization.html
- The PhD thesis of Benoit Pauwels on DFO (2016)
- A reference book on DFO : A. Conn, K. Scheinberg and L. Vincente, Introduction to Derivative Free Optimization, SIAM, 2009.