0% ont trouvé ce document utile (0 vote)

28 vues72 pages

Poly Optimisation

Transféré par

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

28 vues72 pages

Poly Optimisation

Transféré par

chaymae

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Polycopié du cours :

OPTIMISATION CONVEXE (Première partie)

Edoardo Provenzi
Table des matières

1 Les outils algébriques pour la résolution du problème des moindres carrés 3

1.1 Introduction aux outils algébriques de l’optimisation avec le problème des moindres
carrés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Résolution d’un système linéaire dans le sens des moindres carrés . . . . . . . . . . 4
1.3 Les équations normales associées à un système linéaire . . . . . . . . . . . . . . . . 6
1.4 Résolution des équations normales, la matrice pseudo-inverse de Moore-Penrose . . 7
1.4.1 At A inversible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.2 At A non inversible, mais diagonale . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.3 At A non inversible et non diagonale . . . . . . . . . . . . . . . . . . . . . . 9
1.5 La décomposition en valeurs singulières : SVD . . . . . . . . . . . . . . . . . . . . . 10
1.5.1 SVD comme solution de norme minimale au problème des moindres carrés . 13

2 Convexité 14
2.1 Ensembles et fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.1 Caractérisation au premier ordre de la convexité et ses conséquences . . . . 17
2.1.2 La convexité est une propriété unidimensionnelle : caractérisation de la
convexité via monotonie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.3 Caractérisation au second ordre de la convexité . . . . . . . . . . . . . . . . 23
2.1.4 Exemples d’ensembles convexes . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1.5 Opérations qui préservent la convexité des ensembles . . . . . . . . . . . . . 30
2.2 Comment détecter la convexité de fonctions : fonctions convexes standards et
opérations qui préservent leur convexité . . . . . . . . . . . . . . . . . . . . . . . . 32
2.2.1 Les fonctions convexes standards . . . . . . . . . . . . . . . . . . . . . . . . 32
2.2.2 Opérations qui préservent la convexité de fonctions . . . . . . . . . . . . . . 34
2.2.3 L’interprétation analytique du problème des moindres carrés . . . . . . . . 35
2.3 Lien entre ensembles convexes et fonctions convexes : épigraphe et hypographe,
enveloppe convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.4 Enveloppe convexe, combinaisons linéaires convexes et inégalité de Jensen . . . . . 38
2.5 Fonctions convexes à valeurs dans R “ R Y t˘8u . . . . . . . . . . . . . . . . . . . 41
2.5.1 Les minima locaux d’une fonction convexe propre sont des minima globaux 41
2.5.2 Semicontinuité inférieure et existence des minima des fonctions convexes . . 43

Appendices 44

A Un très bref rappel d’algèbre linéaire 45

A.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
A.2 Projecteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

B Un très bref rappel sur les espaces métriques et le calcul différentiel en Rn 57

B.1 Espaces métriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
B.1.1 Le théorème de Bolzano-Weierstrass . . . . . . . . . . . . . . . . . . . . . . 59
B.2 Éléments de calcul différentiel en Rn pour l’optimisation . . . . . . . . . . . . . . . 60

1
B.2.1 Dérivée directionnelle, partielle, gradient et ligne de niveau . . . . . . . . . 61
B.2.2 Calcul de quelque gradient utile pour l’optimisation via la dérivée directionnelle 64
B.2.3 Les points stationnaires et les équations de Euler-Lagrange . . . . . . . . . 66
B.2.4 La matrice Jacobienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
B.2.5 La matrice Hessienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
B.2.6 La formule de Taylor pour fonctions de plusieurs variables . . . . . . . . . . 69

2
Chapitre 1

Les outils algébriques pour la

résolution du problème des
moindres carrés

Dans ce chapitre initial on va introduire des outils algébriques, qu’on trouve souvent dans
les applications pratiques, pour la résolution d’un problème d’optimisation très simple mais très
répandu : le problème des moindres carrés.

1.1 Introduction aux outils algébriques de l’optimisation

avec le problème des moindres carrés
Dans les applications des mathématiques on trouve souvent des systèmes d’équations sur-
déterminés, i.e. avec un nombre d’équations supérieur au nombre des inconnues, ou sous-déterminés,
i.e. avec un nombre d’équations supérieur au nombre des inconnues.
La raison est simple à comprendre : imaginons de devoir déterminer un vecteur x via des
expériences et que chaque expérience donne les valeurs d’une équation linéaire satisfaite par x. Les
erreurs dans la mesure imposent, quand il est possible, d’estimer x avec une quantité d’expériences
supérieure à celle des inconnues. Cela correspond à un système sur-déterminé. Par contre, il est
possible que la difficulté d’accès aux données (par exemple la mesure d’une particule qui tombe sur
la Terre rarement) fait que le système aı̈t moins d’équations que des inconnues, cette fois-ci on
tombe dans le cas d’un système sous-déterminé.
Dans les deux cas, la solution exacte du système n’existe pas, il faut se contenter de calculer
le vecteur x̄ qui minimise, dans un sens à préciser, les erreurs expérimentales. Pour formaliser
mathématiquement cela, on a à disposition le concept de distance entre vecteurs, i.e. la norme
de leur différence. En réalité, on va voir que, plutôt que la norme de la différence, on utilisera la
norme au carré pour des raisons qui seront claires plus tard. La minimisation de la norme au carré
entre deux vecteurs est appelée une méthode des ! moindres carrés ".
Allons introduire concrètement le problème des moindres carrés avec un exemple très simple.
Imaginons de savoir qu’une quantité y dépend linéairement d’une autre quantité x, fixons 4 valeurs
de x et allons mesurer les valeurs de y correspondants. Supposons d’obtenir la table suivante :

x̄ ȳ
1 6
2 5
3 7
4 10

3
On veut trouver la droite d’équation y “ α1 ` α2 x qui détermine le relation linéaire entre x et
y. On sait que pour déterminer une droite il faut et il suffit un couple d’équations indépendantes
pour α1 et α2 , donc, avec le système (sur-déterminé) suivant
$
’α1 ` α2 “ 6
’
’
&α ` 2α “ 5
1 2
’α1 ` 3α2 “ 7
’
’
%
α1 ` 4α2 “ 10

on ne peut pas trouver une solution analytique à notre problème, en fait, par exemple, si on
considère les deux premières équations, on obtient le système linéaire :
#
α1 ` α2 “ 6
α1 ` 2α2 “ 5

qui est résolu par α1 “ 7 et α2 “ ´1, mais le couple pα1 , α2 q “ p7, ´1q n’est pas solution de
l’équation α1 ` 3α2 “ 7 ni de l’équation α1 ` 3α2 “ 10 !
Le fait que le système ne soit pas résoluble analytiquement ne veut pas dire qu’on doit renoncer
à notre propos, comme on l’a dit avant, il faut changer le paradigme : on se contente de trouver
la droite qui mieux approxime la relation de dépendance linéaire entre x et y. Cela implique
d’établir un critère d’approximation : quand ce critère est la minimisation de la somme des erreurs
quadratiques entre le côté de gauche et le côté de droite des équations du système, alors on parle
d’un problème des moindres carrés.
Le but des sections suivantes est de montrer que ce problème peut être résolu avec de techniques
d’algèbre linéaire relativement simples, élégants et rapides.

Le lecteur est fortement invité à lire l’appendice A, relative aux outils de l’algèbre linéaire, avant
de continuer la lecture.

1.2 Résolution d’un système linéaire dans le sens des moindres

carrés
Considérons un système linéaire avec m équations et n inconnues écrit sous forme matricielle
Ax “ b, où ¨ ˛
a11 . . . a1n
A P Mm,n pRq, A “ ˝ ... .. ‹ “ pa qi“1,...,m
˚
. ‚ ij j“1,...,n
am1 . . . amn
est la matrice des coefficients du système,
¨ ˛
x1
x P Rn , x “ ˝ ... ‚
˚ ‹

xn
est les vecteur des inconnues, et
¨ ˛
b1
b P Rm , b “ ˝ ... ‚
˚ ‹

bm
est le vecteur des donnés connus, typiquement mesurées.

Déf. 1.2.1 Le système Ax “ b est résoluble s’il existe, au moins, une solution, i.e. un vecteur x̄
tel que l’équation Ax̄ “ b est une identité.

4
Par définition, Ax “ b est résoluble si et seulement si b P ImpAq.
Il est important de rappeler que la solution générale de Ax “ b est donnée par la somme de
la solution générale du système homogène associé, i.e. Ax “ 0, et d’une solution particulière de
Ax “ b. En fait, si x0 est la solution générale de Ax “ 0 et x̄ est une solution particulière de
Ax “ b, i.e. Ax̄ “ b, alors :
Apx0 ` x̄q “ Ax0 ` Ax̄ “ 0 ` b “ b,
par conséquent, si kerpAq ‰ t0u, à chaque solution x̄ de Ax “ b on peut rajouter une solution non
nulle de Ax “ 0, i.e. un vecteur qui appartient à kerpAq, et obtenir une autre solution. Ceci a une
conséquence importante : si Ax “ b est résoluble, alors, soit il a une seule solution, soit il en a
une infinité, en fait, s’il existe x0 ‰ 0, x0 P kerpAq, alors aussi λx0 P kerpAq @λ P R, donc on peut
construire une infinité de solutions différentes en faisant varier le coefficient λ.
Sous l’hypothèse que b P ImpAq, analysons les trois possibilités qu’on peut avoir :
— n ą m : on a plus d’inconnues que d’équations, le système est dit sous-déterminé.
Comme r “rankpAq ď minpm, nq “ m ă n, alors, grâce au théorème de nullité + rank
(appendice A) dimpkerpAqq “ n ´ m ą 0, donc le système a un nombre infini de solutions,
il existe un nombre n´r d’inconnues libres, auxquelles on peut donner un valeur quelconque ;

— n “ m : même nombre d’inconnues et d’équations, le système est dit déterminé. Dans

ce cas, la condition nécessaire et suffisante pour l’unicité de la solution est rankpAq “ n
ô kerpAq “ t0u. Si rankpAq ă n, le système a un nombre infini de solutions ;

— n ă m : plus d’équations que d’inconnues, les système est dit sur-déterminé. Si on a n

équations indépendantes et les autres m ´ n sont combinaisons linéaires des précédentes,
i.e. si rankpAq “ n, alors on a l’unicité de la solution. Autrement, si rankpAq ă n, on a des
inconnues libres et, donc, un nombre infini de solutions.
Jusqu’ici on a examiné les systèmes résolubles, supposons maintenant que b R ImpAq, alors
Ax “ b n’est pas résoluble de manière exacte, mais, comme ImpAq est un sous-espace vectoriel de
Rm , on a la tentation de remplacer b par le vecteur de ImpAq le plus proche à lui. Dans l’appendice
A on démontre que ce vecteur est la projection orthogonale de b sur ImpAq :
b1 “ PImpAq b.
Allons examiner les propriétés du nouveau système linéaire Ax “ b1 .
Théorème 1.2.1 La résolution du système Ax “ PImpAq b est équivalente à la résolution du
problème suivant :
arg min}Ax ´ b}2 .
xPRn

Interprétation du théorème : Ax̄ “ PImpAq b si et seulement si x̄ est le vecteur qui minimise la

distance Euclidienne entre Ax et b, i.e. }Ax̄ ´ b} ď }Ax ´ b} pour tout x P Rn .

Preuve. Dans l’appendice A on montre que l’erreur y entre b et PImpAq b appartient au complément
orthogonale de ImpAq :

b
y P ImpAqK
y “ b ´ PImpAq b

PImpAq b

5
b “ PImpAq b ` y

Ax ´ b “ looAx
moon ´ P ImpAq b ` loo´y
looomooon moon
ImpAq ImpAqK
ImpAq
looooooooomooooooooon
ImpAq

Vu que Ax ´ PImpAq b et y sont orthogonales et comme } ´ y}2 “ }y}2 , on peut appliquer le

théorème de Pythagore généralisé (Annexe A) pour écrire :

}Ax ´ b}2 “ looooooooomooooooooon

}Ax ´ PImpAq b}2 ` }y}2 ,
ě0 @xPRn

donc arg min}Ax ´ b}2 “ x̄ tel que }Ax ´ PImpAq b}2 “ 0 (car }y}2 est une constante par rapport à
xPRn
x), i.e. Ax ´ PImpAq b “ 0, d’où Ax “ PImpAq b.
En résumé, le fait que y, le résidu de la projection, soit perpendiculaire à ImpAq, nous permet
d’utiliser les théorème de Pythagore et la définie positivité de la norme pour obtenir le résultat. 2

1.3 Les équations normales associées à un système linéaire

Maintenant qu’on a montré l’équivalence entre le nouveau système linéaire Ax “ PImpAq b et la
minimisation de la norme au carré de Ax ´ b, on se pose le problème de déterminer une méthode
simple pour résoudre le nouveau problème. Cette méthode sera, automatiquement, une technique
d’optimisation !
Encore une fois, les propriétés d’orthogonalité vont nous aider pour déterminer cette technique.

Théorème 1.3.1 Soient A P Mm,n pRq, x P Rn , b P Rm , alors :

Ax “ PImpAq b ô x “ arg min}Ax ´ b}2 ô At Ax “ At b ,

xPRn

i.e. la résolution du système projeté Ax “ PImpAq b, qu’on a démontré être équivalente à la solution
du problème des moindres carrés arg min}Ax ´ b}2 , est équivalente à la résolution des équations
xPRn
At Ax̄ “ At b.

Preuve.
Ax “ PImpAq b ùñ At Ax̄ “ At b :

Ax “ PImpAq b ô Ax ´ b “ PImpAq b ´ b ô Ax ´ b “ ´y P pImpAqqK “ kerpAt q,

y“b´PImpAq b A.1.5

mais Ax ´ b P kerpAt q veut dire que At pAx ´ bq “ 0, i.e. At Ax ´ At b “ 0, donc At Ax “ At b.

At Ax “ At b ùñ Ax̄ “ PImpAq b : At Ax “ At b implique At Ax ´ At b “ 0, i.e. At pAx ´ bq “ 0, i.e.
Ax ´ b P kerpAt q “ ImpAqK .
Comme Ax̄ P ImpAq et b ´ Ax̄ P ImpAqK , l’écriture b “ Ax̄ ` pb ´ Ax̄q est la décomposition or-
thogonale de b sur ImpAq. Grâce au théorème de la projection A.1.3 on sait que cette décomposition
est unique, donc Ax̄ “ PImpAq b. 2

6
Déf. 1.3.1 Les équations At Ax “ At b sont dites équations normales associées au système
Ax “ b, elle s’appellent normales car elles descendent de l’orthogonalité (aussi dite normalité)
entre b ´ PImpAq b et ImpAq.

Les équations normales sont obtenues simplement par produit à gauche de la matrice transposée
de A aux deux côtés de l’équation Ax “ b. Il est vraiment remarquable que cette opération,
apparemment très simple, permet de transformer un système qui n’a pas forcément une solution,
Ax “ b quand b R ImpAq, dans un problème toujours résoluble, car b1 “ PImpAq b P ImpAq !
Il faut souligner que c’est le système Ax “ PImpAq b à être équivalent à At Ax “ At b et que, en
général, Ax “ b n’est pas équivalent à At Ax “ At b, car, comme souligné dans l’appendice A, si
M est une matrice avec kerpM q ‰ t0u, alors M N “ M P n’implique pas N “ P !
Donc, il faut bien se rappeler du fait que

At pAx ´ bq “ 0
ùñ Ax ´ b “ 0 !

1.4 Résolution des équations normales, la matrice pseudo-

inverse de Moore-Penrose
Dans cette section on va entrer dans les détails de la résolution des équations normales. Encore
une fois, on souligne qu’il est fortement conseillé de lire l’appendice A avant d’avancer dans la
lecture.

1.4.1 At A inversible
Dans l’appendice A on montre que, pour toute matrice A m ˆ n, la matrice At A est une matrice
carrée de dimension n ˆ n. On va commencer avec le cas le plus simple : imaginons que A soit full
rank, i.e. rankpAq “ n, alors, comme on le démontre dans l’appendice A, At A est inversible, i.e.
DpAt Aq´1 , et la solution des équations normales, i.e. du problème des moindres carrés, est obtenue
très simplement comme ça :

x̄ “ I x̄ “ pAt Aq´1 At Ax̄ “ pAt Aq´1 At b

At Ax̄“At b

donc :
x̄ “ pAt Aq´1 At b est la solution de arg min}Ax ´ b}2 quand DpAt Aq´1 .
xPRn

La caractérisation du projecteur PImpAq est immédiate :

Ax “ PImpAq b ô Ax “ ApAt Aq´1 At b,

donc, dans ce cas, PImpAq “ ApAt Aq´1 At , qu’on a démontré être un projecteur dans l’appendice A.
Si la dimension de A est grande, la formule qu’on vient de déterminer est trop computationnellement
couteuse à cause de l’inversion matricielle. On verra dans la suite des techniques plus efficaces.

1.4.2 At A non inversible, mais diagonale

