Derivative Free
Optimization / Optimisation sans Gradient
(V04 course, season 2016/2017)
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
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 : response
surface methods (RBF, kriging)
Schedule :
Vendredi 26 novembre 2016,
14h00-17h15 (ENSTA, A. Auger)
Vendredi 03 décembre 2016,
14h00-17h15 (ENSTA, A. Auger)
Vendredi 10 décembre 2016,
14h00-17h15 (ENSTA, A. Auger)
Vendredi 17 décembre 2016,
14h00-17h15 (ENSTA, A. Auger)
Vendredi 06 janvier 2017, 14h00-17h15
(ENSTA, A. Auger)
Vendredi 13 janvier 2017, 14h00-17h15
(ENSTA, L. Dumas) :
direct methods
Vendredi 20 janvier 2017, 14h00-18h15 (new schedule, room1224 and for computer session 1212 ENSTA, L. Dumas) : trust region methods
Vendredi 27 janvier 2017, 14h00-18h15 (new schedule ENSTA, L. Dumas) : response surface methods (slides in french)
Vendredi 03 février 2017, 14h00-18h15 (new schedule ENSTA, L. Dumas) :
other DFO methods+ exercices
Exam : vendredi 10 février2017,
14h00-17h00 : sujet (+ Matlab
code)
Scilab/ Matlab scripts
(deterministic part) :
Pattern Search : pattern.sci
Nelder Nead : NelderMead.sci
MDS : MDS.sci
Trust region method (including the
Lagrange interpolation in 2D) : Trust.zip (in Matlab)
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
An article on the non convergence of Nelder Mead : SIAM J. Opt.1998
An article on the convergence of MDS: PhD1989
A review article on metamodels RBF and Kriging : INRIA report, 2009
Description of the DIRECT method : DIRECT.pdf (Journal of Optimization theory and application, 1993)