Aller au contenu
Optimisation 1 · L2

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 :

Hcolonne 1colonne 2
ligne 121
ligne 212

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.

  1. Tout minimum local de f sur C est un minimum global.
  2. L'ensemble des minimiseurs est convexe.
  3. 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.

1Lequel de ces ensembles n'est pas convexe en général ?
Voir la réponse

Réponse B : la réunion de deux convexes. Deux disques disjoints forment une réunion non convexe.

2Une fonction de classe C² est convexe sur un ouvert convexe si et seulement si sa hessienne est :
Voir la réponse

Réponse B : semi-définie positive en tout point. C'est la caractérisation du second ordre.

3Pour une fonction convexe différentiable, un point où le gradient s'annule est :
Voir la réponse

Réponse C : un minimum global. Le graphe est au-dessus de son plan tangent horizontal.

4La matrice de lignes (1, 2) et (2, 1) est :
Voir la réponse

Réponse B : indéfinie. Son déterminant vaut 1 − 4 = −3 < 0.

5Une fonction strictement convexe possède :
Voir la réponse

Réponse B : au plus un minimiseur. L'existence n'est pas garantie (exemple : eˣ).

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ö.

Vous avez fini la leçon ?

Avec un compte Kharandi gratuit, vous cochez les leçons terminées et vous suivez votre progression, cours par cours.

Karamö
Un point pas clair ? Dites à Karamö ce qui vous bloque dans cette leçon : il vous l’explique autrement, pas à pas, sans faire le travail à votre place. Demander à Karamö
Signaler une erreur dans cette leçon

Toutes les leçons de Optimisation 1

Pose ta question à Karamö