Supposons maintenant que At A ne soit pas inversible, i.e. rankpAq ă n. Dans l’appendice A on
a examiné les propriétés de At A, pour le moment on a besoin que du fait que At A est une matrice
carrée de taille n réelle et symétrique.
Les matrices réelles symétriques sont toujours diagonalisables (en fait elles sont des matrices
diagonales ! en cachette "), en fait un théorème basique d’algèbre linéaire dit que si M P Mn pRq,
M t “ M , alors il existe une base orthonormée de Rn donnée par les vecteurs propres de M , si P
est la matrice qui a comme colonnes les vecteurs de cette base, alors P est une matrice orthogonale,
i.e. P ´1 “ P t et
P ´1 M P “ D,

7
où D “ diagpλ1 , . . . , λn q. Donc M , réelle et symétrique, est semblable à une matrice diagonale qui
a les valeurs propres de M sur la diagonale.
Cette observation justifie la volonté de commencer l’analyse de la résolution des équations
normales quand At A n’est pas inversible, mais diagonale, car l’extension au cas général sera très
simple.
Soit, donc :
At A “ diagpd1 , . . . , dr , 0, . . . , 0q, di ‰ 0, i “ 1, . . . , r
(modulo une permutation des colonnes, on peut toujours représenter At A comme ça, i.e. mettre les
valeurs non nulles de la diagonale en premier et les 0 après), bien évidemment r ă n, car si r “ n,
At A serait inversible !
On reprend les équations normales :
¨ ˛
d1 ¨ ˛ ¨ ˛
x̄1 b̄1
˚
˚ . .. ‹
‹ ˚ .. ‹ ˚ .. ‹
˚ ‹˚ . ‹ ˚ . ‹
˚ dr ‹˚ ‹ ˚ ‹
At Ax̄ “ loA t
omobon ô ˚ ‹ ˚ x̄r ‹ “ ˚ b̄r ‹
˚ 0 ‹˚ ‹ ˚ ‹
‹˚ . ‹ ˚ . ‹
‹ ˝ .. ‚ ˝ .. ‚
“b̄
˚
˚ ..
˝ . ‚
x̄n b̄n
0

$
’
’d1 x̄1 “ b̄1
& ..
’ #
x̄i “ db̄ii
’
. i “ 1, ..., r
ô ô
’dr x̄r “ b̄r
’
’ x̄j indéterminées j “ r ` 1, ..., n.
’
0x̄j “ b̄j j “ r ` 1, ..., n
%

Un choix pour fixer les variables indéterminées est, par exemple, x̄j “ 0 j “ r ` 1, ..., n, ce qui
minimise la norme de x̄.
Allons maintenant introduire une matrice très utilisée dans la résolution des problèmes de
moindres carrés.

Déf. 1.4.1 On appelle matrice pseudo-inverse de Moore-Penrose 1 de D P Mn pRq, la ma-

trice ˆ ˙
1 1
D` “ diag , . . . , , 0, . . . , 0 P Mn pRq.
d1 dr
Par calcul direct on voit que
x̄ “ D` b̄ ô x̄ “ D` At b
formellement, c’est comme si D` était pAt Aq´1 car
#
At Ax̄ “ b̄
x̄ “ D` b̄

mais D` ‰ pAt Aq´1 car At A n’est pas inversible ! En fait, par calcul direct, on obtient

D` At A “ diagp1, . . . , 1, 0 . . . , 0q ‰ In ,

où les valeurs 1 se répètent r fois.

En résumé : si At A est non inversible mais diagonale avec rang r ă n, alors

x̄ “ D` At b est solution de Ax “ PImpAq b ô At Ax “ At b ô arg min}Ax ´ b}2 .

xPRn

1. La définition de matrice pseudo-inverse de Moore-Penrose qu’on a donné est un cas particulier d’une théorie,
celle des matrices pseudo-inverses, plus riche et compliquée. Néanmoins, on a voulu rester dans ce cadre pour ne pas
compliquer inutilement la présentation et parce que la définition qu’on a donné est suffisante pour ce cours.

8
1.4.3 At A non inversible et non diagonale
Si At A n’est pas diagonale, on a vu qu’on peut la diagonaliser avec la matrice orthogonale
P , P ´1 “ P t , qui a comme colonnes une base orthonormée de Rn de vecteurs propres de At A :
P t At AP “ D. Comme P est inversible, ker P “ t0u, donc on peut invoquer le théorème A.1.2 et
écrire :

P t At AP “ D ô P P t At AP P t “ P DP t ô At A “ P DP t ,
donc, en reconsidérant les équations normales, on peut écrire

At Ax̄ “ At b ô P DP t x̄ “ At b ô P t P DP t x̄ “ P t At b ô DP t x̄ “ P t At b,

qui est un problème très similaire à ce qu’on a examiné dans la section précédente, i.e Dx̄ “ At b,
et qu’on a résolu avec la matrice pseudo-inverse de Moore-Penrose D` . Pour revenir exactement
au cas précédent on fait les changements de variable suivants :
#»
x “ P t x̄
»
b “ P t At b (rappeler que b̄ “ At b),
» »
alors, en appliquant la même technique de la section précédente à D x “ b, on arrive à écrire
» »
x “ D` b, or

P t x̄ “ D` P t At b ô P P t x̄ “ P D` P t At b ô x̄ “ P D` P t At b.

En résumé : si At A est non inversible et non diagonale, alors

x̄ “ P D` P t At b est solution de Ax “ PImpAq b ô At Ax “ At b ô arg min}Ax ´ b}2 ,

xPRn

où, encore, P est la matrice orthogonale qui a comme colonnes une base orthonormée de Rn de
vecteurs propres de At A.
On voit que la solution nécessite 4 multiplications matricielles appliquées à un vecteur, si la
dimension n du problème est élevée, cette quantité d’opérations peut poser des problèmes de coût
algorithmique. Dans la prochaine section on va voir une solution moins coûteuse qui passe par une
décomposition de A et non pas de At A.

9
1.5 La décomposition en valeurs singulières : SVD
On sait qu’une matrice réelle symétrique A de taille n peut toujours être diagonalisée via la
transformation A “ P DP t , où P a sur les colonnes une base de Rn de vecteurs propres de A et D
est une matrice diagonale, avec les valeurs propres de A déposés sur la diagonale.
Pour toute matrice A P Mm,n pRq quelconque, on a à disposition une formule, la décomposition
en valeurs singulières, qui est un substitut très utile de la formule de diagonalisation.
On commence en rappelant que, dans l’appendice A, on a vu que At A est toujours semi-définie
positive et que ses valeurs propres λi sont toutes ě 0 @A P Mm,n pRq, ce qui nous permet de définir
ce qui suit.

Déf. 1.5.1 On appelle valeurs singulières de A P Mm,n pRq toute les racines carrées des valeurs
propres de la matrice At A, et on les notes σi :
?
σi “ λi avec λi : valeurs propres de At A,

c’est courant d’écrire les valeurs singulières de A dans l’ordre décroissant σ1 ě σ2 ě . . . ě σn , cela
étant toujours possible en permutant les colonnes de la matrice orthogonale P qui diagonalise At A.

La matrice diagonale dont les éléments diagonaux sont les valeurs singuliéres de A intervient dans
une décomposition de A qu’on appelle SVD. Pour prouver cette décomposition, on doit d’abord
introduire deux résultats préliminaires.

Lemme 1.5.1 Hypothèses :

— A P Mm,n pRq avec valeurs singulières σ1 , . . . , σn ;
— pv1 , . . . , vn q : base orthonormée de Rn composée par des vecteurs propres de At A, avec
valeurs propres λi , i “ 1, . . . , n.
Alors :
1. }Avi } “ σi , @i “ 1, . . . , n ;
2. xAvi , Avj y “ λi δi,j , i, j “ 1, . . . , n. En particulier, Avi KAvj , @i ‰ j.

Preuve.
1. }Avi }2 “ xAvi , Avi y = xvi , A?t Avi y = xvi , λi vi y = λi xvi , vi y = λi }vi }2 “ λi , car les vecteurs vi
sont unitaires. Donc : }Avi } “ λi “ σi , @i “ 1, . . . , n.
2. xAvi , Avj y “ xvi , At Avj y “ xvi , λj vj y “ λj xvi , vj y “ λj δi,j par orthonormalité. 2

Lemme 1.5.2 Sous les mêmes hypothèses du Lemme 1.5.1, et avec l’hypothèse supplémentaire
que λ1 ě λ2 ě . . . λr ą λr`1 “ . . . “ λn “ 0, alors rankpAq “ r et :

pAv1 , . . . , Avr q est une base orthogonale de ImpAq.

Preuve. L’hypothèse λ1 , . . . , λr ą 0 implique que σ1 , ¨ ¨ ¨ , σr ą 0 et donc, Lemme 1.5.1 1.,

}Av1 }, . . . , }Avr } ą 0. La propriété 2. du Lemme 1.5.1 implique que les vecteurs pAv1 , . . . , Avr q
sont linéairement indépendants dans ImpAq car non nuls et orthogonaux.
Par contre, λr`1 , . . . , λn “ 0 implique σr`1 , . . . , σn “ 0 et, encore grâce au Lemme 1.5.1 1.,
}Avr`1 } “ . . . “ }Avn } “ 0, i.e. Avr`1 “ ¨ ¨ ¨ “ Avn “ 0.
Soit maintenant w P ImpAq quelconque, alors Dv P Rn tel que w “ Av. Allons ř décomposer v sur
n
la base pv1 , . . . , vn q : ř
ils existent desřscalaires réels ci , i “ 1, . . . , n, tels que v “ i“1 ci vi , or, par
n r
linéarité, w “ Av “ i“1 ci Avi “ k“1 ck Avk , vu que Avr`1 “ ¨ ¨ ¨ “ Avn “ 0. Par conséquent,
ImpAq “ spanpAv1 , . . . , Avr q et, par définition, rankpAq “ r. 2

Avant d’énoncer et démontrer le théorème sur la décomposition en valeurs singulières on a

besoin d’une dernière définition.

10
Déf. 1.5.2 Une matrice M “ pmij q P Mm,n pRq est dite pseudo-diagonale si mij “ 0 toutefois
que i ‰ j.

On observe qu’une matrice carrée pseudo-diagonale est diagonale tout-court. Par contre, si elle
n’est pas carrée, on peut avoir de situations comme celles-ci :
¨ ˛
ˆ ˙ 1 0
2 0 0
M1 “ , M2 “ ˝0 4‚.
0 3 0
0 0

Déf. 1.5.3 Étant donnée une matrice pseudo-diagonale M P Mm,n pRq, sa matrice pseudo-
inverse de Moore-Penrose M ` est la matrice de Mn,m pRq obtenue en considérant la transposée
M t P Mn,m pRq de M et en remplaçant tous les éléments non-nuls di de la diagonale avec leurs
inverses d´1 `
i . Le résultat du produit matriciel M M est une matrice carrée n ˆ n qui a 0 partout,
sauf pour les valeurs 1 sur la diagonale, répétées minpm, nq fois.

L’exigence de passer par la transposition est essentielle pour avoir une cohérence dimensionnelle.
¨ Par
˛
ˆ ˙ 1{2 0
2 0 0
exemple, la pseudo-inverse de la matrice pseudo-diagonale M “ est M ` “ ˝ 0 1{3‚
0 3 0
¨ ˛ 0 0
1 0 0
et M ` M “ ˝0 1 0‚.
0 0 0
On a maintenant la possibilité de démontrer le théorème qui donne la décomposition en valeurs
singulières. On rappelle que le symbole OpN q représente l’ensemble des matrices orthogonales, i.e.
matrices réelles carrés de taille N telles que Ot “ O´1 .

Théorème 1.5.1 (SVD) Soit A P Mm,n pRq, rangpAq “ r et soient σ1 ě σ2 ě . . . σr ą 0 les

valeurs singulières de A. Alors, ça vaut la décomposition en valeurs singulières (SVD) suivante :

A “ U ΣV t ,

où U P Opmq, V P Opnq et Σ est une matrice pseudo-diagonale réelle de taille m ˆ n telle que :
¨ ˛
σ1 0
˚
˚
Σ“˚
..
. 0 ‹
‹
‹ “ diagpσ1 , . . . , σr , 0, . . . , 0q.
˚ 0 σr ‹
0
˝ ‚
0
La SVD n’est pas unique 2 , néanmoins, dans toute décomposition, les éléments non nuls σi de Σ
sont les valeurs singulières de A.

Preuve. At A est réelle symétrique, donc il existe une base orthonormée de Rn composée par de
vecteurs propres de At A, qu’on écrit comme pv1 , ¨ ¨ ¨ , vn q.
Le Lemme 1.5.2 garantit que pAv1 , ¨ ¨ ¨ , Avr q est une base de ImpAq qu’on peut normaliser en
une base orthonormée de ImpAq comme ça :
ˆ ˙
Av1 Avr
pu1 , . . . , ur q “ ,..., ,
σ1 σr

i.e. Avk “ σk uk , k “ 1, . . . , r, où on a utilisé la propriété 1. du Lemme 1.5.2.

pu1 , . . . , ur q peut être étendue à une base orthonormée pu1 , ¨ ¨ ¨ , um q de Rm , l’extension,
évidemment, n’est pas unique.
2. Car, comme on le verra dans la preuve, les matrices U, V , en général, ne sont pas univoquement déterminée.

11
On définit les matrices orthogonales V P Opnq et U P Opmq comme les matrices ayant par
colonnes sont les vecteurs des bases pv1 , ¨ ¨ ¨ , vn q et pu1 , ¨ ¨ ¨ , um q, respectivement :

U “ pu1 ¨¨¨ um q , V “ pv1 ¨¨¨ vn q.

Comme Avk “ σk uk pour k “ 1, . . . , r et Avj “ 0 pour j “ r ` 1, ¨ ¨ ¨ , n (par hypothèse sur

le rang de A), alors AV “ pAv1 | ¨ ¨ ¨ |Avr |0| ¨ ¨ ¨ |0q “ pσ1 u1 | ¨ ¨ ¨ |σr ur |0| ¨ ¨ ¨ |0q, donc, si on définit
Σ “ diagpσ1 , . . . , σr , 0, . . . , 0q, alors U Σ “ pσ1 u1 | ¨ ¨ ¨ |σr ur |0| ¨ ¨ ¨ |0q “ AV , or U ΣV t “ AV V t et,
comme V ´1 “ V t , A “ U ΣV t . 2

Allons finalement utiliser la SVD pour résoudre les équations normale. Observons tout d’abord
que

At A “ V Σt U t U ΣV t “ V Σt ΣV t “ V DV t , où D “ Σt Σ “ 2 2
´ diagpσ1 , . . . , σr , 0,¯. . . , 0q, qui a
comme pseudo-inverse de Moore-Penrose la matrice D` “ diag σ12 , . . . , σ12 , 0, . . . , 0 .
1 r
On a donc At A “ V DV t et, par la SVD, At “ pU ΣV t qt “ V Σt U t et alors les équations
normales deviennent At Ax̄ “ At b ðñ V DV t x̄ “ V Σt U t b, comme V et V t sont inversibles, on
peut invoquer le théorème A.1.2 et écrire :

At Ax̄ “ At b ðñ V DV t x̄ “ V Σt U t b ðñ V t V DV t x̄ “ V t V Σt U t b ðñ DV t x̄ “ Σt U t b.

On utilise maintenant D` pour pseudo-inverser la dernière équation (comme on l’a fait dans la
section 1.4.2) en obtenant V t x̄ “ D` Σt U t b, où :

ˆ ˙
` t 1 1
D Σ “ diag , . . . , 2 , 0, . . . , 0 diagpσ1 , . . . , σr , 0, . . . , 0q
σ2 σr
ˆ 1 ˙
1 1
“ diag , . . . , , 0, . . . , 0
σ1 σr
“ Σ` ,

où Σ` P Mn,m pRq est la pseudo-inverse de la matrice pseudo-diagonale Σ P Mm,n , qui, comme
vu dans la definition 1.5.3, est obtenue en considérant la transposée Σt P Mn,m pRq de Σ et en
remplaçant tous les éléments non-nuls σi avec leurs inverses σi´1 .
Donc, V t x̄ “ Σ` U t b ðñ V V t x̄ “ V Σ` U t b. En résumé :

x̄ “ V Σ` U t b est solution de arg min}Ax ´ b}2 ,

xPRn

et, par définition, la pseudo-inverse de A est :

A ` “ V Σ` U t .

Cette solution du problème des moindres carrés nécessite de 3 multiplications matricielles et non
4 comme dans la section précédente. En realité, comme la matrice Σ` est diagonale, il restent
seulement 2 produits matriciels.

12
Grâce aux propriétés générales des matrices pseudo-inverses, il est possible de démontrer
l’important théorème suivant, qui généralise les calculs qu’on vient de faire.

Théorème 1.5.2 Soit A P Mm,n pRq et A` la matrice pseudo-inverse de Moore-Penrose de A,

alors :
— A` A représente le projecteur orthogonale de Rn sur LignespAq ;

— AA` représente le projecteur orthogonale de Rm sur ColpAq “ ImpAq ;

— @y P Rm , x` “ A` y est la seule solution des moindres carrés de Ax “ y qui appartient à

LignespAq ;

— si rankpAq “ n, alors A` “ pAt Aq´1 At est l’inverse gauche de A ;

— si rankpAq “ m, alors A` “ At pAAt q´1 est l’inverse droite de A ;

— si n “ m et A est inversible, alors A` “ A´1 ;

— si la SVD de A est A “ U ΣV t , alors sa pseudo-inverse A` est :

A ` “ V Σ` U t ,

en particulier, les valeurs singulières de A` sont les inverses de ceux de A.

1.5.1 SVD comme solution de norme minimale au problème des moindres

carrés
Quand A P Mm,n pRq et rankpAq ă n, les solutions du système Ax “ b dans le sens des moindres
carrés sont infinie, précisément elles sont les vecteurs de la forme

x “ A` b ` x 0 , x0 P kerpAq.

Parmi toutes ces solutions, celle donnée par x` “ A` b a norme minimale, en fait x` P
LignespAq “ ColpAt q = ImpAt q “ kerpAqK , donc par le théorème de Pythagore :

}x}2 “ }x` }2 ` }x0 }2 ě }x` }2 ,

donc x` , parmi les solutions de moindre carré de Ax “ b, est celle à distance minimale de l’origine.
Vu que, habituellement, on calcule A` via la SVD en écrivant A` “ V Σ` U t , dans beaucoup
d’ouvrages on dit que la solution au problème des moindres carrés offerte par la SVD est celle
optimale, en faisant une liaison entre optimalité et minimalité de la norme de x` .

13
Chapitre 2

Convexité

Le problème des moindres carrés examiné dans le chapitre 1 est particulièrement simple parce
que la fonction qu’il faut minimiser est la norme Euclidienne au carré. Allons analyser plus en détail
l’expression analytique de cette fonction : en R on a f pxq “ x2 , en R2 on a f p~xq “ }~x}2 “ x2 ` y 2 ,
en Rn on a f p~xq “ }x}2 “ x21 ` . . . ` x2n , dans le premier cas le graphe de f est représenté par une
parabole en R2 , dans le deuxième cas par la surface d’un paraboloı̈de en R3 et, dans le cas général,
par un paraboloı̈de en Rn`1 .
La parabole et les paraboloı̈des qui correspondent à la norme Euclidienne au carré ont la
propriété d’avoir un seul point de minimum absolu, qui coı̈ncide avec le sommet, comme dans la
figure 2.1.

Figure 2.1 – La surface d’un paraboloı̈de qui représente une norme Euclidienne au carré.

Les paraboles et les paraboloı̈des sont un cas particulier de fonctions convexes. Dans les sections
qui suivent on va introduire les concepts les plus importantes relatifs à la convexité, tout en
sachant que la présentation qu’on fera n’est que le début d’une théorie très riche et toujours en
développement.
Pour rendre le discours le plus simple possible, on gardera toujours dans l’esprit l’idée de vouloir
généraliser la propriété clé des paraboles et des paraboloı̈des d’avoir un seul minimum.
Le lecteur est fortement invité à lire l’appendice B, relative aux outils de calcul différentiel, avant
de continuer la lecture.

2.1 Ensembles et fonctions convexes

Il y a deux propriétés géométriques des paraboles qui vont nous aider à comprendre comment
introduire le concept de convexité : le comportement des sécantes et des tangentes.
On va commencer par les sécantes : dans la figure 2.2 on peut voir que, pour une parabole, la
droite sécante en deux points du graphe a toujours une ordonnée supérieure à celle des points du

14
graphe de la parabole. Si on veut étendre cette propriété à une fonction f définie sur un domaine

Figure 2.2 – Propriété géométrique des sécantes à une parabole.

de Rn à valeurs réels on doit tout d’abord s’assurer du fait que le segment de la droite qui connecte
deux points du domaine reste dans le domaine lui-même. Pour traiter ce problème on a besoin
d’introduire les définitions suivantes.

Déf. 2.1.1 On appelle droite passant par deux éléments distincts x et y de Rn l’ensemble (infini)
défini par
rx,y “ ttx ` p1 ´ tqy , t P Ru.
On appelle segment de droite passant par deux éléments distincts x et y de Rn l’ensemble
(borné) défini par
rx, ys :“ ttx ` p1 ´ tqy , t P r0, 1su.

Un élément ξ du segment rx, ys s’écrit aussi sous la forme ξ “ y ` tpx ´ yq. On peut interpréter ξ
comme la somme d’une point initial y et d’une direction x ´ y pondérée par le paramètre t, qui
donne la fraction du chemin reliant y et x où ξ se trouve, en fait, comme t varie de 0 à 1, ξ varie
de y à x comme le montre la figure 2.3.

Figure 2.3 – La droite reliant x et y est décrite par l’équation paramétrique tx ` p1 ´ tqy où t P R.
Le segment reliant x et y est la portion de cette droite qui correspond à t P r0, 1s.

Si l’on remplace dans la définition précédente r0, 1s, respectivement, par les intervalles r0, 1r,
s0, 1s et s0, 1r on définit les segments rx, yr, sx, ys et sx, yr.

Déf. 2.1.2 Une partie E Ă Rn est dite étoilée par rapport à un élément x0 de E si pour tout x
appartenant à E le segment rx0 , xs appartient à E.

Autrement dit, une partie est étoilée par rapport à un élément x0 si tout segment d’extrémité x0 et
un élément de cette partie sont inclus dans cette partie. Une interprétation intuitive consiste à dire

15
Figure 2.4 – Exemples simples de parties étoilée et non étoilée. À gauche : une couronne qui n’est
pas une partie étoilée (par rapport à aucun élément). À droite : il s’agit d’une partie étoilée par
rapport à x0 mais qui n’est pas étoilée par rapport à y.

que, dans une pièce étoilée, il y a toujours une personne pouvant regarder toutes les personnes de
la pièce. En figure 2.4 on montre ce concept sous forme graphique en R2 .

Déf. 2.1.3 (Ensemble convexe) Soit C un sous-ensemble de Rn . On dit que C est un sous-
ensemble convexe de Rn si, pour tout x, y P C, le segment rx, ys appartient à C.

Dans la suite, par abus de langage et en absence d’ambiguı̈té, on parlera simplement d’un convexe
pour désigner un sous-ensemble convexe de Rn . Un interprétation intuitive consiste à dire que,
dans un pièce convexe, deux personnes peuvent toujours s’apercevoir. Dans ce sens, un convexe
est donc une pièce sans recoin. On montrera des exemples explicites d’ensembles convexes dans la
section 2.1.4. En figure 2.1 on montre un exemple de partie convexe et non convexe en R2 .

Figure 2.5 – Exemples simples de parties convexes et non convexes. A est convexe, B est non
convexe.

On a tous les éléments pour définir le concept de fonction convexe, qui va généraliser celui de
parabole, en traduisant mathématiquement la relation entre les points d’une parabole et ceux du
segment de la droite sécante à la parabole en deux points distincts.

Déf. 2.1.4 (Fonction convexe (concave) et strictement convexe (concave)) f : C Ñ R

une fonction définie sur un convexe C en Rn . On dit que f est convexe si :

@x, y P C f ptx ` p1 ´ tqyq ď tf pxq ` p1 ´ tqf pyq @t P r0, 1s.

16
f est dite strictement convexe si ça vaut la condition suivante 1 :

@x, y P C f ptx ` p1 ´ tqyq ă tf pxq ` p1 ´ tqf pyq @t Ps0, 1r,

f : C Ñ R, C Ď Rn est concave (strictement concave) si ´f est convexe (strictement convexe).

On montrera des exemples explicites de fonctions convexes dans la section 2.2.

Les fonctions affines, i.e. celles qui peuvent être écrites comme ça

f pxq “ xa, xy ` b “ at x ` b, a, b P Rn ,

i.e. par la somme d’une forme linéaire et d’une constante, sont toutes et seules les fonctions qui sont
convexes et concaves (non strictement) au même temps car elles satisfont l’inégalité non stricte de
convexité et de concavité avec une égalité (la preuve dans la section 2.2).
Dans la figure 2.6 on peut voir l’exemple d’une fonction convexe mais non strictement, son
graphe montre que les fonctions convexes peuvent avoir une infinité de minima.

Figure 2.6 – Exemple d’une fonction convexe mais non strictement convexe.

2.1.1 Caractérisation au premier ordre de la convexité et ses conséquences

Considérons maintenant le relation géométrique entre droites tangentes et parabole : dans la
figure 2.7 (gauche) on peut voir que la droite tangente à une parabole dans un point de son graphe
a toujours une ordonnée inférieure à celle du points du graphe de la parabole (à l’inverse des
sécantes). Dans la même figure à droite on voit la version 3D avec le plan tangent à la surface d’un
paraboloı̈de.
Comme on veut que les fonctions convexes soient une généralisation des paraboles et paraboloı̈des,
on attend que la propriété ci-dessus soit respectée par une fonction convexe. Le théorème suivant
montre que ceci n’est pas seulement vrai, mais la propriété géométrique qu’on vient d’examiner
caractérise toutes et seules les fonctions convexes et donc, comme pour toute caractérisation, elle
pourrait être utilisée comme définition alternative de fonction convexe, ce qui est très utile quand
l’inégalité qui définit la convexité d’une fonction n’est pas simple à vérifier.

Théorème 2.1.1 (Caractérisation au premier ordre de la convexité d’une fonction) Soit

f : C Ñ R, C convexe en Rn , f dérivable au moins une fois sur C. Alors :

f est convexe ðñ f pyq ´ f pxq ě x∇f pxq, y ´ xy @x, y P C. (2.1)

De plus, f est strictement convexe ðñ f pyq ´ f pxq ą x∇f pxq, y ´ xy @x, y P C.

1. Observer que t “ 0 et t “ 1 ne sont pas considérés car, sinon, on aurait f pyq ă f pyq quand t “ 0 et f pxq ă f pxq
quand t “ 1.

17
Figure 2.7 – Propriété géométrique des tangentes à une parabole et du plan tangent à un
paraboloı̈de.

Avant de démontrer le théorème, allons l’interpréter géométriquement :

— Si n “ 1, alors la thèse du théorème dit que f pyq ´ f pxq ě f 1 pxqpy ´ xq, i.e. f pyq ě
f pxq ` f 1 pxqpy ´ xq, à gauche on trouve les valeurs des ordonnés du graphe de f , tandis que
à droite on trouve les valeurs de l’ordonné sur la droite tangente au graphe de f en x. Ce
qu’on cherchait.
— Si n “ 2, alors, en développant le produit scalaire, on trouve f pyq ě Bx1 f px1 , x2 qpy1 ´ x1 q `
Bx2 f px1 , x2 qpy2 ´x2 q, cette fois-ce à droite on trouve les valeurs des ordonnés du plan tangent
au graphe de f en x “ px1 , x2 q, définit par l’équation z “ Bx1 f pxqpy1 ´x1 q`Bx2 f pxqpy2 ´x2 q,
encore une fois, ceci est cohérent avec la propriété géométrique qu’on voulait.
— Plus en général, l’équation z “ x∇f pxq, y ´ xy définit l’hyperplan tangent à la surface de
f en x, i.e. son approximation au premier ordre, l’inégalité de la thèse du théorème est
traduite souvent avec l’expression suivante : l’hyperplan tangent est un minorant affine en
chaque point de la surface d’une fonction convexe.
Preuve.
ñ : comme f est convexe ça vaut que

@x, y P C f ptx ` p1 ´ tqyq ď tf pxq ` p1 ´ tqf pyq @t P r0, 1s,

on peut réécrire tx ` p1 ´ tqy “ y ` tpx ´ yq et tf pxq ` p1 ´ tqf pyq “ f pyq ` tpf pxq ´ f pyqq, en
obtenant
@x, y P C f py ` tpx ´ yqq ď f pyq ` tpf pxq ´ f pyqq @t P r0, 1s.
Pour tout t Ps0, 1s (on considérera 0 comme cas limite) on peut diviser par t les deux côtés

f py ` tpx ´ yqq f pyq

@x, y P C ď ` f pxq ´ f pyq @t Ps0, 1s,
t t
i.e.
f py ` tpx ´ yqq ´ f pyq
f pxq ´ f pyq ě ,
t
en passant à la limite t Ñ 0 au deux côtés, et comme f pxq ´ f pyq ne dépend pas de t, on obtient

f py ` tpx ´ yqq ´ f pyq

f pxq ´ f pyq ě lim
tÑ0 t
grâce à la dérivabilité de f (qui est dans les hypothèses) la limite existe et elle donne Dx´y f pyq,
la dérivée directionnelle de f en direction du vecteur x ´ y calculée dans le point y. Grâce au
théorème du gradient (B.1) on peut réécrire Dx´y f pyq “ x∇f pyq, x ´ yy, donc

f pxq ´ f pyq ě x∇f pyq, x ´ yy @x, y P C,

18
x, y étant arbitraires, on peut les échanger, en obtenant

f pyq ´ f pxq ě x∇f pxq, y ´ xy @x, y P C,

qui est l’implication directe du théorème.

ð : si ça vaut f pyq ´ f pxq ě x∇f pxq, y ´ xy @x, y P C, alors, en particulier, on peut considérer le
point z “ tx ` p1 ´ tqy, qui appartient à C par convexité, et écrire les deux inégalités suivantes

f pxq ´ f pzq ě x∇f pzq, x ´ zy, (2.2)

f pyq ´ f pzq ě x∇f pzq, y ´ zy. (2.3)

On va multiplier les deux côtés de (2.2) par t et celles de (2.3) par 1 ´ t (on observe que, comme
ces quantités sont positives, l’ordre des inégalités ne change pas) :

tf pxq ´ tf pzq ě tx∇f pzq, x ´ zy,

p1 ´ tqf pyq ´ p1 ´ tqf pzq ě p1 ´ tqx∇f pzq, y ´ zy.

La somme des côtés gauches des deux dernières inégalités est supérieure à la somme des côtés
droits, i.e.

tf pxq ´ tf pzq ` p1 ´ tqf pyq ´ p1 ´ tqf pzq ě tx∇f pzq, x ´ zy ` p1 ´ tqx∇f pzq, y ´ zy,

un peu de maquillage mathématique :

tf pxq ´
tf ` p1 ´ tqf pyq ´ f pzq ` tf
pzq pzq ě x∇f pzq, tpx ´ zqy ` x∇f pzq, p1 ´ tqpy ´ zqy

tf pxq ` p1 ´ tqf pyq ´ f pzq ě x∇f pzq, tx ´

tz ` y ´ z ´ ty `
tz y
tf pxq ` p1 ´ tqf pyq ´ f pzq ě x∇f pzq, tx ` p1 ´ tqy ´ zy.
Mais, par définition, z “ tx`p1´tqy, donc tx`p1´tqy ´z “ 0 et alors x∇f pzq, tx`p1´tqy ´zy “ 0,
ce qui implique

tf pxq`p1´tqf pyq´f pzq ě 0 ðñ tf pxq`p1´tqf pyq ě f pzq ðñ tf pxq`p1´tqf pyq ě f ptx`p1´tqyq,

i.e. f ptx ` p1 ´ tqyq ď tf pxq ` p1 ´ tqf pyq @x, y P C et @t P r0, 1s, qui est la définition de convexité
de f . Donc l’implication inverse est prouvée.
La preuve de l’affirmation par rapport à la convexité stricte est laissé comme (simple) exercice. 2

Le théorème précédent a beaucoup de conséquences importantes, peut être, la plus importante

de toutes est la suivante, qui devrait faire comprendre clairement l’intérêt vers la convexité dans la
théorie de l’optimisation.

Théorème 2.1.2 (Fermat (1637)) Soit f : C Ñ R, C convexe et ouvert 2 en Rn , f convexe et

différentiable au moins une fois sur C. Alors :

x˚ “ arg min f pxq ðñ ∇f px˚ q “ 0, (2.4)

xPC

i.e. pour une fonction convexe dérivable au moins une fois sur un ouvert, la condition nécessaire de
stationnarité ∇f px˚ q “ 0 pour l’existence des extrema dévient une condition nécessaire et suffisante
pour l’existence de minima. Dit d’une manière encore plus directe : les points stationnaires d’une
fonction convexe et dérivable sur un ouvert sont des minima.
2. On souligne l’hypothèse de l’ouverture de C pour la validité du théorème.

