DERIVATIVE FREE OPTIMIZATION (DFO) –
OPTIMISATION SANS GRADIENT
Master Course, Mauritius, January 2018
Laurent Dumas (Versailles University, France)
Muhammad Zaid Dauhoo (University of
Mauritius)
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.
Outline
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
Exercice sessions:
Session 1 : A RECALL ON DESCENT METHODS (in
french), english version,
PLUS correction (partial, in
french)
Session 2 : DFO : STOCHASTIC METHODS (in
french), english version PLUS
correction : DE.sci,
tournoi.sci
Session 3 : DFO : DIRECT AND
TRUST REGION METHODS
Scilab
scripts:
Descent methods (1st or 2nd order,
two linesearch strategies): descente.sci
Simulated Annealing: SA-rastrigin.sci,
LJ problem with SA
Genetic algorithm, real version (GA-rosenbrock.sci and GA-rastrigin.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)
Bibliography :
- 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.