Course/
Computer Sessions on
NUMERICAL OPTIMIZATION
Laurent Dumas
DEGREE: Master of Science
in Mathematics, IMAMIS Program
DATES AND LOCATION: from
January, 23th to February 3rd, 2006, University of the Philippines-Diliman
OUTLINE OF THE COURSE:
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 an applicative problem occuring in the field of telecommunications.
THEORETICAL PART (10 courses of 1h30):
Part 1. Introduction and examples (1h30)
Global and local optimization for real valued functions with n real
parameters, with or without constraints. Examples in various applied fields
Part 2. Stochastic optimization methods (6h)
genetic algorithms, evoution strategies: general principles and examples,
constraints handling, multi objective case
Part 3. Deterministic descent type methods (4h30)
Basic methods. Line search principles. Quasi Newton methods. Other
methods
Part 4. Resolution of 'real world' problems (3h)
COMPUTER SESSIONS (10 sessions of 1h30):
1. Numerical methods (6 sessions):
. Numerical implementation with Scilab of a real-valued genetic algorithm
(4h30)
Application on classical test functions (Rastrigin, Griewank, etc…).
. Numerical implementation with Scilab of a first order descent method
(4h30)
Application on the same previous functions
2. Applicative project: (4 sessions):
Resolution of an inverse problem in telecommunications (synthesis
of a Fiber Bragg filter) by using various optimization methods (6h)
DETAILED PROGRAM:
Monday, January 23th:
17h-18h30(course):
Part 1. Introduction and examples
18h30-20h (computer session, applicative project):
Implementation with Scilab of the associated direct
problem (solution of a system of first order coupled ODEs)
Tuesday, January 24th:
17h-18h30(course):
Part 2. Stochastic optimization methods:
binary genetic algorithms
18h30-20h (computer session, applicative project):
Modelization of the inverse problem
Wednesday, January 25th:
17h-18h30(course):
Part 2. Stochastic optimization methods:
real coded genetic algorithms
18h30-20h (computer session, numerical methods):
Implementation of a real coded genetic algorithms
Validation on classical test functions
Thursday, January 26th:
17h-18h30(course):
Part 2. Stochastic optimization methods:
parameters tuning, constraints handling
18h30-20h (computer session, numerical methods):
Implementation of a real coded genetic algorithms
Validation on classical test functions
Friday, January 27th:
17h-18h30(course):
Part 2. Stochastic optimization methods:
multi objective optimization
18h30-20h (computer session, numerical methods):
Implementation of a real coded genetic
algorithm
Validation on classical test functions
------------------- Second week --------------------------------------------
Monday, January 30th:
17h-18h30(course):
Part 3. Deterministic optimization
method: basic methods, line searches
18h30-20h (computer session, numerical methods):
Implementation of a descent method of first
order
Tuesday, January 31th:
17h-18h30 (course):
Part 3. Deterministic optimization
methods: Newton methods
18h30-20h (computer session, numerical methods):
Implementation of a descent method of first
order
Wednesday, February1st:
17h-18h30(course):
Part 3. Deterministic optimization methods:
constraints handling
18h30-20h (computer session, numerical methods):
Constraints handling
Thursday, February 2nd:
17h-18h30(course):
Part 4. Resolution of 'real world' problems:
can cost fabrication, LJ cluster
18h30-20h (computer session, applicative project):
Resolution of the inverse problem with a
hybrid method
Friday, February 3rd:
17h-18h30(course):
Resolution of 'real world' problems: FBG
synthesis, aerodynamic shape optimization
18h30-20h (computer session, applicative project):
Resolution of the inverse problem with a
hybrid method.
BIBLIOGRAPHY:
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
ON THE WEB:
Theoretical part:
A tutorial 'How
to build an avolutionary algorithm' by the EVONET community
An introduction article on 'Evolution strategies'
by HG Beyer and HP Schweifel
An online course on 'Numerical Optimization'
at Oxford University
An online course on 'Optimization inengineering
design' at the Georgia Institute of Technology
A book Numerical recipes in C or Fortran
77 (Chapter 10 mainly)
An introduction article on 'Numerical Solution of Optimization
Test-Cases by Genetic Algorithms' by N. Marco and J.A. Desideri
Applicative part (inverse problem in telecommunications):
A short tutorial 'Introduction
to Fiber Bragg Gratings'
A talk 'Optimisation
of optical communication systems by means of genetic algorithms' by
myself
A PhD dissertation “Synthesis and characterization
of fiber Bragg gratings” by J. Skaar (chapters 2 and 3.1 mainly)
An article 'Real-coded genetic
algorithm for Bragg grating parameter synthesis' by G. Cormier and
R. Boudreau
An article 'Multi-objective
and constrained design of fibre Bragg gratings using evolutionary algorithms'
by S. Manos and L. Poladian
An article "Semi deterministic vs Genetic Algorithms
for global optimization of multichannel optical filters" by myself,
B. Ivorra, B. Mohammadi, P. Redont and O. Durand
Ohers articles on Lennard-Jones problem: article 1 article 2, article
3, article 4
thesis
FINAL SCILAB PROGRAMS
A program for the computation of a FBG reflectivity spectrum: directFBG.sci
A real valued genetic algorithm: GA.sci
A steepest descent method with backtracking linesearch: steepest.sci
A program for solving the Lennard Jones problem (LJ.sci)
SOME PHOTOS FROM THE COURSE:
Here are 16 pictures taken during my stay at UP: UP-photos.zip (zip file, 10Mo)
FINAL EXAM:
The final exam consist in a project to write in Scilab:
The subject (.doc file) is here
The documents must be sent at dumas@ann.jussieu.fr.
You can also use this email in case of technical problems or misunderstandings
during the project writing.
NEW: contact Julius Basilla
for the final grades at the exam
Sorry for the delay...