19
Preuve. On sait que ∇f px˚ q “ 0 est nécessaire pour avoir x˚ “ arg minxPC f pxq, montrons qu’elle
est aussi suffisante sous les conditions du théorème. Pour cela, tout ce qu’on doit faire est d’utiliser
la caractérisation au premier ordre de la convexité d’une fonction en remplaçant x avec x˚ et
∇f px˚ q avec 0 dans l’éq. (2.1) :

f pyq ´ f px˚ q ě x∇f px˚ q, y ´ x˚ y “ x0, y ´ x˚ y “ 0 @y P C,

i.e. f pyq ě f px˚ q @y P C, i.e. x˚ “ arg min f pxq. 2

xPC

Une deuxième conséquence du théorème 2.1.1 est une autre caractérisation de la convexité, la
monotonie de la dérivée première 3 (en 1D) ou du gradient (en dimension supérieure à 1). On
commence avec la dimension 1.

Théorème 2.1.3 Soit f :sa, brÑ R, a, b P R, a ă b, f dérivable en sa, br. Alors :

f est convexe ðñ f 1 :sa, brÑ R est monotone croissante

De plus, f est strictement convexe ðñ f 1 est strictement croissante.

Si, de plus, f est dérivable deux fois sur sa, br, alors :

f est convexe ðñ f 1 :sa, brÑ R est monotone croissante ðñ f 2 pxq ě 0 @x Psa, br,

et pareil pour la stricte convexité.

Preuve.
ñ : soient f une fonction convexe et @x1 , x2 P C une couple de points qui satisfont la relation
d’ordre suivante : x2 ě x1 . Pour démontrer que f 1 est croissante, il faut démontrer qu’elle préserve
la relation d’ordre, i.e. que f 1 px2 q ě f 1 px1 q. Pour arriver à ça, on utilise la caractérisation (2.1)
pour les couples de points px1 , yq et px2 , yq, avec y P C arbitraire :

f pyq ě f px1 q ` f 1 px1 qpy ´ x1 q, (2.5)

f pyq ě f px2 q ` f 1 px2 qpy ´ x2 q (2.6)

comme y est arbitraire, on peut choisir y “ x2 dans la (2.5), en obtenant :

f px2 q ě f px1 q ` f 1 px1 qpx2 ´ x1 q

qui donne des informations significatives quand x2 ‰ x1 , i.e. x2 ´ x1 ą 0, en fait, dans ce cas,
l’inégalité précédente dévient
f px2 q ´ f px1 q
ě f 1 px1 q
x2 ´ x1
Également, on peut choisir y “ x1 dans la (2.6), en obtenant

f px1 q ě f px2 q ` f 1 px2 qpx1 ´ x2 q ðñ f px1 q ě f px2 q ´ f 1 px2 qpx2 ´ x1 q

d’où, en considérant encore le cas significatif x1 ‰ x2 :

f px2 q ´ f px1 q
f 1 px2 q ě .
x2 ´ x1
En résumé :
f px2 q ´ f px1 q
f 1 px2 q ě ě f 1 px1 q,
x2 ´ x1
3. Penser encore à la parabole peut aider à représenter graphiquement la monotonie de la dérivée. Par simplicité
considérons f pxq “ px ´ sq2 , alors f 1 pxq “ 2px ´ sq, qui tend vers ´8 quand x Ñ ´8, elle augment vers 0 quand
x “ s (le sommet) et elle augmente encore vers `8 quand x Ñ `8.

20
i.e. f 1 px2 q ě f 1 px1 q, i.e. f 1 est croissante. Si f 1 est dérivable, nous savons que f 1 est croissante sur
sa, br si et seulement si sa dérivée première est positive, i.e. pf 1 q1 “ f 2 ě 0 sur sa, br.

ð : soit f 1 croissante, x Psa, br fixé, et considérons la fonction auxiliaire

gpyq “ f pyq ´ f 1 pxqpy ´ xq ´ f pxq, y Psa, br.

La dérivée première de g par rapport à sa variable y est : g 1 pyq “ f 1 pyq ´ f 1 pxq, mais vu que f 1 est
croissante, g 1 pyq ĳ 0 si y ĳ x, i.e. x est un minimum global pour g.
Allons calculer la valeur de g dans son minimum gpxq “ f pxq ´ f 1 pxqpx ´ xq ´ f pxq “ 0, i.e. la
valeur minimale atteinte par g est 0, par conséquent gpyq ě 0 @y Psa, br, mais alors, par définition
de g, @y Psa, br ça vaut : f pyq ´ f 1 pxqpy ´ xq ´ f pxq ě 0, i.e. f pyq ´ f pxq ě f 1 pxqpy ´ xq, que, par
(2.1) est équivalent à la convexité de f .
La preuve de l’affirmation par rapport à la convexité stricte est laissé comme (simple) exercice. 2

Pour étendre ce résultat aux dimensions supérieures à 1 on a besoin d’un résultat (très important)
intermédiaire, une ultérieure caractérisation de la convexité, qu’on va examiner dans la section
suivante.

2.1.2 La convexité est une propriété unidimensionnelle : caractérisation

de la convexité via monotonie
Dans cette section on va examiner formaliser un fait qui devrait déjà être clair depuis la
définition de fonction convexe : la convexité est une propriété unidimensionnelle.
La formalisation passe par fixer un convexe C Ď Rn , deux points x, y P C et considérer le sous
ensemble de R définit comme ça

Dx,y “ tt P R : x ` ty P Cu Ď R, (2.7)

i.e. Dx,y contient les valeurs de t tels que le segment de la droite d’équation z “ x ` ty, qui passe
par x en direction de y, est inclus dans le convexe C.
Si f : C Ď Rn Ñ R est une fonction quelconque, on peut définir la fonction réelle de variable
réelle (et donc unidimensionnelle) suivante

g : Dx,y Ď R ÝÑ R
t ÞÝÑ gptq “ f px ` tyq,

i.e. g prends les valeurs de f restreinte au segment de la droite d’équation z “ x ` ty contenu en C.

Avec un abus de langage plutôt fréquent, mais tout à fait déchiffrable à la lumière de ce qu’on
vient de décrire avec rigueur, on dit que g est la restriction de f à la direction y en C.
Le théorème suivant formalise le caractère unidimensionnel de la convexité.

Théorème 2.1.4 Avec les notations ci-dessus, f est (strictement) convexe ðñ g est (stricte-
ment) convexe.

Preuve.
ñ : par l’absurde, supposons que f soit convexe et que g ne le soit pas, i.e. que

@λ P r0, 1s, Dt, s P Dx,y tels que : gpλt ` p1 ´ λqsq ą λgptq ` p1 ´ λqgpsq

i.e., par définition de g,

f px ` rλt ` p1 ´ λqssyq ą λf px ` tyq ` p1 ´ λqf px ` syq, (2.8)

21
mais :
x ` rλt ` p1 ´ λqssy “ x ` λty ` sy ´ λsy
“ (maquillage mathématique : ˘ λx)
“ λx ` λty ` x ` sy ´ λx ´ λsy
“ λpx ` tyq ` p1 ´ λqpx ` syq.

Si on écrit x ` ty ” ξ et x ` sy ” η, on peut reformuler l’inégalité (2.8) comme ça :

@λ P r0, 1s : f pλξ ` p1 ´ λqηq ą λf pξq ` p1 ´ λqf pηq,

mais, vu que t, s P Dx,y , ξ et η représentent deux points arbitraires de C, par définition de Dx,y ,
donc la dernière inégalité qu’on a écrit est absurde, car elle est contraire à la convexité de f .

ð : c’est pratiquement la même preuve à l’inverse, pour varier un peu on n’utilise pas l’argument
par l’absurde. g est convexe si @t, s P Dx,y et @λ P r0, 1s, gpλt ` p1 ´ λqsq ď λgptq ` p1 ´ λqgpsq, i.e.

f px ` rλt ` p1 ´ λqssyq ď λf px ` tyq ` p1 ´ λqf px ` syq. (2.9)

On observe que

f px ` rλt ` p1 ´ λqssyq “ f px ` λty ` sy ´ λsyq

“ (maquillage mathématique : ˘ λx)
“ f pλx ` λty ` x ` sy ´ λx ´ λsyq
“ f pλpx ` tyq ` p1 ´ λqpx ` syqq.

Posons, comme avant, x ` ty ” ξ et x ` sy ” η, alors on peut réécrire (2.9) comme ça :

@ξ, η P C, f pλξ ` p1 ´ λqηq ď λf pξq ` p1 ´ λqf pηq @λ P r0, 1s,

i.e. la convexité de f .
La preuve de l’affirmation par rapport à la convexité stricte est laissé comme (simple) exercice. 2

Maintenant on peut étendre le théorème 2.1.3 à dimensions supérieures.

Corollaire 2.1.1 Soit f : C Ď Rn , C convexe et ouvert, f différentiable au moins une fois sur C.
Alors f est (strictement) convexe ðñ la restriction de ∇f sur Dx,y est (strictement) croissante
pour n’importe quel choix de x, y P C.

Preuve. Ce résultat est une conséquence directe du théorème précédent et de la caractérisation

(2.1.3) de la convexité (et de la convexité stricte). En fait, ça suffit d’observer que la restriction du
gradient de f sur l’axe unidimensionnel défini par la droite qui a la direction du vecteur y P C
et qui passe par x est la dérivée première de la fonction réelle de variable réelle gptq “ f px ` tyq,
t P Dx,y .
On sait que f est convexe ðñ g est convexe (théorème 2.1.4), i.e. monotone croissante
(théorème 2.1.3), d’ici la thèse. 2

22
2.1.3 Caractérisation au second ordre de la convexité
Dans cette section of va donner une autre caractérisation de la convexité très importante et utile,
cette fois-ci sous l’hypothèse d’existence de la dérivée seconde. Dans la preuve, on profitera pour
voir en action l’artillerie mathématique qu’on vient de développer dans les sections précédentes.

Théorème 2.1.5 Soit f : C Ď Rn Ñ R, C convexe et ouvert, et soit f deux fois différentiable sur
C, alors :

f est convexe ðñ la matrice Hessienne Hf pxq est semi-définie positive @x P C.

De plus, f est strictement convexe ðñ Hf pxq est définie positive @x P C.

Preuve. Si n “ 1, alors 4 C est un intervalle ouvert de R et la matrice Hessienne de f en x est

simplement la dérivée deuxième de f : f 2 pxq. Grâce au théorème 2.1.3, on sait que f est convexe
sur C ðñ f 1 est croissante sur C, mais, comme C est un intervalle, ceci est équivalent à dire que
f 2 pxq ě 0 @x P C.
L’extension au cas n ą 1 est faite à l’aide du théorème 2.1.4. L’argument est le suivant :
— la convexité de f est équivalente à celle des ses restrictions unidimensionnelles gptq “ f px`tyq,
@x, y P C, t P Dx,y , où Dx,y est défini en (2.7) ;
— on vient de démontrer que g est convexe ðñ g 2 ptq ě 0 @t P Dx,y ;
— grâce à la formule (B.4), on peut vérifier (c’est un exercice utile qu’on invite à faire. . .)
que g 2 ptq “ 21 xHf px ` tyqy, yy. Donc, la positivité de g 2 ptq est équivalente à la semi-définie
positivité de Hf .
La preuve de l’affirmation par rapport à la convexité stricte est laissé comme (simple) exercice. 2

Exemple. Allons voir un exemple d’utilisation de ce théorème, qui est particulièrement efficace
1
quand n “ 2. Soit f px, yq “ xy définie sur C “ tpx, yq P R2 , x, y ą 0u. Déterminer si f est convexe.
C est évidemment convexe. Allons utiliser la caractérisation au deuxième ordre : la matrice
Hessienne de f s’écrit
1 x22 xy 1 ˙
ˆ
Hf px, yq “ 1 2
xy xy y2

Hf px, yq est une matrice réelle et symétrique, donc elle est diagonalisable. Si P px, yq est la matrice
qui a sur les colonnes les valeurs propres de Hf px, yq, alors la matrice P px, yqHf px, yqP ´1 px, yq a
sur la diagonale les deux valeurs propres λ1 , λ2 de Hf px, yq et 0 ailleurs.
Nous rappelons que detpHf px, yqq “ detpP px, yqHf px, yqP ´1 px, yqq “ λ1 ¨ λ2 et aussi que
TrpHf px, yqq “ TrpP px, yqHf px, yqP ´1 px, yqq “ λ1 ` λ2 , vu que le déterminant et la trace d’une
matrice sont invariants par changement de base.
Par calcul direct :
3
det Hf px, yq “ 4 4 “ λ1 ¨ λ2 ą 0,
x y
donc les deux valeurs propres de Hf ont le même signe et ils sont non nuls. De plus :
ˆ ˙
2 1 1
Tr Hf px, yq “ ` 2 “ λ1 ` λ2 ą 0,
xy x2 y

ce qui implique que Hf px, yq a deux valeurs propres strictement positifs, donc Hf est définie
positive et alors f est strictement convexe.
4. Un argument élégant pour démontrer que f 2 pxq ě 0 implique la convexité de f dans le cas n “ 1 passe par la
formule de Taylor au deuxième ordre avec reste de Lagrange, qui dit qu’il existe ξ appartenant au segment de droite
entre x et y, tel que f pyq “ f pxq ` f 1 pxqpy ´ xq ` 12 f 2 pξqpy ´ xq2 . Si f 2 pxq ě 0 @x P C, alors 12 f 2 pξqpy ´ xq2 ě 0
yÑx
et alors f pyq ´ f pxq ě f 1 pxqpy ´ xq, i.e. la caractérisation de la convexité au premier ordre.

23
2.1.4 Exemples d’ensembles convexes
Commençons avec des exemples élémentaires.
1. Dans R les ensembles convexes sont exactement les intervalles.

2. Une droite reliant deux éléments de Rn est un ensemble convexe.

3. Les sous-espaces vectoriels de Rn sont convexes.

4. Dans Rn , Ur pcq “ tx P Rn : }x ´ c} ď ru le voisinage fermé de centre c P Rn et de

rayon r ą 0 associée à une norme quelconque } } est un ensemble convexe. Donc, en
particulier, les cercles, les sphères, les carrés et les cubes sont convexes.
En effet, en utilisant l’homogénéité et l’inégalité triangulaire, si }x ´ c} ď r, }y ´ c} ď r et
t P r0, 1s, on a

}tx ` p1 ´ tqy ´ c} “ }tpx ´ cq ` p1 ´ tqpy ´ cq} ď t}x ´ c} ` p1 ´ tq}y ´ c} ď tr ` p1 ´ tqr “ r.

En figure 2.8 on peut voir des exemples avec trois normes. Le résultat reste vrai aussi pour
les voisinages ouverts Ur pcq.

Figure 2.8 – Exemples de voisinages unités fermés dans R2 . À gauche : au sens de la norme }}1 ,
au milieu : au sens de la norme Euclidienne }}2 , à droite : au sens de la norme }}8 . La définition
de ces normes sera rappelée dans la section 2.2.1.

Allons maintenant à examiner des exemples plus compliqués et très importantes pour l’optimi-
sation.

n-Simplexes.
Soient x0 , . . . , xn P Rn affinement indépendantes, i.e. x1 ´ x0 , . . . , xn ´ x0 sont linéairement
indépendantes, alors un n-simplexe est un ensemble définit comme ça
# +
ÿn ÿn
n
S“ xPR : x“ αi xi , αi ě 0 @i “ 1, .., n, αi “ 1 .
i“0 i“1

Cas particuliers : un 2-simplexe est un triangle et un 3-simplexe est un tétraèdre, comme le montre
la figure 2.9.

Cône convexe
Les cônes jouent un rôle important dans la formulation des contraintes d’inégalités.

Déf. 2.1.5 Un ensemble C est appelée cône si pour tout x appartenant à C et t ě 0, tx appartient
à C.

24
Figure 2.9 – Simplexe dans R3 : tétraèdre.

Géométriquement, un cône est la surface obtenue par l’union de demi-droites qui ont une origine
commune, l’apex, c’est-à-dire le plus haut sommet, et qui connectent l’apex avec une courbe (dite
directrice) différente de l’apex et non nécessairement fermé. Un cône n’est pas nécessairement un
convexe comme le montre la figure 2.10.

Figure 2.10 – Exemple d’un cône non convexe en R3 .

Déf. 2.1.6 Un cône convexe est un ensemble qui est à la fois un cône et un convexe.

On laisse comme exercice de montrer la caractérisation suivante des cônes convexes.

Théorème 2.1.6 Un ensemble C est un cône convexe si et seulement s’il est stable par rapport
aux combinaisons linéaires avec coefficients non négatifs de ses éléments.
Les cônes convexes nous donnent la possibilité de montrer des exemples importants de convexes
non bornés : dans la figure 2.11, les éléments s’écrivant sous la forme t1 x1 ` t2 x2 avec t1 , t2 ě 0
sont les éléments appartenant au domaine d’apex 0 et délimité par les demi-droites passant,
respectivement, par x1 et x2 .
Un exemple simple de cône convexe est l’orthant positif : il s’agit de l’ensemble

Rn` :“ tx P Rn |x ě 0u,

où la notation x ě 0 signifie que pour tout i P t1, ..nu, la composante xi de x est ě 0 (figure 2.12).

Hyperplans et demi-planes
Déf. 2.1.7 On appelle hyperplan tout sous-ensemble de Rn définit par

Hs,r “ tx P Rn : st x “ xs, xy “ ru

avec r P R et s P Rn .

25
Figure 2.11 – Le domaine contient tous les éléments de la forme t1 x1 ` t2 x2 avec t1 , t2 ě 0. L’apex
0 correspond à t1 “ t2 “ 0.

Figure 2.12 – Orthant positif dans R2 .

Géométriquement, il s’agit de l’ensemble d’éléments dont le produit scalaire avec un vecteur

donné s, appelé vecteur normal, reste constant. La constante r détermine le décalage de l’hy-
perplan affine par rapport à l’origine. Analytiquement, l’hyperplan est la solution de l’équation
linéaire xs, xy “ r d’inconnue x.
Démontrons que Hs,r est un convexe : il faut prouver que si x, y P Hs,r et t P r0, 1s, alors
tx ` p1 ´ tqy P Hs,r , i.e. xs, tx ` p1 ´ tqyy “ r.
Comme x, y P Hs,r , xs, xy “ xs, yy “ r, donc @t P r0, 1s :
xs, txy “ txs, xy “ tr,
xs, p1 ´ tqyy “ p1 ´ tqxs, yy “ p1 ´ tqr,
donc, si on fait la somme des côtés gauche et droite des deux dernières équations, on obtient :
xs, txy ` xs, p1 ´ tqyy “ xs, tx ` p1 ´ tqyy “ tr ` p1 ´ tqr “ r.

On va expliquer maintenant pourquoi s est dit vecteur normal. Observons maintenant que, si a
est un élément quelconque fixé de Hs,r , on a :
Hs,r “ tx P Rn : xs, xy “ xs, ayu “ tx P Rn : xs, x ´ ay “ 0u “ tx P Rn : x ´ a P Hs,0 u.
Fixons s et faisons varier r dans Rzt0u : les hyperplans Hs,r sont les translations (par les vecteurs
a) de l’hyperplan Hs,0 . Or Hs,0 est le sous espace vectoriel des vecteurs perpendiculaires à s que
l’on note par tsuK , on peut donc écrire
Hs,r “ a ` tsuK ,
avec a P Hs,r . En figure 2.13 on montre la représentation graphique bidimensionnelle qu’on trouve
habituellement dans les livres de ce qu’on vient de dire.
Un hyperplan affine divise Rn en deux sous-ensembles :

26
Figure 2.13 – Un hyperplan de R2 de vecteur normal s et a un élément de cet hyperplan. Pour
tout élément x de l’hyperplan, x ´ a est orthogonal à s.

Déf. 2.1.8 On appelle demi-plan fermé un sous-ensemble de Rn de la forme

`
Hs,r :“ tx P Rn : xs, xy ě ru
ou
´
Hs,r :“ tx P Rn : xs, xy ď ru
avec r P R et s P Rn .
De même, si a un élément quelconque de l’hyperplan associé, i.e. vérifiant xs, ay “ r, alors
` ´ ` ´
xs, xy ´ xs, ay “ xs, x ´ ay qui est ě 0 @x P Hs,r et ď 0 @x P Hs,r , donc les ensembles Hs,r et Hs,r
peuvent s’écrire, respectivement, sous la forme
`
Hs,r “ tx P Rn : xs, x ´ ay ě 0u,
´
Hs,r “ tx P Rn : xs, x ´ ay ď 0u.
´
Ceci nous permet d’interpréter géométriquement Hs,r comme l’ensemble composé par s plus tout
`
vecteur faisant un angle obtus π{2 ď ϑ ď π avec s et Hs,r comme l’ensemble composé par s plus
tout vecteur faisant un angle aigu 0 ď ϑ ď π{2 avec s.
Dans les figures 2.14 et 2.15 on montre la représentation graphique de cela en 2D.
Les demi-plans sont des ensembles convexes (on fait la preuve dans un de deux cas). Soient
´ ´
x, y P Hs,r et t P r0, 1s, montrons que tx ` p1 ´ tqy appartient à Hs,r : xs, tx ` p1 ´ tqyy “
txs, xy ` p1 ´ tqxs, yy. Comme t P r0, 1s, p1 ´ tq P r0, 1s et txs, xy ` p1 ´ tqxs, yy ď tr ` p1 ´ tqr “ r.
S’il l’on remplace l’inégalité large dans la définition de demi-plan par une inégalité stricte, on
obtient la définition de demi-plan ouvert.
Puisque le produit scalaire . ÞÑ xs, .y est une application continue, un demi-plan ouvert (resp.
fermé) est un ouvert (resp. fermé) de l’espace Rn muni de sa topologie usuelle. Un demi-plan
ouvert est l’intérieur du demi-plan fermé correspondant et un demi-plan fermé est l’adhérence du
demi-plan ouvert correspondant.

Ensembles de sous-niveau
Soit C Ď Rn un convexe et f : C Ñ R une fonction convexe. Pour tout λ P R on définit
l’ensemble de λ-sous-niveau de f comme ceci
Sλ “ tx P C : f pxq ď λu,
i.e. les points du domaine de f tels que leurs images sont ď à λ, comme le montre la figure 2.16.
Montrons que Sλ est convexe : soient x, y P Sλ , il faut montrer que @t P r0, 1s, tx ` p1 ´ tqy P C,
i.e. que f ptx ` p1 ´ tqyq ď λ :
f ptx ` p1 ´ tqyq ď tf pxq ` p1 ´ tqf pyq ď tλ ` p1 ´ tqλ “ λ.
(convexité) x,yPSλ

27
Figure 2.14 – L’hyper plan affine divise R2 en deux demi-plans : un demi-plan (en gris) de R2
d’équation xs, xy ď r se situant dans la direction de ´s et celui déterminé par xs, xy ě r se situant
dans la direction de s.

Figure 2.15 – Le vecteur x1 ´ a fait un angle aigu avec s, il n’appartient pas donc à l’hyperplan
´
Hs,r . Le vecteur x2 ´ a fait un angle obtus avec s donc il y appartient.

Figure 2.16 – En rouge on voit l’intervalle qui représente un ensemble de sous niveau en 2D.

Les ensembles de sur-niveau, définis de la manière qu’on peut imaginer, ne sons pas convexes.

28
Ellipsoı̈des
Déf. 2.1.9 Soit c P Rn et P P M pn, Rq une matrice définie positive. On appelle ellipsoı̈de de
centre c tout sous-ensemble de Rn de la forme

E :“ tx P Rn : xx ´ c, P px ´ cqy ď 1u.

Comme on l’a vu dans l’Annexe 1, une matrice définie positive P peut être écrite comme ça
P “ At A, pour une matrice opportune A P M pn, Rq, donc la condition xx ´ c, P px ´ cqy ď 1 dévient

xx ´ c, At Apx ´ cqy “ xApx ´ cq, Apx ´ cqy “ }Apx ´ cq}2 ď 1,

qui montre que, si A “ 1r In , alors on obtient une hypersphère de rayon r et de centre c comme cas
particulier, vue que, dans ce cas, }Apx ´ cq}2 ď 1 est équivalent à }x ´ c}2 ď r2 .
La matrice P détermine comment l’ellipsoı̈de s’étend à partir du centre c dans chaque
? direction.
Les valeurs propres λi de la matrice P donnent les longueurs de ses demi-axes : 1{ λi .
Le fait qu’un ellipsoı̈de est un ensemble convexe suit simplement de la condition }Apx ´ cq}2 ď 1.

Matrices symétriques définies positive

On termine avec un exemple très abstrait, mais qui a beaucoup d’applications. L’ensemble

Sn` “ tA P M pn, Rq : At “ A, A semi-définie positiveu,

2
est un cône convexe en Rn , en fait, il est clair que la multiplication par un coefficient réel positif
ne change pas la symétrie ou la définie positivité d’une matrice ; de plus, si A, B P Sn` et t P r0, 1s,
alors, pour tout x P Rn :

