Derivative Free Optimization / Optimisation sans Gradient

 (V04 course, season 2017/2018)

Common course between M2 AMS et M2 Optimisation (Paris Saclay)

 Anne Auger (INRIA), Laurent Dumas (UVSQ)

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.

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.

 Previous courses :

 cours 2011/2012, cours 2012/2013, cours 2013/2014  cours 2014/2015 course 2015/2016 course 2016/2017

 Outline

-PART 1 : STOCHASTIC METHODS (see page of Anne Auger)

1) General introduction / Motivation for DFO

2) Stochastic algorithms framework (essentially ES)

3) General principles for step size and covariance matrix adaptation. CMA-ES algorithm.

4) Comparisons between CMA/PSO/NEWUOA/BFGS

-PARTIE 2 : DETERMINSTIC METHODS

1) Local methods: direct methods (Pattern Search, Nelder Mead, MDS), trust region methods (NEWUOA)

2) Global methods : DIRECT response surface methods  (RBF, kriging)

 Schedule : 

Vendredi 01 décembre 2017, 14h00-17h15 (ENSTA, A. Auger) 

Vendredi 08 décembre 2017, 14h00-17h15 (ENSTA, A. Auger) 

Vendredi 15 décembre 2017, 14h00-17h15 (ENSTA, A. Auger) 

Vendredi 22 décembre 2017, 14h00-17h15 (ENSTA, A. Auger) 

Vendredi 12 janvier 2018, 14h00-17h15 (ENSTA, A. Auger) 

Vendredi 19 janvier 2018, 14h00-17h15 (ENSTA, L. Dumas) : direct methods

Vendredi 26 janvier 2018, 13h30 17h45 (new schedule ENSTA, L. Dumas) :  direct methods (MDS)

Vendredi  2 février 2018, 13h30 17h45 (new schedule ENSTA, L. Dumas) : Trust region methods

Vendred16 février, 13h30-17h45 (new schedule ENSTA, L. Dumas) : Global methods (DIRECT and RSM)

Exam : vendredi 23 février 2018, 13h30-16h30 , salle 2413 énoncé partie 1, énoncé partie 2

 
 Scilab/ Matlab scripts (deterministic part) : 

Pattern Search : pattern.sci

Nelder Nead : NelderMead.sci

MDS: MDS.sci

A trust region method (with derivatives) : trust_noDFO.sci

A langrange interpolation script : lagrange_DFO.sci

A trust region method (without derivatives) : Trust.zip (in Matlab)

Surrogate models : RBF.sci, krige.sce

 Bibliography (determinsitic part) : 

A. Conn, K. Scheinberg and L. Vincente, Introduction to Derivative Free Optimization, SIAM, 2009.

A review article on DFO : Journal Global Opt. 2013

The PhD thesis of Benoit Pauwels on DFO (2016) 

An article on the non convergence of Nelder Mead : SIAM J. Opt.1998

An article on the convergence  of MDS:  PhD1989

N. Gould, S. Leyffer, An introdution to algorithms for non linear optimization

The slides of Max Cerf ‘Techniques d’optimisation’

The slides (in french) on Response Surface Methods (RBF  and kriging)

Description of the DIRECT method : DIRECT.pdf (Journal of Optimization theory and application, 1993)

A list of optimization test functions : http://www.sfu.ca/~ssurjano/optimization.html