Optimisation Convexe

📚 Résumé du contenu

Un cours et un manuel complets au niveau master couvrant la théorie, les applications et les algorithmes numériques de l'optimisation convexe. Il met l'accent sur la reconnaissance et la formulation de problèmes convexes en ingénierie et en sciences.

Maîtriser les fondations mathématiques et les algorithmes pratiques de l'optimisation convexe pour l'ingénierie et la science des données.

Auteur : Stephen Boyd, Lieven Vandenberghe

Remerciements : Soutenu en partie par le NSF, ainsi que grâce aux contributions d'étudiants et collègues de Stanford et UCLA, notamment Arkadi Nemirovski et Kishan Baheti.

🎯 Objectifs d'apprentissage

1. Définir les composantes d'un problème d'optimisation mathématique, y compris la fonction objectif, les contraintes et les variables.
2. Distinger les problèmes de moindres carrés, de programmation linéaire et d'optimisation convexe selon leurs propriétés mathématiques.
3. Comparer les stratégies d'optimisation locale et globale, et évaluer la complexité computationnelle associée à chacune.
4. Définir et distinguer les ensembles affines, les ensembles convexes et les cônes à l'aide de notations formelles de combinaison.
5. Identifier et représenter des ensembles convexes standards tels que les boules euclidiennes, les ellipsoïdes, les polyèdres et le cône semi-défini positif.
6. Appliquer des opérations préservant la convexité, telles que l’intersection, les transformations affines et les fonctions perspective, pour vérifier les propriétés des ensembles.
7. Identifier et appliquer des opérations préservant la convexité, notamment le supremum ponctuel de fonctions affines et les règles de composition vectorielle.
8. Dériver le conjugué de Lagrange de diverses fonctions et appliquer l'inégalité de Young.
9. Caractériser la quasi-convexité à l’aide des ensembles de sous-niveau et des conditions différentielles du premier et second ordre.
10. Formuler et transformer : convertir des problèmes d’optimisation bruts en formes convexes standard en utilisant des variables de marge et l’élimination de contraintes.

🔹 Leçon 1 : Introduction à l'optimisation mathématique

Aperçu : Cette leçon présente les concepts fondamentaux de l'optimisation mathématique, passant de la formulation générale du problème aux classes spécifiques résolvables comme les moindres carrés et la programmation linéaire. Elle insiste sur la distinction cruciale entre optimisation convexe et non convexe, détaillant comment les méthodes convexes servent de repère fiable en termes d'efficacité et fournissent des outils essentiels pour traiter des problèmes non linéaires plus difficiles.

Objectifs d'apprentissage :

• Définir les composantes d’un problème d’optimisation mathématique, y compris la fonction objectif, les contraintes et les variables.
• Distinguer les problèmes de moindres carrés, de programmation linéaire et d’optimisation convexe selon leurs propriétés mathématiques.
• Comparer les stratégies d’optimisation locale et globale, et évaluer la complexité computationnelle associée à chacune.

🔹 Leçon 2 : Théorie des ensembles convexes

Aperçu : Cette leçon explore la géométrie fondamentale de l’optimisation, passant des structures linéaires élémentaires aux propriétés complexes des ensembles convexes et des cônes. Elle couvre les définitions mathématiques des ensembles affines et convexes, examine des géométries spécifiques comme les polyèdres et les cônes semi-définis positifs, et détaille les opérations et théorèmes permettant aux chercheurs de caractériser et manipuler des ensembles convexes dans des espaces à haute dimension.

Objectifs d'apprentissage :

• Définir et distinguer les ensembles affines, les ensembles convexes et les cônes à l’aide de notations formelles de combinaison.
• Identifier et représenter des ensembles convexes standards tels que les boules euclidiennes, les ellipsoïdes, les polyèdres et le cône semi-défini positif.
• Appliquer des opérations préservant la convexité, telles que l’intersection, les transformations affines et les fonctions perspective, pour vérifier les propriétés des ensembles.

🔹 Leçon 3 : Fonctions convexes et propriétés

