Optimisation, algorithmes et applications

1) Elementary notions: convex sets and functions, projection on a convex set, proximity operator, properties, sub-differential calculus

2) The proximal point algorithm, Dougas-Rachford algorithm, minimisation with linear constraints, minimisation under linear constraints, application : sparse and low-rank recovery

3) The proximal gradient algorithm: the majorization-minimization algorithm, the proximal gradiet algorithm, convergence rate, application: iterative thresholding

4) Acceleration method: Nesterov's method, Armijo's rule, application: accelerated iterative thressholding

5) Generalised proximal algorithms: Fenchel transform, a generalized proximal point algorithm, and algorithm for calculatng certain proximity operators, a generalozed proximal gradient algorithm, applications

 

This course offers students n mathematics and statstics an introduction to the tools and methods frequently encountered in the field of numerical optimization. In particular, we will study numerical optimization methods applicable to large scale problems, such as e.g. in mathematical imaging.

 

The first chapter deals with elementary notions of convex optimization. In particular, we will study the projection on a convex set, and its generalization under the form of proximity operator. This proximity operator will be the basic tool used used for the solution of optimization problems in the remainder of the course. We also treat the concept of sub-differential of a non-smooth function.

 

The second chapter introduces some optimization problems that can be solved numerically using proximity operators. The chapter also introduces some methods that allow for proving the convergence of iteratif algorithms.

Next we treat a class of problems combining smooth and non smooth parts in the objective functon. An iteratif algorithms is introduced and its convergence is shown. An upper bound for its convergence speed is derived. Finally, the algorithm is applied to the numerical solution of sparse and low-rank reconstruction problems.

 

The next chapter deals with acceleration methods for the algorithm introduced in the previous chapter.. We will discuss the method of Nesterov, the Armijo and Barzilai-Borwein rules.

 

The last chapter introduces the Fenchel transform and its implications for proximity operators. Several algorithms of the preceding chapters are generalized.

The concepts and methods are illustrated by applying them to real problems in mathematica imagingand statistics

Required and Corequired knowledge and skills

Elementary notions of real analysis (sequence, series, convergence, ...) and linear algebra (vector spaces, linear operators, ...)

Ex-cathedra course (2h/week) and exercises (1h/week) under supervision of the lecturer.

Contribution to the teaching profile

This course contributes to the following points of the competence framework:

1.1. Learn fundamental concepts of certain branches of modern mathematics
1.2. Learn advanced notions in mathematics.
1.3. Analyze, synthesize and connect different branches in mathematics

2.1. Implement rigorous criteria, arguments and proofs.
2.2. Create concepts starting from examples or observations.
2.3. Elaborate an abstraction process starting from data or examples

3.1. Explore the consequences of a mathematical result


4.1. Use clear and rigorous language

References, bibliography, and recommended reading

Convex Analysis and Monotone Operator Theory in Hilbert Spaces, H. H. Bauschke & P. L. Combettes (Springer, 2011)

Iterative Optimization in Inverse Problems, C. L. Byrne (Chapman and Hall/CRC, 2014)

Convex Optimization, S. Boyd & L. Vandenberghe (Cambridge University Press, 2004)

Convex analysis and minimization algorithms, J. B. Hiriart-Urruty & C. Lemarechal, (Springer, 1993)

Nonlinear programming, D. P. Bertsekas (Athena Scientific, 1999)

Convex Optimization Theory , D. P. Bertsekas (Athena Scientific, 2009)

Course notes

• Syllabus

Contacts

mail (Ignace.Loris@ulb.be) or in person in my office (campus Plaine, building NO, office 2.O7.107)

Campus

Plaine

Method(s) of evaluation

• Oral examination

Oral examination

• Examination with preparation

Oral Exam. Typically 20-30 minutes per student. Exam schedule fixed together with students.

Mark calculation method (including weighting of intermediary marks)

Typically two questions (two chapters). 10 points per question.

Language(s) of evaluation

• french
• (if applicable english )