OPTIMISATION ET APPLICATIONS (cours M3, saison 2013/2014)

Université Versailles Saint Quentin en Yvelines

Master M2S

Laurent Dumas (UVSQ), Max Cerf (EADS)

Les problèmes d'optimisation se rencontrent dans de nombreux domaines de l'ingénierie ou de la médecine où les fonctions à optimiser sont de différents types: boîte noire ou explicites, à variables continues ou discrètes, etc.. Dans la plupart des cas, ces fonctions possèdent très souvent un grand nombre de minima locaux imposant de définir de nouvelles stratégies d’optimisation.

Ce cours présente les principales méthodes d'optimisation utilisées dans de telles situations en les classant en deux catégories :

(i) les méthodes sans gradient (méthode de Nelder Mead, méthodes de type régions de confiance, surfaces de réponse, recuit simulé, algorithmes génétiques, essaim de particules)

(ii) les méthodes de type SQP basées à chaque étape sur une approximation quadratique de la fonction à optimiser.

Dans ce cours, l’accent sera mis sur l’implémentation de ces méthodes à travers la réalisation de deux projets informatiques associés aux deux familles précédentes.

Archives : cours 2011/2012, cours 2012/2013

Planning : 

Mardi 15 octobre 2013, 14h00-17h00 (ENSTA, L. Dumas) : introduction et exemples (M3_2013.pdf, SQP.pdf)

Mardi 22 octobre 2013, 14h00-17h00 (maison de la simulation, M. Cerf) : projet lanceur

Mardi 05 novembre 2013, 14h00-17h00 (maison de la simulation, M. Cerf) : projet lanceur (notes de cours)

Mardi 12 novembre 2013, 14h00-17h00 (maison de la simulation, M. Cerf) : projet lanceur

Mardi 19 novembre 2013, 14h00-17h00 (maison de la simulation, L. Dumas) : optimisation sans gradient § 1.1 et 1.2 (NelderMead.sci, MDS.sci)

Mardi 26 novembre 2013, 14h00-17h00 (maison de la simulation, L. Dumas) : optimisation sans gradient § 1.2 à 2.1 (RBF.sci, krige.sce, présentation krige-RBF)

Mardi 03 décembre 2013, 14h00-17h00 (maison de la simulation, M. Cerf) : projet lanceur

Mardi 10 décembre 2013, 14h00-17h00 (maison de la simulation, M. Cerf) : projet lanceur

Mardi 7 janvier 2014, 14h00-17h00 (maison de la simulation, L. Dumas) : optimisation sans gradient § 2.2 (SA.sci, GA-binary.sci, GA-real2012.sci)

Mardi 14 janvier 2014, 14h00-17h00 (maison de la simulation, L. Dumas) : optimisation sans gradient § 2.2 et projet (PSO.sci)

Mardi 21 janvier 2014, 14h00-17h00 (maison de la simulation, L. Dumas) : optimisation sans gradient

Mardi 29 janvier 2014, 14h00-17h00 (maison de la simulation, L. Dumas) : optimisation sans gradient

Vendredi 31 janvier 2014, 14h00-17h00 (Ecole Centrale, M. Cerf) : projet lanceur

Vendredi 7 février 2014, 14h00-17h00 (Ecole Centrale, M. Cerf) : projet lanceur

Mardi 18 février 2014, 14h00-17h00 (M. Cerf et L. Dumas) : soutenance des deux projets

Plan du cours : 

PARTIE 1: Méthodes d’optimisation sans gradient

1. Méthodes locales

1.1 Méthodes locales directes (Nelder Mead, MDS)

1.2 Méthodes de type régions de confiance (NEWUOA)

2. Méthodes globales

2.1 Méthodes de type surfaces de réponse (RBF, Krigeage)

2.2 Méthodes stochastiques (recuit simulé, AG, ES, PSO)

PARTIE 2 Méthodes de type SQP (Sequential Quadratic Programming)

associées respectivement aux projets:

PROJET 1: Deux problèmes applicatifs d’optimisation globale (Laurent Dumas)

PROJET 2: Lanceur spatial (Max Cerf)

Détails du projet 1 :

Description du projet 1 : M3-projet1-2014.pdf

Documents relatifs au projet 1 :

Programmes Scilab/Matlab d’évaluation de la fonction coût pour le réseau de Bragg : directFBG.sci, directFBG.m, fctode.m

Exemple d’optimisation d’un FBG de longueur 0.01m pour un filtre de 0.1nm autour de 1550nm par la méthode PSO (PSO-projet1.sci)

Résultats optimaux du problème de Lenanrd Jones (N=6 à 13 atomes)

Description de la méthode DIRECT : DIRECT.pdf (Journal of Optimization theory and application, 1993) ou DIRECT2.pdf (manuel d’utilisation d’un code Matlab)

Description de la méthode CMAES : cmaestutorial.pdf (CEC proceedings,1996) et site du logiciel

Ensemble des documents : M3-projet1-2014.zip

Autres références relatives aux deux problèmes applicatifs (Lennard Jones et Bragg):

The LJ problem: article 1 article 2 , article 3 , article 4 thesis

The FBG problem: a talk  'Optimisation of optical communication systems by means of genetic algorithms' by myself
The FBG problem: a PhD dissertation “Synthesis and characterization of fiber Bragg gratings” by J. Skaar  (chapters 2 and 3.1 mainly)
The FBG problem: an article 'Real-coded genetic algorithm for Bragg grating parameter synthesis' by G. Cormier and R. Boudreau
The FBG problem: an article 'Multi-objective and constrained design of fibre Bragg gratings using evolutionary algorithms' by S. Manos and L. Poladian

Autres liens utiles : 

Un article de review des méthodes sans gradient (DFO) : Journal Global Opt. 2013
Un article sur la (non) convergence de Nelder Mead : SIAM J. Opt.1998
Un article sur la convergence de MDS: PhD1989
Un article sur les metamodèles RBF/krigeage: Meta2009
Présentation du recuit simulé avec application au voyageur de commerce: Interstices