xx, ptA ` p1 ´ tqBqxy “ txx, Axy ` p1 ´ tqxx, Bxy ě 0,

grâce au fait que A, B sont définies positive.

Polyèdres
Déf. 2.1.10 Soient A une matrice réelle de taille m ˆ n et b un vecteur de Rm . Un polyèdre est
un sous-ensemble de Rn qui s’écrit sous la forme

P :“ tx P Rn : Ax ď bu

Si on identifie la j-ème ligne de la matrice A avec un vecteur de Rn et on la note Aj et, de

même, si on note avec bj la j-ième composante du vecteur b, alors l’ensemble P s’écrit sous la forme

P :“ tx P Rn : xAj , xy ď bj , j “ 1, .., mu,

il s’agit donc d’une intersection finie de demi-plans fermés de Rn (voir figure 2.17). Comme on le
verra dans la section suivante, l’intersection d’ensembles convexes est encore un convexe, ce qui
donne la prouve de la proposition suivante.

Théorème 2.1.7 Un polyèdre est un ensemble convexe de Rn .

29
Figure 2.17 – Le polyèdre P est l’intersection des demi-plans de vecteurs normaux s1 , .., s5 .

2.1.5 Opérations qui préservent la convexité des ensembles

Allons examiner des opérations qui préservent la convexité des ensembles et leurs conséquences.
Commençons pas la suivante.

Théorème 2.1.8 Soit pCi qi“1,...,n une famille de convexes de Rn . Alors leur intersection
Ş
Ci
i“1,...,n
est un convexe.
Ş
Preuve. Presque immédiate : si x, y P Ci , alors, par convexité, tx ` p1 ´ tqy P Ci , pour tout
i“1,...,n
2
Ş
t P r0, 1s et i “ 1, . . . , n, donc tx ` p1 ´ tqy P Ci , i.e. la convexité de l’intersection.
i“1,...,n

Cependant, l’union de convexes n’est pas en général un convexe. Par exemple les segments r0, 1s
et r2, 3s sont des convexes de R, mais r0, 1s Y r2, 3s n’est pas un convexe car pour tout t Ps0, 1r,
t ¨ 1 ` p1 ´ tq ¨ 2 “ 2 ´ t n’appartient pas à r0, 1s Y r2, 3s.

Théorème 2.1.9 Soient pCi qii n1,..,N une famille finie de convexes de Rni . Alors leur produit
cartésien C1 ˆ .. ˆ CN est un convexe de Rn1 ˆ .. ˆ RnN .

On laisse la simple preuve du théorème comme exercice.

Théorème 2.1.10 Soit A : Rn Ñ Rm une application affine, alors :

1. si C est un convexe de Rn alors l’image directe de C par A, notée ApCq, est un convexe de
Rm ;
2. si D est un convexe de Rm alors l’image réciproque de C par A, notée A´1 pDq, est un
convexe de Rn .

Preuve. Il est suffisant d’observer que, si x, y sont deux éléments de Rn , par affinité de A, l’image
du segment de droite rx, ys par A est le segment de droite rApxq, Apyqs Ď Rm , ceci prouve que
ApCq est convexe, mais aussi que A´1 pCq l’est, car si x, y sont deux éléments de Rn tels que Apxq
et Apyq sont deux éléments du convexe D, alors tout élément du segment rx, ys a son image dans
rApxq, Apyqs Ď D. 2

Des conséquences directes des résultats ci-dessus sont le suivants (C Ď Rn ).

1. L’opposé ´C “ t´x, x P Cu d’un convexe C est un convexe.
2. Le translaté a ` C “ ta ` x, x P Cu d’un convexe C par un vecteur a de Rn est un convexe.
3. L’homothétie αC d’un convexe C de rapport α P R est un convexe.
4. La somme vectorielle de convexes C1 , C2 Ď Rn , C1 ` C2 “ tx1 ` x2 , x1 P C1 , x2 P C2 u,
est un convexe.

30
5. Plus généralement, si C1 , C2 Ď Rn sont convexes et si α1 et α2 sont deux réels, alors
α1 C1 ` α2 C2 “ tα1 x1 ` α2 x2 , x1 P C1 , x2 P C2 u est un convexe. En fait, il s’agit de l’image
directe du convexe C1 ˆC2 par l’application affine A : px1 , x2 q P Rn ˆRn ÞÑ α1 x1 `α2 x2 P Rn .

31
2.2 Comment détecter la convexité de fonctions : fonctions
convexes standards et opérations qui préservent leur
convexité
Dans la suite du cours, on verra que, dans un problème d’optimisation, détecter la convexité de
la fonction objectif et des éventuelles contraintes est cruciale : on verra que les problèmes avec
cette propriété possèdent des caractéristiques théoriques très agréables (par exemple, on a vu
que les conditions locales nécessaires d’optimalité sont suffisantes pour fonctions convexes) et, ce
qui est beaucoup plus important, les problèmes convexes peuvent être résolus efficacement (dans
le sens théorique et, dans une certaine mesure, dans le sens pratique de ce mot), ce qui n’est
pas, malheureusement, le cas pour des problèmes non convexes généraux. C’est pourquoi il est
si important de savoir comment détecter la convexité d’une fonction donnée. On a bien sûr la
possibilité d’utiliser les caractérisations au premier et deuxième ordre qu’on a vu, mais on peut
aussi suivre la procédure suivante.
Le plan de notre recherche est typique dans le cadre mathématique et c’est exactement ce qu’on
utilise en analyse pour détecter la continuité d’une fonction : ça serait vraiment un désastre si
chaque fois que nous devons prouver la continuité d’une fonction, nous étions obligés d’utiliser
la définition ! ε ´ δ " ! Ce qu’on fait c’est d’utiliser cette définition sur les fonctions élémentaires
de l’analyse, nos ! matières premières ", e sur les opérations élémentaires entre elles, nos ! outils
premiers ", comme l’addition, la multiplication, la composition, etc., mais après que cet effort
soit fait une seule fois, nous n’avons normalement aucune difficulté à prouver la continuité d’une
fonction donnée : il suffit de démontrer qu’elle peut être obtenue, en nombre fini d’étapes, de nos
matières premières en appliquant nos outils premiers, i.e. les règles de combinaison qui préservent
la continuité. Typiquement, cette démonstration est effectuée par un mot simple ! évident " ou
même est assumée par défaut.
C’est exactement le cas avec la convexité. Ici nous devons également préciser la liste d’un certain
nombre de fonctions convexes standards et d’opérations qui préservent la convexité.

2.2.1 Les fonctions convexes standards

On invite à prouver les premières 7 propriétés de la liste suivante.
‚ ex

‚ ´ log x

‚ xa , avec x ą 0 et a ě 1 ou a ď 0.

‚ ´xa , avec x ą 0 et a P r0, 1s

‚ |x|a , x P R, a ě 1

‚ x log x, x ą 0

‚ px ´ bq` “ maxtx ´ b, 0u et px ´ bq´ “ ´ mintx ´ b, 0u sont convexes @x, b P Rn

‚ Les fonctions affines, et donc, en particulier, les fonctions linéaires, sont convexes, en fait,
si f pxq “ xa, xy ` b, a, b, x P Rn , alors @t P r0, 1s :

f ptx ` p1 ´ tqyq “ xa, tx ` p1 ´ tqyy ` b “ txa, xy ` p1 ´ tqxa, yy ` bloooomoooon

` tb ´ tb
tb`p1´tqb

“ tpxa, xy ` bq ` p1 ´ tqpxa, yy ` bq “ tf pxq ` p1 ´ tqf pyq.

32
‚ Une fonction f : Rn Ñ R, positivement homogène de degré 1 et sous-linéaire, i.e. :
f ptxq “ tf pxq, @t ě 0, et, f px ` yq ď f pxq ` f pyq @x, y P Rn ,
est convexe. En fait : @t P r0, 1s, @x, y P Rn
f ptx ` p1 ´ tqyq ď f ptxq ` p1 ´ tqf pyq ď tf pxq ` p1 ´ tqf pyq.
sous-lin. homog.

‚ Comme cas particulier du cas précédent on obtient le très important résultat que : toutes
les normes sont des fonctions convexes } } : Rn Ñ R` 0 , car elles sont positivement
homogènes de degré 1 et, grâce à l’inégalité triangulaire, sous-linéaires. Dans la figure (2.18)
on peut voir la représentation graphique en 2D du voisinage de rayon 1 centré en 0 engendré
par les normes-` :
" b * " *
` 2 ` ` ` 8 2
U0 p1q “ x P R : }x}` “ |x1 | ` |x2 | “ 1 , U0 p1q “ x P R : }x}8 “ max |xi | “ 1 .
i“1,2

Figure 2.18 – Voisinage de rayon 1 centré en 0 engendré par les normes-` en R2 .

Exercice : vérifier que f pxq “ x2 est une fonction strictement convexe sur R.
Il faut vérifier que f ptx`p1´tqyq ă tf pxq`p1´tqf pyq @t Ps0, 1r @x, y P R, x ‰ y, i.e. rtx`p1´tqys2 ă
tx2 ` p1 ´ tqy 2 .
rtx ` p1 ´ tqys2 ă tx2 ` p1 ´ tqy 2
?
t2 x2 ` p1 ´ tq2 y 2 ` 2tp1 ´ tqxy ă tx2 ` p1 ´ tqy 2
?
pt2 ´ tqx2 ` rp1 ´ tq2 ` p1 ´ tqsy 2 ` 2tp1 ´ tqxy ă 0
?
2 2
tpt ´ 1qx ` p1 ´ tqrp1 ´ tq ` 1sy ` 2tp1 ´ tqxy ă 0
?
2 2
tpt ´ 1qx ` tpt ´ 1qy ´ tpt ´ 1q2xy ă 0
?
2 2
tpt ´ 1qrx ` y ´ 2xys ă 0
?
2
t pt ´ 1qpx ´ yq ă 0.
pą0q pă0q pą0q oui !

33
2.2.2 Opérations qui préservent la convexité de fonctions
‚ Si f est une fonction convexe et k ě 0, alors kf est une fonctions convexe. La preuve est
laissé comme exercice.

‚ La combinaison conique de fonctions convexes est une fonction convexe, i.e. si f1 , . . . , fn :

n
Rn Ñ R sont des fonctions convexes et c1 , . . . , cn ě 0, alors
ř
ci fi est une fonction convexe.
i“1
On fait la preuve pour n “ 2, le cas général suit par l’induction. Soient f, g : Rn Ñ R
convexes, a, b ě 0 et soit h “ af ` bg, alors @t P r0, 1s

hptx ` p1 ´ tqyq “ af ptx ` p1 ´ tqyq ` bgptx ` p1 ´ tqyq “ (af et bg convexes car a, b ě 0)

ď artf pxq ` p1 ´ tqf pyqs ` brtgpxq ` p1 ´ tqgpyqs “ (réarrangement)
“ traf pxq ` bgpxqs ` p1 ´ tqraf pyq ` bgpyqs
“ thpxq ` p1 ´ tqhpyq.

‚ Si on fait une combinaison linéaire de fonctions convexes avec des coefficients de signe
alterne, alors la fonction qu’on obtient peut être convexe, mais on ne peut pas le garantir en
général (ça dépend de la relation entre les coefficients et l’expression analytique des fonctions).

‚ La composition d’une fonction convexe avec une fonction affine est encore une fonction
convexe : A P M pn, Rq, b P Rn , f : Rn Ñ R convexe, alors gpxq “ f pAx ` bq @x P Rn est
convexe.

‚ Si f1 , f2 : Rn Ñ R sont convexes, alors f “ maxpf1 , f2 q est convexe. On verra la preuve de

ce résultat dans la section 2.3.

‚ La composition d’une fonction convexe avec une fonction convexe et croissante est encore
une fonction convexe : C Ď Rn ensemble convexe, f : C Ñ R convexe, φ : f pCq Ñ R convexe
et croissante, alors φ ˝ f : C Ñ R est convexe.

34
2.2.3 L’interprétation analytique du problème des moindres carrés
Allons voire une conséquence importante de ces propriétés : pour toute matrice A P Mm,n pRq
et tout vecteur b P Rn , la fonction

fA,b : Rn ÝÑ R
x ÞÝÑ fA,b pxq “ 12 }Ax ´ b}2 ,

est convexe, comme on le voit dans le diagramme suivant,

Rn ÝÑ Rn ÝÑ R`0 ÝÑ R`0 ÝÑ R`
0
1
x ÞÝÑ Ax ´ b ÞÝÑ }Ax ´ b} ÞÝÑ }Ax ´ b}2 ÞÝÑ 2 }Ax´ b}2 ,

elle est obtenue par composition entre une fonction affine, une fonction convexe (la norme Eu-
clidienne), une fonction convexe et croissante (sur R` 0 !) et par multiplication d’un coefficient
positif.
Comme on l’a vu dans la section B.2.2, formule (B.2.5), ∇fA,b pxq “ At pAx ´ bq, donc les
équations de Euler-Lagrange pour la fonction fA,b sont :

∇fA,b px̄q “ 0 ðñ At pAx̄ ´ bq “ 0 ðñ At Ax̄ “ At b,

i.e. le point stationnaire x̄ de la fonction fA,b pxq “ 12 }Ax ´ b}2 est les solutions des équations
normales associées au système linéaire Ax “ b qu’on sait être la solution du système dans le sens
des moindres carrés.
Vu que fA,b est convexe, les points stationnaires de fA,b sont de minima, ça montre l’in-
terprétation analytique au problème des moindres carrés, qui se rajoute à l’interprétation géométrique
et algébrique, comme résumé ci-dessous.

Les trois interprétations alternatives du problème des moindres carrés

x̄ “ arg min }Ax ´ b}2

xPRn

— Interprétation géométrique : Ax̄ “ PImpAq b, i.e. résolution du système linéaire projeté

sur l’espace image de A ;

— Interprétation algébrique : At Ax̄ “ At b, i.e. résolution des équations normales ;

` ˘
— Interprétation analytique : ∇ 12 }Ax̄ ´ b}2 “ 0, i.e. résolution des équations de Euler-
Lagrange associées à la fonction fA,b pxq “ 12 }Ax ´ b}2 .

35
2.3 Lien entre ensembles convexes et fonctions convexes :
épigraphe et hypographe, enveloppe convexe
Dans cette section on va formaliser le lien entre fonctions et ensembles convexes. Commençons
par rappeler que le graphe d’une fonction f : Ω Ď Rn Ñ R, est le sous-ensemble de Rn`1 défini
par :
graphepf q “ tpx, yq P Ω ˆ R : y “ f pxqu.
Le graphe de f est un sous-ensemble de l’ensemble suivant, qui joue un rôle très important dans la
théorie de l’optimisation.

Déf. 2.3.1 (Épigraphe) Soit f : Ω Ď Rn Ñ R, on appelle épigraphe de f le sous-ensemble de

Rn`1 défini par :
Epipf q “ tpx, λq P Ω ˆ R : λ ě f pxqu.

Le nom dérive du fait que επι veut dire ! au-dessus ", qui fait référence au fait que les valeurs de λ
dans la deuxième entrée des coordonnés de l’épigraphe sont au-dessus du graphe de f , comme le
montre la figure 2.19.

Figure 2.19 – Le graphe des fonctions est dessinée en trait foncé. L’épigraphe est constitué de la
partie grise et du graphe de la fonction.

La figure montre aussi que l’épigraphe d’une fonction convexe est un ensemble convexe et que
celui d’une fonction non convexe n’est pas un ensemble convexe. Le résultat suivant montre que
ceci n’est pas un hasard, mais la règle.

Théorème 2.3.1 Soit f : C Ď Rn Ñ R une fonction et C un ensemble convexe. Alors f est

convexe (en tant que fonction) si et seulement si Epipf q est convexe (en tant que ensemble).

Avant de démontrer le théorème, il faut le commenter : d’un côté, à l’aide de la définition

d’épigraphe, on peut construire, à partir d’une fonction convexe f , l’ensemble convexe Epipf q,
réciproquement, si Ω Ă Rn ˆ R est l’épigraphe d’une certaine fonction convexe, alors on obtient
cette fonction via
f pxq “ inf λ,
px,λqPΩ

car les valeurs du graphe de f sont les minimiseurs des valeurs de λ dans l’épigraphe.
Ceci montre un lien étroit entre les fonctions convexes et les ensembles convexes.

Preuve.
ñ Supposons que f soit convexe et montrons que Epipf q est convexe : soient px, λq, py, ρq P
Epipf q, il faut démontrer que, pour tout t P r0, 1s, tpx, λq`p1´tqpy, ρq “ ptx`p1´tqy, tλ`p1´tqρq P
Epipf q, mais ça, par définition, est vrai si et seulement si tλ ` p1 ´ tqρ ě f ptx ` p1 ´ tqyq.
Comme f est convexe, on a

f ptx ` p1 ´ tqyq ď tf pxq ` p1 ´ tqf pyq ď tλ ` p1 ´ tqρ (par définition d’épigraphe).

36
ð Supposons que Epipf q soit convexe et montrons que f est convexe : on rappelle que le
graphe de f est inclus dans son épigraphe, donc @x, y P C, px, f pxqq, py, f pyqq P Epipf q, comme on a
supposé que Epipf q est convexe, pour tout t P r0, 1s ça vaut que tpx, f pxqq`p1´tqpy, f pyqq P Epipf q,
d’où ptx`p1´tqy, tf pxq`p1´tqf pxqq P Epipf q, c’est à dire f ptx`p1´tqyq ď tf pxq`p1´tqf pxq. 2

Grâce à ce théorème la preuve du fait que, si f1 , f2 sont convexes, alors f “ maxpf1 , f2 q est
convexe, est immédiate. En fait, f est une fonction convexe ðñ Epipf q est un ensemble convexe,
mais l’épigraphe de f est l’intersection de l’épigraphe de f1 et de f2 , qui sont deux ensembles
convexes car f1 , f2 sont convexes. Comme l’intersection d’ensembles convexe est encore un ensemble
convexe, Epipf q est convexe et donc f est convexe.

Allons renverser l’ordre. . .

Déf. 2.3.2 (Hypographe) Soit f : Ω Ď Rn Ñ R, on appelle hypographe de f le sous-ensemble

de Rn`1 défini par :
Hypopf q “ tpx, λq P Ω ˆ R : λ ď f pxqu.

Le nom dérive du fait que hypo veut dire ! en dessous ", qui fait référence au fait que les valeurs
de λ dans la deuxième entrée des coordonnés de l’épigraphe sont en dessous du graphe de f .
On invite le lecteur à démontrer le résultat suivant.
Théorème 2.3.2 Soit f : C Ď Rn Ñ R une fonction et C un ensemble convexe. Alors f est
concave (en tant que fonction) si et seulement si Hypopf q est convexe (en tant que ensemble).

37
2.4 Enveloppe convexe, combinaisons linéaires convexes et
inégalité de Jensen
Considérons les points dans la figure 2.20 : on peut les envelopper dans un nombre infini
d’ensembles convexes, mais le plus petit ensemble convexe qui les enveloppe tous est celui dessiné.

Figure 2.20 – Exemples d’enveloppe convexe de quinze éléments de R2 .

On formalise cette observation avec la définition suivante.

Déf. 2.4.1 (Enveloppe convexe d’un ensemble) L’enveloppe convexe, en anglais convex
hull, d’un ensemble S Ď Rn , notée conv pCq ou hull pCq, est l’intersection 5 de tous les ensembles
convexes contenant S. Il s’agit donc du plus petit convexe contenant S. Évidemment, si C est déjà
convexe, C ” convpCq.

Comme d’habitude, on veut donner une caractérisation plus opérationnelle d’enveloppe convexe,
par exemple pour savoir comment dessiner l’enveloppe convexe d’un ensemble. Cette caractérisation
est faite via les combinaisons convexes de n vecteurs de Rn , qu’on va définir ci-dessous et que
généralisent le concept de combinaison convexe de deux vecteurs.

Déf. 2.4.2 (Combinaison convexe) Soient x1 , . . . , xn des éléments de Rn et λ1 , . . . , λn des

réels ě 0 tels que λ1 ` . . . ` λn “ 1. On dit que x “ λ1 x1 ` . . . ` λn xn est une combinaison
convexe des éléments x1 , . . . , xn . Plus généralement, si S est un sous-ensemble de Rn on dit que
x P Rn est combinaison convexe d’éléments de S s’il existe un nombre fini d’éléments de S dont x
soit une combinaison convexe.

Une combinaison convexe n’est rien d’autre donc qu’une moyenne pondérée et une combinaison
convexe de deux éléments n’est rien d’autre que le segment qui les relie, car, dans ce cas λ1 ` λ2 “ 1
ðñ λ2 “ 1 ´ λ1 .
La proposition suivante donne une importante caractérisation d’un ensemble convexe via les
combinaisons convexes de ses éléments.

Théorème 2.4.1 C Ď Rn est convexe si et seulement si C contient toutes les combinaisons

convexes de ses éléments.

Preuve.
ð : si un ensemble C contient toutes les combinaisons convexes de ses éléments, alors, comme
on l’a vu ci-dessus, il contient, en particulier, tous les segments reliant deux de ces éléments, qui
est la définition de convexité.
řn
ñ : soient C un ensemble convexe et y un élément de C s’écrivant sous la forme y “ λi xi
i“1
n
ř
avec les λi des réels positifs vérifiant λi “ 1 et les xi P C, montrons que y est un élément de C,
i“1

5. Cette notion est bien définie car on sait que l’intersection de convexes est un convexe.

38
i.e. que C contient une arbitraire combinaison convexe de ses éléments. Puisque la sommes des λi
vaut 1, il existe au moins un λi ą 0, quitte à réindexer, supposons que λ1 ą 0.
On considère la construction suivante :
λ1 λ2
z1 “ x1 ` x2 pP Cq
λ1 ` λ2 λ1 ` λ2
λ1 ` λ2 λ3
z2 “ z1 ` x3 pP Cq
λ1 ` λ2 ` λ3 λ1 ` λ2 ` λ3
λ1 ` λ2 ` . . . ` λn´1 λn
zn´1 “ n
ř zn´2 ` řn xn n “ pλ1 ` λ2 ` . . . ` λn´1 qzn´2 ` λn xn pP Cq.
λi λi
ř
λi “1
i“1
i“1 i“1

Avec un instant de réflexion sur la structure des zk , k “ 1, . . . , n ´ 1 (considérer, par exemple,

n “ 3), on constate que zn´1 “ y, donc y P C. 2

On est prêt pour démontrer la caractérisation de l’enveloppe convexe d’un ensemble.

Théorème 2.4.2 L’enveloppe convexe d’un ensemble S, convpSq, coı̈ncide avec l’ensemble Ŝ de
toutes les combinaisons convexes d’éléments de S.

Preuve.
convpSq Ď Ŝ : d’un côté, convpSq est, par définition, le plus petit convexe qui contient S, de
l’autre côté, le théorème 2.4.1 dit que Ŝ est convexe et, bien sûr, S Ď Ŝ, car tout élément de S est
identifiable comme une combinaison convexe de lui même avec un seul coefficient : λ “ 1 ! Donc,
convpSq Ď Ŝ.

convpSq Ě Ŝ : convpSq est un convexe qui contient S, alors, d’après la proposition 2.4.1, il
contient toutes les combinaisons convexes d’éléments de S, d’où Ŝ Ď convpSq. 2

En résumé, lorsqu’un ensemble S Ă Rn n’est pas convexe, on peut considérer le convexe le plus
similaire à lui : son enveloppe convexe, qu’on peut construire en connectant avec des segments de
droite (issus, justement, de combinaisons convexes, comme prescrit par le théorème qu’on vient de
démontrer !) les points extrêmes de l’ensemble original, comme on peut le voir dans la figure 2.21.

Figure 2.21 – Exemples d’enveloppe convexe d’un ensemble non-convexe de R2 .

D’un point de vu théorique, on constate donc que l’enveloppe convexe d’un ensemble S de Rn
peut être construit de deux manières : une construction ! interne ", en considérant les combinaisons
convexes d’éléments de S, et une construction ! externe ", en considérant l’intersection des convexes
contenant S.
Bien que la construction par dessus semble plus naturelle, on utilise souvent en pratique la
deuxième, car la description de toutes les combinaisons convexes d’un ensemble peut parfois être
compliquée.

39
On termine cette section avec la relation entre fonctions convexes et combinaisons convexes.

Théorème 2.4.3 (Inégalité de Jensen) Soit C Ă Rn un ensemble convexe et f : C Ñ R une

n
ř
fonction convexe. Soient xi P C, λi ě 0, i “ 1, . . . , n, λi “ 1, alors :
i“1
˜ ¸
n
ÿ n
ÿ
f λi xi ď λi f pxi q.
i“1 i“1

Avant de démontrer ce résultat, on observe que, quand n “ 2, l’inégalité de Jensen coı̈ncide

avec la définition de convexité. Donc, ce théorème dit que satisfaire cette inégalité pour n “ 2 est
équivalent à la satisfaire pour n quelconque, fini.