Aperçu : Cette leçon explore des opérations avancées préservant la convexité, telles que les supremums ponctuels et des règles de composition spécifiques, et introduit la fonction conjuguée de Lagrange. Elle étend le concept de convexité aux fonctions quasi-convexes et log-concaves, tout en examinant la convexité par rapport aux inégalités généralisées et aux propriétés matricielles spécifiques comme le complément de Schur. Ces concepts forment la base mathématique pour identifier et formuler des problèmes d’optimisation complexes.

Objectifs d'apprentissage :

• Identifier et appliquer des opérations préservant la convexité, notamment le supremum ponctuel de fonctions affines et les règles de composition vectorielle.
• Dériver le conjugué de Lagrange de diverses fonctions et appliquer l’inégalité de Young.
• Caractériser la quasi-convexité à l’aide des ensembles de sous-niveau et des conditions différentielles du premier et second ordre.

🔹 Leçon 4 : Formulation des problèmes d’optimisation convexe

Aperçu : Cette leçon traite de la structure formelle et de la transformation des problèmes d’optimisation convexe, allant des formes standards et des conditions d’optimalité aux classes spécifiques de problèmes comme la Programmation Linéaire (PL), la Programmation Quadratique (PQ) et la Programmation Semi-Définie (PSD). Les étudiants apprendront à identifier l’optimalité globale, à utiliser la méthode de dichotomie pour les problèmes quasi-convexes, et à appliquer la scalarisation à l’optimisation multicroîtante vectorielle.

Objectifs d'apprentissage :

• Formuler et transformer : convertir des problèmes d’optimisation bruts en formes convexes standards à l’aide de variables de marge et de l’élimination de contraintes.
• Analyser l’optimalité : appliquer le critère d’optimalité basé sur le gradient pour déterminer si un point est globalement optimal.
• Classifier et résoudre : distinguer entre PL, PQ, SOCP, GP et PSD, et appliquer des méthodes spécialisées comme la Méthode de Dichotomie pour les fonctions quasi-convexes.

🔹 Leçon 5 : Dualité de Lagrange et conditions KKT

Aperçu : Cette leçon explore la théorie fondamentale de la dualité de Lagrange, passant de la définition de la fonction duale de Lagrange à la formulation du problème dual. Elle couvre l’écart critique entre les valeurs optimales primales et duales, les interprétations géométriques et jeux théoriques de ces relations, et les conditions de Karush-Kuhn-Tucker (KKT) qui caractérisent les solutions optimales. Enfin, la leçon étend ces concepts à l’analyse de sensibilité et aux prix ombres.

Objectifs d'apprentissage :

• Dériver la fonction duale de Lagrange et formuler le problème dual pour divers problèmes d’optimisation.
• Évaluer la relation entre les problèmes primal et dual à l’aide de la dualité faible/forte et de la condition de qualification de Slater.
• Appliquer les conditions d’optimalité KKT pour résoudre et vérifier les solutions optimales de problèmes convexes et non convexes.

🔹 Leçon 6 : Approximation, ajustement et régularisation

Aperçu : Cette leçon explore les fondements mathématiques et les applications pratiques de l’approximation des solutions à des systèmes d’équations linéaires et de l’ajustement de fonctions aux données. Elle couvre l’approximation basée sur les normes, incluant les fonctions de pénalité et la régularisation pour gérer les points aberrants et la parcimonie, ainsi que les techniques d’optimisation robuste pour traiter l’incertitude des données. Elle détaille également l’ajustement de fonctions sous des contraintes spécifiques telles que la convexité et la monotonie.

Objectifs d'apprentissage :

• Formuler et résoudre des problèmes d’approximation de norme, et interpréter les différences géométriques et statistiques entre les approches des moindres carrés, de Chebyshev et de L1.
• Concevoir et implémenter des modèles d’approximation régularisée afin d’obtenir un compromis entre l’erreur résiduelle, la grandeur de la solution et la parcimonie.
• Construire des cadres d’approximation robuste prenant en compte les incertitudes dans la matrice de données.

🔹 Leçon 7 : Estimation et inférence statistiques

Aperçu : Cette leçon explore l’intersection entre l’inférence statistique et l’optimisation convexe. Elle se concentre sur la formulation de problèmes d’estimation — y compris la vraisemblance maximale, l’estimation non paramétrique de distribution et la conception optimale de détecteurs — sous forme de programmes convexes. Les étudiants apprendront à utiliser l’optimisation pour trouver des paramètres et concevoir des expériences informatives.

