NUMERICAL OPTIMIZATION and APPLICATIONS (Electif 9)
 
Laurent DUMAS
Tahar BOULMEZAOUD

Archives : course 2009 , 2010

Course Objectives :

Many problems occuring in industry consist in minimizing (or maximizing) a certain cost function. This course is aimed to present various optimization methods in order to solve such problems.
After a general introduction on  numerical optimization, two different families of optimization methods will be presented:  first, the the stochastic methods (genetic algorithms, evolution strategies, etc...) and then deterministic descent-type methods (gradient, newton, etc…). A numerical implementation with Scilab of these differents methods will be done during the computer sessions, before being applied for the resolution of applicative problems

Teachers : L . Dumas , T. Boulmezaoud (Université de Versailles)

Course prerequisites :

No specific prerequisites are needed for this course.
It is accessible with basic tools in analysis (functions of n variables).

Syllabus (see timetable ): 

Mercredi 02 février (14-17h, LD): cours

1. Introduction et exemples  (presentation ppt , fichier Scilab LJ )

2. Conditions d'optimalité

    2.1 Formules de Taylor
    2.2 CN d'ordre 1, probleme sans contrainte
    2.3 CN d'ordre 1, probleme avec contrainte égalité
    2.4 CN d'ordre 1, probleme avec contrainte inégalité

Vendredi 04 février (8h-11h, TB): cours + TD   (TD1.pdf )

3.  Programmation convexe

    3.1 Rappels sur la convexité
    3.2 Programme convexe et conditions d'optimalité
    3.3 Introduction à la sous-différentielle

Mercredi 16 février (14-17h) LD: cours+TP Scilab

4.Optimization algorithms for unconstrained problems

steepest descent method: definition, convergence result and implementation with Scilab (programme Scilab )
Newton, quasi Newton method

Vendredi 18 février (08-11h) TB

Mercredi 23 février (14-17h) TB

Vendredi 25 février (8h-11h) TB

5.Simplex method

Implementation of the simplex method  ( programme Scilab )

Mercredi 2 mars (14-17h) LD

6.Non deterministic methods

6.1 Simulated annealing (annealing.sci )
6.2 Genetic algorithms (GA-binary2011.sci )

Vendredi 4 mars (8h-11h) LD

6.2 (suite) + Particle Swarm optimization  ( ECP2011-PSO.sci )

Pas de cours le Mercredi 9 mars

Vendredi 11 mars (8h-11h) TB

TD3 (conjugate gradient)

Mercredi 16 mars (14-17h) LD

6.3 Some questions about non deterministic methods:

Constraints handling (Scilab script ecp-canette-AG.sci )
Multi objective optimization (Scilab script NSGA-2010.sci )
Surrogate models (Scilab script ECP2011-RBF.sci   and slides )

References : 

Livres:
Numercial optimization, theoretical and practical aspects : JF Bonnans, JC Gilbert, C. Lemaréchal, C. Sagastizbal, Springer Verlag 2003.
Genetic Algorithms on search, optimization and machine learning : D. Goldberg, 1989
Multi-Objective Optimization Using Evolutionary Algorithms , K. Deb, 2001

Articles (online):
An introdution to algorithms for non linear optimization : N. Gould, S. Leyffer

Exam :

Examen 2011

Training :

Examen 2010 , rattrapage 2010 , examen 2009 , rattrapage 2009