Preuve. La preuve la plus simple passe par l’épigraphe : les points pxi , f pxi qq P C ˆ R appartiennent
au graphe de f et donc à son épigraphe, qu’on sait être convexe car f est convexe par hypothèse,
donc, grâce au théorème 2.4.1, la combinaison convexe de points de C ˆ R
˜ ¸
ÿn n
ÿ n
ÿ
λi pxi , f pxi qq “ λ i xi , λi f pxi q
i“1 i“1 i“1

appartient encore à Epipf q.

Par définition d’épigraphe, ceci implique que
˜ ¸
n
ÿ n
ÿ
λi f pxi q ě f λi xi .
i“1 i“1

40
2.5 Fonctions convexes à valeurs dans R “ R Y t˘8u
En optimisation, il est parfois intéressant de travailler sur des fonction pouvant prendre des
valeurs infinies. Par exemple, quand on travaille sur le problème d’optimisation avec contraintes
min f pxq (C est un sous-ensemble de Rn ), il est parfois utile de le remplacer par le problème
xPC
d’optimisation sans contraintes minn f˜pxq où f˜ prend les mêmes valeurs que f sur C et la valeur
xPR
`8 sur le complémentaire de C.
Cette astuce permet de traiter au même temps les problèmes avec ou sans optimisation. D’où,
on prend souvent C “ Rn et on autorise f à prendre les valeurs ˘8.
Quand on autorise f à prendre des valeurs infinies, il y a un ensemble de définitions de l’analyse
convexe qu’il faut connaı̂tre et qu’on résume ci-dessous.
Déf. 2.5.1 (Fonction indicatrice) On appelle fonction indicatrice de l’ensemble convexe C Ď
Rn la fonction suivante :
IC : C ÝÑ t0, `8u #
0 si x P C
x ÞÝÑ IC pxq “
`8 si x R C.

Il est clair que minimiser la fonction f : C Ñ R sur C est équivalent à minimiser sur Rn la
fonction f˜ : Rn Ñ R Y t`8u, f˜ “ f ` IC , ou, plus précisément :

f˜ : Rn ÝÑ R Y t`8u#
˜ f pxq si x P C
x ÞÝÑ f pxq “
`8 si x R C.

Déf. 2.5.2 (Domaine effectif ) On appelle domaine effectif, ou simplement domaine, de la fonc-
tion f : Rn Ñ R Y t˘8u l’ensemble de points x P Rn tels que f pxq ‰ `8. On écrit dompf q.
On admet aussi ´8 dans cette définition pour permettre à dompf q d’être convexe lorsque f l’est.
Une fonction identiquement égale à `8 présente peu d’intérêt. On se limite donc aux fonctions
suivantes.
Déf. 2.5.3 (Fonction propre) f : Rn Ñ R Y t˘8u est dite propre si elle n’est pas identiquement
égale à `8, i.e. si dompf q ‰ H.
Déf. 2.5.4 (Fonction coercive) f : Rn Ñ R Y t˘8u est dite coercive si elle tend vers `8
quand sa variable tend vers l’infini, i.e. lim f pxq “ `8.
}x}Ñ`8

2.5.1 Les minima locaux d’une fonction convexe propre sont des minima
globaux
Le résultat suivant souligne encore plus clairement l’importance de la convexité dans la théorie
de l’optimisation.
Théorème 2.5.1 Soit f : C Ď Rn Ñ R̄, C convexe, une fonction convexe et propre. S’il existe un
minimiseur local x˚ P Rn de f , alors x˚ est aussi un minimiseur global.
De plus, l’ensemble ArgminC pf q Ď Rn de tous les minimiseurs locaux (et donc globaux) de f
sur C est convexe.
Pour terminer, si f est strictement convexe, elle peut avoir un seul minimiseur (global).
Donc, si f : C Ď Rn Ñ R est convexe et propre, elle peut avoir seulement de minima globaux, qui
peuvent être une infinité (par exemple, un plateaux où f est constante à la valeur minimale) ; mais
si f est strictement convexe, alors elle peut avoir seulement un point di minimum, nécessairement,
global.

41
Preuve. Par l’absurde : supposons que x˚ P C soit un minimiseur local de f en C, si x˚ n’est pas un
minimiseur global, alors il existe x̄ P C tel que f px̄q ă f px˚ q, f px̄q ă `8 car f est propre. Alors,
par convexité de C, le segment de la droite qui connecte x̄ avec x˚ , i.e. tx˚ ` p1 ´ tqx̄, t P r0, 1s,
est inclus en C et, si on applique la fonction f , par convexité on peut écrire

f ptx˚ ` p1 ´ tqx̄q ď tf px˚ q ` p1 ´ tqf px̄q.

Analysons cette dernière expression :

— quand t “ 0 le majorant est f px̄q ;
— quand 0 ă t ă 1 le majorant est une combinaison convexe de f px̄q et f px˚ q ;
— quand t “ 1 le majorant f px˚ q.

Si on élimine t “ 1 on a la possibilité d’écrire la majoration suivante :

f ptx˚ ` p1 ´ tqx̄q ă f px˚ q @t P r0, 1r.

Cette écriture est en contradiction avec l’hypothèse que x˚ soit un minimum local pour f , en fait,
l’existence d’un segment continu de points de C dans lesquels f prend des valeurs strictement
inférieures à f px˚ q empêche l’existence d’un voisinage U px˚ q dans lequel f px˚ q ď f pξq @ξ P U px˚ q.

Pour montrer que ArgminC pf q est un sous-ensemble convexe de Rn il suffit de noter λ ” min f pxq
xPC
et d’observe que ArgminC pf q est l’ensemble de λ-sous-niveau de f , que l’ont sait être convexe.

Terminons avec le cas de la stricte convexité. Par l’absurde, supposons qu’il existe une couple de
points x˚1 , x˚2 qui soient minima (nécessairement globaux, pour ce que l’on vient de démontrer)
pour f , en particulier, on observe que : f px˚1 q “ f px˚2 q “ min f pxq (sinon, un des deux ne serait
xPC
pas un minimum !). Par convexité de C, le point au milieu entre x˚1 et x˚2 , i.e.
ˆ ˙
x˚ ` x˚2 1 1 1 1
ξ“ 1 “ x˚1 ` x˚2 “ x˚1 ` 1 ´ x˚2
2 2 2 2 2

appartient à C, si on applique f à ξ on obtient, par convexité stricte :

ˆ ˆ ˙ ˙
1 ˚ 1 1 1 1 1
f pξq “ f x1 ` 1 ´ x˚2 ă f px˚1 q ` f px˚2 q “ min f pxq ` min f pxq “ min f pxq,
2 2 2 2 2 xPC 2 xPC xPC

i.e. f pξq ă min f pxq, ce qui est une évidente contradiction. 2

xPC

42
2.5.2 Semicontinuité inférieure et existence des minima des fonctions
convexes
Dans la section précédente on a vu que, pour une fonction convexe et propre, si un point est un
minimum local, alors il est automatiquement un minimum global. Néanmoins, on n’a pas garanti
l’existence d’un tel point.
On va introduire ici une condition technique (due au mathématicien Réne Baire) qui garantit
l’existence des minima pour les fonctions convexes.

Déf. 2.5.5 (Semicontinuité inférieure) f : C Ď Rn Ñ R̄ est semicontinue inférieurement

(SCI) en x P C si

@ε ą 0, D un voisinage U pxq tel que f pyq ą f pxq ´ ε @y P U pxq,

i.e.
lim inf f pyq ě f pxq ðñ lim inf f pxn q ě f pxq @pxn qnPN tel que xn ÝÑ x.
yÑx nÑ`8 nÑ`8
n
f : C Ď R Ñ R est semicontinue inférieurement sur C si elle l’est dans tous les points de C.

Théorème 2.5.2 Soit f : C Ď Rn Ñ R̄, C convexe, une fonction

— convexe ;
— propre ;
— SCI sur C.

Alors, f admet au moins un minimiseur (nécessairement global) dans C. Si on remplace la convexité

de f avec la convexité stricte, alors f admet un seul minimiseur (global) dans C.

La preuve de ce théorème n’est pas difficile, mais un peu technique et on préfère l’admettre pour
avancer plus rapidement avec le cours.

43
Appendices

44
Annexe A

Un très bref rappel d’algèbre

linéaire

Dans cette appendice, on va rappeler les concepts d’algèbre linéaire dont on a besoin dans le
cours. L’exposition des concepts est volontairement rapide parce qu’on imagine que les lecteurs
ont déjà une base d’algèbre linéaire et parce qu’il y a une grande quantité de livres excellentes
sur le sujet qui peuvent (doivent. . .) être consultés comme complément à ces notes. Seulement les
preuves des théorèmes qui apportent des éléments d’intérêt pour les cours seront reproduites.

A.1 Généralités
On commence par rappeler que le produit scalaire Euclidien de Rn est défini comme ça :
n
ÿ
@x, y P Rn : xx, yy “ xt y “ xi yi ,
i“1

où xt est le vecteur transposé de x. On rappelle que deux vecteurs x, y P Rn sont orthogonaux
quand xx, yy “ 0. Deux vecteurs orthogonaux sont linéairement indépendants.
La norme Euclidienne, ou norme-2, de x P Rn , est :
˜ ¸1{2
a ? n
ÿ
}x} “ xx, xy “ xt x “ x2i .
i“1

On utilisera souvent ces deux faits :

— Le seul vecteur orthogonale à tous les autres est le vecteur nul ;
— @x P Rn , }x} “ 0 ùñ x “ 0, qui entraine }x ´ y} “ 0 ùñ x ´ y “ 0, i.e. x “ y, ceci
donne une technique (standard) pour montrer l’égalité de deux vecteurs via l’analyse de la
norme de leur différence.
Étant donné un opérateur linéaire A : Rn Ñ Rm , fixé une base de Rn et de Rm , on peut lui
associer univoquement une matrice 1 , qu’on écrit encore avec le symbole A :
¨ ˛
a11 . . . a1n
A P Mm,n pRq, A “ ˝ ... .. ‹ “ pa qi“1,...,m ,
˚
. ‚ ij j“1,...,n
am1 ... amn
i est l’indice des lignes et j l’indice des colonnes, donc la matrice A a :

1. On écrit avec Mm,n pRq l’ensemble des matrices m ˆ n à coefficients réels.

45
— m vecteurs lignes L1 , . . . , Lm P Rn (m comme la dimension de l’espace d’arrivé de l’opérateur
A) ;
— n vecteurs colonnes C1 , . . . , Cn P Rm (n comme la dimension du domaine de l’opérateur A) ;

— La matrice transposée At P Mn,m pRq de la matrice A P Mm,n pRq est la matrice que a par
colonnes les lignes de A et par lignes les colonnes de A ;
— A P Mn,n pRq est dite symétrique si At “ A, i.e. l’échange de lignes et colonnes ne change
pas la matrice : aij “ aji @i, j “ 1, . . . , n.
Vu l’univocité de l’association entre un opérateur linéaire et sa matrice (une fois fixé les bases du
domaine et de l’espace d’arrivé), dorénavant on utilisera le même symbole pour un opérateur linéaire
et sa matrice associée et chaque définition relative à un opérateur linéaire sera automatiquement
étendue à sa matrice associée.
Un opérateur linéaire A : Rn Ñ Rn est dit endomorphisme, et sa matrice associée est carrée.
Dans ce cas, le produit scalaire entre x et Ay, x, y P Rn , peut être écrit comme xx, Ayy “ xt Ay,
qui est une formule qu’on utilisera dans le cours.
Notation : on écrit avec LpRn , Rm q l’espace des opérateurs linéaires de Rn à Rm et avec EndpRn q
l’espace des endomorphismes de Rn .
On rappelle deux sous-espaces très importantes pour un opérateur A P LpRn , Rm q :

kerpAq “ tx P Rm : Ax “ 0u Ď Rn Noyau de A

ImpAq “ ty P Rn : Dx P Rn : y “ Axu Ď Rm Image de A.

On appelle :
— Nullité de A : dimpker Aq “nulpAq ;
— Rang de A : dimpImAq “rankpAq.
La nullité et le rang sont liés par le célèbre résultat suivant.

Théorème A.1.1 (Théorème de nullité + rang) @A P LpRn , Rm q : nulpAq ` rankpAq “ n .

Un opérateur linéaire A : Rn Ñ Rm est injectif si @x1 , x2 P Rn , x1 ‰ x2 implique Apx1 q ‰ Apx2 q. Il

est connu 2 que cette propriété est équivalente à la condition kerpAq “ t0u, dans ce cas nulpAq “ 0
et rankpAq “ n.
Par conséquent, si A est un endomorphisme, i.e. n “ m, alors l’injectivité de A implique
que rankpAq “ n (en Anglais on dit que A est full rank ), i.e. la surjectivité de A, i.e. si A est
un endomorphisme injectif, alors il est automatiquement bijectif, et donc inversible, i.e. il existe
l’opérateur inverse de A, A´1 : Rn Ñ Rn tel que A´1 Apxq “ AA´1 pxq “ x pour tout x P Rn .
L’un des intérêts principaux de l’organisation des vecteurs lignes ou colonnes dans une matrice
est la possibilité de réaliser deux opérations qui ne sont pas définies pour les vecteurs : le produit
et l’inversion.
Donnés deux matrices A P Mm,n pRq et B P Mn,p pRq, on peut définir la matrice produit
C “ AB P Mm,p pRq comme la matrice donc l’element de position pi, jq est le produit scalaire
Euclidien de la ligne i de A avec la colonne j de B. Le produit matriciel est l’opération algébrique
qui traduit la composition entre applications linéaires associées aux matrices.
C’est un bon exercice de vérifier les affirmations suivantes :

2. La prevue est très simple : si A est injective, alors, comme Ap0q “ 0, si x ‰ 0, alors Ax ‰ 0, i.e. kerpAq “ t0u,
vice-versa, soit kerpAq “ t0u et, par l’absurde, soient x1 ‰ x2 tels que Apx1 q “ Apx2 q, alors Apx1 q ´ Apx2 q “ 0,
i.e. par linéarité, Apx1 ´ x2 q “ 0, mais alors x1 ´ x2 P kerpAq, mais on avait supposé que kerpAq “ t0u, et alors
x1 ´ x2 “ 0, i.e. x1 “ x2 , ce qui est en contradiction avec l’hypothèse que x1 ‰ x2 .

46
— La ligne i de C est le produit matriciel de la ligne i de A (matrice 1 ˆ n) avec la matrice B
(matrice n ˆ p). Le résultat est un vecteur ligne à p composantes, i “ 1, . . . , m, donc on a
bien une matrice m ˆ p ;
— La colonne j de C est le produit matriciel de la matrice A (matrice m ˆ n) avec la colonne
j de B (matrice n ˆ 1). Le résultat est un vecteur colonne à m composantes, j “ 1, . . . , p,
donc on a bien une matrice m ˆ p.
Quand on écrira le produit de deux matrices sans spécifier leur dimensions, on supposera toujours
que les dimensions sont cohérentes pour permettre la bonne définition du produit.
Le produit matriciel est associatif pABqC “ ApBCq, distributif à droite et à gauche, pA1 `
A2 qB “ A1 B ` A2 B et ApB1 ` B2 q “ AB1 ` AB2 , homogène, αpABq “ pαAqB “ ApαBq @α P R.
Néanmoins, le produit matriciel n’est pas commutatif : AB ‰ BA, en général. La transposé
d’une matrice produit est le produit des transposées, mais en sens inverse : pABqt “ B t At .
En plus, pour le produit matriciel il ne vaut pas la loi d’élimination, i.e. le produit de
deux matrices ˆpeut être
˙ ˆ nul ˙
sans ˆqu’au˙moins une des deux matrices soit nécessairement nulle,
0 1 1 0 0 0
par exemple : “ le produit est la matrice nulle, mais les deux matrices
0 0 0 0 0 0
facteur ne sont pas nulles !
Une conséquence très importante est que, en général, pour les matrices, l’équation
AB “ AC n’implique pas B “ C, ceci est dû au fait que AB “ AC est équivalent à AB ´AC “ 0,
i.e. par distributivité, ApB ´ Cq “ 0, mais, comme on l’a vu ci-dessus, cette équation n’implique
pas, en général, que B ´ C “ 0, i.e. que B “ C !
Néanmoins, il existe une exception, décrite par le théorème suivant.

Théorème A.1.2 Si kerpAq “ t0u, alors AB “ AC implique B “ C.

Preuve. Soit vrai que AB “ AC alors AB ´ AC “ 0 et ApB ´ Cq “ 0. Il est utile d’interpréter

chaque colonne fixée du produit matriciel ApB ´ Cq comme le résultat du produit matriciel de A
avec une colonne fixée de B ´ C. Le fait que ApB ´ Cq “ 0 est traduit par le fait que toute colonne
de la matrice B ´ C appartiennent à kerpAq, qui, par hypothèse, est t0u, donc toutes les colonnes
de B ´ C sont nulles, i.e. B “ C. 2

Un corollaire immédiat est le suivant.

Corollaire A.1.1 Si A est une matrice carrée de dimension n full rank, i.e. rankpAq “ n, alors
AB “ AC implique B “ C.

Venons maintenant à l’inversion : si A est une matrice carrée de taille n, alors A est inversible
si existe une matrice B carré de taille n telle que : AB “ BA “ In , où In (ou simplement I quand
la spécification de la dimension n’est pas importante) est la matrice identité de dimension n, qui a
zéro partout, sauf sur la diagonale, où elle a 1 dans chaque position. On écrit B “ A´1 . L’inverse
d’une matrice produit est le produit des inverses, mais en sens contraire : pABq´1 “ B ´1 A´1 .
Condition nécessaire et suffisante pour l’inversibilité d’une matrice carré est que son déterminant
soit ‰ 0.
Si A P Mm,n pRq, alors on peut définir l’inverse droite et gauche comme ça :
— B P Mn,m pRq est l’inverse gauche de A si BA “ In

— B P Mn,m pRq est l’inverse droite de A si AB “ Im .

En général, si n ‰ m l’inverse gauche et droite ne coı̈ncident pas. Par contre, l’inverse d’une matrice
carrée, si elle existe, est unique.

Allons maintenant à rappeler la relation entre rank et colonnes d’une matrice non nécessairement
carrée. Pour cela, allons développer le produit Ax, avec A matrice m ˆ n et x vecteur colonne de

47
dimension n :
¨ ˛¨ ˛ ¨ ˛ ¨ ˛ ¨ ˛
a11 ... a1n x1 a11 x1 ` . . . ` a1n xn a11 a1n
˚ .. .. ‹ ˚ .. ‹ “ ˚ .. ‹ ˚ .. ‹ ˚ . ‹
Ax “ ˝ . . ‚˝ . ‚ ˝ . ‚ “ ˝ . ‚x1 ` . . . ` ˝ .. ‚xn ,
am1 ... amn xn am1 x1 ` . . . ` amn xn am1 amn

@j “ 1, . . . , n, on écrit la j-ième colonne de A comme ça

¨ ˛
a1j
Cj P Rm , Cj “ ˝ ... ‚,
˚ ‹

amj

alors
Ax “ C1 x1 ` . . . ` Cn xn ,
c’est-à-dire, l’image d’un vecteur Ax est combinaison linéaire des colonnes de A et les coefficients
de la combinaison linéaire sont les composantes du vecteur x.
Donc 3 :
ImpAq “ spanpC1 , . . . , Cn q ” ColpAq Ď Rm
et, par conséquent, rankpAq coı̈ncide avec nombre de colonnes linéairement indépendantes de A.
Il est possible de démontrer que la dimension de l’espace vectoriel engendré par les vecteurs
lignes de A, spanpL1 , . . . , Lm q ” LignespAq Ď Rn , coı̈ncide avec celle de l’espace vectoriel engendré
par les vecteurs colonnes de A, donc le rankpAq peut être définit aussi comme le nombre de lignes
linéairement indépendantes de A. Ceci implique nécessairement que :

rankpAt q “ rankpAq ď minpn, mq.

Allons maintenant à prendre en considération la présence du produit scalaire Euclidien en Rn .

Donné un sous-espace vectoriel V Ď Rn , on appelle complément orthogonale de V le sous-espace
de Rn définit comme ça
V K “ tx P Rn : xx, yy “ 0 @y P V u,
évidemment V X V K “ t0u. En dimension finie l’orthogonalisation est une involution, i.e. V KK “ V .

Théorème A.1.3 (Théorème de la projection) Pour tout sous-espace vectoriel V de Rn ça

vaut que :
Rn “ V ‘ V K ,
i.e. tout vecteur x P Rn peut être écrit d’une manière unique comme x “ PV pxq ` PV K pxq, où
PV pxq est la projection orthogonale de x sur V et PV K pxq est la projection orthogonale de x sur
V K.

On caractérisera dans la section A.2 les opérateurs de projection.

On a déjà vu que ColpAq coı̈ncide avec ImpAq pour toute matrice A P Mm,n pRq, en utilisant le
complément orthogonale, on peut montrer la relation entre LignespAq et kerpAq.

Théorème A.1.4 Pour toute matrice A P Mm,n pRq, c’est vrai que :

kerpAq “ LignespAqK et LignespAq “ kerpAqK .

3. Donné un ensemble de vecteurs pv1 , . . . , vn q, on écrit avec spanpv1 , . . . , vn q l’espace vectoriel engendré par ces
vecteurs, i.e. l’espace vectoriel dont les éléments sont toutes les combinaisons linéaires des vecteurs pv1 , . . . , vn q.

48
Preuve. Soient L1 , . . . , Lm P Rn les vecteurs ligne de A, alors :
¨ ˛ ¨ ˛
L1 xL1 , xy
Ax “ ˝ ... ‚x “ ˝ ..
‚,
˚ ‹ ˚ ‹
.
Lm xLm , xy

donc x P kerpAq, i.e. Ax “ 0 ðñ xLi , xy “ 0 @i “ 1, . . . , m ðñ x est orthogonale à toutes

les lignes de A ðñ x K LignespAq, donc kerpAq “LignespAqK . Si on considère le complément
orthogonale de cette relation on obtient : kerpAqK “LignespAqKK “LignespAq. 2

Une propriété très importante des vecteurs orthogonaux est exprimé par la généralisation du
théorème de Pythagore suivante : si x K y, alors }x ` y}2 “ }x}2 ` }y}2 .
Grâce à la présence du produit scalaire, on peut associer à chaque opérateur A P LpRn , Rm q un
seul opérateur A: P LpRm , Rn q qui satisfait cette propriété :

xAx, yy “ xx, A: yy, @x, y P Rn ,

de plus, la matrice associée à A: est la transposée de la matrice associée à A (par rapport au

choix des mêmes bases, bien évidemment). On appelle A: l’opérateur transposé ou adjoint de
l’opérateur A.
Pour tout opérateur A P LpRn , Rm q, A: satisfait :
— pA: q: “ A
— xA: x, yy “ xx, Ayy, @x, y P Rn
— Si, en plus, A est un endomorphisme inversible, alors : pA´1 q: “ pA: q´1 .
Il existe une relation extrêmement importante entre le noyau de A et l’image de A: et vice-versa,
comme dit par le théorème suivant.

Théorème A.1.5 Pour tout opérateur A P LpRn , Rm q ça vaut que :

kerpA: q “ pImpAqqK et ImpAq “ pkerpA: qqK .

Preuve. Le théorème est un corollaire immédiat du théorème A.1.4, en fait, pour toute matrice
A P Mm,n pRq, ColpAq “ LignespAt q et LignespAq “ ColpAt q, comme Col pAq “ ImpAq, les formules
de ce théorèmes sont une simple réécriture de celles du théorème A.1.4. Néanmoins, on veut proposer
une preuve alternative, qui a l’avantage de pouvoir être étendue sans difficulté à la dimension
infinie, différemment de la précédente.
kerpA: q Ď pImpAqqK : soit x P kerpA: q, i.e. A: x “ 0, alors @y P Rn :

0 “ x0, yy “ xA: x, yy “ xx, Ayy,

i.e. x est orthogonale à tous les éléments de l’image de A, ce qui prouve que kerpA: q Ď pImpAqqK .

pImpAqqK Ď kerpA: q : soit y P pImpAqqK , i.e. xy, Axy “ 0 @x P Rn , mais alors xA: y, xy “ 0 @x P Rn ,
ce qui est possible seulement si A: y “ 0 car le seul vecteur orthogonal à tous les autres est le
vecteur nul, mais alors y P kerpA: q.

La deuxième formule descend de la première tout simplement en considérant le complément ortho-

gonale aux deux côtés et en rappelant que le biorthogonale d’un sous-espace de dimension finie est
le sous-espace même. 2

49
La composition entre A et son adjoint A: génère deux opérateurs très importantes dans la
théorie de l’optimisation : A: A et AA: . Tout d’abord, on observe que si A P LpRn , Rm q, la matrice
associée à A est m ˆ n, alors AA: est associé à une matrice carrée m ˆ m et A: A est associé à une
matrice carrée n ˆ n. Le fait de travailler avec des endomorphismes associés à des matrices carrées à
déjà un avantage évitent : la possibilité d’examiner l’inversion de ces opérateurs et de ces matrices.
Allons examiner d’abord les propriétés de A: A via l’analyse de sa matrice associée At A.
Tout d’abord : At A est une matrice symétrique, en fait :

