OPTIMISATION (MA 751), année 2015-2016

Université Versailles Saint Quentin en Yvelines
Master de Mathématiques Fondamentales

Tahar Boulmezaoud (cours et TD, semaine 1 à 6) 
 Laurent Dumas (cours et TD, semaine 7 à 12) 

Séances le mardi de 15h15 à 18h30 et le jeudi de 13h30 (ou 15h15) à 16h45

Several problems in industry, in physics and in economics consist to minimize or to maximize an objective function. The objective of this course is to provide a number of theorical and practical for handling these issues. The first part of the course is devoted to some central elements of constrained and unconstrained optimization theory. In the second part, focus is on numerical deterministic and stochastic optimization methods. The course could combine conceptual presentations with practical hands-on computer sessions. 

Cours:

weeks number 1 to 6 :

– Introduction. Examples.

– Convexity : convex sets, convex functions convexes, properties.

– Unconstrained Optimization : first and second order optimality conditions. The case of convex programming.

– Constrained Optimization : Karush-Kuhn-Tucker theorem, Lagrange multipliers.

weeks number 7 to 12 : Optimisation, aspects algorithmiques

– Numerical methods : descent methods (gradient descent, quasi-Newton methods,..etc),

– Stochastic methods (simulated annealing, evolutionary algorithms,...)

Contenu de la partie ‘Aspects algorithmiques’ :

I Introduction et exemples

(minimas locaux, globaux, exemples : Lenard Jones et programmation linéaire)

II Méthodes de descente

2.1 Rappels d’analyse (Taylor)

2.2 Optimisation sans contraintes (rappel des conditions d’optimalité, gradient, Newton, quasi-Newton et gradient conjugué)

2.3 Optimisation avec contraintes (2 exemples concrets : canette + I Beam, pénalisation externe/interne, méthode de point intérieur, algorithme d’Uzawa)

III Méthodes de nature stochastique

3.1 Recuit simulé

3.2 Algorithmes génétiques

3.3 Cas de l’optimisation avec contraintes

3.4 Version multi-objectif

3.5 Couplage avec les méthodes de descente

Jeudi 12 Novembre 15h15-16h45 (salle 2104) : Introduction, méthodes de descente

Mardi 17 Novembre 15h15-18h30 (amphi I) : méthodes de descente sans contraintes (cours + TD)

Jeudi 19 Novembre 13h30-16h45 (salle G101) : méthodes de descente sans contraintes (cours + TP)

Mardi 24 Novembre: pas de séance

Jeudi 26 Novembre 13h30-16h45 (salle G101) : méthodes de descente avec contraintes inégalités (cours + TP)

Mardi 1 Décembre 17h00-18h30 (amphi I) : méthodes de descente avec contraintes inégalités (cours)

Jeudi 3 décembre 15h15-16h45 (salle G101) : algorithme d’Uzawa (cours+ TD)

Mardi 8 Décembre 17h00-18h30 (amphi I) : recuit simulé

Jeudi 10 décembre 13h30-16h45 (salle G101) : algorithmes génétiques (cours et TP)

Mardi 15 décembre 15h15-18h30 (amphi I) : optimisation multi-objectif, prise en compte des contraintes (cours et TD)

Jeudi 17 Décembre 13h30-16h45 (salle G101) : CC 2

Travaux dirigés:

TD 1 : énoncé

TD 2 : énoncé

TD 3 : énoncé

TD 4 : énoncé

TD 5 : énoncé corrigé : problème des disques en mouvement (fichier Scilab)

TD 6  : énoncé, corrigé : AG avec stochastic ranking (fichier Scilab)

CC1 : énoncé et corrigé

CC2 : énoncé (corrigé, programme DE corrigé)

Examen : énoncé session 1

TP et programmes Scilab :

TP1 : méthodes de descente (fichier Scilab)

TP 2 : problème de la canette (fichier Scilab)

Programmes Scilab ; Recuit simulé, Algorithmes génétiques, AG multi-objectif

Documents en ligne :

- Ph. G. Ciarlet, Introduction à l’analyse numérique matricielle et Optimisation, Masson, 1988.

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

- J. F. Bonnans, Optimisation continue : cours et exercices, Dunod, 2006.

- J. B. Hiriart-Urruty and C. Lemaréchal, Convex analysis and minimization algorithms, Vol. I, II, Springer-Verlag, 1993.

- Présentation du recuit simulé avec application au voyageur de commerce: Interstices