Partie Convexité PDF [PDF]

Zitiervorschau

Ensembles et fonctions convexes

1

Ensemble convexes • Définition : Etant donné deux points 𝑥, , ∈ ℝ𝑛 , la droite passante par 𝑥 et 𝑦 est définie par l’ensemble 𝑧 ∈ ℝ𝑛 : 𝑧 = 𝜃𝑥 + 1 − 𝜃 𝑦, 𝜃 ∈ ℝ𝑛

• Définition : Etant donné deux points 𝑥, 𝑦 ∈ ℝ𝑛 , le segment de droite reliant 𝑥 et 𝑦 est définie par l’ensemble: ℑ 𝑥, 𝑦 = 𝑧 ∈ ℝ𝑛 : 𝑧 = 𝜃𝑥 + 1 − 𝜃 𝑦, 𝜃 ∈ 0,1

𝑦

𝑥

𝑦

ℑ(𝑥, 𝑦) 𝑥

• Définition : Un ensemble 𝑋 ⊂ ℝ𝑛 est convexe si pour toute paire de points 𝑥, 𝑦 ∈ 𝑋, le segment de droite ℑ 𝑥, 𝑦 ⊂ 𝑋.

Ensemble convexes

Ensemble non convexes

2

Fonctions convexes Définition : Etant donné un ensemble convexe 𝑋 ⊂ ℝ𝑛 ,une fonction à valeur Réelles 𝑓: 𝑋 → ℝ est convexe si pour toute paire de points 𝑥, 𝑦 ∈ 𝑋 𝑓 𝜃𝑥 + 1 − 𝜃 𝑦 ≤ 𝜃𝑓 𝑥 + 1 − 𝜃 𝑓 𝑦 , ∀𝜃 ∈ 0,1 𝜃𝑓(𝑥) + 1 − 𝜃 𝑓(𝑦)

𝑓(𝑥)

h𝑓 𝜃𝑥 + 1 − 𝜃 𝑦

𝑥

𝑦

𝜃𝑥 + 1 − 𝜃 𝑦 3

Fonctions convexes • Définition : Etant donné un ensemble convexe 𝑋 ⊂ ℝ𝑛 , une fonction à valeur réelles 𝑓: 𝑋 → ℝ est strictement convexe si pour toute paire de points 𝑥, 𝑦 ∈ 𝑋 𝑓 𝜃𝑥 + 1 − 𝜃 𝑦 < 𝜃𝑓 𝑥 + 1 − 𝜃 𝑓 𝑦 , ∀𝜃 ∈ (0,1) • Définition : Etant donné un ensemble convexe 𝑋 ⊂ ℝ𝑛 , une fonction à valeur réelles 𝑓: 𝑋 → ℝ est :

• concave si pour toute paire de points 𝑥, 𝑦 ∈ 𝑋 𝑓 𝜃𝑥 + 1 − 𝜃 𝑦 ≥ 𝜃𝑓 𝑥 + 1 − 𝜃 𝑓 𝑦 ,

∀𝜃 ∈ 0,1

• strictement concave si pour toute paire de points 𝑥, 𝑦 ∈ 𝑋 𝑓 𝜃𝑥 + 1 − 𝜃 𝑦 > 𝜃𝑓 𝑥 + 1 − 𝜃 𝑓 𝑦 , ∀𝜃 ∈ 0,1

• Donc 𝑓 est concave si −𝑓 est convexe

4

Fonctions convexes • Proposition 4.1 : soit 𝑋 ⊂ ℝ𝑛 un ensemble convexe, si 𝑓: 𝑋 → ℝ est convexe, alors l’ensemble 𝑋𝑓 𝜉 = 𝑥 ∈ 𝑋: 𝑓 𝑥 ≤ 𝜉 Est convexe pour tout 𝜉 ∈ ℝ

• Preuve : Soient 𝑥 et 𝑦 ∈ 𝑋𝑓 (𝜉) et 𝜃 ∈ (0,1). Alors, puisque 𝑓 est convexe, 𝑓 𝜃𝑥 + 1 − 𝜃 𝑦 ≤ 𝜃𝑓 𝑥 + 1 − 𝜃 𝑓 𝑦 ≤ 𝜃𝜉 + 1 − 𝜃 𝜉 = 𝜉 Ce qui implique que 𝜃𝑥 + 1 − 𝜃 𝑦 ∈ 𝑋𝑓 𝜉 . Donc 𝑋𝑓 (𝜉) est convexe la réciproque n’est vraie 𝑋(𝜉) convexe mais 𝑓 n’est pas convexe





𝑋𝑓 𝜉

𝑋𝑓 𝜉

5