pAt Aqt “ At Att “ At A.

pM N qt “N t M t

La même propriété vaut pour AAt . Toute matrice symétrique a des valeurs propres réels grâce à
un résultat standard de l’algèbre linéaire.
On rappelle un concept important.

Déf. A.1.1 M P M pn, Rq est dite semi-définie positive si M est symétrique et si :

xM x, xy ě 0 @x P Rn .

Si ça vaut l’inégalité stricte @x P Rn zt0u, alors M est dite définie positive.

Théorème A.1.6 Soit M P M pn, Rq une matrice symétrique. Alors, les affirmations suivantes
sont équivalentes :

1. M est semi-définie positive ;

2. Toutes les valeurs propres de M sont ě 0 ;

3. M “ N t N pour une matrice opportune N P M pn, Rq.

Preuve.
1q ñ 2q : soit λ P R un valeur propre de M , alors :

0 ď xAx, xy “ xλx, xy “ λxx, xy “ λ}x}2 ,

ce qui implique λ ě 0.
2q ñ 3q : Comme M est réelle et symétrique, elle est diagonalisable, i.e. il existe une matrice
orthogonale P , i.e. P ´1 “ P t , telle que : P M P t “ D, où D “ diagpλ1 , . . . , λn q, avec λi ě 0 : i-ème
valeur propre de M .
2
Vu que?les éléments
? de la diagonale de D sont ě 0 par hypothèse, on peut écrire D “ C , où
C “ diagp λ1 , . . . , λn q.
Mais alors : P M P t “ D peut être réécrit comme M “ P t DP “ P t CCP , si on écrit N “ CP ,
alors N t “ P t C t “ P t C vue que la transposée d’une matrice diagonale est elle-même, donc
M “ N tN .
3q ñ 1q : pour tout x P Rn ,

xM x, xy “ xN t N x, xy “ xN x, N xy “ }N x}2 ě 0,

i.e. M est semi-définie positive. 2

On laisse la (simple) preuve de ce théorème au lecteur.

Corollaire A.1.2 Soit M P M pn, Rq une matrice symétrique. Alors, M est définie positive ðñ
toutes les valeurs propres de M sont positives.

50
Reconsidérons la matrice At A et allons à examiner ses propriétés.

Théorème A.1.7 Pour toute matrice A P M pn, Rq, la matrice At A est semi-définie positive.

Preuve. On a déjà vu que At A est symétrique, de plus, @x P Rn :

xAt Ax, xy “ xAx, Axy “ }Ax}2 ě 0.

En tant que matrice semi-définie positive, les valeurs propres de At A sont ě 0. Ceci implique
qu’on peut calculer leurs racines carrées.

Déf. A.1.2 Le valeurs singulières d’une matrice A P M pn, Rq sont les racines carrées des valeurs
propres de la matrice At A :
?
t λ, λ : valeur propre de At Au “ Valeurs singulières de A.

Les valeurs singulières de A seront utilisées pour introduire la technique de décomposition en

valeurs singulières : SVD.

Théorème A.1.8 Soit A P Mm,n pRq quelconque, alors kerpAt Aq “ kerpAq .

Preuve.
kerpAq Ď kerpAt Aq : soit x P kerpAq, alors At pAxq “ At 0 “ 0, donc x P kerpAt Aq.
kerpAt Aq Ď kerpAq : soit x P kerpAt Aq, alors At pAxq “ 0, i.e. Ax P kerpAt q, mais, grâce au théorème
A.1.5, ceci est équivalent à Ax P pImpAqqK , mais Ax est, par définition, un élément de ImpAq, donc
Ax P ImpAq X pImpAqqK “ t0u, c’est-à-dire Ax “ 0 et donc x P kerpAq. 2

Théorème A.1.9 Soit A P Mm,n pRq quelconque, alors ImpAt Aq “ ImpAt q .

Preuve. ImpAt q “ kerpAqK “ kerpAt AqK “ LignespAt Aq, donc ImpAt q “ LignespAt Aq, mais
pA.1.4q
At A est symétrique, donc LignespAt Aq “ ColpAt Aq “ ImpAt Aq et alors ImpAt q “ ImpAt Aq. 2

Corollaire A.1.3 Soit A P Mm,n pRq quelconque, alors rankpAt Aq “ rankpAq .

Preuve. La thèse suit du fait que rankpAt q “ rankpAq et que rankpAq “ dim ImpAq. 2

La propriété kerpAq “ kerpAt Aq et le fait que At A soit un endomorphisme permettent de

caractériser l’inversibilité de At A avec une condition sur A :

At A inversible ðñ A est full rank ðñ kerpAq “ t0u .

En plus, dans ce cas, At A est définie positive, i.e. xAt Ax, xy ą 0 @x ‰ 0, en fait, comme vu
avant, At A est toujours semi-définie positive, car xAt Ax, xy “ xAx, Axy “ }Ax}2 , mais }Ax} “ 0
ðñ Ax “ 0 ðñ x “ 0 car kerpAq “ t0u. Comme vu avant, ceci est équivalent au fait que,
quand At A est inversible, At A a seulement des valeurs propres strictement positives.

51
A.2 Projecteurs
Les opérateurs de projection, ou projecteurs, jouent un rôle fondamentale dans pratiquement
toutes les disciplines des mathématiques pures et appliquées, dans le cours on aura l’occasion
d’apprécier leur importance aussi dans le champ de l’optimisation. Il est donc essentiel un rappel
de ces opérateurs.
On commence par rappeler qu’une famille de n vecteurs orthogonaux non nuls de Rn est dite
base orthogonale de Rn . Si, en plus, la famille est orthonormée, i.e. chaque vecteur a norme
unitaire, alors on l’appelle base orthonormée de Rn . Une base orthonormée pu1 , . . . , un q peut
être caractérisée via la relation suivante :
#
1 si i “ j
xui , uj y “ δi,j “ ,
0 si i ‰ j

δi,j est dit symbole de Kronecker.

On rappelle que, pour déterminer les composantes d’un vecteur par rapport à une base
quelconque on doit résoudre un système linéaire de n équations avec n inconnues. Par contre, si
on a une base orthogonale ou orthonormale, les composantes sont déterminées par des produits
scalaires, en fait on peut démontrer que, si B “ pu1 , . . . , un q une base orthogonale de Rn , alors :

n
ÿ xv, ui y
v“ ui ,
i“1
}ui }2

en particulier, si B est une base orthonormée, alors :

n
ÿ
v“ xv, ui y ui .
i“1

On observe que la résolution d’un système linéaire de n équations avec n inconnues nécessite,
en général, beaucoup plus d’opérations que le calcul de produits scalaires, ceci montre un des
avantages de connaı̂tre une base orthogonale de Rn .
Interprétation géométrique du théorème : le théorème qu’on vient de démontrer est la
généralisation du théorème de décomposition d’un vecteur dans le plan R2 ou dans l’espace R3 sur
la base canonique des vecteurs unitaires des axes. Pour simplifier, on considère le cas de R2 comme
dans la figure A.1.

Figure A.1 – Représentation graphique du théorème de décomposition sur la base canonique en

R2 .

Si ı̂ et ̂ sont respectivement les vecteurs unitaires des axes x et y, alors le théorème de

décomposition dit que :

v “ looomooon
}v} cos α ı̂ ` }v} cos β ̂ “ xv, ı̂y ı̂ ` xv, ̂y ̂,
looomooon
xv,ı̂y xv,̂y

52
qui est un cas particulier du théorème ci-dessus.
Dans l’espace Euclidien R2 , il est clair que le produit scalaire d’un vecteur v avec un vecteur
unitaire u réalise la projection orthogonale de v dans la direction donnée par u.
De la même manière, on peut définir la projection orthogonale p d’un vecteur de R3 sur le plan
engendré par deux vecteurs unitaires comme la somme des projections orthogonales p1 et p2 sur
les deux vecteurs unitaires considérés séparément, comme il est montré dans la figure A.2.

Figure A.2 – Projection orthogonale p d’un vecteur de R3 sur le plan engendré par deux vecteurs
unitaires.

On considère maintenant une famille orthogonale F “ tu1 , . . . , um u, m ď n, de vecteurs

non nuls : ui ‰ 0 @i “ 1, . . . , m. On étend d’une façon naturelle la définition de la projection
orthogonale d’un vecteur v P V sur S “spanpF q comme ceci :

m
ÿ xv, ui y
PS pvq “ ui ,
i“1
}ui }2

il faut noter que la présence de la norme au carré est due au fait qu’il faut normaliser deux fois ui .
On définit l’opérateur de projection orthogonale ou projecteur sur S comme l’application
(évidemment) linéaire :
PS : Rn ÝÑ S Ď V
m
ř xv,ui y
v ÞÝÑ PS pvq “ }ui }2 ui ,
i“1

PS v est une combinaison linéaire des vecteurs u1 , . . . , um . Le théorème suivant montre que la
projection orthogonale définie ci-dessus a toutes les propriétés de la projection orthogonale en R2
et R3 .

Théorème A.2.1 Avec les notations ci-dessus :

1) Si s P S alors PS psq “ s, i.e. l’action de PS sur les vecteurs de S est l’identité. Par
conséquent PS2 “ idS ;
2) @v P Rn et s P S, le vecteur résidu de la projection, i.e. v ´ PS pvq, est K à S :

xv ´ PS pvq, sy “ 0 ðñ v ´ PS pvq K s ;

3) @v P Rn et s P S :
}v ´ PS pvq} ď }v ´ s}
et l’égalité vaut si et seulement si s “ PS pvq.

Observation importante : la propriété 3) dit que, parmi tous les vecteurs de S, le vecteur
qui minimise la fonction distance à v, i.e. d : Rn ˆ Rn Ñ r0, `8r, dpv, sq “ }v ´ s}, est la
projection orthogonale PS pvq : PS pvq “ argminsPS dpv, sq.

53
Figure A.3 – Visualisation de la propriété 2) en R2 .

Par ailleurs, la propriété 2) est la généralisation d’un fait géométrique qu’on peut visualiser très
facilement en R2 , comme dans la figure A.3.
m
ř
Preuve de 1) : Soit s P S, i.e. s “ αj uj , alors :
j“1

m
ř
m x αj uj , ui y m m
ÿ j“1 ÿ αi xui , ui y ÿ
PS psq “ ui “ ui “ αi ui “ s.
i“1
}ui }2 pui Kuj @i‰jq
i“1
}ui }2 i“1

Par conséquent, @v P Rn , PS2 pvq “ PS pPS pvqq “ PS pvq car PS pvq P S, donc PS2 “ idS .

Preuve de 2) : On commence par considérer encore le produit scalaire de PS pvq avec un vecteur
quelconque uj , j P t1, . . . , mu fixé :
m
ÿ xv, ui y xv, uj y
xPS pvq, uj y “ 2
xui , uj y “ xuj , uj y “ xv, uj y
}ui } pui Kuj @i‰jq }uj }2
i“1

d’où
xv, uj y ´ xPS pvq, uj y “ 0 ðñ xv ´ PS pvq, uj y “ 0 @j P t1, ..., mu.
linéarité de x , y
m
ř
Maintenant, si s P S, alors D α1 , . . . , αm tels que s “ αj uj , donc
j“1

m
ÿ m
ÿ
xv ´ PS pvq, sy “ xv ´ PS pvq, αj uj y “ αj loooooooomoooooooon
xv ´ PS pvq, uj y “ 0,
j“1 j“1
“0

et la propriété 2) est prouvée.

Preuve de 3) : il est utile d’écrire la différence v ´ s comme ceci : v ´ PS pvq ` PS pvq ´ s. La

propriété 2) nous dit que v ´PS pvqKS, par contre, PS pvq, s P S donc PS pvq´s P S. Par conséquent :
pv ´ PS pvqq K pPS pvq ´ sq.
En utilisant la généralisation du théorème de Pythagore on peut alors écrire :

}v ´ s}2 “ }v ´ PS pvq ` PS pvq ´ s}2 “ }v ´ PS pvq}2 ` }P 2 2

S pvq ´ s} ě }v ´ PS pvq} ,
loooooomoooooon
ě0

ce qui implique : }v ´ s} ě }v ´ PS pvq} @v P V, s P S.

54
Bien évidemment, }PS pvq ´ s}2 “ 0 si et seulement si s “ PS pvq, et dans ce cas on a
}v ´ s}2 “ }v ´ PS pvq}2 . 2

Comme conséquence du théorème qu’on vient de prouver, on peut dire que la formule v “ v´s`s
pour tout v P V et s P S cache une information importante : v ´ s est orthogonale à s.
Terminons en montrant comment on peut réaliser les opérateur de projection sous forme matricielle.
On commence avec la projection sur un seul axe donné par le vecteur u P Rn et après on va
généraliser le discours.
Soit Pu le projecteur orthogonale sur l’axe u P Rn , alors, si on l’applique à n’importe quel
vecteur v P Rn , on obtient un multiple de u, i.e. Pu v “ αu, avec α P R. Allons maintenant utiliser
le fait que le vecteur résidu v ´ Pu v est orthogonal à u :

0 “ xu, v ´ Pu vy “ ut pv ´ Pu vq “ ut pv ´ αuq “ ut v ´ αut u,

donc ut v “ αut u, ce qui permet de caractériser α comme ça : α “ ut v{ut u. On utilise cette
information pour déterminer Pu :

ut v 1
Pu v “ αu “ uα “ u “ t uput vq.
αPR ut u uu
Par l’associativité du produit matriciel, ça vaut que uput vq “ puut qv, où uut est à interpréter
comme la matrice n ˆ n obtenue comme produit matricielle de u vu comme une matrice colonne
t
n ˆ 1 et de ut vu comme une matrice ligne 1 ˆ n. Donc on peut écrire : Pu v “ uu ut u v, pour tout
vecteur v, i.e.
uut
Pu “ t }u} ‰ 1,
uu
en particulier, si ut u “ }u}2 “ 1, i.e. si u est un vecteur unitaire, alors :

Pu “ uut }u} “ 1.

Considérons maintenant un sous-espace S de Rn engendré par une famille de vecteurs non

nuls et orthogonaux entre eux qu’on indique avec pu1 , . . . , um q, m ă n. On a vu que la projection
orthogonale sur S d’un vecteur v P Rn , dans ce cas, est un vecteur de S, i.e. il est obtenu
par combinaison linéaire des vecteurs u1 , . . . , um . Si on place les coefficients α1 , . . . , αm de la
combinaison linéaire dans un vecteur colonne et on utilise les générateurs de S comme
colonnes d’une matrice A de type n ˆ m, i.e.
¨ 1 ˛
u1 u1m
A “ ˝ ... ... .. ‹ ,
˚
. ‚
un1 unm

alors on peut réécrire la projection orthogonale comme ça :

¨ 1 ˛¨ ˛ ¨ ˛
u1 u1m α1 α1 u11 ` . . . ` αm u1m
˚ .. .. .. ‹˚ .. ‹ ” A~ ..
PS v “ ˝ . αon “ ˝ ‚ “ α1 u1 ` . . . ` αm um , @v P Rn .
˚ ‹
. . ‚˝ . ‚ loomo .
un1 unm loomoon
loooooooomoooooooon αm nˆ1 α1 un1 ` . . . ` αm unm
nˆm mˆ1

La formule montre que PS v P ImpAq, par contre on sait que le vecteur résidu v ´ PS v P pImpAqqK “
kerpAt q, donc :
0 “ At pv ´ PS vq “ At pv ´ A~αq “ At v ´ At A~ α,

55
i.e. At A~
α “ At v. Allons se concentrer sur At A, qui est une matrice m ˆ m écrite comme ça :
¨ 1 ˛¨ 1 ˛
u1 un1 u1 u1m
At A “ ˝ ... .. .. ‹ ˚ .. .. .. ‹ “ diagp}u }2 , . . . , }u }2 q,
˚
. . ‚˝ . . . ‚ 1 m
u1m unm un1 unm

vu que les vecteurs u1 , . . . , um sont orthogonaux entre eux et donc tous les éléments hors de la
diagonale sont nuls car obtenus via le produit scalaire de vecteurs orthogonaux ! Sur la diagonal on
trouve la norme au carré des vecteurs u1 , . . . , um , toutes ces normes sont strictement positives, car
nous avons supposé que ces vecteurs sont non nuls. Donc At A est une matrice inversible et alors
nous pouvons obtenir α ~ comme ça :

~ “ pAt Aq´1 At v
α

et, comme PS v “ A~ α “ ApAt Aq´1 At v pour tout vecteur v P Rn , on obtient la représentation

matricielle de PS :

PS “ ApAt Aq´1 At colonnes de A : générateurs orthogonaux de S.

Il faut observer que les matrices A et At ne sont pas carrés, donc il ne faut pas tomber dans la
tentation de simplifier la formule précédente comme ceci : AA´1 pAt q´1 At “ I ! On observe aussi que
la matrice pAt Aq´1 joue un rôle analogue à celui du facteur put uq´1 dans le cas mono-dimensionnel,
en fait :
Pu “ uput uq´1 ut vs. PS “ ApAt Aq´1 At .
Si u était unitaire, le facteur ut u pouvait être simplifié, dans ce cas, si u1 , . . . , um est une famille
orthonormale, alors At A “ diagp1, . . . , 1q “ Im et donc la formule pour le projecteur orthogonale
devient :
PS “ AAt colonnes de A : générateurs orthonormés de S.

Il est possible de démontrer que les projecteurs orthogonaux P en Rn peuvent être caractérisés
par la chaine d’égalités suivante :
P “ P 2 “ P t,
allons vérifier que le projecteur ApAt Aq´1 At possède ces propriétés :

pApAt Aq´1 At qt “ Att ppAt Aq´1 qt At “ AppAt Aqt q´1 At “ ApAt Att q´1 At “ ApAt Aq´1 At ,

pApAt Aq´1 At q2 “ pApAt Aq´1 At qpApAt Aq´1 At q “ ApAt Aq´1 pAt AqpAt Aq´1 At “ ApAt Aq´1 At .

La vérification de ces propriétés pour AAt est encore plus facile et elle est laissée par exercice.

56
Annexe B

Un très bref rappel sur les espaces

métriques et le calcul différentiel
en Rn

Dans cette deuxième appendice on va présenter un court résumé des concepts fondamentales des
espaces métriques et du calcul différentiel en Rn . Malgré le fait que les résultats et les algorithmes
présentés dans le cours sont développés pour Rn et ses parties, on a néanmoins voulu présenter
quelque détail de la théorie des espaces métriques vu leur grande utilité dans l’optimisation.

B.1 Espaces métriques

En Rn on peut mesurer la distance entre deux points x, y P Rn , par exemple, grâce à la norme
Euclidienne : dpx, yq “ }x ´ y}. Dans les applications des mathématiques on peut devoir traiter
des espaces plus compliqués que Rn , et même de dimension infinie, il est donc essentiel d’abstraire
et de généraliser la notion de distance, la bonne définition est la suivante.

Déf. B.1.1 Soit X un ensemble quelconque et d : X ˆ X Ñ r0, `8q. d est une distance ou
métrique sur X si :

1. @x, y P X, dpx, yq ě 0 et dpx, yq “ 0 ô x “ y (positivité)

2. @x, y P X, dpx, yq “ dpy, xq (symétrie)
3. @x, y, z P X, dpx, zq ď dpx, yq ` dpy, zq (inégalité triangulaire)

La couple pX, dq est dite un espace métrique.

Une suite 1 à valeurs en E Ď pX, dq est une fonction ϕ : N Ñ X, n ÞÑ ϕpnq “ xn . Souvent
on identifie la suite avec son codomaine, dans ce cas on écrira pxn qnPN Ď E. L’ensemble N peut
être remplacé par un autre ensemble dénombrable. Par exemple si on remplace N avec Z on parle
de suites bilatérales.
Une suite pxn qnPN Ă X est convergente à la limite L P X si :

@ε ą 0 DNε P N tel que n ą Nε ùñ dpxn , Lq ă ε.

On écrit xn ÝÑ L, ou L “ lim xn .
nÑ`8 nÑ`8

1. Les suites émergent d’une manière naturelle en optimisation quand on considère les algorithmes itératifs pour
approcher la solution à un problème trop compliqué pour être résolu d’une manière analytique.

57
Étant donné un point x0 P pX, dq quelconque, on appelle voisinage de centre x0 et rayon
r P R, r ą 0 l’ensemble des points de X qui ont une distance de x0 inférieure à r, i.e.

Ur px0 q “ tx P X : dpx, x0 q ă ru,

une autre notation habituelle qu’on trouve dans les livres est Br px0 q. Si d est la distance Euclidienne
et X “ Rn , on appelle le voisinage une ! boule ".

Le concept de limite est intimement lié avec le concept défini ci dessous.

Déf. B.1.2 On dit que x0 P pX, dq est un point d’adhérence, ou un point d’accumulation,
ou un point limite pour une partie E Ď X si pour tout r ą 0, il existe un voisinage Ur px0 q qui
contient des éléments de E différents de x0 .

Interprétation de la définition : si on fait un ! zoom " autour d’un point d’adhérence, avec n’importe
quel niveau d’agrandissement, on voit toujours de points de E différents de x0 .

Déf. B.1.3 On dit que E Ă pX, dq est une partie fermé si E contient tous ses points d’adhérence.

Un exemple de partie fermé en R est n’importe quel intervalle ra, bs, a, b P R, a ă b, mais ra, br
n’est pas fermé.

Déf. B.1.4 On appelle fermeture de E Ă pX, dq l’intersection de toutes les parties fermés qui
contiennent E, ou, d’une manière équivalente, le plus petit sous-ensemble fermé de X qui contient
E.

Pour les intérêts de l’optimisation, il est utile de caractériser la fermeture d’une partie et les
points d’adhérence à travers des suites, allons revoir les concepts et les résultats qui permettent de
formaliser cette affirmation.

Déf. B.1.5 Considérons une suite croissante ψ à valeurs en N, i.e. ψ : N Ñ N, k ÞÑ ψpkq “ nk ,

nk ă nk`1 @k P N. On appelle suite extraite (ou sous-suite) de la suite ϕ la suite composée
ϕ ˝ ψ : N Ñ N Ñ E, k ÞÑ nk ÞÑ xnk . Comme pour les suites, souvent on identifie la suite extraite
avec son codomaine pxnk qkPN .

Déf. B.1.6 Une suite pxn qnPN Ď E est bornée si Dx0 P E et r ą 0 tels que : txn n P Nu Ď Ur px0 q.

Interprétation : les éléments d’une suite bornée sont tous contenus dans le voisinage d’un élément
de E si on choisit un rayon suffisamment grande, mais fini !
On observe que toute suite convergente est bornée, en fait, par définition, si L est la limite
de la suite, alors @ε ą 0 et @n ě Nε : txn n P Nu Ď Uε pLq. Considérons

r̃ “ maxtdpxn , Lq, n “ 0, 1, . . . , Nε ´ 1u,

alors, si on définit r “ maxpε, r̃q, il est clair que txn n P Nu Ď Ur pLq.

Le théorème suivant dit que les points d’adhérence sont comme des aimant pour les suites. . .

Théorème B.1.1 Soit L P X un point d’adhérence pour E Ă pX, dq, alors il existe une suite
pxn qnPN Ď E qui converge vers L.

Autrement dit : tout point d’adhérence de E est la limite d’une suite à valeurs en E.
On montre la preuve de ce théorème car elle permet de comprendre, via un argument classique
et très élégant, la signification de la définition de point d’adhérence, qui peut être un peu obscure
au tout début.

