Méthodes d’optimisation (ULCO, Spring 2023)
Illustrations of (Left) the Simplex Method (on a polyhedron generated by Geogebra) and (Right) gradient descent on a non convex landscape
Although the history of optimisation can be traced back to 16th/17th centuries (Cardano, Pascal), the scope of modern optimisation (as we know it today) only goes back to World War II. Because of the war effort, there was a need to allocate resources optimally and to the various military operations. Two factors played a key role in the rapid development of optimisation during the 19’s. One was the substantial progress that was made in the development of the mathematical techniques. After the war, many of the scientists who had participated in the operations were motivated to pursue research in relation to the field. Another factor was the onslaught of the computer revolution. The advent of the digital computer enabled the resolution of more interesting problems, faster. Since then, mathematical optimisation has found a wide range of applications including in science, engineering, economics, and industry and has led to several Nobel Prizes.
See here as well as here for related sets of open problems
In this course, we will discuss the graphical resolution of linear programs as well as the Simplex Method, the Ellipsoid Method and Interior Point Methods. We will study the resolution and relaxation of integer programs, and introduce cutting plane (including Gomory’s Fractional Cuts) and Branch and bound.
In a second part, we will cover Nonlinear optimization, Optimality conditions and gradient methods as well as Newton’s method.
The assignments will include (but not be limited to) paper readings, pen and paper exercises as well as numerical simulations (Julia or Python).
The class will follow the structure
1. Lectures (=CM) (introduction of the new material that will be needed during the lab sessions and for the assignements)
2. Programming (lab) sessions (=TD, TP), (you have the opportunity to apply what you have learned during the lecture, and you can ask all the questions you want to make sure you understand everything before the assignement)
3. Assignments (=DM) (You are given a new problem and you are evaluated on your ability to use the course material to solve this new problem)
Horaire et Salle de cours
Cours et TD/TPs: Mardis: 8h00pm – 10h00, 10h15 – 12h15, 13h1515h15, 15h30 – 17h30 ,
Salle 21A, Bâtiment Angelier, 34 Grande Rue
(voir horaire détaillé cidessous)
Assignments policy
Except if explicitly stated otherwise, assignments are due at the beginning of each class.
Current (temporary) version of the notes: see below as well as the list of sections for the Final
Practice (theory) Questions for each exam can be found by clicking on those exams below
Exams:
Enter password:
Partiel
Enter password:
Examen
Partiel : (Matière))
Assignments : 30 % of the grade (Tentative schedule below)
The Github page for the class will be hosted at https://github.com/acosse/NumericalAnalysisCalaisFall2022 and will essentially be used to post numerical verifications for the recitations.
Tentative schedule:
Legend: Lab sessions are in green, Homeworks are in red (right side of the table), dates related to the project are in orange.
Week #  date  Topic  Assignements 
Semaine 1 CM/CM 
03/02 10h0012h00 
General Introduction Modelling, Standard form, Geometry of Polytopes Lecture 1, Recitation 01, Solutions, (HandWritten) Solutions 

Semaine 2 CM/TD 
10/02 10h0012h00 
Graphical resolution, Basic solutions + Simplex (Part I)

Assignment 1 
Semaine 3 CM/TD 
17/02 10h0012h00 13h0015h00 
Simplex (Part II)
Lecture , Recitation 02, TD 01 
Readings 
Semaine 4 CM/TD 
03/03 10h0012h00 13h0015h00 
Shadow Prices + Sensitivity Analysis Lecture , Recitation 03, (Partial) Solutions recitation 
Readings
Assign. 2, Assig. 1 due 
Semaine 5 CM/TD 
10/03 15h0017h00  Duality + Integer Programming (Part I) Lecture, Recitation 04 
Readings 
Semaine 6 CM/TD 
17/03 13h0015h00 15h3017h30 
Integer Programming (Part II) including Cutting planes and Branch and Bound Lecture, Recitation 05, Solution 
Assign. 2 due, Project choice MidTerm Revisions 
Semaine 7 CM/TD 
24/03 10h0012h00  Ellipsoid + Interior Point Methods Lecture , Recitation 06 
Readings 
Semaine 8 CM/TD/TD 
31/03 10h0012h00 
Nonlinear optimization, gradient methods, line searches + Newton’s/quasi Newton’s method Lecture , Recitation 
Readings 
Semaine 9 CM/TD 
07/04 10h0012h00 
Conjugate gradient project presentations 
Readings 
Semaine 10 Examen 
14/04 13h0015h00 15h3017h30 
Additional ressources (Projects)
Additional ressources (beyond course material)
Lab Sessions and programming policy
The lab sessions will require you to do some programming. It is strongly recommended to use python as it is more flexible and will be useful to you when moving to pytorch later on for more advanced machine learning methods requiring GPU processing.
Downloading and getting started with Julia.