Optimisation, algorithmes et applications

1) Notions élémentaires : ensembles et fonctions convexes, projection sur un convexe, opérateur de proximité, propriétés de l’opérateur de proximité, Le calcul sous-différentiel

2) L’algorithme du point proximal : l’algorithme du point proximal, l’algorithme de Douglas-Rachford, minimisation sous contraintes linéaires, application : la reconstruction parcimonieuse ou de faible rang

3) L’algorithme du gradient proximal : le principe de minimisation par majorisation, l’algorithme du gradient proximal, taux de convergence de l’algorithme du gradient proximal, Application : le seuillage itératif

4) Méthodes d’accélération : la méthode de Nesterov, l’algorithme du gradient proximal avec la règle d’Armijo, application : le seuillage itératif accéléré

5) Algorithmes proximaux généralisés : la transformée de Fenchel, une généralisation de l’algorithme du point proximal, un algorithme itératif pour calculer certains opérateurs de proximité, une généralisation de l’algorithme du gradient proximal, applications

Ce cours permet aux étudiants en mathématique et  statistique d'acquérir une connaissance de base concernant les outils et méthodes rencontrés fréquemment dans le domaine de l'optimisation. En particulier, on traitera des méthodes d'optimisation numérique applicable à des problèmes de grande taille, comme p. ex. en imagerie mathématique.

Le premier chapitre concerne les notions élémentaires de l'optimisation convexe. En particulier, on étudiera la projection sur un convexe et sa généralisation sous forme d'opérateur de proximité. Cet opérateur de proximité sera l'outil principal de résolution de problèmes d'optimisation dans le reste du cours. Le concept de sous-différentiel d'une fonction non lisse sera également traité.

Le second chapitre introduit plusieurs problèmes d'optimisation pouvant être résolus numériquement à l'aide d'opérateurs de proximité. Ce chapitre introduit également des méthodes permettant de démontrer l convergence d'algorithmes itératifs.

Ensuite nous abordons le traitement d'une classe de problèmes nécessitant l'optimisation de la somme d'une fonction lisse et d'une fonction non lisse. Un algorithme itératif de résolution est présenté et la convergence est démontrée. Une borne supérieure pour la vitesse de convergence est dérivée. Finalement, l'algorithme est appliqué à la résolution numérique de problèmes de reconstruction parcimonieuse et de faible rang.

Le chapitre suivant est consacré à des méthodes d'accélération de l'algorithme proposé dans le chapitre précédent. On discute la méthode de Nesterov et les règles d'Armijo et de Barzilai-Borwein.

Le dernier chapitre introduit la transformée de Fenchel et ses implications pour les opérateurs de proximité. Plusieurs algorithmes des chapitres précédents sont généralisés.

Les concepts et les méthodes sont illustrés en les appliquant à des problèmes réels en imagerie mathématique ou en statistique.

Connaissances et compétences pré-requises ou co-requises

Les prérequis sont les notions élémentaires de l'analyse réelle (suites, séries, limites, ...) et de l'algèbre linéaire (espaces vectoriels, opérateurs, ...)

Cours ex-cathedra (2h/semaine) et exercices dirigés (1h/semaine) encadrés par le titulaire.

Contribution au profil d'enseignement

Ce cours contribue aux points suivants du profil d'enseignement :

1.1. S'approprier les concepts fondamentaux de certaines branches récentes des mathématiques.
1.2. Acquérir des notions avancées de domaines des mathématiques.
1.3. Analyser, synthétiser, relier les connaissances de différentes branches des mathématiques.

2.1. Mettre en pratique des critères de rigueur, une argumentation, des techniques de démonstration.
2.2. Dégager un concept à partir d'observations ou d’exemples.
2.3. Elaborer un processus d’abstraction ou une étude soit de données soit d’exemples en vue du développement d’une théorie ou d’un modèle.

3.1. Explorer les conséquences d’un résultat mathématique.

4.1. Utiliser un langage clair et rigoureux.

Références, bibliographie et lectures recommandées

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)

Support(s) de cours

• Syllabus

Contacts

mail (Ignace.Loris@ulb.be) ou en personne au bureau du titulaire (campus Plaine, bâtiment NO, local 2.O7.107)

Campus

Plaine

Méthode(s) d'évaluation

• Examen oral

Examen oral

• Examen avec préparation

Construction de la note (en ce compris, la pondération des notes partielles)

Typiquement deux questions (deux chapitres). 10 points par question.

Langue(s) d'évaluation

• français