Derivative Free Optimization / Optimisation sans Gradient

 

 (V04 course, season 2021/2022)

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, course 2017/2018, course 2018/2019, course 2019/2020, course 2020/2021


 Outline

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



-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 : 

 

Friday 26th november 2021, 13h30-16h45 (ENSTA, A. Auger) DFO/STO/

Friday 3th décember 2021, 13h30-16h45 (ENSTA, A. Auger) DFO/STO/

Friday 10th décember2021, 13h30-16h45 (ENSTA, A. Auger) DFO/STO/

Friday 17th december 2021, 13h30-16h45 (ENSTA, A. Auger) DFO/STO/

Friday 7th january 2020, 13h30-16h45 (ENSTA, A. Auger) : DFO/STO/

Friday 14th january 2022, 14h00-17h15 (ENSTA, L. Dumas) : DFO/DET/ 

Friday  21th january 2022, 13h30-16h45 (ENSTA, L. Dumas) : DFO/DET/

Friday   28th january 2022, 13h30-16h45 (ENSTA, L. Dumas) : DFO/DET/

Friday 4th february 2022, 13h30-16h45 (ENSTA, L. Dumas): DFO/DET/:

Friday 11th february 2022, 13h30-16h45 (ENSTA, L. Dumas): DFO/DET/


 Exercices : 

A list of exercices

 Bibliography : 

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

A review article on DFO : Journal of Global Optimization 2013

On direct search methods :

  1. The PhD thesis of Benoit Pauwels on DFO (2016) 

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

  3. An article on the convergence  of MDS:  PhD1989

  4. Convergence results for direct search methods (three references)

On trust region methods :

  1. An article on the convergence of Trust Region methods : SIAM Journal of Optimization, 2010

On global methods :

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

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

  3. A review article on response surface methods (RBF and kriging)

Other references :

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