58
Preuve. La démonstration est constructive, i.e. on va construire la suite qui converge vers L. L’idée
à la base de la preuve consiste en utiliser la propriété définitoire de point d’adhérence, i.e. le fait
qu’on peut toujours trouver au moins un point de E différent de L en chaque voisinage de L :
considérons la suite de rayons r “ 1, 1{2, . . . , 1{n . . ., alors, pour tout n P N, il existe xn ‰ L tel
que dpxn , Lq ă 1{n.
On va montrer que ceci implique la convergence de pxn qnPN vers L : pour tout ε ą 0 fixé, on va
définir 2 : Z ^
1 1 1 1
Nε “ `1ą ùñ ă 1 “ε
ε ε Nε ε
1 1
alors, pour tout n ě Nε ça vaut que n ď Nε ă ε et donc, en résumé, on a démontré que :

1
@ε ą 0 DNε ą 0 : n ě Nε ùñ dpxn , Lq ă ă ε,
n
qui est la définition de convergence de pxn qnPN vers L. 2

Ce dernier théorème nous donne la possibilité de caractériser l’adhérence d’un espace métrique :
quand on écrit X “ E ça veut dire que pour tout x P X il existe une suite pxn qnPN Ď E telle que
x “ lim xn . On dit aussi que E est dense en X.
nÑ`8

B.1.1 Le théorème de Bolzano-Weierstrass

On va examiner ici la relation entre limites de suites et des suites extraites. Tout d’abord, on
observe qu’une suite non-convergente peut admettre des suites extraites convergentes, l’exemple le
plus simple est probablement le suivant :

pxn q “ p´1qn qui n’est pas convergente, mais qui admet la suite extraite

px2n q “ p´1q2n ” 1 qui converge à 1 en tant que suite constante.

Néanmoins, si une suite est convergente vers une limite L, alors toutes ses suites extraites sont
obligées à être convergentes vers la même limite L. La preuve de cette affirmation est immédiate :
si L “ lim xn alors @ε ą 0 DNε ą 0 : n ě Nε ùñ dpxn , Lq ă ε, mais alors, comme pnk qkPN est
nÑ`8
une suite croissante, il existe un Kε ą 0 tel que nKε ě Nε et alors, pour tout k ě nKε ça vaut que
dpxnk , Lq ă ε, i.e. L “ lim xnk .
kÑ`8
Donc, en résumé, si une suite est convergente, alors toutes ses suites extraites sont convergentes
à la même limite, si elle n’est pas convergente, alors elle peut avoir des suites extraites convergentes.
Le théorème suivant dit que, si le codomaine d’une suite admet un point d’adhérence, alors la suite
doit avoir une suite extraite qui converge vers ce même point.

Théorème B.1.2 Soit pxn qnPN une suite à valeurs en pX, dq. Si la partie E “ txn , n P Nu Ď X
admet un point d’adhérence L, alors il existe une suite extraite de pxn qnPN qui converge vers L.

Preuve. On utilise le même argument de la preuve précédente : grâce à la définition de point

d’adhérence, il existe
xn1 tel que dpxn1 , Lq ă 1
1
xn2 tel que dpxn2 , Lq ă
2
..
.
1
xnk tel que dpxnk , Lq ă
k
2. On rappelle que tξu est la partie entière, i.e. le plus petit nombre entier non supérieur à ξ.

59
donc lim xnk “ L. 2
kÑ`8
La conséquence du théorème précédent est que, si on garantit l’existence d’un point d’adhérence
pour la suite, alors on garantit automatiquement l’existence d’une suite extraite convergente. En
dimension infinie ce problème est plutôt délicat, par contre, en dimension finie, une condition
suffisante est garantie par le célèbre théorème qui suit, donc on assumera la preuve.

Théorème B.1.3 (Théorème de Bolzano-Weierstrass) Soit E Ď Rn une partie borné (i.e.

contenue dans le voisinage d’un point de Rn ) et infinie (i.e. avec un nombre infini d’éléments),
alors E admet un point d’adhérence.

Corollaire B.1.1 Toute suite bornée à valeurs en Rn admet une suite extraite convergente.

Preuve. Conséquence directe des deux derniers théorèmes. Supposons que la suite soit constante
après un certain n̄ P N : alors elle est sûrement bornée et convergente (vers la constante même),
donc toutes ses suites extraites sont convergentes.
Supposons maintenant que la suite soit non constante et borné. Comme la suite n’est pas
constante, elle est composé par un nombre infini d’éléments, et donc, en tant que partie de Rn ,
elle est bornée et infinie. Par conséquent, elle admet un point d’adhérence par le théorème de
Bolzano-Weierstrass, ce qui implique l’existence d’une suite extraite convergente par le théorème
B.1.2. 2

B.2 Éléments de calcul différentiel en Rn pour l’optimisa-

tion
Dans cette section on rappelle les éléments de calcul différentiel en Rn qui sont indispensables
pour l’optimisation. On assumera pratiquement toutes les preuves des résultats qu’on va citer, car
on imagine que le lecteur a déjà eu la possibilité de les voir dans les cours canoniques d’analyse.
Pour commencer, le calcul différentiel est développé d’abord pour les ensembles ouverts, dont on
rappelle la définition ci-dessous.

Déf. B.2.1 E Ď Rn est dit ouvert si :

@x0 P E Dr ą 0 tel que Ur px0 q Ď E,

i.e. pour tout élément d’une partie ouverte E de Rn , on peut trouver un voisinage de rayon positif
composé que par des éléments de E même. La raison pour laquelle cette propriété est si importante
en analyse est que l’opération basique du calcul différentiel est la perturbation de la position d’un
point, le fait d’avoir un entier voisinage de chaque point de E composé par des éléments de E permet
d’opérer des perturbations dans toutes les directions, sans devoir se préoccuper de ! sortir " de E.

Déf. B.2.2 La partie

BE “ tx0 P E tels que Dr ą 0 tel que Ur px0 q X E ‰ H et Ur px0 q X E c ‰ Hu

est dite frontière de E, où E c est le complémentaire de E, i.e. E c “ Rn zE.

Donc la frontière de E est composée par les points de Rn qui ont de voisinages qui intersectent
d’une manière non triviale E et son complémentaire E c .

Déf. B.2.3 E est fermé si son complémentaire E c est ouvert, et vice-versa.

60
B.2.1 Dérivée directionnelle, partielle, gradient et ligne de niveau
On commence par une définition préliminaire.
Déf. B.2.4 Soit u P Rn , }u} “ 1, un vecteur unitaire. On appelle droite en Rn passant par le
point x0 P Rn en direction de u l’ensemble défini comme ça :
rx0 ,u “ tx P Rn : x “ x0 ` tu, t P Ru.
Dans les définitions suivantes on va considérer une fonction f : D Ď Rn Ñ R, où D est le
domaine de f , qu’on va supposer ouvert.
Déf. B.2.5 Soit u P Rn un vecteur unitaire, }u} “ 1. La dérivée directionnelle de f en x0 P D en
direction direction u est la valeur de la limite suivante, si elle existe et elle est finie :

f px0 ` εuq ´ f px0 q

Du f px0 q “ lim .
εÑ0 ε
La dérivée directionnelle est l’expression de la vitesse de variation d’une fonction quand on se
déplace d’un point en suivant la droite passant par le point en direction d’un vecteur unitaire fixé.
Comme la définition est faite en utilisant l’opération de limite, qui est linéaire, la dérivée
directionnel est linéaire elle-même.
a Si n “ 2, on peut expliciter simplement la définition : si x0 “ px0 , y0 q et u “ pu1 , u2 q,
u21 ` u22 “ 1, alors :
f px0 ` εu1 , y0 ` εu2 q ´ f px0 , y0 q
Du f px0 q “ lim .
εÑ0 ε
En Rn on a n directions privilégiées, celles de la base canonique ei pjq “ δi,j , i, j “ 1, . . . , n, les
dérivées directionnelles calculées par rapport aux vecteurs de la base canonique ont un nom et un
symbole particulier.
Déf. B.2.6 On appelle derivée partielle selon l’axe i, i “ 1, . . . , n, de f en x0 P D la valeur de
la limite suivante, si elle existe et elle est finie :
Bf f px0 ` εei q ´ f px0 q
Dei f px0 q ” px0 q “ lim ,
Bxi εÑ0 ε
plus explicitement, comme x0 ` εei “ px0 , . . . , xi ` ε, . . . , xn q, on peut écrire

Bf f px0 , . . . , xi ` ε, . . . , xn q ´ f px0 , . . . , xi , . . . , xn q
px0 q “ lim .
Bxi εÑ0 ε

Notations alternatives : Bxi f px0 q, fxi px0 q.

Donc, quand on calcule la dérivée partielle i-ème, seulement la composante i varie, les autres
doivent être considérées comme fixes.
L’interprétation géométrique des dérivées partielles est une conséquence directe de celle de
dérivée d’une fonction d’une variable réelle. Pour visualiser cela, considérons le cas n “ 2 et fixons
avant x “ x0 et après y “ y0 , ce qu’on obtient sont deux courbes sur la surface définie par l’équation
z “ f px, yq, comme dans la figure B.2.1.
Les dérivées partielles représentent la peinte des droites tangentes en chaque point à la courbe
mentionnée ci-dessus.
Déf. B.2.7 Les dérivées partielles de f : D Ď Rn Ñ R en x0 P D peuvent être utilisées comme
composantes d’un vecteur de Rn qu’on appelle gradient de f en x0 :
ˆ ˙
Bf Bf
∇f px0 q ” gradf px0 q “ px0 q, . . . , px0 q .
Bx1 Bxn

On peut considérer ∇f px0 q comme un vecteur colonne ou ligne, selon les nécessités.

61
Figure B.1 – Variations d’une seule variable pour une fonction de deux variable.

Figure B.2 – Représentent géométrique d’un dérivée partielle comme peinte de la droite tangente.

Exemple : calculer le gradient de f : R2 Ñ R, f px, yq “ logp1`x2 `y 2 q dans un point arbitraire de

coordonnées px, yq. Avant tout on calcule les dérivées partielles en px, yq : fx px, yq “ 2x{p1`x2 `y 2 q,
fy px, yq “ 2y{p1 ` x2 ` y 2 q, alors :
ˆ ˙
2x 2y
∇f px, yq “ , .
1 ` x2 ` y 2 1 ` x2 ` y 2

Le gradient n’est pas simplement une forme compacte pour organiser les dérivées partielles, en
fait il contient une information géométrique très importante, comme dit par le théorème suivant.

Théorème B.2.1 Soient f : D Ď Rn Ñ R, x0 P D, u P Rn , }u} “ 1. Alors :

Du f px0 q “ x∇f px0 q, uy. (B.1)

Grâce à la formule (B.1) on peut calculer le gradient via la dérivée directionnelle ou vice-versa,
selon l’utilité et la simplicité de calcul. Allons voir un` exemple
? : calculer
? ˘ la dérivée directionnelle
de f px, yq “ x2 e´y en px, yq dans la direction de u “ 1{ 2, 1{ 2 . Le calcul direct donne :

f px ` hux , y ` huy q ´ f px, yq

Du f px, yq “ lim
hÑ0 h
i.e. ´ ¯2 ´ ¯
h ´ y` ?h2
x` ?
2
e ´ x2 eý
lim ,
hÑ0 h
qui est une limite difficile à calculer, pour cela on utilise la formule (B.1) après avoir calculé le
gradient : fx px, yq “ 2xeý , fy px, yq “ ´x2 eý , donc ∇f px, yq “ p2xeý , ´x2 eý q et

2xeý p´x2 eý q xeý

Du f px, yq “ x∇f px, yq, uy “ ? ` ? “ ? p2 ´ xq.
2 2 2

62
L’utilisation inverse de la formule, i.e. le calcul du gradient via la dérivée directionnelle, sera montré
dans la section suivante.
On termine cette section avec la signification géométrique de la formule (B.1). On rappelle que,
pour toute couple de vecteurs v, w P Rn

xv, wy “ }v}}w} cos α,

où α est l’angle le plus petit entre les deux vecteurs.

D’après cette observation, on peut réécrire (B.1) comme ceci :

Du f px0 q “ }∇f px0 q}}u} cos α, α “ angle entre ∇f px0 q et u,

mais }u} “ 1, donc :

Du f px0 q “ }∇f px0 q} cos α .
Le cosinus est une fonction bornée entre -1 et +1, donc :

´}∇f px0 q} ď Du f px0 q ď `}∇f px0 q} , @u P Rn .

Il y a trois situations remarquables pour la valeur de la fonction cosinus : quand elle prend sa valeur
inférieure -1, sa valeur supérieure +1 et quand elle s’annule. Ces trois situations correspondent,
respectivement, au fait que la dérivée directionnelle atteint sa valeur minimale (la plus négative),
sa valeur maximale et que elle soit nulle. Allons examiner la signification de ces trois situations.
— cos α “ `1 si et seulement si ∇f px0 q et u sont parallèles (∇f px0 q k u), i.e. α “ 0. Donc, la
direction de plus rapide croissance de la function f par rapport au point x0 es celle
du gradient de f en x0 . Le vecteur unitaire qui représente cette direction est :

∇f px0 q
umax. croissance “ .
}∇f px0 q}

— De la même manière, cos α “ ´1 si et seulement si ∇f px0 q et u son anti-parallèles, i.e.

α “ π. Ceci implique que la direction de plus rapide décroissance de la function f
par rapport au point x0 es celle opposée au gradient de f en x0 . Le vecteur unitaire qui
représente cette direction est :

∇f px0 q
umax. décroissance “ ´ .
}∇f px0 q}

— Du f px0 q : s’il y a eu un déplacement, le gradient ne peut pas être nul, donc,}∇f px0 q} ‰ 0
et, comme }u} “ 1, la seule possibilité d’avoir Du f px0 q est que cos α “ 0. Ceci est possible
seulement si ∇f px0 q et u son orthogonaux(∇f px0 q K u).
La dernière option qu’on a examiné nous permet d’introduire un concept très importante en
optimisation sous contraintes.

Déf. B.2.8 On appelle ligne de niveau λ de la fonction f : D Ď Rn Ñ R l’ensemble

Cf pλq “ tx P D : f pxq “ λu.

Comme f est constante sur une ligne de niveau, la dérivée directionnelle de f en un point x0
calculé par rapport au vecteur u tangent à la ligne de niveau de f qui passe par x0 est nulle. Mais
on vient de voir que la nullité de la dérivée directionnelle correspond à l’orthogonalité entre la
direction de dérivation et le vecteur gradient de f en x0 , donc les lignes de niveau de f peuvent
être définies d’une manière équivalente comme les lignes dont le vecteur tangent est orthogonale au
gradient de f en chaque point. Avec un langage pas formel, mais qui a le don de la synthèse, on dit
habituellement que ! le gradient est orthogonale aux lignes de niveau ". La figure B.2.1 visualise ce
concept.

63
Figure B.3 – Relation ligne de niveau et gradient.

B.2.2 Calcul de quelque gradient utile pour l’optimisation via la dérivée

directionnelle
Le calcul de la dérivée directionnelle de fonctions qui dépendent de la norme au carré ou du
produit scalaire est particulièrement simple, comme on va le voir dans les exemples suivants. Les
calculs de cette section seront utilisés souvent dans le cours.
Avant de commencer avec les calculs, on rappelle que, pour tout a, b P Rn :

}a ` b}2 “ xa ` b, a ` by “ xa, ay ` xa, by ` xb, ay ` xb, by,

par symétrie du produit scalaire Euclidien réel, on obtient

}a ` b}2 “ }a}2 ` }b}2 ` 2xa, by.

Théorème B.2.2 Si f pxq “ }x}2 alors ∇f pxq “ 2x @x P Rn .

Preuve. Par calcul direct :

f px ` εuq ´ f pxq }x ` εu}2 ´ }x}2

Du f pxq “ lim “ lim
εÑ0 ε εÑ0 ε
2 2 2
}x} ` }εu} ` 2xx, εuy ´ }x}
“ lim
εÑ0 ε
ε2 }u}2 ` 2εxx, uy
“ lim
εÑ0
` ε ˘
2
“ lim ε}u} ` 2xx, uy “ 2xx, uy.
εÑ0

Grâce à (B.1), Du f pxq “ x∇f pxq, uy “ 2xx, uy, i.e. x∇f pxq, uy “ x2x, uy, or x∇f pxq ´ 2x, uy “ 0
pour toutes les directions u, mais cela est possible si et seulement si ∇f pxq´2x “ 0, i.e. ∇f pxq “ 2x.
2
Observation sur les dimensions : f : Rn Ñ R, f pxq “ }x}2 , ∇f : Rn Ñ Rn , ∇f pxq “ 2x !

Théorème B.2.3 Si fa pxq “ }x ´ a}2 alors ∇fa pxq “ 2px ´ aq @x, a P Rn .

Interprétation : le calcul du gradient de la fonction norme au carré de x P Rn (et de ses

translations) est, formellement, identique au calcul de la dérivée première d’une fonction de variable
réelle au carré (et de ses translations).
Preuve. Par calcul direct :

64
}x ` εu ´ a}2 ´ }x ´ a}2
Du fa pxq “ lim
εÑ0 ε
}px ´ aq ` εu}2 ´ }x ´ a}2
“ lim
εÑ0 ε
}x ´ a}2 ` }εu}2 ` 2xx ´ a, εuy ´ }x ´ a}2
“ lim
εÑ0 ε
ε2 }u}2 ` εx2px ´ aq, uy
“ lim
εÑ0
` ε ˘
“ lim ε}u}2 ` x2px ´ aq, uy “ x2px ´ aq, uy.
εÑ0

Le même argument de la preuve précédente amène à écrire x∇f pxq ´ 2px ´ aq, uy “ 0 pour
toutes les directions u, i.e. ∇f pxq “ 2px ´ aq. 2

Théorème B.2.4 Si fw pxq “ xw, xy alors ∇fw pxq “ w @x, w P Rn .

Interprétation : le calcul du gradient de la fonction produit scalaire entre deux vecteurs de Rn est,
formellement, identique au calcul de la dérivée première de la fonction produit d’une variable réelle
par un scalaire.
Preuve. Par calcul direct :

xw, x ` εuy ´ xw, xy

Du fw pxq “ lim
εÑ0 ε
xw, xy ` εxw, uy ´ xw, xy
“ lim
εÑ0 ε
εxw, uy
“ lim
εÑ0 ε
“ xw, uy.
Donc x∇f pxq ´ w, uy “ 0 pour toutes les directions u, i.e. ∇f pxq “ w. 2

Théorème B.2.5 Si fA,b pxq “ 12 }Ax ´ b}2 alors ∇fA,b pxq “ At pAx ´ bq @x P Rn , b P Rm et pour
toute matrice A P Mm,n pRq.
Preuve. Calculons fA,b px ` εuq :

1 1
fA,b px ` εuq “ }Apx ` εuq ´ b}2 “ }pAx ´ bq ` εAu}2
2 2
1` ˘
“ }Ax ´ b} ` ε }Au}2 ` 2εxAx ´ b, Auy .
2 2
2
Donc :

}Ax ´ b}2 ` ε2 }Au}2 ` 2εxAx ´ b, Auy ´ }Ax ´ b}2

Du fA,b pxq “ lim
εÑ0 2ε
ε2 }Au}2 ` 2εxAx ´ b, Auy
“ lim
εÑ0 2ε
ε}Au}2
ˆ ˙
“ lim ` xAx ´ b, Auy “ xAx ´ b, Auy
εÑ0 2
“ xAt pAx ´ bq, uy.
Donc x∇fA,b pxq ´ At pAx ´ bq, uy “ 0 pour toutes les directions u, i.e. ∇fA,b pxq “ At pAx ´ bq. 2

65
B.2.3 Les points stationnaires et les équations de Euler-Lagrange
Rappelons les définitions d’extrema d’une fonction de plusieurs variables réelles :

Déf. B.2.9 Soit f : D Ď Rn Ñ R et x0 P D, alors on dit que

— x0 est un point de minimum globale pour f si f px0 q ď f pxq @x P D ;
— x0 est un point de maximum globale pour f si f px0 q ě f pxq @x P D ;
— px0 q est un point de minimum locale pour f s’il existe un voisinage U px0 q tel que f px0 q ď
f pxq @x P U px0 q ;
— px0 q est un point de maximum locale pour f s’il existe un voisinage U px0 q tel que
f px0 q ě f pxq @x P U px0 q.
Un point de minimum ou de maximum est appelé un extremum.

Une représentation graphique est offerte dans la figure B.2.3.

Figure B.4 – Exemples de minimum et maximum d’une fonction de deux variables réelles.

Déf. B.2.10 On appelle x0 P D un point stationnaire pour une fonction f : D Ď Rn Ñ R si

∇f px0 q “ ~0. L’équation ∇f px0 q “ ~0 correspond aux système de n équations qui impose l’annulation
des n dérivés partielles de f en x0 , qui sont appelées équations de Euler-Lagrange.

Le résultat suivant est l’équivalent du théorème de Fermat sur les extrema pour les fonctions
de plusieurs variables réelles.

Théorème B.2.6 (Fermat en n dimensions) Si f : D Ď Rn Ñ R est partiellement dérivable

en x0 P D et si x0 es un extremum pour f , alors : ∇f px0 q “ ~0.

Par conséquent, les extrema de f peuvent se trouver dans :

— Les points de frontière de D ;
— Les points où f n’est pas dérivable ;
— Les points stationnaires de f .
La condition de stationnarité est seulement nécessaire, pour devenir suffisante elle a besoin
d’être accompagné par des autres conditions, notamment la convexité, comme on le montre dans le
chapitre 2. La figure B.2.3 montre un cas emblématique : un point ! selle ", qui est un maximum
par rapport à une direction et un minimum par rapport à une autre. Un point selle est stationnaire
sans être un extremum.

66
Figure B.5 – Un point selle : maximum par rapport à une direction, minimum par rapport à une
autre direction.

B.2.4 La matrice Jacobienne

Dans cette section on va examiner l’extension du concept de gradient aux fonctions à valeurs
vectoriels : f : D Ď Rn Ñ Rm , f “ pf1 , . . . , fm q, où fi : D Ď Rn Ñ R, i “ 1, . . . , m, sont les
fonctions composantes, qui sont à valeur scalaires et pour lesquelles on peut définir les dérivées
partielles comme on l’a fait avant, i.e.

Bfi fi px0 ` hej q ´ fi px0 q

px0 q “ lim , i “ 1, . . . , m, j “ 1, . . . , n,
Bxj hÑ0 h
ˆ ˙
Bfi Bfi
∇fi px0 q “ px0 q, . . . , px0 q , i “ 1, . . . , m.
Bx1 Bxn
Si on fait varier les indices i et j on obtient m ¨ n dérivées partielles, qui peuvent être organisées
en m vecteurs gradient à n composantes.

Exemple : calculer les dérivées partielles et les gradients des fonctions composantes de la fonction
suivante :
f: R3 ÝÑ R2
px, y, zq ÞÝÑ f px, y, zq “ px ` y ` z, xyz 3 q.
Comme n “ 3 y m “ 2, on va avoir 6 dérivées partielles et 2 vecteurs gradient avec 3 composantes.
Les fonctions composantes sont : f1 px, y, zq “ x ` y ` z, f2 px, y, zq “ xyz 3 , donc :
Bf1 Bf1 Bf1
px, y, zq “ px, y, zq “ px, y, zq “ 1,
Bx By Bz
Bf2 Bf2 Bf2
px, y, zq “ yz 3 , px, y, zq “ xz 3 , px, y, zq “ 3xyz 2 .
Bx By Bz
Les gradients des fonctions composantes sont :

∇f1 px, y, zq “ p1, 1, 1q, ∇f2 px, y, zq “ pyz 3 , xz 3 , 3xyz 2 q.

Les m ¨ n dérivées partielles de f : D Ď Rn Ñ Rm peuvent être disposées dans une matrice dite
Jacobienne, une matrice m ˆ n avec lignes données par les gradients des fonctions composantes :
¨ ˛ ¨ Bf1 Bf1 ˛
∇f1 pxq Bx1 pxq ¨ ¨ ¨ Bx n
pxq
Jf pxq “ ˝
˚ .. ‹ ˚ .. .. .. ‹ .
. ‚“ ˝ . . . ‚
Bfm Bfm
∇fm pxq Bx1 pxq ¨¨¨ Bxn pxq

67
Retenir que :
— Le nombre de colonnes de Jf pxq est la dimension du domaine de f ;
— Le nombre de lignes de Jf pxq est la dimension du codomaine de f .
Exemple de matrice Jacobienne : f px, y, zq “ px ` y ` z, xyz 3 q, alors :
ˆ ˙ ˆ ˙
∇f1 px, y, zq 1 1 1
Jf px, y, zq “ “ .
∇f2 px, y, zq yz 3 xz 3 3xyz 2

B.2.5 La matrice Hessienne

Comme pour les fonctions d’une seule variable réelle, on peut définir les dérivées partielles
d’ordre supérieure. Par exemple, considérons une fonction de deux variables f px, yq :
Bf
Bx : R2 ÝÑ R
Bf
px, yq ÞÝÑ Bx px, yq
Bf
By : R2 ÝÑ R
Bf
px, yq ÞÝÑ By px, yq,

si on dérive partiellement une autre fois on obtient :

B Bf B2 f
px, yq “ px, yq “ fxx px, yq
Bx Bx Bx2
B Bf B2 f
px, yq “ px, yq “ fyx px, yq
By Bx ByBx
B Bf B2 f
px, yq “ px, yq “ fxy px, yq
Bx By BxBy
B Bf B2 f
px, yq “ 2 px, yq “ fyy px, yq.
By By By
On définit :
— fxx px, yq, fyy px, yq : dérivées partielles d’ordre 2 pures ;
— fyx px, yq, fxy px, yq : dérivées partielles d’ordre 2 mixtes.
On peut itérer le processus de dérivation jusqu’à l’ordre que l’on veut.
Si, au lieu de deux variables on a n ą 2 variables, alors la technique pour obtenir les dérivées
partielles d’ordre supérieure est la même. Il y a n2 dérivées partielles d’ordre 2 dans ce cas.
Heureusement, un résultat très connu nous aide dans le calcul de ces dérivées.

Théorème B.2.7 (Théorème de Schwarz) Si les dérivées partielles d’ordre 1 de f : D Ď

Rn Ñ R existent et sont dérivables en un voisinage de x0 , alors les dérivées partielles d’ordre 2
de f dans le même voisinage existent et coı̈ncident.

Comme pour les dérivées partielles d’ordre 1, il existe une structure algébrique très importante
dans laquelle on peut placer les dérivées partielles d’ordre 2.

Déf. B.2.11 La matrice suivante est dite matrice Hessienne en x0 de la fonction f (évidemment
supposée être 2 fois partiellement dérivable en x0 ) :
ˆ ˙
fxx px, yq fyx px, yq
Hf px, yq “ n“2
fx,y px, yq fyy px, yq
¨ ˛
fx1 x1 px, yq fx1 x2 px, yq ... fx1 xn px, yq
˚ fx2 x1 px, yq fx2 x2 px, yq ... fx2 xn px, yq ‹
Hf px, yq “ ˚ n arbitraire.
˚ ‹
.. .. .. .. ‹
˝ . . . . ‚
fxn x1 px, yq fxn x2 px, yq ... fxn xn px, yq

68
Sous les hypothèses du théorème de Schwarz la matrice Hessienne est symétrique.

Exemple : f px, yq “ sinpx2 yq,

fx px, yq “ 2xy cospx2 yq, dérivable partout

fy px, yq “ x2 cospx2 yq, dérivable partout

ça vaut le théorème de Schwarz, donc :

fxx px, yq “ 2y cospx2 yq ´ 4x2 y 2 sinpx2 yq

fxy px, yq “ fxy px, yq “ 2x cospx2 yq ´ 2x3 y sinpx2 yq

fyy px, yq “ ´x4 sinpx2 yq
el alors la matrice Hessienne de f dans le point px, yq est :
ˆ ˙
2y cospx2 yq ´ 4x2 y 2 sinpx2 yq 2x cospx2 yq ´ 2x3 y sinpx2 yq
Hf px, yq “ .
2x cospx2 yq ´ 2x3 y sinpx2 yq ´x4 sinpx2 yq

B.2.6 La formule de Taylor pour fonctions de plusieurs variables

Rappelons la formule de Taylor à l’ordre 1 pour fonctions d’une seule variable réelle : si f est
dérivable en un voisinage de x0 avec dérivée première continue, alors ça vaut :

f pxq “ f px0 q ` f 1 px0 qpx ´ x0 q ` opx ´ x0 q,

xÑx0

où :
op}x ´ x0 }q
lim “ 0.
xÑx0 }x ´ x0 }
L’expression “ veut dire qu’il existe un voisinage de x0 dans lequel la formule est valide.
xÑx0
L’interprétation de la formule de Taylor au premier ordre est d’importance fondamentale : elle dit
qu’il existe un voisinage de x0 dans lequel la fonction f peut être approchée par la fonction linéaire
y “ f px0 q ` f 1 px0 qpx ´ x0 q, i.e. la droite tangente au graphe de f en x0 , et que l’erreur qu’on fait
avec cette approximation, mesuré par le terme opx ´ x0 q (! o petit "), est négligeable par rapport
à la distance Euclidienne entre x et x0 , i.e. }x ´ x0 }.
Si f : D Ď Rn Ñ R est une fonction de n variables, on doit remplacer la dérivée première par le
gradient : si f est partiellement dérivable 1 fois dans un voisinage de x0 P D, avec dérivée partielles
d’ordre 1 continues, alors ça vaut la formule de Taylor à l’ordre 1 suivante :
¨g ˛
n fn
ÿ Bf fÿ
f pxq “ f px0 q ` px0 qpxi ´ x0,i q ` o ˝e pxi ´ x0,i q2 ‚,
xÑx0
i“1
Bx i i“i

