Optimisation Convexe

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.