Objectifs d'apprentissage :

• Formuler et résoudre des problèmes d’estimation de vraisemblance maximale (MLE) et de régression logistique comme des tâches d’optimisation convexe.
• Concevoir des détecteurs optimaux à l’aide de la programmation linéaire (PL) et interpréter les caractéristiques de réception des opérateurs (ROC).
• Appliquer des techniques d’estimation non paramétrique, notamment le principe de maximum d’entropie et la minimisation de la divergence de Kullback-Leibler.

🔹 Leçon 8 : Problèmes géométriques et classification

Aperçu : Cette leçon explore l’application de l’optimisation convexe aux problèmes géométriques, y compris la projection de points sur des ensembles, le calcul des distances entre ensembles et la caractérisation des centres d’ensembles. Elle étend également ces principes géométriques à des tâches du monde réel telles que la classification linéaire et non linéaire, le placement optimal d’installations et la planification de planchers à l’aide de la programmation géométrique.

Objectifs d'apprentissage :

• Formuler et résoudre des problèmes de projection et de distance entre des ensembles convexes en utilisant les conditions KKT et les représentations duales.
• Approcher des ensembles convexes complexes à l’aide d’ellipsoïdes de volume extrémal et identifier leurs facteurs d’efficacité.
• Calculer divers centres d’ensembles et les appliquer à la discrimination et à la classification robustes.

🔹 Leçon 9 : Algorithmes d’optimisation sans contraintes

Aperçu : Cette leçon couvre les fondements théoriques et les implémentations algorithmiques de l’optimisation sans contraintes pour les fonctions convexes. Elle détaille les méthodes de descente allant du Gradient à première ordre jusqu’au Méthode de Newton à second ordre. Une grande partie est consacrée à l’analyse de convergence, mettant l’accent sur la convexité forte et la théorie affine-invariante de l’autosimilarité.

Objectifs d'apprentissage :

• Définir la convexité forte et exploiter ses implications pour établir des bornes supérieures sur l’erreur de sous-optimalité et la distance vers l’optimum.
• Comparer et contraster le Gradient Descendant avec la Descente la plus raide sous les normes euclidienne, quadratique et L1.
• Calculer l’étape de Newton et le décrochement de Newton, expliquant pourquoi la méthode de Newton est affine-invariante.

🔹 Leçon 10 : Optimisation sous contraintes d’égalité

Aperçu : Cette leçon explore les méthodes de résolution des problèmes d’optimisation convexes avec des contraintes d’égalité linéaires. Elle se concentre sur la dérivation et l’implémentation de l’étape de Newton, compare les méthodes à départ réalisable et à départ irréalisable, et interprète ces étapes dans un cadre primal-duel. Une attention particulière est portée à l’implémentation numérique efficace via l’élimination par blocs du système KKT.

Objectifs d'apprentissage :

• Calculer et interpréter l’étape de Newton et son décrochement pour les problèmes sous contraintes d’égalité.
• Démontrer l’équivalence entre la méthode de Newton avec contraintes d’égalité et l’élimination de ces contraintes.
• Implémenter la méthode de Newton à départ irréalisable et expliquer sa propriété de réduction du résidu primal-duel.

🔹 Leçon 11 : Méthodes de points intérieurs

Aperçu : Cette leçon traite des méthodes de points intérieurs, qui résolvent les problèmes d’optimisation convexes avec des contraintes d’inégalité en appliquant la méthode de Newton à une séquence de problèmes sous contraintes d’égalité. Le cœur du sujet concerne les fonctions barrières logarithmiques, le tracé d’une trajectoire centrale menant vers la solution optimale, et l’utilisation de cadres primal-duel pour améliorer l’efficacité et la robustesse.

Objectifs d'apprentissage :

• Définir et construire des fonctions barrières logarithmiques, et caractériser la trajectoire centrale et ses points duaux associés.
• Implémenter la méthode barrière, y compris le compromis entre les étapes de centrage et les itérations externes.
• Formuler et résoudre les problèmes de phase I de faisabilité afin de trouver des points de départ strictement réalisables.