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 2^nd 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.