Fonctions convexes • Proposition 4.1 : soit 𝑋 ⊂ ℝ𝑛 un ensemble convexe, si 𝑓: 𝑋 → ℝ est convexe, alors l’ensemble 𝑋𝑓 𝜉 = 𝑥 ∈ 𝑋: 𝑓 𝑥 ≤ 𝜉 Est convexe pour tout 𝜉 ∈ ℝ

• Preuve : Soient 𝑥 et 𝑦 ∈ 𝑋𝑓 (𝜉) et 𝜃 ∈ (0,1). Alors, puisque 𝑓 est convexe, 𝑓 𝜃𝑥 + 1 − 𝜃 𝑦 ≤ 𝜃𝑓 𝑥 + 1 − 𝜃 𝑓 𝑦 ≤ 𝜃𝜉 + 1 − 𝜃 𝜉 = 𝜉 Ce qui implique que 𝜃𝑥 + 1 − 𝜃 𝑦 ∈ 𝑋𝑓 𝜉 . Donc 𝑋𝑓 (𝜉) est convexe la réciproque n’est vraie 𝑋(𝜉) convexe mais 𝑓 n’est pas convexe





𝑋𝑓 𝜉

𝑋𝑓 𝜉

6

Fonctions convexes • Proposition 4.1 : soit 𝑋 ⊂ ℝ𝑛 un ensemble convexe, si 𝑓: 𝑋 → ℝ est convexe, alors l’ensemble 𝑋𝑓 𝜉 = 𝑥 ∈ 𝑋: 𝑓 𝑥 ≤ 𝜉 Est convexe pour tout 𝜉 ∈ ℝ

• Preuve : Soient 𝑥 et 𝑦 ∈ 𝑋𝑓 (𝜉) et 𝜃 ∈ (0,1). Alors, puisque 𝑓 est convexe, 𝑓 𝜃𝑥 + 1 − 𝜃 𝑦 ≤ 𝜃𝑓 𝑥 + 1 − 𝜃 𝑓 𝑦 ≤ 𝜃𝜉 + 1 − 𝜃 𝜉 = 𝜉 Ce qui implique que 𝜃𝑥 + 1 − 𝜃 𝑦 ∈ 𝑋𝑓 𝜉 . Donc 𝑋𝑓 (𝜉) est convexe la réciproque n’est vraie 𝑋(𝜉) convexe mais 𝑓 n’est pas convexe

 

𝑋𝑓 𝜉

𝑋𝑓 𝜉

7

Fonctions convexes • Proposition 4.2 : soit 𝑋 ⊂ ℝ𝑛 , si 𝑓𝑖 : 𝑋 → ℝ est convexe pour 𝑖 = 1, … , 𝑚 et si 𝜆1 , … , 𝜆𝑚 sont des scalaires non négatifs, alors 𝑓 𝑥 = σ𝑚 𝑖=1 𝜆𝑖 𝑓𝑖 𝑥 est convexe sur 𝑋.

• Preuve : Pour toute paire de points 𝑥, 𝑦 ∈ 𝑋 et pour tout 𝜃 ∈ 0,1 𝑚

𝑓 𝜃𝑥 + 1 − 𝜃 𝑦 = ෍ 𝜆𝑖 𝑓𝑖 𝜃𝑥 + 1 − 𝜃 𝑦 𝑖=1 𝑚

≤ ෍ 𝜆𝑖 𝜃𝑓𝑖 𝑥 + 1 − 𝜃 𝑦 puisque 𝑓𝑖 convexe et 𝜆𝑖 ≥ 0 𝑖=1 𝑚

𝑚

= 𝜃 ෍ 𝜆𝑖 𝑓𝑖 𝑥 + 1 − 𝜃 ෍ 𝜆𝑖 𝑓𝑖 𝑦 𝑖=1

𝑖=1

= 𝜃𝑓 𝑥 + 1 − 𝜃 𝑓 𝑦 8

Fonctions convexes • Proposition 4.3 : Soit 𝑋 ⊂ ℝ𝑛 un ensemble convexe. Si 𝑓: 𝑋 → ℝ est convexe, Si 𝑥 1 , … , 𝑥 𝑚 ∈ 𝑋, et si 𝜆1 , … , 𝜆𝑚 sont des scalaires non négatifs tels que σ𝑚 𝑖=1 𝜆𝑖 = 1, alors: 𝑚

𝑚

𝑓 ෍ 𝜆𝑖 𝑥 𝑖 ≤ ෍ 𝜆𝑖 𝑓(𝑥 𝑖 ) 𝑖=1

𝑖=1

