ArchivesOPTIMISATION,
année 2017-2018
Université
Versailles Saint Quentin en Yvelines
Master MINT
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 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.
PARTIE 1 (semaine 1
à 6): ASPECTS THEORIQUES (avec Mr Boulmezaoud)
--
La convexité (ensembles convexes, fonctions convexes, propriétés
des fonctions convexes)
-- Optimisation sans contraintes. Points
critiques. Cas convexe.
-- Cônes normaux et cônes tangents,
lemme de Farkas, points qualifiés.
-- Conditions suffisantes
de qualification (dont conditions de Slater).
-- Optimisation
avec contraintes. Conditions KKT. Cas convexe.
-- Introduction au
Calcul de Variations: équation d'Euler-Lagrange, etc.
PARTIE 2 (semaine 7 à 12): ASPECTS ALGORITHMIQUES (avec Mr Dumas)
1 Introduction et rappels d’analyse
- exemple de problème d’optimisation de formes en mécanique
- formules de Taylor
- rappel des conditions d’optimalité avec et sans contraintes
2. Méthodes de descente sans contrainte
2.1 ordre 1 : descente avec recherche linéaire par backtracking et condition d’Armijo (implémentation, convergence)
2.2 ordre 2 : Newton et quasi Newton
3. Méthodes de descente avec contraintes
(exemple concret : canette, 3 méthodes: gradient projeté, pénalisation externe, algorithme d’Uzawa)
4. Méthodes de nature stochastique
4.1 Recuit simulé
4.2 Algorithmes génétiques
4.3 Stratégies d’évolution
4.4 Essaim de particules (PSO)
Mardi 7 Novembre 15h15-18h30 (amphi I) : Introduction, méthodes de descente (cours)
Jeudi 9 Novembre 15h15-16h15 (amphi H): méthodes de descente d’ordre 1 (cours)
Mardi 14 Novembre 15h15-16h45 : méthodes de descente d’ordre 1 (TD)
Jeudi 16 Novembre 15h15-16h45 : méthodes de descente d’ordre 2 (cours)
Mardi 21 Novembre 15h15-18h30 : méthodes de descente d’ordre 2 (TD), optimisation avec contraintes (pénalisation)
Jeudi 23 Novembre 15h15-16h45 : optimisation avec contraintes (Uzawa)
Mardi 28 Novembre 15h15-18h30 optimisation avec contraintes (TD)
Jeudi 30 Novembre : pas de séance
Mardi 5 décembre Méthodes de nature stochastique
Jeudi 7 Décembre Méthodes de nature stochastique
Mardi 12 Décembre Méthodes de nature stochastique (TD)
Jeudi 14 Décembre CC2
CC1 (partie 1) : énoncé
CC2 (partie 2) : énoncé
Examen session 1 : énoncé
Session 2 : sujet
TD1 (partie 2) : méthodes de descente d’ordre 1 (énoncé)
TD2 (partie 2) : méthodes de descente d’ordre 2 (énoncé, programme Scilab)
TD3 (partie 2) : algorithme d’Uzawa (énoncé)
TD4 (partie 2) : Méthodes de nature stochastique (énoncé)
Méthodes de descente sans contraintes (ordre 1 ou 2 avec deux recherches linéaires différentes) : descente.sci
Méthodes de descente avec contraintes (pénalisation externe ou interne) : canette.sci
Méthode d’Uzawa (canette_uzawa.sci, uzawa_quadratique.sci)
Recuit simulé : SA.sci
Algorithme génétique binaire (GA-binary.sci) ou réel (GA-banana.sci et GA-rastrigin.sci)
Stratégie d’évolution : ES.sci
Essaim de particules : PSO.sci
- 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