qui peut être écrite dans une forme compacte grâce au gradient et au produit scalaire Euclidien :

f pxq “ f px0 q ` x∇f px0 q, px ´ x0 qy ` op}x ´ x0 }q . (B.2)

xÑx0

Déf. B.2.12 L’équation :

z “ f px0 q ` x∇f px0 q, px ´ x0 qy ,
définit l’hyperplan tangent à la surface de f en x0 .
Si n “ 2 l’équation du plan tangent est :

Bf Bf
z “ f px0 , y0 q ` px0 , y0 qpx ´ x0 q ` px0 , y0 qpy ´ y0 q ,
Bx By

69
L’interprétation de la formule de Taylor pour une fonction de n variables est la suivante : il
existe un voisinage de x0 dans lequel la fonction f peut être approchée par la fonction linéaire
z “ f px0 q ` x∇f px0 q, px ´ x0 qy, i.e. l’hyperplan tangent à la surface de f en x0 , et l’erreur qu’on
fait avec cette approximation est négligeable par rapport à la distance Euclidienne entre x et x0 .
?
Il est connu que la fonction valeur absolu f pxq “ |x| “ x2 n’est pas dérivable en x0 “ 0, en
fait dans ce point on ne peut pas définir d’une manière unique une droite tangente a à la fonction
valeur absolu. L’extension à 2 variables de ce cas est la fonction f px1 , x2 q “ x21 ` x22 “ }x}, qui
n’est pas partiellement dérivable en p0, 0q, qui est le a sommet du cône décrit par cette fonction. La
généralisation à n variables est simple : f px1 , x2 q “ x21 ` . . . ` x2n “ }x}.
Observation importante : le fait de pouvoir approcher localement f à travers d’une fonction
linéaire nous permet d’utiliser les outils de l’algèbre linéaire pour obtenir des informations sur
l’action de f . Le prix à payer est que cette approximation est précise seulement dans un voisinage
d’un point, dès qu’on sort de ce voisinage on doit répéter le processus d’approximation linéaire par
rapport à un deuxième point. Celle-ci est la raison pour laquelle les méthodes numériques basés sur
les approximations linéaires des fonctions ont besoin de plusieurs étapes d’itération avant d’arriver
à un bon résultat.
Si f : D Ď Rn Ñ Rm , alors la formule de Taylor à l’ordre 1 doit être écrite à l’aide de la matrice
Jacobienne :
f pxq “ f px0 q ` Jf px0 qpx ´ x0 q ` op}x ´ x0 }q , (B.3)
xÑx0

la formule a les dimensions correctes si on représente f pxq comme un vecteur colonne m ˆ 1, alors
le produit matriciel Jf px0 qpx ´ x0 q a dimensions pm ˆ nq ˆ pn ˆ 1q “ m ˆ 1 et op}x ´ x0 }q est aussi
un vecteur colonne m ˆ 1.

Rappelons aussi la formule de Taylor à l’ordre 2 pour une fonction d’une seule variable réelle :
si f est 2 fois dérivable avec continuité dans un voisinage de x0 , alors ça vaut :
1
f pxq “ f px0 q ` f 1 px0 qpx ´ x0 q ` f 2 px0 qpx ´ x0 qpx ´ x0 q ` oppx ´ x0 q2 q,
xÑx0 2

où oppx ´ x0 q2 q es un erreur négligeable par rapport à px ´ x0 qn , i.e.

oppx ´ x0 q2 q
Ñ 0.
px ´ x0 q2 xÑx0

La généralisation à n variables est faite à l’aide de la matrice Hessienne pour remplacer la

dérivée seconde : si f : D Ď Rn Ñ R est partiellement dérivable 2 fois avec continuité dans un
voisinage de x0 P D, alors ça vaut la formule :

1
f pxq “ f px0 q ` x∇f px0 q, px ´ x0 qy ` xHf px0 qpx ´ x0 q, px ´ x0 qy ` op}x ´ x0 }2 q , (B.4)
xÑx0 2

qui montre que 12 f 2 px0 qpx ´ x0 q2 en dimension supérieure à 1 est remplacée par le terme
1
2 xHf px0 qpx ´ x0 q, px ´ x0 qy. Si n “ 2, alors on peut écrire explicitement cette formule comme ça :

f px, yq “ f px0 , y0 q ` fx px0 , y0 qpx ´ x0 q ` fy px0 , y0 qpy ´ y0 q

px,yqÑpx0 ,y0 q
1` ˘
` fxx px0 , y0 qpx ´ x0 q2 ` 2fxy px0 , y0 qpx ´ x0 qpy ´ y0 q ` fyy px0 , y0 qpy ´ y0 q2
2
` oppx ´ x0 q2 ` py ´ y0 q2 q.

Les termes d’ordre supérieur dans la formule de Taylor rajoutent des détails plus fins par
rapport à l’approximation linéaire de f , comme on peut le voir dans les figures B.2.6 et B.2.6.

70
Figure B.6 – Approximations d’ordre 0 et 1

Figure B.7 – Approximations d’ordre 2 et 3

Vous aimerez peut-être aussi

Opti l3
Pas encore d'évaluation
Opti l3
49 pages
Poly Cours
Pas encore d'évaluation
Poly Cours
142 pages
End 1
Pas encore d'évaluation
End 1
56 pages
Introduction à l'optimisation mathématique
Pas encore d'évaluation
Introduction à l'optimisation mathématique
73 pages
Poly Optimisation
Pas encore d'évaluation
Poly Optimisation
46 pages
Introduction à la recherche opérationnelle
Pas encore d'évaluation
Introduction à la recherche opérationnelle
70 pages
Dualité Lagrangienne et Optimisation
Pas encore d'évaluation
Dualité Lagrangienne et Optimisation
70 pages
Cours Galerne
Pas encore d'évaluation
Cours Galerne
38 pages
Cours Optimisation
100% (1)
Cours Optimisation
43 pages
Polyao 101
Pas encore d'évaluation
Polyao 101
109 pages
Optimisation EA1
Pas encore d'évaluation
Optimisation EA1
130 pages
Poly CSC 216
Pas encore d'évaluation
Poly CSC 216
158 pages
Introduction à l'optimisation convexe
Pas encore d'évaluation
Introduction à l'optimisation convexe
44 pages
Cours d'Optimisation Mathématique
Pas encore d'évaluation
Cours d'Optimisation Mathématique
51 pages
Optimisation Convexe de Fonctions Non Linéaires
Pas encore d'évaluation
Optimisation Convexe de Fonctions Non Linéaires
27 pages
Optimisation et Calcul Différentiel ECP
Pas encore d'évaluation
Optimisation et Calcul Différentiel ECP
104 pages
CoursOptim PDF
Pas encore d'évaluation
CoursOptim PDF
104 pages
Introduction à l'optimisation mathématique
100% (1)
Introduction à l'optimisation mathématique
45 pages
Poly Optimisation
Pas encore d'évaluation
Poly Optimisation
45 pages
Algorithmes d'Optimisation Différentiable
Pas encore d'évaluation
Algorithmes d'Optimisation Différentiable
44 pages
Support - cours-PM-Licence (1) Optimisation Casa
Pas encore d'évaluation
Support - cours-PM-Licence (1) Optimisation Casa
36 pages
Optimisation Mathématique Avancée
Pas encore d'évaluation
Optimisation Mathématique Avancée
55 pages
Résolution Numérique de Systèmes Linéaires
Pas encore d'évaluation
Résolution Numérique de Systèmes Linéaires
72 pages
ANUM Poly Mines Cours NEW
Pas encore d'évaluation
ANUM Poly Mines Cours NEW
172 pages
Optimisation Numerique
Pas encore d'évaluation
Optimisation Numerique
29 pages
Optimisation EA1
Pas encore d'évaluation
Optimisation EA1
130 pages
Polycopie ANI
Pas encore d'évaluation
Polycopie ANI
68 pages
Poly GMM4
Pas encore d'évaluation
Poly GMM4
106 pages
OptiAlgo PDF
Pas encore d'évaluation
OptiAlgo PDF
53 pages
L3MIASHS AnalyseAvancée2
Pas encore d'évaluation
L3MIASHS AnalyseAvancée2
23 pages
Méthodes Numériques Systèmes Linéaires
100% (1)
Méthodes Numériques Systèmes Linéaires
72 pages
coursOptNum23 1
Pas encore d'évaluation
coursOptNum23 1
44 pages
Optimisation
Pas encore d'évaluation
Optimisation
12 pages
MACS2 AnaNumAv
Pas encore d'évaluation
MACS2 AnaNumAv
60 pages
Exam Optimi 07
Pas encore d'évaluation
Exam Optimi 07
4 pages
Chapitres 1-2-3 Cours Optimisation Sans Contraintes
100% (1)
Chapitres 1-2-3 Cours Optimisation Sans Contraintes
43 pages
Opti Algo
Pas encore d'évaluation
Opti Algo
50 pages
Transp Optim 2018
Pas encore d'évaluation
Transp Optim 2018
38 pages
Maths Éco : Optimisation et Algèbre
Pas encore d'évaluation
Maths Éco : Optimisation et Algèbre
80 pages
Optimisation Non-Linéaire L3
Pas encore d'évaluation
Optimisation Non-Linéaire L3
53 pages
Recueil Exercices Problemes
Pas encore d'évaluation
Recueil Exercices Problemes
43 pages
Fiche Ao 101
Pas encore d'évaluation
Fiche Ao 101
10 pages
PolyMethNumBentobache2020 2021
Pas encore d'évaluation
PolyMethNumBentobache2020 2021
50 pages
Analyse Numérique et Optimisation
Pas encore d'évaluation
Analyse Numérique et Optimisation
150 pages
Poly 2022
Pas encore d'évaluation
Poly 2022
69 pages
Chap1 2
Pas encore d'évaluation
Chap1 2
38 pages
00poly PDF
Pas encore d'évaluation
00poly PDF
130 pages
Magistere
Pas encore d'évaluation
Magistere
192 pages
Analyse Num 12-13
Pas encore d'évaluation
Analyse Num 12-13
72 pages
Exercices corrigés en optimisation convexe
100% (3)
Exercices corrigés en optimisation convexe
346 pages
Methodes Numeriques-CIFAD
Pas encore d'évaluation
Methodes Numeriques-CIFAD
124 pages
Optimisation Numérique L3 Paris-Dauphine
Pas encore d'évaluation
Optimisation Numérique L3 Paris-Dauphine
78 pages
Exo 122
Pas encore d'évaluation
Exo 122
1 page
Livre Exercice Correge A F
Pas encore d'évaluation
Livre Exercice Correge A F
55 pages
TD Serie3
Pas encore d'évaluation
TD Serie3
2 pages
Algèbre Bilinéaire et Applications
Pas encore d'évaluation
Algèbre Bilinéaire et Applications
67 pages
Cours PTM ECUE1
Pas encore d'évaluation
Cours PTM ECUE1
44 pages
Estimation Yule-Walker CAR(p) Discret
Pas encore d'évaluation
Estimation Yule-Walker CAR(p) Discret
19 pages
Setif FreeFem II
Pas encore d'évaluation
Setif FreeFem II
40 pages
Puissances Fiches Pedagogiques Maths 3AC PDF 2
Pas encore d'évaluation
Puissances Fiches Pedagogiques Maths 3AC PDF 2
7 pages
6.-Corrige Colle06 Reduction Endomorphisme
Pas encore d'évaluation
6.-Corrige Colle06 Reduction Endomorphisme
6 pages
TD6 Diagonalisation et Propriétés des Matrices
100% (1)
TD6 Diagonalisation et Propriétés des Matrices
2 pages
2324DS4 Matrices Symplectiques
Pas encore d'évaluation
2324DS4 Matrices Symplectiques
4 pages
Epreuve de Mathematique Bac Blanc Diocesain de Porto Novo Serie C 2ere Edition Mai 2023 - 2023 - 13 - 2 - 52
Pas encore d'évaluation
Epreuve de Mathematique Bac Blanc Diocesain de Porto Novo Serie C 2ere Edition Mai 2023 - 2023 - 13 - 2 - 52
3 pages
Concours Commun Polytechniques (CCINP) 2023 MP-MPI Mathématiques 2 Ca
Pas encore d'évaluation
Concours Commun Polytechniques (CCINP) 2023 MP-MPI Mathématiques 2 Ca
8 pages
Feuilletage
Pas encore d'évaluation
Feuilletage
16 pages
Algèbre Avancée : Formes Quadratiques
Pas encore d'évaluation
Algèbre Avancée : Formes Quadratiques
4 pages
Exercices Mathématiques pour Lycéens
Pas encore d'évaluation
Exercices Mathématiques pour Lycéens
4 pages
Chapitre2 - Series Numeriques - Copie
Pas encore d'évaluation
Chapitre2 - Series Numeriques - Copie
6 pages
Fonction Logarithme Neperien
Pas encore d'évaluation
Fonction Logarithme Neperien
4 pages
CM1 L9 Ranger Des Fractions Simples 2020
100% (3)
CM1 L9 Ranger Des Fractions Simples 2020
3 pages
Problème D'analyse
Pas encore d'évaluation
Problème D'analyse
1 page
Chaiptre 6
Pas encore d'évaluation
Chaiptre 6
17 pages
Devoir de Contrôle N°3 - Math - Bac Technique (2013-2014) MR Fawzi Khemiri
Pas encore d'évaluation
Devoir de Contrôle N°3 - Math - Bac Technique (2013-2014) MR Fawzi Khemiri
2 pages
Cours sur les intégrales généralisées
Pas encore d'évaluation
Cours sur les intégrales généralisées
6 pages
Algèbre bilinéaire et formes quadratiques
0% (1)
Algèbre bilinéaire et formes quadratiques
21 pages
Théorème d'incomplétude de Gödel
Pas encore d'évaluation
Théorème d'incomplétude de Gödel
12 pages
Nombredecimauxrlatif 6 Eme
100% (2)
Nombredecimauxrlatif 6 Eme
3 pages
Introduction à l'analyse de Fourier
Pas encore d'évaluation
Introduction à l'analyse de Fourier
39 pages
Tle STT
Pas encore d'évaluation
Tle STT
2 pages
Les Ens Et Les App
Pas encore d'évaluation
Les Ens Et Les App
6 pages
Racines Carrees Cours Et Exercices Ma
100% (1)
Racines Carrees Cours Et Exercices Ma
3 pages
Exercices de Graphes pour Terminale ES
0% (1)
Exercices de Graphes pour Terminale ES
6 pages
Andre
Pas encore d'évaluation
Andre
9 pages
Épreuves de mathématiques 3ème et Tle
Pas encore d'évaluation
Épreuves de mathématiques 3ème et Tle
2 pages
Bac S Polynésie 2020 : Examen de Mathématiques
Pas encore d'évaluation
Bac S Polynésie 2020 : Examen de Mathématiques
5 pages

Poly Optimisation

Transféré par

Poly Optimisation

Transféré par

Polycopié du cours :

OPTIMISATION CONVEXE (Première partie)

1 Les outils algébriques pour la résolution du problème des moindres carrés 3

A Un très bref rappel d’algèbre linéaire 45

B Un très bref rappel sur les espaces métriques et le calcul différentiel en Rn 57

Les outils algébriques pour la

1.1 Introduction aux outils algébriques de l’optimisation

1.2 Résolution d’un système linéaire dans le sens des moindres

— n “ m : même nombre d’inconnues et d’équations, le système est dit déterminé. Dans

— n ă m : plus d’équations que d’inconnues, les système est dit sur-déterminé. Si on a n

Interprétation du théorème : Ax̄ “ PImpAq b si et seulement si x̄ est le vecteur qui minimise la

Vu que Ax ´ PImpAq b et y sont orthogonales et comme } ´ y}2 “ }y}2 , on peut appliquer le

}Ax ´ b}2 “ looooooooomooooooooon

1.3 Les équations normales associées à un système linéaire

Théorème 1.3.1 Soient A P Mm,n pRq, x P Rn , b P Rm , alors :

Ax “ PImpAq b ô x “ arg min}Ax ´ b}2 ô At Ax “ At b ,

Ax “ PImpAq b ô Ax ´ b “ PImpAq b ´ b ô Ax ´ b “ ´y P pImpAqqK “ kerpAt q,

mais Ax ´ b P kerpAt q veut dire que At pAx ´ bq “ 0, i.e. At Ax ´ At b “ 0, donc At Ax “ At b.

1.4 Résolution des équations normales, la matrice pseudo-

x̄ “ I x̄ “ pAt Aq´1 At Ax̄ “ pAt Aq´1 At b

La caractérisation du projecteur PImpAq est immédiate :

Ax “ PImpAq b ô Ax “ ApAt Aq´1 At b,

1.4.2 At A non inversible, mais diagonale

Déf. 1.4.1 On appelle matrice pseudo-inverse de Moore-Penrose 1 de D P Mn pRq, la ma-

où les valeurs 1 se répètent r fois.

x̄ “ D` At b est solution de Ax “ PImpAq b ô At Ax “ At b ô arg min}Ax ´ b}2 .

En résumé : si At A est non inversible et non diagonale, alors

x̄ “ P D` P t At b est solution de Ax “ PImpAq b ô At Ax “ At b ô arg min}Ax ´ b}2 ,

Lemme 1.5.1 Hypothèses :

pAv1 , . . . , Avr q est une base orthogonale de ImpAq.

Preuve. L’hypothèse λ1 , . . . , λr ą 0 implique que σ1 , ¨ ¨ ¨ , σr ą 0 et donc, Lemme 1.5.1 1.,

Avant d’énoncer et démontrer le théorème sur la décomposition en valeurs singulières on a

Théorème 1.5.1 (SVD) Soit A P Mm,n pRq, rangpAq “ r et soient σ1 ě σ2 ě . . . σr ą 0 les

i.e. Avk “ σk uk , k “ 1, . . . , r, où on a utilisé la propriété 1. du Lemme 1.5.2.

U “ pu1 ¨¨¨ um q , V “ pv1 ¨¨¨ vn q.

Comme Avk “ σk uk pour k “ 1, . . . , r et Avj “ 0 pour j “ r ` 1, ¨ ¨ ¨ , n (par hypothèse sur

x̄ “ V Σ` U t b est solution de arg min}Ax ´ b}2 ,

et, par définition, la pseudo-inverse de A est :

Théorème 1.5.2 Soit A P Mm,n pRq et A` la matrice pseudo-inverse de Moore-Penrose de A,

— AA` représente le projecteur orthogonale de Rm sur ColpAq “ ImpAq ;

— @y P Rm , x` “ A` y est la seule solution des moindres carrés de Ax “ y qui appartient à

— si rankpAq “ n, alors A` “ pAt Aq´1 At est l’inverse gauche de A ;

— si rankpAq “ m, alors A` “ At pAAt q´1 est l’inverse droite de A ;

— si n “ m et A est inversible, alors A` “ A´1 ;

— si la SVD de A est A “ U ΣV t , alors sa pseudo-inverse A` est :

en particulier, les valeurs singulières de A` sont les inverses de ceux de A.

1.5.1 SVD comme solution de norme minimale au problème des moindres

}x}2 “ }x` }2 ` }x0 }2 ě }x` }2 ,

2.1 Ensembles et fonctions convexes

Figure 2.2 – Propriété géométrique des sécantes à une parabole.

Déf. 2.1.4 (Fonction convexe (concave) et strictement convexe (concave)) f : C Ñ R

@x, y P C f ptx ` p1 ´ tqyq ď tf pxq ` p1 ´ tqf pyq @t P r0, 1s.

@x, y P C f ptx ` p1 ´ tqyq ă tf pxq ` p1 ´ tqf pyq @t Ps0, 1r,

f : C Ñ R, C Ď Rn est concave (strictement concave) si ´f est convexe (strictement convexe).

On montrera des exemples explicites de fonctions convexes dans la section 2.2.

2.1.1 Caractérisation au premier ordre de la convexité et ses conséquences

Théorème 2.1.1 (Caractérisation au premier ordre de la convexité d’une fonction) Soit

f est convexe ðñ f pyq ´ f pxq ě x∇f pxq, y ´ xy @x, y P C. (2.1)

De plus, f est strictement convexe ðñ f pyq ´ f pxq ą x∇f pxq, y ´ xy @x, y P C.

Avant de démontrer le théorème, allons l’interpréter géométriquement :

@x, y P C f ptx ` p1 ´ tqyq ď tf pxq ` p1 ´ tqf pyq @t P r0, 1s,

f py ` tpx ´ yqq f pyq

f py ` tpx ´ yqq ´ f pyq

f pxq ´ f pyq ě x∇f pyq, x ´ yy @x, y P C,

f pyq ´ f pxq ě x∇f pxq, y ´ xy @x, y P C,

qui est l’implication directe du théorème.

f pxq ´ f pzq ě x∇f pzq, x ´ zy, (2.2)

f pyq ´ f pzq ě x∇f pzq, y ´ zy. (2.3)

tf pxq ´ tf pzq ě tx∇f pzq, x ´ zy,

p1 ´ tqf pyq ´ p1 ´ tqf pzq ě p1 ´ tqx∇f pzq, y ´ zy.

un peu de maquillage mathématique :

tf pxq ` p1 ´ tqf pyq ´ f pzq ě x∇f pzq, tx ´ 

tf pxq`p1´tqf pyq´f pzq ě 0 ðñ tf pxq`p1´tqf pyq ě f pzq ðñ tf pxq`p1´tqf pyq ě f ptx`p1´tqyq,

Le théorème précédent a beaucoup de conséquences importantes, peut être, la plus importante

Théorème 2.1.2 (Fermat (1637)) Soit f : C Ñ R, C convexe et ouvert 2 en Rn , f convexe et

x˚ “ arg min f pxq ðñ ∇f px˚ q “ 0, (2.4)

tf pxq ` p1 ´ tqf pyq ´ f pzq ě x∇f pzq, tx ´