Leçon 405 — Convexité dans ℝⁿ. Théorèmes de séparation.
Points clés
Ensembles convexes : définition et exemples
Enveloppe convexe et points extrémaux
Projection sur un convexe fermé
Théorèmes de séparation par un hyperplan
Applications en optimisation
Plan
Ensembles convexes
Définition : [formule] convexe si [formule]
Exemples : boules, demi-espaces, polyèdres, épigraphes de fonctions convexes
Opérations : intersection, somme de Minkowski, image par application linéaire
Enveloppe convexe
Définition : plus petit convexe contenant un ensemble [formule]
Théorème de Carathéodory : dans [formule], tout point de [formule] est barycentre de [formule] points de [formule]
Points extrémaux : [formule] est extrémal s'il n'est milieu d'aucun segment inclus dans [formule]
Projection sur un convexe fermé
Théorème de projection : pour tout [formule] et tout convexe fermé non vide [formule], il existe un unique [formule] minimisant [formule]
Caractérisation : [formule] ssi [formule] pour tout [formule]
Le projecteur [formule] est [formule]-lipschitzien
Théorèmes de séparation
Hyperplan séparant : [formule] et [formule] sont séparés par [formule] si [formule] et [formule]
Théorème de séparation faible : deux convexes disjoints dont l'un est compact peuvent être strictement séparés
Théorème de Hahn-Banach géométrique : un convexe fermé et un point extérieur sont strictement séparés par un hyperplan
Théorème de Krein-Milman
Énoncé : tout convexe compact non vide est l'enveloppe convexe fermée de ses points extrémaux
Application : la boule unité de [formule] (norme euclidienne) a pour points extrémaux la sphère
Application : description des matrices bistochastiques (théorème de Birkhoff)
Applications
Programmation linéaire : l'optimum est atteint en un sommet du polyèdre
Inégalité de Jensen pour les fonctions convexes
Dualité en optimisation convexe
Théorèmes clés
Théorème de Carathéodory : dans [formule], tout point de [formule] s'écrit comme combinaison convexe d'au plus [formule] points de [formule]
Théorème de séparation stricte : si [formule] est un convexe fermé de [formule] et [formule], il existe un hyperplan séparant strictement [formule] et [formule]
Théorème de Krein-Milman : tout convexe compact non vide de [formule] est l'enveloppe convexe de ses points extrémaux
Théorème de Birkhoff : les points extrémaux de l'ensemble des matrices bistochastiques sont les matrices de permutation
Exemples importants
Enveloppe convexe de [formule] points en position générale dans [formule] : simplexe
Projection sur un sous-espace affine : projection orthogonale classique
Boule unité de [formule] : points extrémaux [formule]
Théorème de Birkhoff : matrice doublement stochastique = combinaison convexe de matrices de permutation
Erreurs courantes
Confondre séparation faible et séparation stricte
Oublier l'hypothèse de compacité dans Krein-Milman
Appliquer la projection sans vérifier que le convexe est fermé
Conseils du jury
Le théorème de Krein-Milman est un développement apprécié
Savoir appliquer le théorème de séparation pour démontrer d'autres résultats (Farkas, programmation linéaire)
Le jury attend une bonne connaissance des exemples géométriques