• Preuve : • Si 𝑚 = 2 nous retrouvons la définition de fonction convexe. Procédons par induction et supposons que le résultat est vrai pour (𝑚 − 1) ;

i.e., si 𝜃1 , … , 𝜃𝑚−𝑖 ≥ 0 sont tels que σ𝑚−1 𝑖=1 𝜃𝑖 = 1 , alors 𝑚−1 𝑖 𝑖 ≤ σ𝑚−1 𝜃 𝑓 𝑥 𝑖 σ𝑚−1 𝑖=1 𝜃𝑖 𝑥 ∈ 𝑋 et 𝑓 σ 𝑖=1 𝜃𝑖 𝑥 𝑖=1 𝑖 9

Fonctions convexes 𝜆

Ainsi posant 𝜃𝑖 = σ𝑚−1𝑖

𝑘=1 𝜆𝑘

𝑚−1

෍

on a

𝑚−1

𝜆𝑖

σ𝑚−1 𝜆 𝑖=1 𝑘=1 𝑘

𝜆𝑖 𝑥 𝑖 ෍ 𝑚−1 ∈ 𝑋, σ𝑘=1 𝜆𝑘

= 1,

𝑚−1

𝑓

𝑖=1

𝜆𝑖 𝑥 𝑖 ෍ 𝑚−1 σ𝑘=1 𝜆𝑘 𝑖=1

𝑚−1

𝜆𝑖 𝑓(𝑥 𝑖 ) ≤ ෍ 𝑚−1 σ𝑘=1 𝜆𝑘 𝑖=1

• par définition de convexité, 𝑚−1

𝑚−1

𝑘=1

𝑖=1

𝜆𝑖 𝑥 𝑖 ෍ 𝜆𝑘 ෍ 𝑚−1 + 𝜆𝑚 𝑥 𝑚 ∈ 𝑋 σ𝑘=1 𝜆𝑘

𝑓

𝑚−1

𝑚−1

𝑚−1

𝑚−1

𝑘=1

𝑖=1

𝑘=1

𝑖=1

𝜆𝑖 𝑥 𝑖 ෍ 𝜆𝑘 ෍ 𝑚−1 + 𝜆𝑚 𝑥 𝑚 ≤ ෍ 𝜆𝑘 𝑓 σ𝑘=1 𝜆𝑘 𝑚−1

𝑓

෍ 𝜆𝑖 𝑖=1

𝑥𝑖

+ 𝜆𝑚

𝑥𝑚

𝑚−1

𝑚−1

𝑘=1

𝑖=1

𝜆𝑖 𝑥 𝑖 ෍ 𝑚−1 + 𝜆𝑚 𝑓 𝑥 𝑚 σ𝑘=1 𝜆𝑘

𝜆𝑖 𝑓 𝑥 𝑖 ≤ ෍ 𝜆𝑘 ෍ 𝑚−1 + 𝜆𝑚 𝑓 𝑥 𝑚 σ𝑘=1 𝜆𝑘

10

Fonctions convexes • Proposition 4.4 : soit 𝑋 ⊂ ℝ𝑛 un ensemble convexe. 𝑓: 𝑋 → ℝ est convexe si et seulement si 𝜙 𝜆 = 𝑓 𝜆𝑥 + 1 − 𝜆 𝑦 est une fonction convexe sur 0,1 pour toute paire de points 𝑥, 𝑦 ∈ 𝑋. • Note : 𝜙(𝜆) dénote la restriction de 𝑓 sur le segment de droite entre 𝑥 et 𝑦.

𝜑(𝜆)

𝑦 0

𝑥 𝜆

1 11

Fonctions convexes Preuve : • pour démontrer la nécessité, considérons la paire de points 𝑥, 𝑦 ∈ 𝑋. • Soit 𝜆1 , 𝜆2 ∈ [0,1], alors : 𝜙 𝜃𝜆1 + 1 − 𝜃 𝜆2 = 𝜙 𝜆2 + 𝜃 𝜆1 − 𝜆2

