Optimisation

0) Preliminary notions (infimum, supremum, sup-inf inqequality, definition of an optimization problem, ...)

1) Introduction to convex geometry (convex sets, projection separation, cones, ...)

2) Linear programming (definition, examples, standard form, extremal points and basic solutions, simplex algorithm, duality, complementary slackness, applications: optimal transport, the minimaz theorem, max-flow/min-cut theorem, ...)

3) Introduction to convex analysis (convex functions, epigraph, caracterisations and proprerties, strong convexity, subdifferential, ...)

4) Fenchel transform (motivation, definition, examples, properties, Fenchel duality, ...)

5) Non linear programming (problems without constraints, problems with constraints, Karush-Kuhn-Tucker conditions, second order conditions, application: optimal control, ...)

6) Lagrangian duality (Lagrangian, dual problem, Slater conditions, saddle points, interpretation of Lagrange multipliers, application: the best hyperplane separating two point clouds,...)

At the end of this course the student will be able to

1) understand and use properties of convex sets and convex functions
2) understand and compute Fenchel transforms
3) transform certain optimization problems in their dual
4) model certain problems in terms of linear programs
5) solve simple linear programs
6) formulate the KKT conditions for non linear problems
7) write down the Lagrangian dual of a constrained optimization problem
8) identify optimization problems in other disciplines
 

Required and Corequired knowledge and skills

analysis (continuity, differentiability, functions of several variables, gradient, open/closed/compact sets...) and linear algebra (vector spaces, matrices, scalar products, ...)

Required and corequired courses

Ex-cathedra course and exercises

Contribution to the teaching profile

1. Acquire and use knowledge
1.1. Learn fundamental concepts in mathematics.
1.2. Assimilate basic notions in algebra, analysis and geometry.
1.3. Analyze, synthesize and link knowledge and different branches of mathematics.
1.4. Master the principles of logical reasoning and use them as the basis of an irrefutable argument .
1.6. Identify an underlying mathematical framework to a given problem.
1.7. Get acquainted with multiple modelisation methods.

2. Understanding and practice of the specifics of a scientific undertaking
2.1. Understand criteria for mathematical rigor, a mathematical argument, methods of proofs.
2.4. Understand the process of studying and modelling data.
2.5. Understand the process of the generalization of a theory.
2.6. Understand the importance of the unification of existing theories.
2.7. Identify questions that occur inside a theory.
2.8. Explore the consequences of a mathematical result.

3. Communication
3.3. Use a clear and rigorous language, adapted to the audience.

4. Ethics and relation to society
4.3. Learn self-criticism with respect to the validity of an argument.

References, bibliography, and recommended reading

R. Tyrrell Rockafellar. Convex Analysis. Princeton University Press, 1970.
J. B. Hiriart-Urruty and C. Lemarechal. Convex analysis and minimization algorithms. Springer, 1993.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Dimitri P. Bertsekas. Convex Optimization Theory. Athena Scientific, 2009.
Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer, 2 edition, 2006.
Amir Beck. Introduction to nonlinear optimization. SIAM, 2014.

Course notes

• Syllabus
• Université virtuelle

Additional information

Course notes (pdf) are available (French only)

Contacts

mail (Ignace.Loris@ulb.be), Teams or in teacher's office (campus Plaine, building NO, room 2.O7.107)

Campus

Plaine

Method(s) of evaluation

• written examination
• Oral presentation

written examination

Oral presentation

written exam for exercises and oral exam for theory

Mark calculation method (including weighting of intermediary marks)

Oral exam (theory, typically 20-30 minutes per student). Written exam (exercises).

Ponderation: theory (50%), exercises (50%).

Language(s) of evaluation

• french
• (if applicable english )