Optimisation numérique

Une microbrasserie rennaise veut savoir combien de blonde et d’ambrée brasser cette semaine pour gagner le plus possible, sans dépasser ses cuves ni son stock de malt. Un réseau de neurones cherche les millions de poids qui rendent son erreur la plus petite possible. Une entreprise de livraison veut placer un entrepôt au plus près de ses clients, mais seulement dans une zone autorisée. Ces trois problèmes n’ont l’air de rien avoir en commun, et pourtant ils s’écrivent tous de la même façon : minimiser (ou maximiser) une fonction sous des contraintes. C’est l’objet de l’optimisation.

Ce cours part des problèmes les plus simples, les programmes linéaires, que l’on résout exactement avec l’algorithme du simplexe. Il passe ensuite aux fonctions quelconques sans contrainte : comment reconnaître un minimum, puis comment l’approcher numériquement par descente de gradient ou par la méthode de Newton. Il se termine avec les contraintes (multiplicateurs de Lagrange, conditions de Karush-Kuhn-Tucker) et avec ce que tout cela change pour l’apprentissage automatique.

Objectifs pédagogiques

À la fin de ce cours, vous serez capable de :

• Modéliser une situation concrète comme un problème d’optimisation : variables, fonction objectif, contraintes.
• Résoudre un programme linéaire graphiquement et avec l’algorithme du simplexe, y compris quand il faut une phase de démarrage (grand M, deux phases).
• Écrire et interpréter le dual d’un programme linéaire : prix des ressources, écarts complémentaires, jeux matriciels.
• Caractériser les minimums d’une fonction de plusieurs variables avec le gradient, la Hessienne et la convexité.
• Programmer et régler une descente de gradient (pas fixe, pas optimal) et une méthode de Newton, et expliquer leurs vitesses de convergence.
• Résoudre un problème sous contraintes avec les multiplicateurs de Lagrange et les conditions KKT, et relier ces outils à l’entraînement des modèles d’apprentissage.

Prérequis

• Le calcul différentiel de base : dérivées, dérivées partielles, développement de Taylor à l’ordre 2.
• L’algèbre linéaire : matrices, produit matriciel, résolution d’un système linéaire, valeurs propres d’une matrice symétrique.
• Python avec NumPy, pour les exemples de code.

Le dernier chapitre fait le lien avec le cours d’Apprentissage automatique, qu’il est utile d’avoir parcouru, ou de lire en parallèle.

Le plan du cours

Partie 1 · Programmation linéaire

1. Formulez un problème d’optimisation : vocabulaire, minimum local et global, modélisation d’un programme linéaire et méthode graphique.
2. Résolvez un programme linéaire avec le simplexe : forme standard, variables d’écart, solutions de base, pivot et tableau.
3. Démarrez le simplexe avec le grand M ou deux phases : contraintes « supérieur ou égal », variables artificielles, détection d’un problème irréalisable.
4. Exploitez la dualité : programme dual, dualité faible et forte, écarts complémentaires, prix des ressources et jeux matriciels.

Partie 2 · Optimisation sans contrainte

5. Caractérisez les minimums d’une fonction : gradient, Hessienne, conditions d’optimalité, existence et convexité.
6. Descendez le gradient : pas fixe, pas optimal, conditionnement et recherche linéaire.
7. Accélérez avec Newton et quasi-Newton : méthode de Newton, convergence quadratique, BFGS.

Partie 3 · Contraintes et apprentissage

8. Traitez les contraintes d’égalité avec Lagrange : lagrangien, interprétation géométrique et sens du multiplicateur.
9. Maîtrisez les conditions KKT : contraintes d’inégalité, complémentarité, qualification et cas convexe.
10. Reliez l’optimisation à l’apprentissage : moindres carrés, gradient stochastique, momentum et Adam, régularisation et SVM.

Chaque chapitre se termine par un résumé et des exercices corrigés, de difficulté croissante.

D’où vient ce cours

Ce cours reprend l’enseignement d’optimisation numérique suivi en 4e année du cycle ingénieur de l’INSA Rennes, en spécialité informatique (semestre 7) : programmation linéaire et dualité, optimisation sans contrainte, optimisation sous contraintes d’égalité et d’inégalité, avec des travaux dirigés, des devoirs surveillés et un TP en Python. Les exemples marqués « en TP » proviennent de notre notebook d’optimisation sans contrainte (méthode de Newton en dimension 1, gradient à pas fixe et à pas optimal en dimensions 1 et 2), et leurs chiffres sont ceux qui s’affichent dans ses sorties.

Le texte, les exemples (la brasserie, l’entrepôt de livraison) et les exercices ont été entièrement réécrits. Plusieurs notions ont été complétées à partir de sources standard du domaine (manuels d’optimisation continue et de recherche opérationnelle, documentation de SciPy et de PyTorch) : la recherche linéaire d’Armijo, la vitesse de convergence liée au conditionnement, les méthodes de quasi-Newton (BFGS), les moindres carrés, et tout le dernier chapitre sur le gradient stochastique, Adam et la régularisation, qui fait le pont avec l’apprentissage automatique.