Leçon 1 sur 5
Convexité des ensembles et des fonctions
Je sais reconnaître un ensemble convexe et une fonction convexe sur ℝⁿ, utiliser les caractérisations par le gradient et la matrice hessienne, et expliquer pourquoi la convexité est la propriété clé de l'optimisation.
- 1 h 10
- 4 exercices corrigés
- QCM de 5 questions
À la fin de la leçon, vous saurez :
- Définir et reconnaître un ensemble convexe, montrer qu'une intersection de convexes est convexe
- Définir une fonction convexe, strictement convexe, et son épigraphe
- Utiliser la caractérisation du premier ordre (tangente sous le graphe)
- Utiliser la caractérisation du second ordre (hessienne semi-définie positive)
- Énoncer le théorème : pour une fonction convexe, tout minimum local est global
Avant de commencer : Calcul différentiel de L1-L2 (dérivées partielles, gradient, développement de Taylor) ; algèbre linéaire (formes quadratiques, valeurs propres d'une matrice symétrique).
1Je découvre
Une coopérative maraîchère de Kindia veut placer un point de collecte pour trois villages. Elle cherche l'emplacement qui minimise la somme des distances de transport. Un étudiant teste plusieurs points au hasard et trouve un « creux » de la fonction coût ; un autre trouve un point différent, un peu meilleur. Comment être sûr qu'il n'en existe pas de bien meilleur ailleurs ?
Dans d'autres problèmes (choisir la production de deux cultures sous une contrainte de surface, ajuster une droite à des mesures), la même inquiétude revient : un minimum trouvé est-il le minimum ?
Quelle propriété des ensembles et des fonctions garantit qu'un minimum local est en réalité le minimum global ?
2Je comprends
1. Les ensembles convexes
Une partie C de ℝn est convexe si, pour tous x, y ∈ C et tout λ ∈ [0, 1] :
λ x + (1 - λ) y ∈ C
Autrement dit, le segment [x, y] est entièrement contenu dans C.
Exemples. Un sous-espace vectoriel, un demi-espace { x : aT x ≤ b }, une boule (pour toute norme), un hyperplan sont convexes. Un disque est convexe ; une couronne (disque troué) ne l'est pas.
Propriété. Une intersection (quelconque) d'ensembles convexes est convexe. Conséquence : un polyèdre { x : Ax ≤ b }, intersection de demi-espaces, est convexe. Les ensembles de contraintes linéaires de l'économie (budget, surface, capacité) sont donc convexes.
Attention : la réunion de deux convexes n'est pas convexe en général (deux disques disjoints).
Exemple résolu. C = { (x, y) : x2 + y2 ≤ 4, x + y ≥ 1 } est convexe : c'est l'intersection d'un disque fermé et d'un demi-plan, tous deux convexes.
2. Les fonctions convexes
Soit C convexe et f : C → ℝ. La fonction f est convexe si pour tous x, y ∈ C, λ ∈ [0,1] :
f(λ x + (1-λ) y) ≤ λ f(x) + (1 - λ) f(y)
Géométriquement, la corde est au-dessus du graphe. Elle est strictement convexe si l'inégalité est stricte pour x ≠ y et λ ∈ ]0,1[. f est concave si -f est convexe.
L'épigraphe de f est { (x, t) : x ∈ C, t ≥ f(x) } : f est convexe si et seulement si son épigraphe est convexe.
Opérations qui préservent la convexité.
- somme de fonctions convexes ; produit par un réel positif ;
- maximum d'une famille de fonctions convexes ;
- composée g ∘ f avec f convexe et g convexe croissante ;
- composée avec une application affine : x ↦ f(Ax + b).
Exemples de référence. Fonctions affines (convexes et concaves) ; x ↦ x2, ex, -ln x sur ]0, +∞[ ; toute norme ; x ↦ ‖ x ‖2.
Lien avec les ensembles. Si f est convexe, ses sous-niveaux { x : f(x) ≤ α } sont convexes. (La réciproque est fausse.)
3. Caractérisation du premier ordre
Si f est différentiable sur un ouvert convexe C, alors f est convexe si et seulement si, pour tous x, y ∈ C :
f(y) ≥ f(x) + ∇ f(x)T (y - x)
Le graphe est au-dessus de ses plans tangents. Conséquence capitale : si ∇ f(x^*) = 0, alors f(y) ≥ f(x^*) pour tout y : tout point critique d'une fonction convexe est un minimum global.
4. Caractérisation du second ordre
Si f est de classe C2 sur un ouvert convexe C, de hessienne ∇2 f(x) (matrice des dérivées secondes) :
- f est convexe si et seulement si ∇2 f(x) est semi-définie positive pour tout x ∈ C ;
- si ∇2 f(x) est définie positive pour tout x, alors f est strictement convexe (la réciproque est fausse : x ↦ x4 est strictement convexe mais f''(0) = 0).
Tester une matrice symétrique 2 × 2 H de coefficients a, b (première ligne) et b, c (deuxième ligne) :
- définie positive ⇔ a > 0 et ac - b2 > 0 ;
- semi-définie positive ⇔ a ≥ 0, c ≥ 0 et ac - b2 ≥ 0.
En dimension quelconque : valeurs propres toutes ≥ 0 (ou > 0), ou critère des mineurs principaux.
Exemple résolu. f(x, y) = x2 + xy + y2 - 3x. Hessienne constante :
| H | colonne 1 | colonne 2 |
|---|---|---|
| ligne 1 | 2 | 1 |
| ligne 2 | 1 | 2 |
a = 2 > 0 et ac - b2 = 4 - 1 = 3 > 0 : H est définie positive, f est strictement convexe sur ℝ2.
Fonction quadratique. f(x) = 12 xT Q x + cT x avec Q symétrique : ∇2 f = Q, donc f est convexe ⇔ Q semi-définie positive.
5. Pourquoi la convexité est essentielle
Théorème. Soit C convexe et f convexe sur C.
- Tout minimum local de f sur C est un minimum global.
- L'ensemble des minimiseurs est convexe.
- Si f est strictement convexe, le minimiseur, s'il existe, est unique.
Idée de preuve de 1. Si x^* est minimum local et f(y) < f(x^*), alors pour λ petit, z = x^* + λ (y - x^*) est proche de x^* et f(z) ≤ (1-λ) f(x^) + λ f(y) < f(x^) : contradiction.
Existence. La convexité ne garantit pas l'existence (ex sur ℝ n'a pas de minimum). On utilise par exemple : f continue sur un compact non vide (Weierstrass), ou f continue et coercive (f(x) → +∞ quand ‖ x ‖ → +∞) sur un fermé.
Retour au cas de Kindia. La somme des distances x ↦ Σ ‖ x - ai ‖ est une somme de normes, donc convexe : un minimum local trouvé est global. Les deux étudiants ont seulement mal convergé.
3Je retiens
Je retiens
C est convexe si le segment entre deux points quelconques de C reste dans C ; une intersection de convexes est convexe.
f est convexe si la corde est au-dessus du graphe : f(λx + (1−λ)y) ≤ λf(x) + (1−λ)f(y).
Premier ordre : f(y) ≥ f(x) + ∇f(x)ᵀ(y − x) ; le graphe est au-dessus de ses tangentes.
Second ordre : f convexe ⟺ hessienne semi-définie positive en tout point.
Hessienne définie positive partout ⟹ strictement convexe (réciproque fausse).
Pour f convexe : point critique = minimum global, minimum local = minimum global.
Strictement convexe : au plus un minimiseur ; l'existence demande compacité ou coercivité.
4Erreurs fréquentes
- Croire que la réunion de deux convexes est convexe : seule l'intersection l'est.
- Conclure « strictement convexe ⟹ hessienne définie positive » : x ↦ x⁴ est un contre-exemple en 0.
- Tester seulement les termes diagonaux de la hessienne : il faut aussi le déterminant (ou les valeurs propres).
- Oublier que la convexité garantit l'unicité (si stricte) mais pas l'existence d'un minimum.
- Composer deux fonctions convexes sans vérifier que la fonction extérieure est croissante.
5Je m’exerce
1Exercice 1
(Questions de cours) a) Définissez un ensemble convexe et une fonction convexe. b) Montrez que l'intersection de deux convexes est convexe. c) Donnez un exemple de fonction strictement convexe dont la dérivée seconde s'annule.
Voir le corrigéCacher le corrigé
a) Voir les définitions des parties 1 et 2. b) Soient C1, C2 convexes et x, y ∈ C1 ∩ C2, λ ∈ [0,1]. Le point λ x + (1-λ) y est dans C1 (car C1 convexe) et dans C2, donc dans C1 ∩ C2. c) f(x) = x4 : strictement convexe sur ℝ et f''(0) = 0.
2Exercice 2
Les ensembles suivants sont-ils convexes ? Justifiez. a) A = { (x,y) : y ≥ x2 }. b) B = { (x,y) : xy ≥ 1 }. c) D = { (x,y) : x ≥ 0, y ≥ 0, 2x + 3y ≤ 12 }.
Voir le corrigéCacher le corrigé
a) Oui : c'est l'épigraphe de x ↦ x2, fonction convexe. b) Non : (1, 1) et (-1, -1) sont dans B, mais leur milieu (0, 0) vérifie 0 · 0 = 0 < 1. c) Oui : intersection de trois demi-plans (polyèdre), donc convexe.
3Exercice 3
Étudiez la convexité sur ℝ2 de : a) f(x,y) = 3x2 + 2xy + y2 + 4y ; b) g(x,y) = x2 - 4xy + y2 ; c) h(x,y) = ex+y + x2.
Voir le corrigéCacher le corrigé
a) Hessienne de lignes (6, 2) et (2, 2) : 6 > 0 et 12 - 4 = 8 > 0, définie positive : strictement convexe. b) Hessienne de lignes (2, -4) et (-4, 2) : déterminant 4 - 16 = -12 < 0, valeurs propres de signes opposés : ni convexe ni concave (point selle en 0). c) (x,y) ↦ ex+y est la composée de l'exponentielle (convexe, croissante) et d'une application linéaire : convexe ; x2 est convexe ; la somme est convexe. (Hessienne : lignes (ex+y + 2, ex+y) et (ex+y, ex+y), déterminant 2ex+y > 0 : elle est même strictement convexe.)
4Exercice 4
(Type examen) Soit f(x,y) = x2 + 2y2 - 2xy - 2x + 6. a) Calculez le gradient et la hessienne. b) Montrez que f est strictement convexe. c) Déterminez son unique point critique. d) Justifiez que c'est le minimum global et calculez la valeur minimale. e) L'ensemble { (x,y) : f(x,y) ≤ 10 } est-il convexe ? Justifiez.
Voir le corrigéCacher le corrigé
a) ∇ f = (2x - 2y - 2, 4y - 2x). Hessienne de lignes (2, -2) et (-2, 4). b) 2 > 0 et 8 - 4 = 4 > 0 : définie positive en tout point, donc f strictement convexe. c) 4y - 2x = 0 ⇒ x = 2y ; 2(2y) - 2y - 2 = 0 ⇒ y = 1, x = 2. Point critique (2, 1). d) f convexe et ∇ f(2,1) = 0 : minimum global (unique car stricte convexité). f(2,1) = 4 + 2 - 4 - 4 + 6 = 4. e) Oui : c'est un sous-niveau d'une fonction convexe.
Cherchez d’abord seul, sur votre cahier, puis ouvrez le corrigé pour comparer.
6Je vérifie
Choisissez une réponse pour chaque question : la correction s’affiche aussitôt.
Karamö, votre enseignant
Il a lu cette leçon. Posez-lui votre question : il vous répond ici.
Connectez-vous pour poser vos questions à Karamö.
Avec un compte Kharandi gratuit, vous cochez les leçons terminées et vous suivez votre progression, cours par cours.