Intervenants :  Claude Lemaréchal (http://www.inrialpes.fr/bipop/people/lemarechal/) &  Jérôme Malick (http://www.inrialpes.fr/bipop/people/malick/)

Dates : 17 – 21 janvier 2011 – ENS Lyon

Planning (sujet à modifications):

Lundi (3h30) —  Introduction

  • 10h30 – 12h — présentation du cours, objectifs
  • 13h30 – 15h30 — introduction a l’optimisation, exemples

Mardi (5h15) — Optimisation classique

  • 10h30 -12h  — principes algorithmiques
  • 13h30 – 15h15 — méthodes classiques, méthodes pour la grande taille
  • 15h30 – 17h30 — TP

Mercredi (5h) — Optimisation convexe non-différentiable

  • 09h00 – 12h00  — non-différentiabilité naturelle, ou provoquée
  • 13h30 – 15h30  — TD

Jeudi (5h15) — Théorie de l’optimisation convexe

  • 10h30 – 12h   — analyse convexe
  • 13h30 – 15h15  — théorie de la dualité
  • 15h30 – 17h30  — TD

Vendredi (5h) — Algorithmique de l’optimisation non-différentiable

  • 9h – 10h30 — algorithmes à oracle
  • 10h30 – 12h  — algorithmes pour problèmes structurés
  • 13h30 – 15h30  — fin + examen

Langue de la présentation : FRANCAIS.

Objectifs:

  1. introduction a l’optimisation, applications sur des problèmes réels
  2. algorithmique de l’optimisation convexe non-différentiable
  3. relaxations convexes de problèmes combinatoires, décomposables ou non-convexes structurés

Programme prévisionnel : (enveloppe supérieure du programme)

———————
Partie 1 : Introduction à l’optimisation
– qu’est ce qu’un problème d’optimisation ? objectifs, classification
– exemples: moindres carrés, gestion de production, allocation
– principes mathématiques, rôle de la convexité
– principes algorithmiques: estimation + correction

———————
Partie 2 : Algorithmes d’optimisation différentiable

2.1 principes des méthodes classiques
– estimation : (quasi- Gauss-) Newton
– correction : recherche linéaire, région de confiance
– exemple : classification supervisée

2.2 méthodes pour la grande taille
– mémoire limitée, Newton tronqué
– exemples : prévision météo, maximisation d’entropie

———————
Partie 3 : Optimisation non-différentiable: théorie et applications

3.1 motivations:
– non-différentiabilité naturelle
– non-différentiabilité provoquée : relaxation, problèmes décomposables, optimisation combinatoire

3.2 éléments d’analyse convexe
– sous-différentiabilité
– conjugaison, dualité (Lagrange, Fenchel)
– analyse de sensibilité, interprétation économique

3.3 applications :
– optimisation de la production électrique
– optimisation des réseaux de communication
– optimisation de valeurs propres, application en théorie des graphes

———————
Partie 4 : Algorithmes d’optimisation convexe non-différentiable

4.1 Problèmes à oracle
– méthodes: sous-gradient, plans sécants, faisceaux
– récupération primale
– identification du second-ordre

4.2 Problèmes à non-différentiabilité structurée
– exploitation de la structure
– méthode de points intérieurs
– optimisation semidéfinie (SDP)
– relaxations SDP et applications (combinatoire, stats)

———————
Partie 5 : Deux applications de l’optimisation

4.1 Apprentissage
– contexte, rôle de l’optimisation, exemples
– applications des algorithmes, nouveaux enjeux numériques, optimisation « huge-scale »
– illustrations en vision par ordinateur, en bio-stats

4.2 Optimisation polynomiale
– optimisation globale, lien avec l’optimisation semidéfinie (SDP)
– approximations successives par SDP, preuve de fermeture
– illustrations en commande de systèmes, en certification de programmes

Correspondants locaux : T. Begin et P. Gonçalves.
Sponsor : Pôle ResCom du GDR CNRS ASR