25 0 981KB
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