= 𝑓 𝜆2 + 𝜃 𝜆1 − 𝜆2 𝑥 + 1 − 𝜆2 − 𝜃 𝜆1 − 𝜆2 𝑦 = 𝑓 𝜆2 + 𝜃 𝜆1 − 𝜆2 𝑥 + 1 + 𝜃 − 𝜃 − 𝜆2 − 𝜃 𝜆1 − 𝜆2 𝑦 = 𝑓 𝜃 𝜆1 𝑥 + 1 − 𝜆1 𝑦 + ( 1 − 𝜃 𝜆2 𝑥 + 1 − 𝜆2 𝑦 ≤ 𝜃𝑓 𝜆1 𝑥 + 1 − 𝜆1 𝑦 + 1 − 𝜃 𝑓 𝜆2 𝑥 + 1 − 𝜆2 𝑦 ≤ 𝜃𝜙 𝜆1 + 1 − 𝜃 𝜙 𝜆2

Donc 𝜙 est convexe sur 0,1

12

Fonctions convexes Preuve : • Pour démontrer la suffisance, considérons également la paire de points 𝑥, 𝑦 ∈ 𝑋. La fonction 𝜙 𝜃 = 𝑓 𝜃𝑥 + 1 − 𝜃 𝑦 étant convexe sur 0,1 𝜙 𝜃 = 𝜙 𝜃. 1 + 1 − 𝜃 0 ≤ 𝜃𝜙 1 + 1 − 𝜃 𝜙 0 Pour tout 𝜃 ∈ 0,1

• Alors 𝑓 𝜃𝑥 + 1 − 𝜃 𝑦 ≤ 𝜃𝑓 𝑥 + 1 − 𝜃 𝑓 𝑦 Pour tout 𝜃 ∈ 0,1 , Donc 𝑓 est convexe.

• La proposition suivante introduit une des propriétés qui rendent les fonctions convexes si intéressantes en programmation mathématique. 13

Fonctions convexes • Proposition 4.5 : Soit 𝑋 ⊂ ℝ𝑛 un ensemble convexe. Soit 𝑓: 𝑋 → ℝ une fonction convexe. Si 𝑥ҧ est un minimum local de 𝑓 sur 𝑋, alors 𝑥ҧ est un minimum global de 𝑓 sur 𝑋.

• Preuve : la preuve se fait par contradiction en supposant qu’il existe un point 𝑥෤ ∈ 𝑋 tel que 𝑓 𝑥෤ < 𝑓 𝑥ҧ . Puisque 𝑓 est convexe, 𝑓 𝜃 𝑥෤ + 1 − 𝜃 𝑥ҧ ≤ 𝜃𝑓 𝑥෤ + 1 − 𝜃 𝑓 𝑥ҧ < 𝜃𝑓 𝑥ҧ + 1 − 𝜃 𝑓 𝑥ҧ = 𝑓 𝑥ҧ

pour tout 𝜃 ∈ 0,1 . • Or pour 𝜃 > 0 suffisamment petit, 𝑥 𝜃 = 𝜃𝑥෤ + 1 − 𝜃 𝑥ҧ ∈ 𝑉𝜀 𝑥ҧ ∩ 𝑋 • Ainsi 𝑓 𝑥 𝜃

< 𝑓(𝑥)ҧ où 𝑥 𝜃 ∈ 𝑉𝜀 𝑥ҧ ∩ 𝑋, contredisant que 𝑥ҧ est

un minimum local de 𝑓 sur 𝑋. 14

Fonctions convexes • Proposition 4.6 : (inégalité du gradient). Soit 𝑋 ⊂ ℝ𝑛 un ensemble convexe. Soit 𝑓: 𝑋 → ℝ une fonction de classe 𝐶/𝑋. Alors 𝑓 est convexe sur 𝑋 si et seulement si 𝑓 𝑥 ≥ 𝑓 𝑦 + 𝛻𝑓 𝑦 𝑇 𝑥 − 𝑦 Pour toute paire de points 𝑥, 𝑦 ∈ 𝑋 • Preuve (nécessité) Soit 𝑓 convexe. Alors pour toute paire de points 𝑥, 𝑦 ∈ 𝑋 et pour tout 𝜃 ∈ 0,1 𝑓 𝜃𝑥 + 1 − 𝜃 𝑦 ≤ 𝜃𝑓 𝑥 + 1 − 𝜃 𝑓 𝑦 ce qui s’écrit aussi sous la forme 𝑓 𝑦+𝜃 𝑥−𝑦 −𝑓 𝑦 ≤ 𝜃 𝑓 𝑥 −𝑓 𝑦 4.1 Se référant au théorème de Taylor, il existe un 𝜏 ∈ 0,1 tel que 𝑓 𝑦+𝜃 𝑥−𝑦

= 𝑓 𝑦 + 𝛻𝑓 𝜏 𝑦 + 𝜃 𝑥 − 𝑦

𝑓 𝑦+𝜃 𝑥−𝑦

+ 1−𝜏 𝑦

− 𝑓 𝑦 = 𝜃𝛻𝑓 𝑦 + 𝜏𝜃 𝑥 − 𝑦

𝑇

𝑇

𝑦+𝜃 𝑥−𝑦 −𝑦

𝑥−𝑦

4.2 15

Fonctions convexes • La figure suivant illustre l’inégalité du gradient pour une fonction 𝑓: ℝ → ℝ dans ce cas l’inégalité du gradient devient

𝑓 𝑥 ≥ 𝑓 𝑦 + 𝑓′ 𝑦 𝑥 − 𝑦

𝑓(𝑥)

𝑔𝑦 𝑥 = 𝑓 𝑦 + 𝑓′(𝑦)(𝑥 − 𝑦) 𝑔𝑦 𝑥 = 𝑓 𝑦 + 𝑓 ′ 𝑦 𝑦 − 𝑦 = 𝑓(𝑦)

𝑔𝑦′ 𝑥 = 𝑓′ 𝑦 𝑔𝑦′ 𝑦 = 𝑓′(𝑦) y

x

• La droite 𝑔𝑦 𝑥 = 𝑓 𝑦 + 𝑓′(𝑦)(𝑥 − 𝑦) a les propriétés suivantes : 𝑔𝑦 𝑦 = 𝑓 𝑦 , 𝑔𝑦′ 𝑦 = 𝑓 ′ 𝑦 . • Ainsi la droite 𝑔𝑦 𝑥 = 𝑓 𝑦 + 𝑓′(𝑦)(𝑥 − 𝑦) prend la même valeur que 𝑓 Au point 𝑦 , et sa pente est la même que celle de 𝑓au point 𝑦. Cette droite Est donc une fonction support de 𝑓 au point 𝑦. • L’inégalité du gradient indique que la fonction prend toujours une valeur plus grande ou égale à celle de la fonction support en tout point 𝑦. 16

Fonctions convexes Preuve: 𝑓 𝑦+𝜃 𝑥−𝑦

−𝑓 𝑦 ≤ 𝜃 𝑓 𝑥 −𝑓 𝑦

4.1

• Combinant les relations 4.1 et 4.2 , pour tout 𝜃 ∈ 0,1 𝜃𝛻𝑓 𝑦 + 𝜏𝜃 𝑥 − 𝑦 𝑇 𝑥 − 𝑦 ≤ 𝜃 𝑓 𝑥 − 𝑓 𝑦 • Si 𝜃 > 0, nous pouvons diviser par 𝜃 de chaque côté de l’inéquation et obtenir 𝛻𝑓 𝑦 + 𝜏𝜃 𝑥 − 𝑦 𝑇 𝑥 − 𝑦 ≤ 𝑓 𝑥 − 𝑓 𝑦 pour tout 𝜃 ∈ 0,1 . • Par conséquent, en prenant la limite quand 𝜃 → 0 Nous obtenons lim 𝛻𝑓 𝑦 + 𝜏𝜃 𝑥 − 𝑦 𝑇 𝑥 − 𝑦 ≤ lim 𝑓 𝑥 − 𝑓 𝑦 𝜃→0 𝜃→0 Ou encore 𝛻𝑓 𝑦 + lim 𝜏𝜃 𝑥 − 𝑦 𝜃→0

𝑇

𝑥−𝑦 ≤ 𝑓 𝑥 −𝑓 𝑦

𝑓 𝑥 ≥ 𝑓 𝑦 + 𝛻𝑓 𝑦

𝑇

𝑥−𝑦 17

Fonctions convexes Preuve suffisance • Démontrons maintenant que la condition est suffisante.

• Puisque 𝑓 𝑥 ≥ 𝑓 𝑦 + 𝛻𝑓 𝑦 𝑇 (𝑥 − 𝑦) pour toute paire de points 𝑥, 𝑦 ∈ 𝑋 𝑓 𝑥 ≥ 𝑓 𝜃𝑥 + 1 − 𝜃 𝑦 + 𝛻𝑓 𝜃𝑥 + 1 − 𝜃 𝑦

𝑇

𝑥 − 𝜃𝑥 − 1 − 𝜃 𝑦

4.3

𝑓 𝑦 ≥ 𝑓 𝜃𝑥 + 1 − 𝜃 𝑦 + 𝛻𝑓 𝜃𝑥 + 1 − 𝜃 𝑦

𝑇

𝑦 − 𝜃𝑥 − 1 − 𝜃 𝑦

4.4

• (4.3) et 4.4 s’écrivent respectivement 𝑓 𝑥 ≥ 𝑓 𝜃𝑥 + 1 − 𝜃 𝑦 + 1 − θ 𝛻𝑓 𝜃𝑥 + 1 − 𝜃 𝑦

𝑇

𝑥−𝑦

4.3

𝑓 𝑦 ≥ 𝑓 𝜃𝑥 + 1 − 𝜃 𝑦 −

𝑇

𝑥−𝑦

4.4

𝜃

𝛻𝑓 𝜃𝑥 + 1 − 𝜃 𝑦

• Multiplions 4.3 par 𝜃 et 4.4 par 1 − 𝜃 𝜃𝑓 𝑥 ≥ 𝜃𝑓 𝜃𝑥 + 1 − 𝜃 𝑦 + 𝜃 1 − 𝜃 𝛻𝑓 𝜃𝑥 + 1 − 𝜃 𝑦 1 − 𝜃 𝑓 𝑦 ≥ 1 − 𝜃 𝑓 𝜃𝑥 + 1 − 𝜃 𝑦 − 1 − 𝜃 𝜃𝛻𝑓 𝜃𝑥 + 1 − 𝜃 𝑦

𝑇

𝑇

𝑥−𝑦 𝑥−𝑦

• Et additionnons les deux relations résultantes : 𝜃𝑓 𝑥 + 1 − 𝜃 𝑓 𝑦 ≥ 𝑓 𝜃𝑥 + 1 − 𝜃 𝑦

18

Fonctions convexes • Corollaire 4.7 : soit 𝑋 ⊂ ℝ𝑛 un ensemble convexe. Soit 𝑓: 𝑋 → ℝ une fonction convexe de classe 𝐶/𝑋. Alors si 𝛻𝑓 𝑥 ∗ 𝑇 𝑥 − 𝑥 ∗ ≥ 0 pour tout 𝑥 ∈ 𝑋, alors 𝑥 ∗ est un minimum global de 𝑓 sur 𝑋. • Preuve : le résultat découle directement de l’inégalité du gradient. En effet, puisque 𝑓 est convexe sur , alors 𝑓 𝑥 ≥ 𝑓 𝑥 ∗ + 𝛻𝑓 𝑥 ∗ 𝑇 𝑥 − 𝑥 ∗ • Pour tout 𝑥 ∈ 𝑋. Puisque par hypothèse 𝛻𝑓 𝑥 ∗ 𝑇 𝑥 − 𝑥 ∗ ≥ 0, alors 𝑓 𝑥 − 𝑓 𝑥 ∗ ≥ 𝛻𝑓 𝑥 ∗ 𝑇 𝑥 − 𝑥 ∗ ≥ 0 • D’où 𝑓 𝑥 ≥ 𝑓(𝑥 ∗ ) pour tout 𝑥 ∈ 𝑋. Donc 𝑥 ∗ est un minimum global de 𝑓 sur 𝑋. Conséquence : Si 𝛻𝑓 𝑥 ∗ = 0, alors 𝑥 ∗ est un minimum global de 𝑓 sur 𝑋. 19

Fonctions convexes • Pour les fonctions 𝑓 de classe 𝐶 2 , il existe un critère pour vérifier la convexité qui est basé sur le Hessien 𝛻 2 𝑓. • Proposition 𝟒. 𝟖 : • Soit 𝑋 ⊂ ℝ𝑛 un ensemble convexe dont l’intérieur est non vide.

• Soit 𝑓: 𝑋 → ℝ une fonction de classe 𝐶 2 /𝑋. • Alors 𝑓 est convexe sur 𝑋 si et seulement si son Hessien 𝛻 2 𝑓(𝑥) est une matrice semi défini positive pour tout 𝑥 ∈ 𝑋.

20

Hyperplan théorie de séparation Définition : • L’hyperplan spécifié par le point 𝑎 ∈ ℝ𝑛 et le scalaire 𝛽 est l’ensemble de ℝ𝑛 𝐻 𝑎, 𝛽 = 𝑥 ∈ ℝ𝑛 : 𝑎𝑇 𝑥 = 𝛽 • Les demis espaces (fermés) associés a l’hyperplan 𝐻 𝑎, 𝛽 sont les ensemble suivants de ℝ𝑛 : 𝐻 + 𝑎, 𝛽 = 𝑥 ∈ ℝ𝑛 : 𝑎𝑇 𝑥 ≥ 𝛽 𝐻 − 𝑎, 𝛽 = 𝑥 ∈ ℝ𝑛 : 𝑎𝑇 𝑥 ≤ 𝛽 • Note : il est facile de vérifier que tous ces ensembles 𝐻 + 𝑎, 𝛽

𝐻 𝑎, 𝛽 𝐻 − 𝑎, 𝛽 21

Hyperplan théorie de séparation • Définition Hyperplan de séparation • L’hyperplan 𝐻(𝑎, 𝛽) sépare deux ensembles non vides 𝑋 et 𝑌 si 𝑎𝑇 𝑥 ≥ 𝛽 pour tout 𝑥 ∈ 𝑋 (i.e., 𝑋 ⊂ 𝐻 + [𝑎, 𝛽]) 𝑎𝑇 𝑦 ≤ 𝛽 pour tout 𝑦 ∈ 𝑌 (i.e., 𝑌 ⊂ 𝐻 − [𝑎, 𝛽]) • La séparation est stricte si les inégalités dans les relations précédentes sont strictes. 𝐻(𝑎1 , 𝛽1 )

Y

𝐻(𝑎1 , 𝛽1 ) hyperplan de séparation

𝐻(𝑎2 , 𝛽2 ) hyperplan de séparation stricte

X

𝐻(𝑎 2 , 𝛽2 )

22

Hyperplan théorie de séparation • Définition étant donné un ensemble non vide 𝑋 ⊂ ℝ𝑛 l’hyperplan 𝐻 𝑎, 𝛽 est un support de 𝑋 si : • 𝐻 𝑎, 𝛽 ∩ 𝑋ത ≠ Φ et • 𝑋 ⊂ 𝐻 + 𝑎, 𝛽 ou 𝑋 ⊂ 𝐻 − 𝑎, 𝛽 (où 𝑋ത dénote la fermeture de l’ensemble 𝑋)

X 𝐻(𝑎, 𝛽) est support 23

Hyperplan théorie de séparation • Théorème 4.9 : Soient les vecteurs 𝑥, 𝑦, 𝑎 ∈ ℝ𝑛 . Si 𝑎𝑇 𝑦 < 𝑎𝑇 𝑥, alors pour tout 𝜃 ∈ 0,1 𝑎𝑇 𝑦 < 𝑎𝑇 𝜃𝑥 + 1 − 𝜃 𝑦 < 𝑎𝑇 𝑥 • Preuve :

𝑎𝑇 𝜃𝑥 + 1 − 𝜃 𝑦 < 𝑎𝑇 𝜃𝑥 + 1 − 𝜃 𝑥 = 𝑎𝑇 𝑥 𝑎𝑇 𝜃𝑥 + 1 − 𝜃 𝑦 > 𝑎𝑇 𝜃𝑦 + 1 − 𝜃 𝑦 = 𝑎𝑇 𝑦

• Théorème 4.10 : (Théorème de séparation) ത alors il Si 𝑋 ⊂ ℝ𝑛 est un ensemble convexe non vide et si 𝑦 ∉ 𝑋, existe un hyperplan qui sépare (strictement) 𝑋ത et 𝑦.

x

X X



x0  24

y

Hyperplan théorie de séparation Preuve :

• Il existe un point 𝑥 0 ∈ 𝑋ത tel que : 𝑥 0 − 𝑦 = min 𝑥 − 𝑦 𝑥∈𝑋ത

• (où Il est facile de vérifier que 𝑋ത est un ensemble convexe, et par ത conséquent le segment de droite ℑ 𝑥 0 , 𝑥 ⊂ 𝑋ത pour tout 𝑥 ∈ 𝑋. Donc pour tout 𝜃 ∈ [0,1] 𝑥0 − 𝑦 ≤

𝜃𝑥 + 1 − 𝜃 𝑥 0 − 𝑦

• Ainsi pour tout 𝜃 ∈ 0,1 𝑇

𝑥0 − 𝑦 ≤

𝑥0 − 𝑦 𝑥0 − 𝑦

𝑇

𝑥0 − 𝑦 ≤ 𝑥0 − 𝑦 + 𝜃 𝑥 − 𝑥0 𝑥0 − 𝑦 + 𝜃 𝑥 − 𝑥0 𝑥 0 − 𝑦 ≤ 𝑥 0 − 𝑦 𝑇 𝑥 0 − 𝑦 + 2𝜃 𝑥 − 𝑥 0 𝑇 𝑥 0 − 𝑦 + 𝜃 2 𝑥 − 𝑥 0

𝑇

𝜃𝑥 + (1 − 𝜃 𝑥 0 ) − 𝑦

𝑇

𝑥0 − 𝑦

𝜃𝑥 + 1 − 𝜃 𝑥 0 − 𝑦

𝑇

𝑇

𝑥 − 𝑥0

25

Hyperplan théorie de séparation • Preuve (suite) : • Par conséquent pour tout 𝜃 ∈ 0,1 2𝜃 𝑥 − 𝑥 0

𝑇

𝑥0 − 𝑦 + 𝜃2 𝑥 − 𝑥0

• Mais alors ceci implique que 𝑥 − 𝑥 0 • 𝑥 − 𝑥0

𝑇

𝑇

𝑇

𝑥 − 𝑥0 ≥ 0

𝑥0 − 𝑦 ≥ 0

𝑥 0 − 𝑦 < 0 , alors pour 𝜃෨ > 0 suffisamment petit

2𝜃෨ 𝑥 − 𝑥 0 𝑇 𝑥 0 − 𝑦 > 𝜃෨ 2 𝑥 − 𝑥 0 −2𝜃෨ 𝑥 − 𝑥 0 𝑇 𝑥 0 − 𝑦 > 𝜃෨ 2 𝑥 − 𝑥 0 • Et alors nous aurions que 2𝜃෨ 𝑥 − 𝑥 0 𝑇 𝑥 0 − 𝑦 + 𝜃෨ 2 𝑥 − 𝑥 0

𝑇

𝑇 𝑇

𝑥 − 𝑥0 𝑥 − 𝑥0

𝑥 − 𝑥0 < 0

26

Hyperplan théorie de séparation • Preuve (suite) : • Nous avons donc que 𝑥 − 𝑥 0 𝑥

0𝑇

𝑥 0 − 𝑦 ≥ 0 ou encore

𝑥0 − 𝑦 ≤ 𝑥𝑇 𝑥0 − 𝑦

ത 𝑥0 − 𝑦 • Puisque 𝑦 ∉ 𝑋, 𝑇

𝑇

2

= 𝑥0 − 𝑦

0

𝑦 𝑥 −𝑦 < 𝑥

0𝑇

𝑇

5.3

𝑥 0 − 𝑦 > 0, ou encore

𝑥0 − 𝑦

5.4

• Alors en appliquant le Théorème 4.9 avec les vecteurs 𝑥 0 − 𝑦 , 𝑥 0 , 𝑦 et utilisant la relation 5.4 𝑦 𝑇 𝑥 0 − 𝑦 < 𝜃𝑥 0 + 1 − 𝜃 𝑦

𝑇

𝑇

𝑥0 − 𝑦 < 𝑥0 𝑥0 − 𝑦

1

• Et avec 𝜃 = 2

1 0 𝑦 𝑥 −𝑦 < 𝑥 +𝑦 2 𝑇

0

𝑇

𝑇

𝑥0 − 𝑦 < 𝑥0 𝑥0 − 𝑦 27

Hyperplan théorie de séparation • Preuve (suite) : • En utilisant maintenant la relation 5.3 1 0 𝑦 𝑥 −𝑦 < 𝑥 +𝑦 2 𝑇

0

𝑇

0

𝑥 −𝑦 𝑏 𝑇 𝑦 = 𝑥 𝑇 𝐴𝑇 𝑦 ≥ 0 Une contradiction.

35

Hyperplan théorie de séparation • Dénotons par 𝑎•𝑗 , 𝑗 = 1, … , 𝑛, la jième colonne de 𝐴 • Considérant l’alternative (𝐈𝐈), celle-ci est vérifiée ou elle ne l’est pas. • Dans le cas où elle ne l’est pas, il s’ensuit que le système 𝐴𝑇 𝑦 ≥ 0, 𝑏 𝑇 𝑦 < 0 ne possède pas de solution 𝑦 ∈ ℝ𝑚 i.e., le 𝑇 système 𝑎•𝑗 𝑦 ≥ 0, 𝑗 = 1, … , 𝑛, 𝑏 𝑇 𝑦 < 0 ne possède pas de solution 𝑇 𝑦 ∈ ℝ𝑚 si 𝑎•𝑗 𝑦 ≥ 0, 𝑗 = 1, … , 𝑛, alors nécessairement 𝑏 𝑇 𝑦 ≥ 0.

• Donc par le Théorème 4.11, il existe un vecteur 𝑥 ∈ ℝ𝑛 , 𝑥 ≥ 0 tel que 𝐴𝑥 = 𝑎•1 𝑥1 + ⋯ + 𝑎•n 𝑥𝑛 = 𝑏, et l’alternative (𝐈) tient.

36

Hyperplan théorie de séparation • Illustration du cas où le système 𝐴𝑥 = 𝑏, 𝑥 ≥ 0 possède une solution 𝑐𝑇 𝑑 = 𝑐

𝑑 cos 𝜃

a1 a1 x1 b y0 T

a2 x2

a1T y  0

b

a2

et a2T y  0

Le système 𝐴𝑇 𝑦 ≥ 0, 𝑏 𝑇 𝑦 < 0 ne possède pas de solution.

37

Hyperplan théorie de séparation • Illustration du cas où le système 𝐴𝑥 = 𝑏, 𝑥 ≥ 0 ne possède pas une solution

b

a1 a1T y  0

b y0 T

bT y  0

b

a2

et a2T y  0

Le système 𝐴𝑇 𝑦 ≥ 0, 𝑏 𝑇 𝑦 < 0 possède une solution

38