Poly Cours
Poly Cours
Optimisation
Guillaume Garrigos
Prérequis : Notions d’Algèbre Linéaire et de Calcul Différentiel. Les notions dont nous
aurons besoin pour ce cours sont réunies dans le Chapitre I, qui sert d’introduction à ce
cours. En particulier, il est nécessaire d’avoir une bonne compréhension de ce que sont les
matrices (semi-)définies positives, et le gradient et la hessienne d’une fonction à valeurs
réelles.
Hors-piste : Les sections dont le titre se termine par une astérisque ∗ sont plus avancées.
Elles sont donc, par défaut, hors programme, à moins que le temps nous permette de les
traiter en cours. Elles permettent dans tout les cas d’apporter des informations complémentaires,
qui je l’espère satisferont les plus curieuses et curieux. C’est le cas des Annexes, qui
contiennent les preuves de résultats qui ont été admis pendant le cours, ainsi que des
développements un peu plus avancés.
3
4
Références
Ces notes de cours ont été rédigées entre 2020-2021, sur la base d’un polycopié d’Olivier
Bokanowski, ajourné par Matthieu Bonnivard. Au cas où le contenu de ce polycopié ne
vous suffise pas, voici quelques références qui vous permettront d’aller plus loin.
• Optimisation et analyse convexe : Exercices et problèmes corrigés, avec rappels de cours par
Jean-Baptiste Hiriart-Urruty [7]. L’auteur est un très bon pédagogue et agréable à lire.
Comme le suggère le titre, son livre contient de nombreux exercices corrigés. Attention
toutefois, son contenu est de difficulté variable, avec des chapitres qui dépassent le
cadre de ce cours. Focalisez-vous sur les 3 premiers chapitres (sauf III.2). Je ne peux que
vous inviter à lire également la section historique en fin du livre, riche en anecdotes.
• Objectif Agrégation, par Vincent Beck, Jérôme Malick et Gabriel Peyré [3]. Voici également
un livre que je trouve très bien écrit, certainement un de mes préférés. C’est un livre
généraliste (qui couvre analyse et algèbre), mais son premier chapitre donne une vi-
sion d’ensemble sur le calcul différentiel et ses applications qui je pense vaut le coup
d’œil.
• Nonlinear Programming, par Dimitri P. Bertsekas [4]. L’auteur est bon pédagogue, et ac-
compagne ses explications par des dessins et schémas très utiles à la compréhension.
Les chapitres 1.1-4 portent sur le contenu des chapitres II et IV. Le chapitre 3, en parti-
culier la partie 3.3, développe en détail le contenu du chapitre V.
• Introduction à l’analyse numérique matricielle et à l’optimisation, par Phillipe Ciarlet [5].
Un classique, mais qui a un peu vieilli. Le chapitre 1 vous fournira de bons rappels en
Algèbre Linéaire. Les chapitres 7.1-4 et 8.1-4 portent sur le contenu du cours, le reste
dépasse le cadre du cours.
• Analyse numérique et optimisation : Une introduction à la modélisation mathématique et à
la simulation numérique, par Grégoire Allaire [1]. Ce livre se focalise sur la résolution
des Équations aux Dérivées Partielles, et ses chapitres 9-10 fournissent des exemples
intéressants d’application des résultats de ce cours aux EDPs. Attention cependant,
l’auteur travaille dans le cadre d’espaces de Hilbert, et sa présentation des résultats
diffère du contenu de ce cours et parfois dépasse son cadre.
5
6
Table des matières
7
8 TABLE DES MATIÈRES
L’optimisation est une discipline qui emprunte beaucoup de notions à l’algèbre linéaire et
au calcul différentiel. Voici donc quelques rappels concernant les notions dont vous aurez
besoin dans ce cours. Les résultats qui suivent sont admis, bien que pour certains nous
reverrons leurs preuves en TD. J’en profite également pour tordre le cou à certaines idées
préconçues.
Comment lire ce chapitre ? Ceci est essentiellement un chapitre de rappels, bien qu’il
puisse contenir des choses que vous n’avez pas vues, ou simplement oubliées. Je vous
conseille donc d’en faire une première lecture en diagonale, afin de déterminer si ce qui
s’y trouve vous semble familier ou non ; puis, dans un deuxième temps, de travailler les
parties qui vous semblent les plus obscures. Vous pourrez par exemple vous tourner vers
les exercices qui sont proposés, que vous trouverez également dans la feuille de TD. Ils
ne seront pas tous traités en TD, donc n’hésitez pas à en piocher quelques-uns par vous-
mêmes.
Notations.
9
10 CHAPITRE I. ÉLÉMENTS D’ALGÈBRE LINÉAIRE ET DE CALCUL DIFFÉRENTIEL
Si on regarde les vecteurs de R N comme des vecteurs colonne, on peut également écrire le
produit scalaire comme un produit matriciel entre une ligne et une colonne : h x, yi = x > y.
La norme euclidienne de R N , notée k · k : R N → R+ , est définie par :
v
q uN
(∀ x ∈ R ) k x k := h x, x i = t ∑ xi2 .
u
N
i =1
i =1
Voici quelques propriétés utiles pour faire des calculs incluant des produits scalaires
et des normes :
Proposition I.1.
i) (Identité remarquable 1) Pour tous x, y ∈ R N , k x + yk2 = k x k2 + kyk2 + 2h x, yi.
ii) (Identité remarquable 2) Pour tous x, y ∈ R N , k x k2 − kyk2 = h x + y, x − yi.
iii) (Inégalité de Cauchy-Schwarz) Pour tous x, y ∈ R N , −k x kkyk ď h x, yi ď k x kkyk.
iv) (Règle de l’adjoint) Pour toute matrice A ∈ M M,N (R), x ∈ R N , y ∈ R M , h Ax, yi =
h x, A> yi.
Remarque I.2. Cette quatrième propriété est souvent méconnue/oubliée par les étudiant(e)s.
Elle est pourtant essentielle pour tout les calculs impliquant matrice et produit scalaire.
On la retrouvera régulièrement au long de ce cours. Elle permet par exemple d’écrire des
choses comme k Ax k2 = h A> Ax, x i.
I.I. RAPPELS ET COMPLÉMENTS D’ALGÈBRE LINÉAIRE 11
I.I.1.ii) Orthogonalité
Définition I.3. On dira que deux vecteurs x et y de R N sont ORTHOGONAUX lorsque
h x, yi = 0.
Remarque I.4. C’est une notion que vous avez rencontré à de multiples reprises, par
exemple les bases orthogonales (bases dont les vecteurs sont tous orthogonaux les uns
avec les autres).
F ⊥ := { x ∗ ∈ R N | (∀ x ∈ F ) h x ∗ , x i = 0}.
Proposition I.6.
i) F ⊥ est un sous-espace vectoriel de R N .
ii) F et F ⊥ sont supplémentaires. En particulier, dim F + dim F ⊥ = N.
iii) ( F ⊥ )⊥ = F.
Proposition I.7. Soit A ∈ M N (R). Alors Ker( A)⊥ = Im( A> ) et Im( A)⊥ = Ker( A> ).
B( x, r ) := {y ∈ R N | d( x, y) < r }.
B( x, r ) := {y ∈ R N | d( x, y) ď r }.
Définition I.9.
• On dit qu’un ensemble U ⊂ R N est OUVERT si
(∀ x ∈ U )(∃r > 0) B( x, r ) ⊂ U.
• Étant donné un ensemble C ⊂ R N , on définit son INT ÉRIEUR , que l’on note int C,
comme étant l’ensemble
Remarque I.10. Par définition, l’intérieur d’un ensemble est le plus petit ouvert inclus
dans cet ensemble. Ces définitions impliquent également que la boule ouverte est ouverte,
et que la boule fermée est fermée (heureusement !).
Proposition I.12. Les valeurs propres de A ∈ M N (R) sont les racines réelles du polynôme
caractéristique X 7→ det( XIN − A).
Remarque I.13. Une matrice A ∈ M N (R) peut ne posséder aucune valeur propre. Par
exemple la matrice
0 −1
1 0
Définition I.14. On dit que λ ∈ C est une VALEUR SPECTRALE (ou valeur propre com-
plexe) de A ∈ M N (R) s’il existe un vecteur non nul x ∈ C N tel que Ax = λx. Autrement
dit, si A − λI n’est pas inversible dans M N (C). Le SPECTRE de A, noté spec( A), est l’en-
semble des valeurs spectrales de A.
Proposition I.15. Les valeurs spectrales de A ∈ M N (R) sont les racines complexes du polynôme
caractéristique det( XIN − A).
Remarque I.17.
• Dans certains cas, toutes les valeurs spectrales sont réelles : spec( A) = specR ( A). On
va par exemple voir que c’est le cas pour les matrices symétriques.
• Le spectre n’est jamais vide. C’est une conséquence du fait que tout polynôme réel
admet au moins une racine dans C.
I.I. RAPPELS ET COMPLÉMENTS D’ALGÈBRE LINÉAIRE 13
Remarque I.19. Pour les matrices triangulaires, et en particulier pour les matrices dia-
gonales, les valeurs propres se situent donc sur la diagonale. C’est très pratique
!
Mais
0 −1
c’est malheureusement faux en règle générale. Par exemple, le spectre de est
1 0
{−i, +i }, qui ne contient pas {0}.
i) tr( A) = ∑iN=1 λi ,
ii) det( A) = ∏iN=1 λi .
Il est clair que spec( A) = {2} (et non pas (2, 2, 2) : on parle d’ensemble, pas de uplet !),
c’est à dire qu’il y a une unique valeur spectrale 2. Pour autant on voit bien que tr( A) 6= 2
et det( A) 6= 2. Pour que ce résultat marche, il nous faut prendre en compte la multipli-
cité algébrique de 2. Cette multiplicité est exactement la puissance apparaissant dans le
polynôme caractéristique de A, qui est ici ( X − 2)3 .
Définition I.22. Le RAYON SPECTRAL d’une matrice A ∈ M N (R), noté ρ( A), est défini
par
ρ( A) := max{|λ| | λ ∈ spec( A)}.
Remarque I.23. Un contre-sens classique est de penser que le rayon spectral est la plus
grande valeur propre . Ceci est faux, pour de nombreuses raisons :
• Les valeurs propres peuvent ne pas exister. Le rayon spectral porte sur les valeurs
spectrales (ou les valeurs propres complexes).
• On ne peut pas parler de plus grande valeur spectrale non plus, car C n’est pas
muni d’une relation d’ordre total, contrairement à R ! On ne peut
√ pas comparer 2i et
1 + i par exemple. Par contre on peut comparer leur module 2 et 2.
14 CHAPITRE I. ÉLÉMENTS D’ALGÈBRE LINÉAIRE ET DE CALCUL DIFFÉRENTIEL
• Même lorsque le spectre est réel, le rayon spectral ne maximise pas les valeurs propres
mais leur valeur absolue. Par exemple, pour la matrice
1 0
A=
0 −2
la plus grande valeur propre est 1 (puisque 1 > −2), mais ρ( A) = 2. Cela peut paraitre
un détail mais cela a son importance !
k Ax k
A := sup .
x 6 =0 kxk
Remarque I.25 (NormeS matricielleS). Il existe de nombreuses façons de munir M M,N (R)
d’une norme. Ceux parmi vous ayant suivi le cours d’Analyse Numérique Matricielle en
auront vu une palanquée (les normes d’opérateur ` p /`q , la norme de Froebenius) et il en
existe bien d’autres (citons la très utile norme nucléaire), les plus curieux pourront consul-
ter l’article Wikipédia sur le sujet1 . Néanmoins, dans ce cours nous ferons seulement appel
à la norme d’opérateur subordonnée à la norme euclidienne · mentionnée ci-dessus.
Cette norme d’opérateur · vérifie deux inégalités très importantes. La première est
une conséquence directe de la définition. La seconde est une propriété de sous-multiplicativité,
qui fait de · ce que l’on appelle une norme d’algèbre.
Proposition I.26.
Exercice I.27. Soit A ∈ M N (R) telle que A < 1. Montrer que Ak tend vers 0 (la matrice
nulle) lorsque k → +∞.
Exercice I.30. Pour toute matrice A ∈ M M,N (R), montrer que les matrices A> A ∈ M N (R)
et AA> ∈ M M (R) sont symétriques.
Exercice I.31. Soit A ∈ M N (R) une matrice antisymétrique. Montrer que, pour tout x ∈
R N , h Ax, x i = 0.
Exercice I.32. Soit A ∈ M N (R) quelconque. Montrer que A + A> est symétrique, et que
A − A> est antisymétrique.
Proposition I.33. Toute matrice A ∈ M N (R) peut se décomposer comme la somme d’une ma-
trice symétrique et d’une matrice antisymétrique. En effet :
A + A> A − AT
(∀ A ∈ M N (R)) A= + .
2 }
| {z 2 }
| {z
symétrique antisymétrique
>
Remarque I.34. On peut en fait même montrer que la matrice symétrique A+2A est la
projection orthogonale de A sur le sous-espace vectoriel des matrices symétriques.
Théorème I.35 (Théorème spectral). Soit A ∈ M N (R) une matrice symétrique. Alors il existe
• une matrice diagonale réelle D ∈ M N (R)
• une matrice inversible U ∈ M N (R) telle que U −1 = U T (une matrice orthogonale, donc)
telles que A = U > DU.
Proposition I.36. Soit A ∈ M N (R) une matrice symétrique. Alors sa norme d’opérateur est
égale au rayon spectral :
A = ρ ( A ).
Remarque I.37. La norme d’opérateur est égale au rayon spectral est faux en général,
puisque cela s’applique seulement aux matrices symétriques. Pour une matrice générale,
c’est la Proposition I.28 qui s’applique. Pour s’en rendre compte, considérons par exemple
0 1 > 1 0
A= telle que A A = .
0 0 0 0
On voit que spec( A> A) = {1, 0}, donc on déduit de la Proposition I.28 que A = 1.
Pour autant, spec( A) = {0} (immédiat puisque A est triangulaire avec des zéros sur la
diagonale) donc ρ( A) = 0. Ici, la norme d’opérateur est bien différente du rayon spectral.
Puisque les matrices symétriques ont des valeurs propres réelles, on introduit deux
notations qui nous seront utiles par la suite :
La Proposition I.39 ne dit rien d’autre que le fait que f circ ( x1 , x2 ) ď f ell ( x1 , x2 ) ď f insc ( x1 , x2 ).
L’ordre entre ces fonctions peut se voir clairement lorsque on trace leur graphe (cf Figure
I.1).
1 0
F IGURE I.1 – Inégalité de la Proposition I.39 pour A = .
0 4
Attention toutefois à bien garder en tête que la Proposition I.39 est encore vraie lorsque
λmin ( A) < 0 ! Dans ce cas, cette histoire d’ellipses ne tient plus puisque la fonction qua-
dratique associée à A est dégénérée, et ses courbes de niveaux ne sont plus des ellipses
mais des hyperboles (voir Figure I.2).
(∀ x ∈ R N ) h Ax, x i ě 0.
−1 0
F IGURE I.2 – Inégalité de la Proposition I.39 pour A = .
0 4
Remarque I.43 (Matrice semi-définie positive vs. coefficients positifs). La notion de ma-
trice semi-définie positive est parfois confondue avec la notion de matrice-dont-les-
coefficients-sont-positifs , or ces deux notions n’ont rien en commun. Par exemple, la
matrice
0 −1
(I.1)
1 0
possède un coefficient négatif, néanmoins elle est bien semi-définie positive puisque
0 −1 x x −y x
(∀( x, y) ∈ R )
2
h , i=h , i = −yx + xy = 0 ě 0.
1 0 y y x y
Remarque I.44 (Matrice semi-définie positive et valeurs propres). Une autre confusion
fréquente est la suivante :
Une matrice est semi-définie positive si et seulement si ses valeurs propres sont
positives ,
I.I. RAPPELS ET COMPLÉMENTS D’ALGÈBRE LINÉAIRE 19
voire également :
Une matrice est définie positive si et seulement si ses valeurs propres sont strictement
positives .
Ces deux énoncés sont faux en général. Rappelons par exemple qu’une matrice carrée
n’admet pas nécessairement de valeurs propres, c’est le cas de la matrice (I.1) qui n’admet
aucune valeur propre réelle, mais qui pourtant est bien semi-définie positive. Par contre
que ces énoncés sont vrais si la matrice en question est symétrique :
Proposition I.45. Soit A ∈ M N (R) une matrice symétrique. Alors on a les équivalences sui-
vantes :
1) les matrices A> A ∈ M N (R) et AA> ∈ M M (R) sont symétriques semi-définies posi-
tives ;
2) A> A est définie positive si et seulement si A est injective ;
3) AA> est définie positive si et seulement si A est surjective.
Et pour les matrices non symétriques ? Eh bien nous pouvons toujours nous ramener
aux matrices symétriques, grâce au résultat suivant :
En pratique, pour une matrice carrée A quelconque, il suffit donc de vérifier le signe
>
des valeurs propres de la matrice symétrique A 2+ A .
0 1
Exemple I.48. Si on considère la matrice triangulaire A = , on voit que spec( A) =
0 0
{0}. Mais on ne peut pas en déduire immédiatement que A est semi-définie positive,
A> + A 0 1/2
puisque elle n’est pas symétrique ! Par contre on peut calculer 2 = ,
1/2 0
dont l’ensemble des valeurs propres est {±1/2}. Puisque l’une des valeurs propres est
négative, on en déduit que A n’est pas une matrice semi-définie positive.
sont négatives ? Si elles le sont toutes, on parle de matrice semi-définie négative, sinon on
parle de matrice indéfinie :
(∀ x ∈ R N ) h Ax, x i ď 0.
Exemple I.50. Il peut être intéressant de visualiser ces propriétés d’une matrice A en re-
gardant le graphe de la fonction quadratique associée q A : x 7→ h Ax, x i. Comme on peut
le voir dans la figure I.3, les formes quadratiques définies positives montent à l’infini dans
toutes les directions. Lorsque A est semi-définie positive mais pas définie positive, cela
veut dire qu’il y a un noyau non nul, ce qui se traduit par des directions où la forme qua-
dratique est constante. Lorsque A est non définie, la forme quadratique peut tendre vers
+∞ ou −∞, selon la direction dans laquelle on va. Dans ce cas on parle souvent de point
selle, qui est une notion que l’on reverra bientôt.
F IGURE I.3 – Formes quadratiques respectivement associées à une matrice définie positive,
semi-définie positive et non définie.
I.I.5.ii) La pratique
Un réflexe naturel pour déterminer la positivité d’une matrice symétrique est de calcu-
ler ses valeurs propres, puis de simplement vérifier leur signe. Or, calculer les valeurs
I.I. RAPPELS ET COMPLÉMENTS D’ALGÈBRE LINÉAIRE 21
propres, ce n’est pas facile lorsque la dimension dépasse 3 (et déjà pour N = 3 ce n’est pas
très sympathique).
Mais en réalité nous n’avons pas besoin de calculer les valeurs propres ; tout ce dont
on a besoin est leur signe. Par exemple, pour les matrices 2 × 2 :
Exercice I.51. (Positivité d’une matrice symétrique 2 × 2) Soit A ∈ M2 (R) une matrice
symétrique. Montrer que A est semi-définie positive (resp. définie positive) si et seulement
si sa trace et son déterminant sont positifs (resp. strictement positifs).
Ce critère ne vaut évidemment que pour les matrices de taille 2. Pour des matrices
plus grandes, on dispose en fait d’un critère plus général, qui passe par le calcul de
déterminants de certaines sous-matrices :
Théorème I.53 (Critère de Sylvester). Soit A ∈ M N (R) une matrice symétrique. Alors :
i) A est semi-définie positive si et seulement si tous ses mineurs principaux sont positifs.
ii) A est définie positive si et seulement si tous ses mineurs principaux sont strictement positifs.
Pour commencer, il n’y a qu’une sous-matrice principale de taille 3, qui est A elle-même.
On l’obtient avec A I en prenant I = ∅. Ensuite viennent les sous-matrices de taille 2, qui
22 CHAPITRE I. ÉLÉMENTS D’ALGÈBRE LINÉAIRE ET DE CALCUL DIFFÉRENTIEL
Enfin, les sous-matrices de taille 1, qui s’obtiennent en retirant deux lignes et deux co-
lonnes, et qui correspondent aux éléments diagonaux :
AI = 9 , 5 , 1 .
|{z} |{z} |{z}
I ={1,2} I ={1,3} I ={2,3}
13 14 15 16
Pour commencer, il n’y a qu’une sous-matrice principale de taille 4, qui est A elle-même.
Ensuite les sous-matrices de taille 3, qui s’obtiennent en retirant i-ème ligne et i-ème co-
lonne pour i = 1..4 :
06 07 08 01 03 04 01 02 04 01 02 03
A I = 10 11 12, 09 11 12, 05 06 08, 05 06 07 .
14 15 16 13 15 16 13 14 16 09 10 11
| {z } | {z } | {z } | {z }
I ={1} I ={2} I ={3} I ={4}
Ensuite les sous-matrices de taille 2, qui s’obtiennent en retirant une paire de lignes/colonnes
à A. On peut également les obtenir en retirant UNE ligne/colonne aux sous-matrices prin-
cipales de taille 3 :
11 12 06 08 06 07 01 04 01 03 01 02
AI = , , , , , .
15 16 14 16 10 11 13 16 09 11 05 06
| {z } | {z } | {z } | {z } | {z } | {z }
I ={1,2} I ={1,3} I ={1,4} I ={2,3} I ={2,4} I ={3,4}
I.II.1 Différentielle
Définition I.58 (Différentielle). Soit U ⊂ R N un ouvert et F : U → R M une application.
Soit x ∈ U. On dit que F est DIFF ÉRENTIABLE au point x s’il existe une application linéaire
u ∈ L(R N ; R M ) telle que pour tout h ∈ R N t.q. x + h ∈ U,
F ( x + h) = F ( x ) + u(h) + o (khk).
Lorsque u existe, elle est unique ; on la note u = DF ( x ).
Si l’application x 7→ DF ( x ) est définie sur tout U, et y est continue, on dit alors que F est
de classe C1 sur U et on note F ∈ C1 (U ).
Remarque I.62 (Vecteur Gradient). Si f : R N → R1 (on insiste sur le fait que M = 1) est
différentiable en x, alors J f ( x ) ∈ M1,N (R) est un vecteur ligne (et D f ( x ) est une forme
linéaire). Sa transposée est donc identifiable à un vecteur (colonne), que l’on appelle le
GRADIENT de F en x : ∇ f ( x ) = J f ( x ) T .
i) Elle admet des dérivées directionnelles en toute direction au point x (et en particulier, des
dérivées partielles).
ii) Le gradient de f en x s’écrit
∂f
∂x1 ( x )
∇ f (x) = ..
.
∂f
∂x ( x )
N
iii) On a la relation suivante entre différentielle, gradient, dérivée directionnelle et dérivée partielle :
N
∂f ∂f
(∀d ∈ R N ) D f ( x )(d) = ( x ) = h∇ f ( x ), di = ∑ ( x ) di .
∂d i =1
∂xi
où w ∈ R N est un certain vecteur fixé. Alors, on peut affirmer que f est différentiable en
u, et que
w = ∇ f ( u ).
D ( F + G )( x ) = DF ( x ) + DG ( x ) et J ( F + G )( x ) = JF ( x ) + JG ( x ).
D ( F ◦ G )( x ) = DF ( G ( x )) ◦ DG ( x ) et J ( F ◦ G )( x ) = JF ( G ( x )) JG ( x ) .
| {z } | {z } | {z }
∈M P,N (R) ∈M P,M (R) ∈M M,N (R)
∇( f ◦ G )( x ) = JG ( x )> ∇ f ( G ( x )) .
| {z } | {z } | {z }
∈R N ∈M N,M (R) ∈R M
On termine avec un résultat qui n’est pas central dans ce cours, mais que l’on utilisera
par la suite dans les preuves :
26 CHAPITRE I. ÉLÉMENTS D’ALGÈBRE LINÉAIRE ET DE CALCUL DIFFÉRENTIEL
1
(∀h ∈ U − x ) F ( x + h) = F ( x ) + DF ( x )(h) + b(h, h) + o (khk2 ).
2
Dans ce cas b est uniquement définie, et c’est la différentielle seconde de F en x, notée
D2 F ( x ). Si l’application x 7→ D2 F ( x ) existe et est continue sur U, on note F ∈ C2 (U ).
D2 ( F + G )( x ) = D2 F ( x ) + D2 G ( x ).
I.II. RAPPELS ET COMPLÉMENTS DE CALCUL DIFFÉRENTIEL 27
f ( x ) = h Ax, x i + hb, x i + c,
où A ∈ M N (R), b ∈ R N et c ∈ R.
28 CHAPITRE I. ÉLÉMENTS D’ALGÈBRE LINÉAIRE ET DE CALCUL DIFFÉRENTIEL
Remarque I.89. Les fonctions quadratiques sont des polynômes de degré 2 en les va-
riables x1 , . . . , x N . En effet, en notant aij et bi les coefficients de A et b, on peut écrire
N N N
f (x) = ∑ ∑ aij x j xi + ∑ bi xi + c.
i =1 j =1 i =1
Exemple I.90. Les fonctions quadratiques de R dans R sont exactement les fonctions
du second degré abondamment étudiées au lycée : f ( x ) = ax2 + bx + c.
Exemple I.92. f ( x, y) = 2x2 + y2 − xy2 + 3x − 2 n’est pas une fonction quadratique sur
R2 car c’est un polynôme de degré 3.
Proposition I.93. Soit f ( x ) = h Ax, x i + hb, x i + c une fonction quadratique sur R N . Alors
∇ f ( x ) = ( A + A> ) x + b et ∇2 f ( x ) = A + A > .
f ( x ) = k Ax − yk2 .
Montrer que f est une fonction quadratique, et calculer son gradient et sa Hessienne.
Chapitre II
F IGURE II.1 – La nature agit toujours par les voies les plus courtes , Pierre de Fermat (1657).
Lorsqu’il arrive quelque changement dans la Nature, la quantité d’action, nécessaire pour ce
changement, est la plus petite qu’il soit possible , Pierre de Maupertuis (1756).
( PC ) inf f ( x )
x ∈C
29
30 CHAPITRE II. EXISTENCE DE MINIMISEURS ET CONDITIONS D’OPTIMALITÉ
• L’INFIMUM de f , noté infC f , est défini par infC f := inf{ f ( x ) | x ∈ C } ∈ [−∞, +∞[.
• Lorsque infC f 6= −∞, on dit que f est MINOR ÉE sur C.
• On dit que x̄ ∈ C est un MINIMISEUR de f sur C, si f ( x̄ ) = infC f . Autrement dit, si
(∀ x ∈ C ) f ( x̄ ) ď f ( x ).
argminC f = { x̄ ∈ C | f ( x̄ ) = inf f }.
C
Lorsqu’on sait qu’il existe un minimiseur, on dit que l’infimum est atteint, et au lieu
d’infimum on parle en général plutôt de MINIMUM, que l’on note minC f .
Enfin, lorsque C = R N , on omet de le mentionner, et on parlera simplement d’infimum
(inf f ), minimum (min f ), minimiseur (argmin f ).
• Il arrive parfois que l’on parle de minimum, ou de minC f , sans savoir s’il existe un
minimiseur. C’est un léger abus, qu’on essaiera d’éviter dans ce cours, mais que vous
allez très certainement rencontrer ailleurs.
• Il y a une ambiguı̈té beaucoup plus problématique concernant le terme minimum, dont
le sens est souvent confondu avec celui de minimiseur. Martelons donc ici que :
◦ le minimum désigne la plus petite valeur que peut prendre une fonction,
◦ minimiseur désigne un point en lequel la fonction atteint son minimum.
Encore une fois, on essaiera dans ce cours de bien faire la différence entre les deux, et il
est probable que vous trouviez une utilisation différente de ces termes dans des livres.
• Au lieu de minimiseur, on emploiera parfois le terme de minimiseur GLOBAL, par op-
position avec la Définition II.5 à venir. Les deux termes sont légitimes, on utilisera l’un
ou l’autre en fonction du contexte.
Exemple II.3. Voici quelques exemples typiques, que je vous conseille de toujours gar-
der en tête lorsque vous vous posez des questions sur les minimiseurs/minimum d’une
fonction. Faites un dessin pour vous convaincre !
Exercice II.4 (Existence de minimiseurs). Les fonctions suivantes atteignent-elles leur mi-
nimum ?
1) f ( x ) = exp(− x ) sur C = R+ , puis C = R− .
2) f ( x ) = cos(exp( x2 )) sur C = [0, 1].
3) f ( x ) = −k x k2 sur la boule fermée C = B(0, 1).
4) f ( x, y) = x6 cos y + 2y2 sur C = R2 .
Les notions introduites dans la Définition II.1 peuvent être déclinées localement :
Remarque II.6. On peut reformuler la Définition II.5 ainsi : x̄ est un minimiseur local de f
sur C si il existe un voisinage U de x̄ tel que x̄ soit un minimiseur (global) de f sur C ∩ U.
De manière plus générale, toutes les notions et propriétés que l’on va voir par la suite
porteront sur les problèmes de minimisation, et de recherche de minimiseurs, mais s’adap-
teront très facilement aux maximiseurs : il suffira de remplacer f par − f dans les énoncés.
32 CHAPITRE II. EXISTENCE DE MINIMISEURS ET CONDITIONS D’OPTIMALITÉ
Théorème II.9.
On suppose que f est différentiable en un minimiseur local x̄. Alors ∇ f ( x̄ ) = 0.
Dans le cas où on est en présence d’une contrainte, et que le point que l’on considère
est à l’intérieur de la contrainte, on obtient le même résultat :
∇ f ( x̄ ) = 0.
Remarque II.11. Le Théorème II.10 est encore vrai si on remplace minimiseur local par
maximiseur local . Pour s’en convaincre, il suffit de remplacer f par − f dans l’énoncé.
f ( x̄ + td) − f ( x̄ )
h∇ f ( x̄ ), di = lim ě 0,
t →0 t
où l’inégalité vient du fait que, lorsque kdk|t| < R, on a x̄ + td ∈ B( x̄; R) ⊂ C et donc on
peut utiliser (II.1). On a donc montré que
(∀d ∈ R N ) h∇ f ( x̄ ), di ě 0,
Remarque II.12. Le résultat n’est plus valide lorsque x̄ n’est pas à l’intérieur de la contrainte.
Un contre-exemple simple est f ( x ) = x2 , avec C = [1, 2]. Dans ce cas x̄ = 1 est un minimi-
seur global sur C, mais f 0 ( x ) = 2 6= 0.
Définition II.14. Un point x où f est différentiable et ∇ f ( x ) = 0 est appelé POINT CRI -
TIQUE ( DU PREMIER ORDRE ). On note crit( f ) l’ensemble des points critiques de f .
II.I. CONDITIONS D’OPTIMALITÉ ET PRINCIPE DE FERMAT 33
∃( xn+ )n∈N , ( xn− )n∈N t.q. lim xn+ = lim xn− = x et f ( xn− ) < f ( x ) < f ( xn+ ).
n→+∞ n→+∞
Un tel point est appelé un point selle. Voir la Remarque II.13 pour des exemples de points
selle.
Définition II.17. Un point x où f est deux fois différentiable et tel que ∇ f ( x ) = 0 et
∇2 f ( x ) 0 est un POINT CRITIQUE DU DEUXI ÈME ORDRE.
Démonstration. Avant de commencer, on note B( x̄, R) le voisinage sur lequel x̄ est un mi-
nimiseur local. Quitte à prendre R plus petit, on peut supposer que B( x̄, R) ⊂ C, puisque
x̄ ∈ int C. On sait d’après le Théorème II.10 que ∇ f ( x̄ ) = 0, on ne doit donc vérifier ici
que ∇2 f ( x̄ ) 0. Nous allons raisonner par l’absurde, et supposer qu’il existe d ∈ R N tel
que
h∇2 f ( x̄ )d, di < 0.
Quitte a diviser cette inégalité par kdk, on peut supposer que kdk = 1. Dans la suite, on
notera λ := h∇2 f ( x̄ )d, di < 0.
D’après la formule de Taylor (Proposition I.78 avec h = td), et le fait que ∇ f ( x̄ ) = 0,
on peut écrire, pour tout t > 0 :
1
f ( x̄ + td) − f ( x̄ ) = h∇ f ( x̄ ), tdi + h∇2 f ( x̄ )td, tdi + o (ktdk2 )
2
1 2
= h∇ f ( x̄ )d, dit2 + o (t2 )
2
λ 2
= t + t2 ε ( t ),
2
34 CHAPITRE II. EXISTENCE DE MINIMISEURS ET CONDITIONS D’OPTIMALITÉ
où ε(s) est une fonction telle que lims→0 ε(s) = 0. Maintenant, on se donne t̄ < R tel que
ε(t̄) ď −λ/4. On en déduit :
On a donc trouvé x := x̄ + t̄d ∈ C ∩ B( x̄, R) tel que f ( x ) < f ( x̄ ), ce qui est une contradic-
tion avec le fait que x̄ soit un minimiseur local.
Exemple II.18 (Réciproque). Le Théorème II.16 dit que si x̄ est un minimiseur local alors
c’est un point critique du deuxième ordre. Est-ce que la réciproque est vraie ?
• Si on prend le cas d’une fonction quadratique (cf. Exemple II.22), on a pour tout x ∈
R N que ∇2 f ( x ) = A et ∇ f ( x ) = Ax. Donc tout point critique du second ordre est un
minimiseur global. Dans ce cas la réciproque est vraie.
• Si f ( x ) = x3 , ou − x4 , en zéro on a f 0 (0) = f 00 (0) = 0 (c’est donc un point critique
du deuxième ordre, au sens de la Définition II.17), mais pour autant 0 n’est pas un
minimiseur local.
En général il est impossible, sans faire plus d’hypothèses, de caractériser entièrement les
minimiseurs locaux avec des conditions faisant intervenir les dérivées supérieures. Mais
il est possible de faire une hypothèse un peu plus forte, qui implique qu’un point est un
minimiseur local. En gros, il faut regarder la dérivée seconde autour de x pour savoir si la
fonction est localement convexe.
∇ f ( x̄ ) = 0 et ∇2 f ( x̄ ) 0.
Démonstration.
Soit λ = λmin (∇2 f ( x̄ )) > 0. D’après la formule de Taylor (Proposition I.78) (sachant que
∇ f ( x̄ ) = 0), il existe une fonction ε : R → R t.q. lims→0 ε(s) = 0 et
1 2
(∀d ∈ R N ) f ( x̄ + d) − f ( x̄ ) = h∇ f ( x̄ )d, di + kdk2 ε(kdk)
2
λ
ě kdk2 + kdk2 ε(kdk).
2
Par définition de ε, il existe un R > 0 tel que pour tout s ∈]0, R[, |ε(s)| ď λ/2. Si on prend
x ∈ B( x̄; R) quelconque, on a x = x̄ + d avec d = x − x̄ et kdk ď R, donc on déduit de ce
qui précède que ε(kdk) ě −λ/2, et donc que f ( x ) − f ( x̄ ) ě 0. Ceci prouve que x̄ est un
minimiseur local de f .
II.I. CONDITIONS D’OPTIMALITÉ ET PRINCIPE DE FERMAT 35
Remarque II.20 (Minimiseur local vs. global). Supposons que l’on ait trouvé un point x̄
satisfaisant aux conditions suffisantes d’optimalité du 2e ordre : le Théorème II.19 nous
garantit que x̄ est un minimiseur local. Comment savoir s’il n’est que local, ou en fait
global ?
Une bonne approche consiste à calculer f ( x̄ ), et à se demander si c’est le minimum de
f . Il y a alors deux possibilités :
Exercice II.22 (Fonction quadratique et minimiseurs). Soit f ( x ) = 21 h Ax, x i, où A est une
matrice symétrique. Montrer que f admet un minimiseur en 0 si et seulement si A 0.
Est-ce que dans ce cas le minimiseur est unique ?
Exercice II.23 (Points critiques, extrema locaux et globaux). Pour les fonctions suivantes,
trouver leurs points critiques et dire si ce sont des extrema locaux (ou globaux) :
1) f ( x, y) = x3 + y4
2) f ( x ) = (1 − x2 )2
3) f ( x, y) = x2 + y2 − xy2
4) f ( x ) = ln(1 + cos x )
Les théorèmes II.16 et II.19 nous fournissent des conditions d’optimalité vis-à-vis des
minimiseurs locaux de f . On en déduit immédiatement le corollaire suivant, qui porte sur
les maximiseurs locaux et les points selle :
Corollaire II.24 (CNO et CSO du 2e ordre - Maximiseurs et points selle). Soit f une fonction
deux fois différentiable en x̄ ∈ int C.
2e ordre, donc n’est pas un minimiseur local d’après II.16. De même, si ∇2 f ( x̄ ) n’est pas
semi-définie négative alors x̄ n’est pas un minimiseur local d’après le point 2). C’est donc
un point selle.
lim f ( x ) = +∞,
k x k→∞
x ∈C
Exemple II.27. f ( x ) = e x n’est pas coercive. Par contre elle est coercive sur [0, +∞[.
Exemple II.28. f ( x, y) = x2 n’est pas coercive, car elle est constante lorsque on fixe x.
Exercice II.29 (Coercivité). Dire à propos des fonctions suivantes si elles sont coercives.
1) f ( x ) = (1 − x2 )2 .
2) f ( x, y) = x3 + 2y2 .
3) f ( x, y) = ( x − y)2 .
x2
4) f ( x, y) = y définie sur R×]0, +∞[.
II.II. COERCIVITÉ ET EXISTENCE DE MINIMISEURS 37
• Votre fonction est une fonction univariée f : R −→ R. Dans ce cas c’est facile, car la
coercivité est équivalente à
◦ lim k xn k = +∞,
◦ lim f ( xn ) 6= +∞.
• Votre fonction est multivariée, et vous pensez qu’elle est coercive. C’est un cas un peu
plus difficile, puisqu’il faut montrer que lim f ( xn ) = +∞ pour toute suite divergente.
Il serait tentant de penser que la coercivité équivaut à fixer toutes les variables sauf
une que l’on fait tendre vers ±∞ :
L’exercice suivant est important, et il est bon de connaitre et comprendre les résultats
qu’il contient :
On conclut cette partie avec une proposition importante, qui dit qu’une fonction est
toujours coercive sur un borné.
Démonstration. C’est en fait une conséquence directe de la Définition II.25, et du fait qu’une
implication A ⇒ B est toujours vraie lorsque la proposition A est fausse. En effet, si C est
bornée, il est impossible pour une suite ( xn )n∈N ⊂ C de vérifier lim k xn k = +∞.
n→+∞
Le lien entre coercivité et borné n’est d’ailleurs pas anodin ! En effet, la Proposi-
tion suivante montre que la coercivité d’une fonction f peut entièrement être caractérisée
par le fait que ses sous-niveaux soient bornés.
[ f ď r ] : = { x ∈ U | f ( x ) ď r }.
a) C est fermé,
b) f est continue en tout point de C,
c) f est coercive sur C.
Alors f admet un minimiseur global sur C.
Pour prouver ce résultat on aura besoin d’un Lemme élémentaire sur l’existence de
suites minimisantes :
Exercice II.38. Montrer que si on enlève la moindre des trois hypothèses du Théorème
II.35, alors la conclusion n’est plus vraie.
Le Théorème II.35 est une version plus générale de ce résultat que vous connaissez
déjà certainement :
Un second exercice important sur les fonctions quadratiques, qui montre que les moindres
carrés kΦx − yk2 admettent toujours un minimiseur global :
minimiserx∈C f ( x ).
si f convexe
minimiseur global
Optimisation convexe
Autrement dit, il faut et il suffit que pour toute paire de points x, y dans C, l’intervalle
[ x, y] qui relie ces points soit également contenu dans C (cf. Figure III.1).
43
44 CHAPITRE III. OPTIMISATION CONVEXE
Exercice III.6. Montrer que l’intersection de deux ensembles convexes est encore convexe.
En déduire que l’intersection d’un nombre fini d’ensemble convexes est convexe.
1) f est convexe,
2) l’épigraphe2 de f est convexe, ce dernier étant défini par :
epi f = {( x, y) ∈ R N × R | f ( x ) ď y} ⊂ R N × R.
est assez difficile de retrouver d’où vient la notation Γ0 . Néanmoins il semblerait que cela remonte
1 Il
aux premiers travaux de Fenchel (1951) et Moreau (1965), dans lesquels Γ0 décrit l’ensemble des fonctions
convexes semi-continues inférieurement et propres (pas constantes à l’infini). Le choix d’utiliser la lettre Γ
semblerait être en dualité avec la lettre C (pour convexe), Γ étant également la troisième lettre de l’alphabet
grec. Quand à l’indice 0 son sens s’est perdu mais dans ce cours on va lui donner un signification (cf. Section
sur les focntions fortmeent convexes). Une discussion intéressante à ce sujet ici https://mathoverflow.
net/questions/262851/why-are-gamma-0-functions-called-this/262861
2 epi est un préfixe qui veut dire au-dessus . C’est l’opposé de hypo qui nous est plus familier.
III.I. CONVEXITÉ ET GLOBALITÉ DES MINIMISEURS 45
epiC f = {( x, y) ∈ R N × R | x ∈ C, f ( x ) ď y} ⊂ R N × R.
Proposition III.11. Soit f : R M → R une fonction convexe, et A ∈ M N,M (R). Alors f ◦ A est
convexe.
La relation ii) signifie géométriquement que le graphe de f est au-dessus de son hyperplan
tangent en tout point (cf. Figure III.3).
f (y) ě f ( x ) + f 0 ( x )(y − x )
f ( x ) ě f (y) + f 0 (y)( x − y).
(∀ x, y ∈ C ) la fonction gx,y : t ∈ [0, 1] 7→ f ((1 − t) x + ty) est convexe sur [0, 1].
Démonstration.
⇒ Soient x, y ∈ C, et montrons que gx,y est convexe sur [0, 1]. Pour cela, on se donne
t1 , t2 ∈ [0, 1], α ∈ [0, 1], et on va montrer que
g((1 − α)t1 + αt2 ) = f ([1 − (1 − α)t1 − αt2 ] x + [(1 − α)t1 + αt2 ]y)
= f ((1 − α)[(1 − t1 ) x + t1 y] + α[(1 − t2 ) x + t2 y])
(∀ x, y ∈ C ) f (y) ě f ( x ) + h∇ f ( x ), y − x i. (III.3)
III.I. CONVEXITÉ ET GLOBALITÉ DES MINIMISEURS 49
f (y) ě f ( x ) + h∇ f ( x ), y − x i.
⇐ : Supposons (III.3) et prouvons que f est convexe. Via le Lemme III.17, il suffit donc de
fixer x, y ∈ C et de montrer que g := gx,y : [0, 1] → R est convexe sur [0, 1]. Donc, via la
Proposition III.13, il suffit de montrer que
Or cette inégalité est exactement ce que l’on obtient lorsque dans (III.3) on remplace y par
(1 − b) x + by et x par (1 − a) x + ay.
i) (∀ x ∈ C ) ∇2 f ( x ) 0 ;
ii) f est convexe sur C, c-à-d f ∈ Γ0 (C ).
Démonstration.
i) ⇒ ii). Afin de montrer que f est convexe sur C, nous allons montrer que gx,y est convexe
pour tout x, y ∈ C, puis conclure avec le Lemme III.17 précédent. D’après le Théorème
III.16, il nous suffit de montrer que g00x,y est positive, où
Or notre hypothèse, combinée avec (III.4), et le fait que C est convexe, impliquent que c’est
bien le cas.
ii) ⇒ i). Soit x ∈ C. Afin de montrer que ∇2 f ( x ) 0, on va prendre d ∈ R N quelconque,
et montrer que h∇2 f ( x )d, di ě 0. Puisque C est ouvert, il existe δ > 0 tel que B( x, δ) ⊂ C.
Donc y := x + εd appartient à C pour 0 < ε < δ/2kdk. On peut donc faire appel à la
50 CHAPITRE III. OPTIMISATION CONVEXE
fonction gx,y qui est convexe sur [0, 1] d’après le Lemme III.17. De plus sa dérivée seconde
est bien définie sur [0, 1] (et donnée par (III.4)) puisque x, y ∈ C ⊂ U ouvert. En particulier,
on peut utiliser le Théorème III.16, et en regardant g00 (0), on voit que
h∇2 f ( x )(y − x ), y − x i ě 0.
Remarque III.20 (Cas N = 1). Pour N = 1, on retrouve le critère usuel : f est convexe
ssi f 00 est positive .
Remarque III.21 (Positivité d’une famille de matrices). Pour une fonction multivariée,
vérifier en pratique si une fonction est convexe revient à vérifier que la matrice Hessienne
est semi-définie positive. Il est donc pour cela important d’être capable de déterminer
aisément si une matrice symétrique est semi-définie positive ou non (cf. Chapitre I). Il
également important de souligner qu’il faut vérifier la positivité d’une famille de matrices,
à savoir
{∇2 f ( x ) : x ∈ C }.
Dans le cas où C est ouvert, si une seule de ces Hessiennes échoue à être semi-définie
positive, alors la fonction ne sera pas convexe.
Remarque III.22 (Convexité sur une contrainte non ouverte). Si f ∈ Γ0 (C ), que peut-on
dire de ∇2 f ( x ) pour x ∈ C ?
• Lorsque C est ouvert, le Théorème III.19 nous garantit que ∇2 f ( x ) 0.
• Lorsque int C 6= ∅ et f ∈ C2 (U ), alors on peut également conclure que ∇2 f ( x ) 0.
En effet on sait que la Hessienne est semi-définie positive sur int C, en appliquant le
Théorème III.19 à int C, qui est ouvert. De plus, on suppose que ∇2 f est continue, donc
les valeurs propres de ∇2 f ( x ) sont continues en x. Puisque C ⊂ int C, on déduit en
passant à la limite que la Hessienne est également semi-définie positive sur le bord de
C.
• Lorsque int C = ∅ on ne peut pas se prononcer. En effet sur un C d’intérieur vide on
est aveugle par rapport à ce que fait f en dehors de C, ce qui empêche de décrire
le comportement de la Hessienne dans les directions qui pointent vers l’extérieur.
On peut par exemple considérer le contre-exemple de la fonction f ( x ) = x3 qui est
convexe (car constante !) sur C = {−1}, alors que f 00 ( x ) = −6 < 0 sur C. Si on veut un
exemple avec une contrainte qui ne soit pas un singleton, on peut également considérer
f ( x, y) = x3 qui est convexe sur C = {( x, y) ∈ R2 | x = −1}. On reverra ce genre de
problème lorsqu’on étudiera en détail les problèmes d’optimisation sous contraintes
dans le Chapitre V (voir en particulier la Remarque V.46).
Démonstration. Soit R > 0 tel que x̄ soit un minimiseur de f sur C ∩ B( x̄, R). Soit x ∈ C
quelconque, et montrons que f ( x̄ ) ď f ( x ). Pour simplifier on suppose x 6= x̄. Posons
d = x − x̄. Alors x̄ + td ∈ B( x̄, R), pourvu que 0 < tkdk < R, et donc f ( x̄ ) ď f ( x̄ + td).
Or on peut écrire x̄ + td = (1 − t) x̄ + tx, donc par convexité on a :
f ( x̄ ) ď f ( x̄ + td) ď (1 − t) f ( x̄ ) + t f ( x ),
Une seconde propriété très importante des fonctions convexes est que tout point cri-
tique du premier ordre est un minimiseur global. Lorsque la fonction est deux fois diffé-
rentiable, c’est une conséquence directe du Théorème II.19 et Proposition III.19.i). En fait,
cela reste vrai même si la fonction n’est pas deux fois différentiable.
Remarque III.26 (Gare au bord de la contrainte !). Comme on l’a dit précédemment, la
réciproque est fausse en général lorsque x̄ appartient au bord de la contrainte C. On verra
au chapitre V ce qu’il se passe dans ce cas.
Il faut également noter qu’il existe aussi un résultat analogue lorsque la fonction n’est pas
différentiable en x̄, mais c’est hors programme (cf. Cours du Master MIDS).
Démonstration. Comme x̄ ∈ int C, il existe R > 0 tel que B( x̄, R) ⊂ C. Pour tout x ∈
B( x̄, R), on peut écrire d’après la Proposition III.18 :
0 ď f ( x ) − f ( x̄ ) − h∇ f ( x̄ ), x − x̄ i = f ( x ) − f ( x̄ ).
52 CHAPITRE III. OPTIMISATION CONVEXE
Ceci montre donc que x̄ est un minimiseur local de f sur C. On conclut alors avec le
Théorème III.24.
µ
∀α ∈ [0, 1], ∀( x, y) ∈ C2 , f ((1 − α) x + αy) + α(1 − α)k x − yk2 ď (1 − α) f ( x ) + α f (y).
2
Dans ce cas on dit aussi que f est µ-convexe sur C, et que µ est le coefficient de forte
convexité de f sur C. On notera Γµ (C ) l’ensemble des fonctions fortement convexes sur C.
Autrement dit, toute fonction fortement convexe est la somme d’une fonction convexe et d’une
norme au carré.
f ∈ Γµ (C )
µ
⇔ ∀α ∀ x, y, f (zα ) + α(1 − α)k x − yk2 ď (1 − α) f ( x ) + α f (y)
2
µ µ
⇔ ∀α ∀ x, y, g(zα ) + kzα k2 + α(1 − α)k x − yk2
2 2
µ µ
ď (1 − α) g( x ) + αg(y) + (1 − α) k x k2 + α kyk2 .
2 2
III.II. FORTE CONVEXITÉ : EXISTENCE ET UNICITÉ DU MINIMISEUR 53
− (1 − α)k x |2 − αkyk2
2 2 2 2
= k x k (1 − α ) + α (1 − α ) − (1 − α ) + k y k α + α (1 − α ) − α
= 0.
Donc tous les termes en µ disparaissent, et ce qui reste est exactement la définition pour g
d’être convexe.
Proposition III.31. La somme d’une fonction fortement convexe et d’une fonction convexe est
fortement convexe.
Proposition III.32. La composition d’une fonction fortement convexe avec une application affine
injective est fortement convexe.
Remarque III.34. La forte convexité requiert donc une borne inférieure uniforme sur les
valeurs propres de la Hessienne. Au contraire de la stricte convexité qui n’a besoin que de
la définie positivité en ( presque ) tout point. Il est essentiel ici de bien faire la distinction
entre la caractérisation de la forte convexité :
(∃µ > 0)(∀ x ∈ C ) λmin (∇2 f ( x )) ě µ,
et la propriété beaucoup plus faible :
(∀ x ∈ C )(∃µ > 0) λmin (∇2 f ( x )) ě µ,
54 CHAPITRE III. OPTIMISATION CONVEXE
Exemple III.35. f ( x ) = e x est strictement convexe mais n’est pas fortement convexe. On
le voit par exemple en notant que f n’est pas coercive, ou bien que f 00 tend vers 0 en −∞.
Démonstration. cf. TD
Corollaire III.38. Soit f : U → R une fonction continue et fortement convexe sur C ⊂ U fermé.
Alors f admet un unique minimiseur global sur C.
Démonstration. D’après le Théorème III.37 f est coercive, donc on peut appliquer le Théorème
II.35 et déduire l’existence d’un minimiseur. L’unicité va également découler de la forte
3 Lerésultat reste vrai sans cette hypothèse ! Mais pour le pouver on aurait besoin d’autres outils. Au
choix : Montrer que les fonctions convexes sont localement Lipschitziennes, et donc différentiables presque
partout (Théorème de Rademacher) ; Utiliser le Théorème de Hahn-Banach pour séparer l’épigraphe d’un
point quelconque sous l’épigraphe, et en déduire l’existence d’une minorante affine ; Projeter ce point sur
l’épigraphe et utiliser la caractérisation variationnelle de la projection (cf. dernier chapitre).
III.II. FORTE CONVEXITÉ : EXISTENCE ET UNICITÉ DU MINIMISEUR 55
convexité. En effet, s’il existait deux minimiseurs x1∗ , x2∗ , on aurait via la Définition III.28
que
1 1 x ∗ + x2∗ µ
f ( x1∗ ) + f ( x2∗ ) ě f ( 1 ) + k x1∗ − x2∗ k2 ,
2 2 2 8
x1∗ + x2∗
où 12 f ( x1∗ ) + 12 f ( x2∗ ) = minC f par définition de x1∗ , x2∗ , et f ( 2 ) ě minC f . Ceci implique
donc que 8 k x1∗ − x2∗ k2 ď 0, c-à-d que x1∗ = x2∗ .
µ
56 CHAPITRE III. OPTIMISATION CONVEXE
minimiserx∈C f ( x ).
Utiliser la Hessienne
(∀ x ∈ C ) λmin (∇2 f ( x )) ě 0.
Dans tout ce chapitre, nous allons considérer une fonction différentiable f : R N → R, que
l’on supposera convexe sauf mention du contraire. Rappelons dans ce cas (cf. Théorème
III.25) que tout minimiseur x̄ ∈ argmin f est caractérisé par
∇ f ( x̄ ) = 0.
Cependant, en général, il n’est pas possible de déterminer une formule explicite pour x̄
à partir de ∇ f ( x̄ ) = 0, car ces équations peuvent être non linéaires. C’est pourquoi en
pratique on est amené à chercher une valeur approchée de x̄. C’est tout l’objet de ce cha-
pitre que de présenter une classe de méthodes classiques pour obtenir de telles solutions
approchées : les algorithmes itératifs.
57
58 CHAPITRE IV. ALGORITHMES DE MINIMISATION SANS CONTRAINTE
Exemple IV.2. Les suites arithmétique xk+1 = xk + r ou géométrique xk+1 = rxk sont
définies par des algorithmes itératifs du premier ordre sur R (ici r ∈ R).
x0 = 0, x1 = 1, x k +1 = x k + x k −1
est générée par un algorithme itératif du deuxième ordre sur R. Par contre elle n’est pas
générée par un algorithme itératif du premier ordre sur R.
Remarque IV.4. Faisons le point, et listons ce que l’on peut espérer d’un tel algorithme
dans le cadre de notre problème d’optimisation :
• Comme on l’a dit, on souhaite que limk xk = x ∗ ∈ argmin f . C’est la convergence des
itérés de la suite vers une solution.
• Au vu de la définition IV.1, et si ρk ne tend pas vers 0, on voit que dk doit tendre vers 0.
Or on souhaite à la limite avoir ∇ f ( x ) = 0. Donc il est raisonnable que dk soit construit
à base d’informations sur les dérivées partielles de f .
• On peut également souhaiter la convergence de la suite des valeurs : limk f ( xk ) = inf f .
De plus, puisque en pratique on va s’arrêter avec k fini, on peut espérer qu’à chaque
itération les valeurs s’améliorent, c’est-à-dire f ( xk+1 ) ď f ( xk ).
• On peut également vouloir en savoir plus sur la convergence, d’un point de vu quanti-
tatif. Par example la VITESSE DE CONVERGENCE des itérés vers une solution, ou des va-
leurs vers inf f , ou de k∇ f ( xk )k vers 0. On distingue généralement trois classes de
vitesses :
Définition IV.5. Soit (rk )k∈N ⊂ [0, +∞[ une suite qui tend vers 0 lorsque k → +∞. On dit
que
C
(∃C ∈ [0, 1[)(∃α ∈]0, +∞[)(∀k ∈ N) rk ď .
kα
Remarque IV.6. La convergence linéaire est parfois appelée convergence G ÉOM ÉTRIQUE,
pour des raisons évidentes. Une suite convergeant linéairement vérifie en particulier que
r k ď θ k r0 ,
Remarque IV.7. La convergence superlinéaire est plus rapide que la convergence linéaire.
Par récurrence, on voit qu’une telle suite vérifie (rappelons que rk → 0)
k i βk
r k ď θ ∑i β r0 .
k
Donc à partir d’un certain rang, la suite tend vers 0 à une vitesse r β ce qui est très rapide !
Pour β = 2 on parle de convergence QUADRATIQUE, c’est en général le mieux que l’on
puisse espérer.
Remarque IV.8. La convergence souslinéaire est moins rapide que la convergence linéaire.
f ( x k +1 ) < f ( x k ) ?
f ( x + td) − f ( x )
lim = h∇ f ( x ), di < 0.
t →0 t
Donc, d’après la définition de la limite, il existe ρ > 0 tel que pour tout |t| < ρ,
f ( x + td) − f ( x )
< βh∇ f ( x ), di.
t
Cette proposition suggère donc que les directions de descente sont des candidates de
directions dk à suivre dans notre algorithme IV.1, puisqu’elle permettent de faire décroitre
les valeurs de la fonction, pourvu que le pas choisi soit suffisamment petit.
La plupart des résultats concernant les directions de descente que l’on vient de voir
peuvent s’interpréter de manière géométrique. On peut donc s’aider d’un dessin pour
comprendre de quoi il s’agit.
Considérons une fonction f : R N → R différentiable, et x ∈ R N . On peut alors définir
son ENSEMBLE DE NIVEAU en f ( x )
[ f = f ( x )] := { x 0 ∈ R N | f ( x 0 ) = f ( x )}.
[ f ď f ( x )] := { x 0 ∈ R N | f ( x 0 ) ď f ( x )}.
On a alors le résultat suivant (énoncé informellement, voir le prochain Chapitre pour plus
de détails) :
IV.I. MÉTHODES DE DESCENTE 61
F IGURE IV.1 – Le gradient est normal aux ensembles de sous-niveau et pointe vers
l’extérieur.
xk+1 = xk − ρk ∇ f ( xk ), ρk > 0.
On pourrait se demander si cette méthode est bonne, et si l’on peut trouver mieux. Par
exemple, on a vu dans la Proposition IV.12.i) que plus la dérivée directionnelle h∇ f ( x ), di
est négative, et plus on pourra faire décroitre les valeurs de la fonction dans cette direction.
Il est donc naturel de chercher la direction d qui minimise la dérivée directionnelle en x.
On peut en fait montrer que c’est exactement −∇ f ( x ), ce qui explique qu’on dise parfois
que −∇ f ( x ) est la DIRECTION DE LA PLUS GRANDE PENTE :
1
x − ∇2 f ( x )−1 ∇ f ( x ) = argmin f ( x ) + h∇ f ( x ), x 0 − x i + h∇2 f ( x )( x 0 − x ), ( x 0 − x )i.
x 0 ∈R N
2
Démonstration. On est en train de minimiser la fonction (prendre garde au fait que x est
une constante ici !)
1
φ( x 0 ) := f ( x ) + h∇ f ( x ), x 0 − x i + h∇2 f ( x )( x 0 − x ), ( x 0 − x )i.
2
On voit que c’est une fonction quadratique, telle que
∇φ( x 0 ) = ∇ f ( x ) + ∇2 f ( x )( x 0 − x ) et ∇2 φ ( x 0 ) = ∇2 f ( x ).
Par hypothèse ∇2 f ( x ) est définie positive donc φ est fortement convexe (voir Proposi-
tion III.36). Donc elle admet un unique minimiseur (voir Théorème III.38) que l’on notera
x + . Par convexité de φ, ce minimiseur x + est caractérisé par la condition d’optimalité du
premier ordre ∇φ( x + ) = 0, qui devient ici
∇2 f ( x )( x + − x ) + ∇ f ( x ) = 0.
On peut donc définir une nouvelle méthode de descente :
x k +1 = x k − ∇ 2 f ( x k ) −1 ∇ f ( x k ).
• Beaucoup de méthodes très efficaces son définies en remplaçant ∇2 f ( xk )−1 par une
matrice Hk qui est une approximation facile à calculer de ∇2 f ( xk )−1 . Cette famille de
méthodes s’appelle les méthodes de Quasi-Newton (voir exercice IV.21).
• On n’étudiera pas cet algorithme, dont l’analyse est compliquées. Plus de détails en M1
dans l’UE Optimisation (OP8). On peut néanmoins citer (cf. TP) que 1) l’algorithme
est très sensible aux conditions initiales (choix de x0 ) et que 2) quand l’algorithme
fonctionne, il converge très vite (plus précisément : superlinéairement).
Pour conclure, il est intéressant de noter que la méthode du gradient, tout comme la
méthode de Newton, peut se voir comme la minimisation d’une approximation quadra-
tique de f . Mais ici on parle d’une approximation quadratique qui ignore l’information du
second ordre de f :
Remarque IV.24. On notera Lip( F ) la meilleure (la plus petite) constante de Lipschitz
possible pour F. Elle se définit comme :
k F ( x ) − F (y)k
Lip( F ) := sup ∈ [0, +∞].
x 6 = y ∈R N
k x − yk
IV.II. CONDITIONNEMENT 65
On voit alors immédiatement que F est Lipschitzienne si et seulement si Lip( F ) < +∞, ce
qui implique en particulier que F est Lip( F )-Lipschitzienne.
k F ( x )− F (y)k
Le quotient k x−yk qui apparait dans la remarque ci-dessus n’est pas sans rappeler
la définition de la différentielle. Ce n’est pas une simple coı̈ncidence : il se trouve que
pour les fonctions différentiables, la constante de Lipschitz se calcule directement à partir
de la différentielle (plus précisément, à partir de la jacobienne, qui est la matrice de la
différentielle) :
On déduit alors que F est L-Lipschitzienne, ce qui veut dire que Lip( F ) ď L.
Si Lip( F ) = +∞, on a forcément Lip( F ) ě L. Si Lip( F ) < +∞, alors F est Lip( F )-
Lipschitzienne. Si on utilise le fait que (cf. Proposition I.63)
F ( x + td) − F ( x )
DF ( x )(d) = lim ,
t →0 t
k F ( x + td) − F ( x )k
JF ( x ) = DF ( x ) = sup k DF ( x )(d)k = sup lim ď Lip( F ).
kdk=1 kdk=1 t→0 t
On voit donc ici une propriété en quelque sorte duale1 du Théorème III.33 : une borne
uniforme inférieure sur le spectre de la Hessienne équivaut à la forte convexite, tandis
qu’ici on voit qu’une forte uniforme supérieure équivaut à la Lipschitzianité du gradient.
On en déduit d’ailleurs immédiatement que :
Exercice IV.29 (Constante de Lipschitz). Dans cet exercice nous allons calculer (ou esti-
mer) la constante de lipschitz de ∇ f : Rn → Rn , pour certaines fonctions f : Rn → R.
Soient A ∈ Rm×n , et b ∈ Rm .
...
IV.II. CONDITIONNEMENT 67
Remarque IV.31. Le fait que le conditionnement soit un nombre plus grand que 1 vient
de la Proposition IV.28 qui garantit que L ě µ.
1
Exemple IV.32. Soit A une matrice symétrique définie positive, et f ( x ) = 2 h Ax, x i +
hb, x i + c une fonction quadratique. Alors
λmax ( A)
cond( f ) = = cond( A).
λmin ( A)
On retrouve ici la notion de conditionnement d’une matrice cond( A), qui est très impor-
tante en Calcul Matriciel : on sait qu’elle contrôle plusieurs choses comme :
On verra qu’il se passe la même chose pour les fonctions fortement convexes à gradient
Lipschitzien : plus le conditionnement sera proche de 1, et meilleurs seront les résultats.
F IGURE IV.2 – Ensembles de niveau pour une fonction quadratique ayant un conditionne-
ment cond( f ) = 1, 10, 100 (de gauche à droite).
68 CHAPITRE IV. ALGORITHMES DE MINIMISATION SANS CONTRAINTE
On considère ici l’algorithme du gradient où le pas est fixé tout au long de l’algorithme,
c’est à dire
xk+1 = xk − ρ∇ f ( xk ), ρ > 0.
(∀ x ∈ R N ) x + := x − ρ∇ f ( x ),
où x + désigne le point que l’on obtient en appliquant un pas de la méthode du gradient à
x. Observer que la notation est ambigüe par rapport à la valeur de ρ mais on fera attention
à toujours l’utiliser dans un contexte où on sait ce que vaut ρ.
Une question essentielle à propos de cet algorithme est : comment choisir ρ ? On a
vu dans la Proposition IV.12 qu’il fallait que ρ soit suffisamment petit pour garantir que
l’algorithme fait décroitre les valeurs de f . Mais d’un autre coté on imagine bien que si
le pas est trop petit, on va faire des tout petits pas, donc l’algorithme va être lent et peu
efficace. Il faut donc bien analyser ce qui se passe pour pouvoir prendre le meilleur pas
possible.
Lρ
i) f ( x + ) − f ( x ) ď −ρ 1 − 2 k∇ f ( x )k2 .
Remarque IV.35 (Choix du pas fixe et conditionnement). La condition ρ < 2/L nous
garantit que le pas est suffisamment petit pour que la fonction décroisse après un pas de
l’algorithme. Mais il faut garder en tête que cette contrainte correspond en quelque sorte
à un pire des cas : si on prend un pas plus grand, il se peut que quelque part, il y ait
un point où l’on va aller trop loin et faire réaugmenter les valeurs de la fonctions. En
conséquence, cela veut dire aussi que cette condition peut parfois être trop stricte, car il y
a des points où on pourrait prendre un pas plus grand. On le voit très bien sur la Figure
IV.4, où pour une fonction avec cond( f ) = 10, on voit qu’en le point y, le pas ρ < 2/L
ne nous permet pas d’aller très loin. Mais on ne peut pas non plus prendre un pas plus
grand, car en le point x un pas supérieur à 2/L nous ferait sortir du sous-niveau.
70 CHAPITRE IV. ALGORITHMES DE MINIMISATION SANS CONTRAINTE
L
(∀ x, y ∈ R N ) f (y) − f ( x ) ď ky − x k2 + h∇ f ( x ), y − x i. (IV.2)
2
Prenons maintenant y = x + = x − ρ∇ f ( x ) :
+ L 2
f (x ) − f (x) ď ρ − ρ k∇ f ( x )k2 . (IV.3)
2
2
/ crit f garantit k∇ f ( x )k2 > 0, et 0 < ρ <
On conclut en observant que x ∈ L implique que
L 2
2 ρ − ρ < 0.
On a donc vu qu’un pas ρ ∈]0, 2/L[ est nécessaire pour garantir la décroissance de la
fonction le long des itérés de l’algorithme. Mais ceci ne garantit pas la convergence de l’al-
gorithme. Pour cela, on va faire l’hypothèse supplémentaire que la fonction est fortement
convexe.
Théorème IV.37 (Convergence linéaire des itérés (cas fortement convexe)). Soient L ě µ >
0 et f ∈ C2 (R N ) ∩ Γµ (R N ) ∩ CL1,1 (R N ). On note x ∗ = argmin f , et on considère la méthode du
gradient avec un pas constant ρ ∈]0, 2/L[. Alors
Remarque IV.38 (Pas optimal). La meilleure vitesse est atteinte lorsque θ est le plus petit
possible. Au vu de la définition de θ, il est minimal lorsque ρ = 2/(µ + L), auquel cas
L−µ
θ = L+µ (voir aussi Figure IV.III.1). On dit parfois que ce choix de pas est le PAS OPTI -
MAL . Attention à ne pas confondre avec la Section IV.III.2 ! Il est également possible de
L−µ
montrer que cette vitesse linéaire en L+µ est la meilleure que l’on puisse espérer avec la
méthode du gradient (hors programme). L’inconvénient néanmoins de ce choix de pas est
qu’il nécessite la connaissance de µ, ce qui n’est pas toujours le cas en pratique, où L est
beaucoup plus facile à estimer.
Remarque IV.40 (Pas court). Le choix le plus populaire, lorsqu’on ne connait pas µ, est
de prendre ρ = 1/L. Dans ce cas, θ = 1 − µ/L. C’est un choix raisonnable, au sens où
il donne la meilleure contraction qu’on puisse garantir avec cet algorithme, lorsqu’on ne
connait pas µ. En effet, sur ]0, 1/L], θ est décroissant, tandis que 2/(µ + L) est toujours
supérieur à 1/L, mais peut être arbitrairement proche voire égal à 1/L. On parle parfois
de PAS COURT pour désigner ce choix de pas.
Démonstration du Théorème IV.37. Ici on suppose pour simplifier la preuve que f est également
de classe C2 (R N ), bien que ce ne soit pas nécessaire. Une preuve sans cette hypothèse est
disponible dans la Section A.II.1 en Annexe. On cherche donc à montrer que
Pour tout x ∈ R N , on peut calculer JA( x ) = I − ρ∇2 f ( x ), qui est une matrice symétrique,
donc sa norme peut être calculée via ses valeurs propres :
Lip(A) = sup max | spec I − ρ∇2 f ( x ) | = sup max |1 − ρλ|.
2
x ∈R N x ∈R N λ∈spec(∇ f ( x ))
Or on sait via Proposition IV.27 et III.33 que spec(∇2 f ( x )) ⊂ [µ, L]. Donc nécessairement :
(∀λ ∈ spec(∇2 f ( x ))) |1 − ρλ| ď max{|1 − ρµ|, |1 − ρL|},
et on déduit de tout ce qui précède que l’énoncé du Théorème est vrai avec θ := max{|1 −
ρµ|, |1 − ρL|}. Il reste maintenant à étudier θ.
Tout d’abord, c’est un simple exercice (non trivial, faire un dessin aide beaucoup, cf.
Figure IV.III.1) que de vérifier que
(
|1 − ρµ| si ρ ď µ+2 L
max{|1 − ρµ|, |1 − ρL|} =
|ρL − 1| si ρ ě µ+2 L .
D’autre part, puisque 2/(µ + L) ∈ [1/L, 2/L[, on en déduit que 1 − ρµ ∈ [0, 1[ et ρL − 1 ∈
[0, 1[.
Théorème IV.42 (Convergence linéaire des valeurs (cas fortement convexe)). Soient L ě
µ > 0 et f ∈ C2 (R N ) ∩ Γµ (R N ) ∩ CL1,1 (R N ). On considère la méthode du gradient avec un pas
constant ρ ∈]0, 2/L[. Alors ( f ( xk ) − inf f )k∈N converge linéairement, c’est-à-dire :
(∃θ ∈ [0, 1[)(∀k ∈ N) f ( xk+1 ) − inf f ď θ 2 ( f ( xk ) − inf f ).
Plus précisément, on peut montrer que θ est le même que celui défini dans le Théorème IV.37.iii).
74 CHAPITRE IV. ALGORITHMES DE MINIMISATION SANS CONTRAINTE
Démonstration. Admis. Une démonstration est disponible dans l’Annexe (Section A.II.1).
Exemple IV.43. Soit f ( x ) = x2 /2, tel que µ = L = 1. Alors, pour tout x ∈ R et ρ ∈]0, 2[,
on a :
1 1
f ( x + ) = (1 − ρ)2 x2 et f ( x ) = x2 .
2 2
Donc on a ici θ = (1 − ρ). On voit donc que le θ du Théorème est difficilement améliorable.
Remarque IV.45. Il n’y a pas de vitesses pour les itérés dans ce Théorème, car ils peuvent
tendre vers 0 de manière arbitrairement lente. Pour le voir il suffit de considérer des fonc-
tions qui ressemblent à f ( x ) = | x | p pour p → +∞.
IV.42). Il est remarquable que l’algorithme soit capable d’exploiter cette propriété de forte
convexité sans qu’on ait besoin de le lui dire. C’est pour cela qu’on parle d’adaptivité.
F IGURE IV.5 – Convergence lente de la méthode du gradient pour des fonctions qui s’apla-
tissent.
(∀ x ∈ R N ) f ( x+ ) − inf f ď θ 2 ( f ( x ) − inf f ),
1) Pour que cela marche un tant soit peu (c’est-à-dire pour que les valeurs décroissent), la
Proposition IV.34 nous dit qu’il faut prendre ρ < 2/L. Ce qui nécessite de connaitre L,
ce qui n’est pas toujours le cas. Idéalement on voudrait une méthode qui ne requière
aucune connaissance préalable sur la fonction f : c’est-à-dire qu’elle soit adaptive à L.
2) Pour que cela marche bien, il faut prendre le pas optimal ρ = 2/(µ + L), mais ici
encore, µ n’est pas toujours accessible.
3) Même si on avait accès à µ et L, nos résultats de contraction des vitesse est vrai en
tout x ∈ R N . Ce qui veut dire que la contraction que l’on a est un pire des cas ,
au sens où il y a des mauvais x pour lesquels on va avoir une contraction θ, mais rien
n’empêche que pour un autre bon x la contraction soit meilleure.
Cela suggère donc que l’on choisisse ρk en boucle ouverte, c’est-à-dire que le choix de
ρk va être spécifique à xk . Une façon de faire est de carrément choisir parmi tous les pas
possibles celui qui va donner un point xk+1 qui va le plus faire décroitre la fonction :
76 CHAPITRE IV. ALGORITHMES DE MINIMISATION SANS CONTRAINTE
Remarque IV.49. Ne pas confondre cette méthode du gradient à pas optimal avec la
méthode du gradient à pas constant optimal, vu dans la précédente section, où ρ =
2/(µ + L).
Remarque IV.50. C’est ce que l’on appelle une méthode de recherche en ligne : on cherche
le long de l’espace unidimensionel { x − ρ∇ f ( x ) | ρ ∈ R} un bon successeur à x. Il existe
de nombreuses autres méthodes de ce type (voir l’exercice suivant).
Une des propriétés importantes de la méthode du gradient à pas optimal est qu’elle
génère des trajectoires en zig-zag :
(∀k ∈ N) h∇ f ( xk ), ∇ f ( xk+1 )i = 0.
Remarque IV.53. Calculer le pas optimal nécéssite donc de résoudre un problème d’opti-
misation à chaque itération. Pour que ce soit rentable, il faudrait vraiment que l’algorithme
soit très efficace, i.e. qu’il converge très rapidement. C’est donc pour cela qu’on va analy-
ser sa convergence plus bas. De toute façon, en pratique :
IV.III. MÉTHODE DU GRADIENT 77
k∇ f ( xk )k2
ρk = .
k A∇ f ( xk )k2
k∇ f ( xk )k2
ρk = .
hS∇ f ( xk ), ∇ f ( xk )i
Démonstration. On cherche donc à trouver t qui minimise g. Tout d’abord, observons que
g(t) = f ( x − t∇ f (t)) est la composition d’une fonction fortement convexe avec une fonc-
tion affine injective, donc g est fortement convexe. Donc elle admet un unique minimiseur,
qu’on note ρ. Puisque f est une fonction quadratique, la propriété du zig-zag g0 (ρ) = 0
est équivalente à :
et la conclusion suit.
F IGURE IV.6 – Méthode du gradient optimal (GPO) pour diverses fonctions et points ini-
tiaux.
78 CHAPITRE IV. ALGORITHMES DE MINIMISATION SANS CONTRAINTE
F IGURE IV.7 – Méthode du gradient optimal (GPO) pour une fonction mal conditionnée
et des points initiaux perturbés.
Remarque IV.56 (Pas optimal et zig-zag). Comme on peut le voir sur la Figure IV.6, la
méthode fonctionne mieux sur des fonctions bien conditionnées ; dans le cas contraire la
méthode est ralentie par l’effet zig-zag. Comme on peut le voir également sur la Figure
IV.7, l’effet zig-zag est également impacté par le choix du point initial. En particulier, on
voit que lorsque on perturbe un peu un point initial situé dans l’espace propre de λmax , la
trajectoire change peu, tandis que pour un point initial situé dans l’espace propre de λmin ,
la trajectoire est instable et très vite ralentie par les zig-zag.
Démonstration. Admis. Une preuve est disponible en Annexe, dans la Section A.II.4.
Démonstration dans le cas quadratique. Cf. TD.
Méthodes de descente
• d ∈ R N est une direction de descente pour f en x ∈ R N si h∇ f ( x ), di < 0.
• Une méthode de descente est un algorithme de la forme
x k +1 = x k + ρ k d k
où dk est une direction de descente pour f en xk .
• Une direction de descente de choix est dk = −∇ f ( xk ) : cela donne la méthode du
gradient.
Dans ce chapitre nous nous intéressons aux problèmes d’optimisation avec contrainte :
( PC ) inf f ( x ),
x ∈C
f : U → R, C ⊂ U est non vide, où U ⊂ R N est un ouvert. Jusqu’à présent nous avons
plutôt ignoré la contrainte C :
• Dans le Chapitre II nous avons donné une Condition Nécessaire d’Optimalité lorsque
x̄ est un minimiseur de f sur C qui se trouve être dans l’intérieur de la contrainte
∇ f ( x̄ ) = 0.
Mais nous n’avons pas de CNO générale lorsque x̄ peut se trouver sur le bord de la
contrainte. Or, en pratique, cette situation est la plus courante !
• Nous allons voir que de manière générale on peut décrire une CNO ayant la forme
suivante :
∇ f ( x̄ ) + truc( x̄, C ) = 0,
où truc( x̄, C ) va être un nouvel objet dépendant de C et de x̄, que l’on pourra in-
terpréter comme le gradient de C en x̄ , et qui bien sur s’annule lorsque x̄ ∈ int C.
Dans ce chapitre nous nous focaliserons sur le cas où la contrainte C peut s’écrire sous
la forme d’équations et/ou inéquations.
81
82 CHAPITRE V. OPTIMISATION SOUS CONTRAINTES
V.I.1 Polyèdres
Définition V.1. On munit R M d’un ordre partiel dit canonique, noté ĺ M , défini par
Définition V.3 (Polyèdre). On dit que C ⊂ R N est un POLY ÈDRE 2 s’il existe M ∈ N,
A ∈ M M,N (R) et b ∈ R M tels que C = [ Ax ĺ M b].
Remarque V.4 (Polyèdre = Inégalités affines). On sait que une contrainte d’égalité linéaire
de la forme [ Ax = b] décrit un sous-espace affine. Mais nous sommes moins familiers avec
une contrainte d’inégalité affine [ Ax ĺ M b] telle qu’elle apparait dans la définition d’un
polyèdre. A quoi ressemble cet ensemble ? Si on note a1 , . . . , a M ∈ R N tels que
a1>
A = ... ,
a> M
M
[ Ax ĺ b] = { x ∈ R N | ∀i ∈ {1, . . . , M}, h ai , x i ď bi } =
\
[h ai , ·i ď bi ].
i =1
2 Prendregarde au fait que, dans la littérature française tant qu’anglophone, le terme polyèdre peut
désigner des notions légèrement différentes. Il faut également faire attention à ne pas confondre avec po-
lygone et polytope.
V.I. INTRODUCTION : PROBLÈMES CLASSIQUES 83
F IGURE V.2 – Quelques polyèdres bornés dans R2 . Ce sont des polygones convexes.
F IGURE V.4 – Cinq polyèdres bornés dans R3 (connus comme les cinq solides de Platon).
F IGURE V.5 – Un polyèdre de R3 qui est également un cône (non borné). Le cône a été
tronqué afin de ne pas occuper un espace infini.
Remarque V.6 (Intersections de demi-espaces). Les polyèdres sont donc les ensembles
que l’on obtient en intersectant un nombre fini de demi-espaces. On pourrait se deman-
der ce qui se passe lorsque on prend une intersection infinie de demi-espaces ? La réponse
est : cette procédure nous donne exactement tous les ensembles convexes ! C’est hors-
programme, mais rien ne vous empêche de faire des dessins dans R2 pour vous en convaincre !
Exercice V.7 (Polyèdre et équation affine). Soient A ∈ M M,N (R), b ∈ R M . Montrer que
l’ensemble des solutions du problème linéaire associé
[ Ax = b] = { x ∈ R N | Ax = b}
est un polyèdre.
Exercice V.8 (Polyèdre et espace affine). Montrer que tout sous-espace affine de R N est
un polyèdre. On pourra commencer par le prouver pour un sous-espace vectoriel.
Exercice V.10 (Polyèdre et convexité). Montrer que tout polyèdre est convexe.
V.I. INTRODUCTION : PROBLÈMES CLASSIQUES 85
Les problèmes dits d’optimisation linaire (Linear Programming, ou LP en VO) sont des
problèmes d’optimisation où toutes les composantes sont linéaires. On cherche à minimi-
ser une fonction linéaire sous une contrainte d’égalités ou inégalités affines3 .
F IGURE V.6 – Si chaque point bleu doit aller sur un point rouge, lequel doit aller où pour
minimiser la somme des trajets à vol d’oiseau ? Et surtout : comment répondre à cette
question sans avoir à tester les n! combinaisons ?
F IGURE V.7 – Application du Transport optimal : Une fois calculé un chemin optimal entre
deux images (ici aux extrémités) on peut trouver au milieu de ce chemin une image (ici au
centre) qui combine la forme d’une image avec le style de l’autre. Tout l’art ici consiste à
définir correctement ce que optimal veut dire, qui est un problème beaucoup plus dif-
ficile que résoudre le problème de transport en lui-même. Extrait de l’article Style transfer
by relaxed optimal transport and self-similarity par Kolkin et al., 2019 [11].
Le problème ci-dessus est dit sous forme canonique. Il est souvent bien pratique d’écrire
un problème d’optimisation convexe sous sa forme standard :
Exercice V.18 (Optimisation convexe : forme standard II). Montrer que pour tout problème
d’optimisation convexe, il existe des fonctions f , h : R N −→ R telles que le problème
puisse se réécrire sous la forme
• problème d’optimisation convexe sous contrainte mixtes pour désigner la forme stan-
dard
(
g1 ( x ) ď 0, . . . , g p ( x ) ď 0
minimiser f ( x ) tel que
x ∈R n
h1 ( x ) = 0, . . . , hq ( x ) = 0.
Exemple V.20 (Problème de classification). On suppose que l’on dispose d’un certain type
de données, et on veut être capable de les classer en deux groupes. Ce type de problème
peut être très facile à réaliser pour un humain, mais toute la question est de savoir com-
ment automatiser cette prise de décision pour l’implémenter sur une machine.
F IGURE V.9 – Classifier des nombres écrits à la main, difficulté moyenne. Issu du jeu de
données MNIST, utilisé abondamment pour tester les réseaux de neurones.
F IGURE V.10 – Classifier des photos dans R N , N > 106 , en deux catégories (chat/chien),
très difficile.
où A et b sont construites à partir des données à classer. Dans ce contexte, ce problème est
communément appelé Machine à vecteur de support (Support Vector Machine, ou SVM).
Si le temps le permet, nous verrons comment modéliser et résoudre un tel problème (cf.
feuille de TD5, et le TP associé).
où les fonctions en jeu seront convexes, affines ou quelconques, selon les besoins. Notre
objectif est d’obtenir des Conditions d’Optimalité pour ces problèmes :
• Quel est l’équivalent de la CNO du 1er ordre que l’on avait dans le Théorème II.9 ? La
réponse se trouve dans le Théorème V.34.
• Est-ce que cette CNO devient une CSO lorsque le problème est convexe, comme on
l’avait vu dans le Théorème III.25 ? La réponse est : oui, voir le Théorème V.39.
• Est-ce que l’on peut avoir une CSO du 2e ordre, comme dans le Théorème II.19 ? Encore
une fois, oui, cf. Théorème V.44.
Ces Théorèmes vont donc nous permettre de calculer à la main des minimiseurs lo-
caux/globaux de problèmes d’optimisation sous contrainte, en résolvant des équations,
de la même manière que l’on résolvait ∇ f ( x ) = 0 dans les premiers chapitres.
C = [ g ď 0],
pour g : U ⊂ R N −→ R différentiable.
D’autre part, puisque g est continue et g( x̄ ) < 0, on sait que pour t petit on aura encore
g( x̄ + td) < 0. Autrement dit, x̄ + td ∈ C et f ( x̄ + td) < f ( x̄ ), ce qui contredit le fait que x̄
soit un minimiseur local. Ceci conclut la preuve dans le cas g( x̄ ) < 0.
Supposons maintenant que g( x̄ ) = 0. Dans un premier temps, nous allons montrer que
∇ f ( x̄ ) ∈ Vect (∇ g( x̄ )). Raisonnons par l’absurde, et supposons que ∇ f ( x̄ ) ∈
/ Vect (∇ g( x̄ )).
Puisque on a supposé que ∇ g( x̄ ) 6= 0, cela veut dire que la famille {∇ f ( x̄ ), ∇ g( x̄ )} est
libre. Définissons la matrice dont les lignes sont ces gradients
∇ f ( x̄ )>
A= ∈ M2,N (R).
∇ g( x̄ )>
Ses lignes étant libres, nous en déduisons que A est surjective. Donc il existe un d ∈ R N
tel que Ad = e, où e = (−1, −1)> . Autrement dit, il existe un d ∈ R N tel que
h∇ f ( x̄ ), di = −1 et h∇ g( x̄ ), di = −1. (V.4)
On a donc une direction de descente commune pour ces fonctions ! D’après le Lemme
d’Armijo IV.12 appliqué à f et g, cela veut dire qu’il existe un δ > 0 commun tel que
Autrement dit, pour un tel choix de t ∈]0, δ[, on a x̄ + td qui est toujours dans la contrainte
[ g ď 0] (puisque g( x̄ + td) < 0), mais qui est meilleur que x̄ au sens où f ( x̄ + td) < f ( x̄ ).
On se rend alors compte que ceci est en contradiction avec le fait que x̄ soit un minimiseur
local de f sur C.
Nous avons donc montré par l’absurde que ∇ f ( x̄ )et ∇ g( x̄ ) sont colinéaires. Autre-
ment dit, qu’il existe un α ∈ R tel que
∇ f ( x̄ ) + α∇ g( x̄ ) = 0. (V.5)
Il ne nous reste donc plus qu’à prouver α ě 0. Encore une fois, raisonnons par l’absurde
et supposons que α < 0. Si on pose d0 = −∇ f ( x̄ ), on voit que
−1 1
h∇ f ( x̄ ), d0 i = −k∇ f ( x̄ )k2 < 0 et h∇ g( x̄ ), d0 i = h∇ f ( x̄ ), d0 i = k∇ f ( x̄ )k2 < 0.
α α
On voit que l’on a encore une direction de descente d0 commune pour f et g, ce qui va
impliquer pour les mêmes raisons que précédemment, une contradiction.
92 CHAPITRE V. OPTIMISATION SOUS CONTRAINTES
• La condition ∇ g( x̄ ) 6= 0, qui est essentielle pour garantir le résultat, est appelée condi-
tion de qualification de la contrainte. On parle par exemple de contrainte qualifiée.
• La propriété g( x̄ ) ď 0 ne fait que traduire le fait que x̄ appartient à la contrainte C =
[ g ď 0]. Autrement dit, que le vecteur x̄ est admissible (au sens où il ne viole pas la
contrainte). C’est pour cela que l’on parle en général de condition d’ADMISSIBILIT É.
• On distinguera souvent le fait que x̄ vérifie g( x̄ ) = 0 ou g( x̄ ) < 0. Lorsque g( x̄ ) = 0,
on dira que la contrainte [ g ď 0] est active en x̄, ce qui traduit que l’on est sur le bord
du sous-niveau. Dans le cas où g( x̄ ) < 0, on parlera de contrainte inactive.
• Le coefficient α que l’on voit apparaitre est appelé le multiplicateur de Lagrange as-
socié à la contrainte. On voit ici que α est positif ; on verra d’autres contextes dans
lequel le multiplicateur n’a pas de signe prescrit.
• La condition ∇ f ( x̄ ) + α∇ g( x̄ ) = 0 est appelée la condition de stationnarité du problème.
On vient de voir ici que c’est une condition nécessaire pour x̄ d’être un minimiseur local.
• La propriété αg( x̄ ) = 0 est la condition de complémentarité de la contrainte. Elle peut
se reformuler de façon équivalente en :
Si g( x̄ ) < 0 alors α = 0.
Une fois qu’on dispose de ces solutions, déterminer si elles sont des minimiseurs ou pas
se fait exactement (aussi difficilement donc) comme on le fait pour les problèmes sans
contraintes.
Exercice V.25 (Fonction quadratique sous contrainte d’inégalité linéaire II). Soient f ( x, y) =
2x − y et C = {( x, y) ∈ R2 | 12 x2 + y2 ď 1}.
(∃α ě 0) ∇ f ( x ) + α( x − a) = 0.
4 On rappelle que pour une contrainte d’inégalité [ g ď 0], la contrainte est dite active en x si g( x ) = 0 (en
d’autres termes on est sur le bord de la contrainte).
94 CHAPITRE V. OPTIMISATION SOUS CONTRAINTES
On a vu dans la Proposition V.21 que pour minimiser une fonction f en présence d’une
contrainte d’inégalité simple
g( x ) ď 0,
une condition nécessaire d’optimalité est (V.3), qui demande en particulier la condition de
stationnarité
∇ f ( x̄ ) + α∇ g( x̄ ) = 0.
On peut donc se demander ce qui se passe lorsqu’on a affaire à plusieurs inégalités
g1 ( x ) ď 0, · · · , g p ( x ) ď 0 ?
Ou à plusieurs égalités
h1 ( x ) = 0, · · · , hq ( x ) = 0 ?
Ou à une combinaison des deux (on parle de contrainte mixte) :
C = { x ∈ R N | g1 ( x ) ď 0, · · · , g p ( x ) ď 0, h1 ( x ) = 0, · · · , hq ( x ) = 0}? (V.6)
∇ f ( x̄ ) + α1 ∇ g1 ( x̄ ) + · · · + α p ∇ g p ( x̄ ) + β 1 ∇h1 ( x̄ ) + . . . β q ∇hq ( x̄ ) = 0.
Comme nous allons le voir, cela est essentiellement vrai, les différences principales avec
la Proposition V.21 étant que :
• les multiplicateurs β j associés aux contraintes d’égalité n’ont pas de signe imposé,
• l’hypothèse de contrainte qualifiée (∇ g( x̄ ) 6= 0) va devenir un peu plus compliquée.
Avant d’énoncer notre premier Théorème V.34, donnons quelques définitions qui vont
nous permettre d’exprimer une hypothèse de contrainte qualifiée.
I ( x ) = {i ∈ {1, · · · , p} | gi ( x ) = 0}.
Remarque V.29 (Contraintes actives). Il faut noter que la notion de contrainte active ne
vaut que pour les contraintes d’inégalité.
V.II. THÉORÈME(S) DE LAGRANGE-KKT 95
{∇ gi ( x ), ∇h j ( x )}i∈ I (x),1ďjďq
Remarque V.31 (Contraintes actives 2). Si la famille de tous les vecteurs {∇ gi ( x ), ∇h j ( x )}1ďiďp,1ďjďq
est libre, alors il n’y a pas besoin de calculer I ( x ) puisque toute sous-famille sera également
libre. Mais en pratique, il arrive souvent que I ( x ) soit beaucoup plus petite que {1, . . . , p},
ce qui fait qu’il est plus facile ainsi de vérifier que les contraintes sont qualifiées.
Remarque V.32 (Qualification pour une unique contrainte). Si la contrainte est unique,
alors la condition de qualification de la contrainte est drastiquement simplifiée :
• si on parle d’une contrainte d’égalité [h = 0], que la famille {∇h( x )} soit libre est
équivalent à ce que ∇h( x ) 6= 0 ;
• si on parle d’une contrainte d’inégalité [ g ď 0], une condition suffisante pour que la
contrainte soit qualifiée est que ∇ g( x ) 6= 0.
Noter que ∇ g( x ) 6= 0 est exactement l’hypothèse de qualification que l’on a faite dans la
Proposition V.21 !
Nous sommes est maintenant prêts à énoncer le premier Théorème de cette section, qui
établit la Condition Nécessaire d’Optimalité de KKT du 1er ordre :
est régulière en x̄, alors x̄ vérifie la Condition Nécessaire d’Optimalité de KKT du 1er ordre :
p q
∇ f ( x̄ ) + ∑ ∇ g ( x̄ ) + ∑ β j ∇h j ( x̄ ) = 0
α
i i
i =1 j =1
∀i = 1, . . . , p g ( x̄ ) ď 0
i
(∃α ∈ R p )(∃ β ∈ Rq ) (V.7)
∀ j = 1, . . . , q h j ( x̄ ) = 0
∀i = 1, . . . , p αi ě 0
∀i = 1, . . . , p αi gi ( x̄ ) = 0.
Remarque V.35 (Point critique). On dira que x̄ est un point critique du problème si il
vérifie la Condition Nécessaire d’Optimalité de KKT du 1er ordre. Le Théorème précédent
nous dit donc que les points critiques sont de bons candidats à être des minimiseurs lo-
caux.
Remarque V.36 (Le système d’(in)équations de KKT II). En pratique, lorsque on cherche
un minimiseur de f sur une contrainte mixte, il faut donc chercher ( x, α1 , . . . , α p , β 1 , . . . , β q ) ∈
R N × R p × Rq solution du système :
p q
∇ f ( x ) + ∑ i i∇ g ( x̄ ) + ∑ β j ∇h j ( x̄ ) = 0 (Condition de stationnarité)
α
i =1 j =1
∀i = 1, . . . , p g ( x̄ ) ď 0
(Condition d’admissibilité : inégalités)
i
∀ j = 1, . . . , q h j ( x̄ ) = 0
(Condition d’admissibilité : égalités)
∀i = 1, . . . , p αi ě 0 (Multiplicateur : inégalités)
∀i = 1, . . . , p αi gi ( x̄ ) = 0 (Condition de complémentarité)
• Joseph-Louis Lagrange s’intéresse vers la fin du 18e siècle à des problèmes de mécanique,
qui l’amènent à minimiser certaines quantités sous des contraintes d’égalité (voir Fi-
gure V.37). Il énonce alors une version du Théorème V.34 pour des contraintes d’égalité,
introduisant l’idée de ces variables supplémentaires que l’on appelle désormais les
multiplicateurs de Lagrange. On cite parfois ce résultat comme le Théorème des multi-
plicateurs de Lagrange, mais également comme le Théorème des extrémas liés.
V.II. THÉORÈME(S) DE LAGRANGE-KKT 97
De manière surprenante, on se rendra compte près de 20 ans plus tard que ce résultat
avait déjà été obtenu par William Karush dans . . . son mémoire de Master [9] datant de
1939 ! Depuis lors, les conditions d’optimalité (V.7) sont connues comme les conditions
de Karush-Kuhn-Tucker, ou simplement KKT.
5 Vous connaissez certainement déjà Tucker sans le savoir, puisqu’il est à l’origine du fameux dilemne
du prisonnier . Il a beaucoup travaillé sur la Théorie des Jeux, et a notamment dirigé la thèse de John Nash
sur ce sujet (1950), qui vaudra à ce dernier un prix Nobel en sciences économiques (1994).
98 CHAPITRE V. OPTIMISATION SOUS CONTRAINTES
F IGURE V.13 – Extrait d’un échange de courrier entre Kuhn et Karush, dans lequel Kuhn
s’engage à lui donner la reconnaissance qu’il mérite, et s’étonne que Karush ne se soit pas
manifesté plus tôt [10].
Pour ces raisons, dans ce cours, nous parlerons toujours de conditions de KKT pour les
problèmes d’optimisation sous contraintes mixtes.
Remarque V.38 (Pourquoi les contraintes d’égalité ne se comportent pas comme les contraintes
d’inégalité ?). Si on regarde les conditions nécessaires d’optimalité de KKT, on voit qu’il
y a une asymétrie entre les contraintes d’égalité et d’inégalité : les contraintes d’égalité
n’ont pas
• de condition de compatibilité β j h j ( x̄ ) = 0,
• de condition sur les multiplicateurs β j ě 0.
V.II. THÉORÈME(S) DE LAGRANGE-KKT 99
Il est en fait assez facile de se convaincre qu’en fait ces deux conditions sont triviale-
ment vérifiées, et n’ont donc pas lieu d’apparaı̂tre dans la condition nécessaire. En effet :
Voyons maintenant que cette CNO de KKT du 1er ordre est en fait une CSO globale
lorsque le problème est convexe.
Donc
q
k k
f ( x̄ ) ě φk ( xk ) ě f ( xk ) + ∑
2 i∈ I ( x̄)
gi ( x )2+ +
2 ∑ h j ( x )2 .
j =1
Or f ( xk ) est minorée par infB( x̄,ε) f , qui est indépendant de k. On voit donc que
q
k k
0ď ∑
2 i∈ I ( x̄)
gi ( xk )2+ +
2 ∑ h j ( x k )2 ď f ( x̄ ) − inf f < +∞.
B( x̄,ε)
j =1
Après division par k, on en déduit que les gi ( xk )2+ et h j ( xk )2 tendent vers 0, ce qui implique
que gi ( x∞ )2+ = 0 et h j ( x∞ )2 = 0. Autrement dit, gi ( x∞ ) ď 0 et h j ( x∞ ) = 0. On a donc bien
montré que x∞ ∈ C. Maintenant, on écrit
1
f ( x̄ ) ě φk ( xk ) ě f ( xk ) + k xk − x̄ k2 ,
2
et en passant à la limite on obtient
1
f ( x̄ ) ě f ( x∞ ) + k x∞ − x̄ k2 .
2
Lemme V.41 (de Fritz John). Soit x̄ un minimiseur local de f sur C, et I ( x̄ ) les contraintes
d’inégalités actives en x̄. Alors
q
λ∇ f ( x̄ ) + ∑ αi ∇ gi ( x̄ ) + ∑ β j ∇h j ( x̄ ) = 0, (V.8)
i ∈ I ( x̄ ) j =1
| I ( x̄ )|
où les multiplicateurs λ ∈ R+ , α ∈ R+ , β ∈ Rq sont non tous nuls.
V.II. THÉORÈME(S) DE LAGRANGE-KKT 101
Considérons le vecteur réunissant les multiplicateurs π̂k := (1, α̂i,k , β̂ j,k , 1). Alors kπ̂k k2 =
1 + ∑ α̂2i,k + ∑ β2j,k + 1 est non nul. On peut donc définir πk := π̂k /kπ̂k k, constitué des
coefficients (λk , αi,k , β j,k , λk ), avec λk = 1/kπ̂k k, etc. Si on divise (V.9) par kπ̂k k, on obtient
donc
q
0 = λk ∇ f ( xk ) + ∑ αi,k ∇ gi ( xk ) + ∑ β j,k ∇h j ( xk ) + λk ( xk − x̄ ).
i ∈ I ( x̄ ) j =1
Maintenant, on observe que, par construction, kπk k = 1, donc quitte à prendre une sous-
suite, πk converge vers un vecteur π = (λ, αi , β j , λ) de norme 1 lui aussi. Par ailleurs xk
converge vers x̄, et les gradients sont continus. On peut donc passer à la limite et obtenir
q
0 = λ∇ f ( x̄ ) + ∑ αi ∇ gi ( x̄ ) + ∑ β j ∇h j ( x̄ ),
i ∈ I ( x̄ ) j =1
Lemme V.42 (Cas des contraintes qualifiées). Considérons les hypothèses du Lemme V.41 de
Fritz John. Supposons de plus que les contraintes sont qualifiées en x̄. Alors λ > 0.
Démonstration. On sait déjà d’après le Lemme V.41 que λ ě 0. Supposons par l’absurde
que λ = 0. Alors la condition d’optimalité (V.8) combinée avec λ = 0 veut dire que
q
∑ αi ∇ gi ( x̄ ) + ∑ β j ∇h j ( x̄ ) = 0.
i ∈ I ( x̄ ) j =1
Or la contrainte est qualifiée en x̄, ce qui veut dire que la famille des gradients dans cette
équation est libre. Le fait qu’on ait une combinaison linéaire nulle veut dire que l’on a
forcément αi = 0 et β j = 0. En d’autres termes (λ, α, β) = 0. Ceci contredit le Lemme V.41
qui dit que les multiplicateurs (λ, α, β) sont non tous nuls.
102 CHAPITRE V. OPTIMISATION SOUS CONTRAINTES
Lemme V.43 (Cas des contraintes affines). Considérons les hypothèses du Lemme V.41 de Fritz
John. Supposons de plus que les contraintes sont affines. Alors λ > 0.
ce qui contredit (V.10). Cela veut donc dire que (α, β) = 0. Or on a supposé que λ = 0,
donc en fait (λ, α, β) = 0, ce qui contredit le Lemme de Fritz John V.41.
Démonstration du Théorème V.34. Tout d’abord, observons que x̄ ∈ C garantit déjà que
gi ( x̄ ) ď 0 et h j ( x̄ ) = 0. Ensuite, observons que la condition de complémentarité αi gi ( x̄ ) =
0 est équivalente à dire que αi = 0 ou i ∈ I ( x̄ ) . Autrement dit, montrer (V.7) est
équivalent à montrer que :
q
∑ αi ∇ gi ( x̄ ) + ∑ β j ∇h j ( x̄ ) = 0.
p
(∃α ∈ R+ )(∃ β ∈ Rq ) ∇ f ( x̄ ) +
i ∈ I ( x̄ ) j =1
V.II. THÉORÈME(S) DE LAGRANGE-KKT 103
On fait appel au Lemme de Fritz John V.41 pour obtenir (V.8). On utilise ensuite le fait que
la contrainte est régulière en x̄, avec le Lemme V.42 ou V.43, pour obtenir que λ > 0. On
peut alors diviser (V.8) par λ, et conclure.
q
f ( x̄ ) ď f ( x̄ ) − ∑ αi h∇ gi ( x̄ ), c − x̄ i − ∑ β j h∇h j ( x̄ ), c − x̄ i.
i ∈ I ( x̄ ) j =1
a) la Condition Nécessaire d’Optimalité de KKT du 1er ordre (V.7) avec des multiplicateurs ᾱ ∈
R p , β̄ ∈ Rq ;
b) la définie positivité de la Hessienne Lagrangienne :
p q
∇ f ( x̄ ) + ∑ ᾱi ∇ gi ( x̄ ) + ∑ β̄ j ∇2 h j ( x̄ ) 0;
2 2
i =1 j =1
104 CHAPITRE V. OPTIMISATION SOUS CONTRAINTES
Remarque V.45 (Complémentarité stricte). Que veut dire cette complémentarité stricte ?
Rappelons si nécessaire que dans la condition d’optimalité de KKT du 1er ordre, on de-
mande une condition de complémentarité qui s’écrit
αi gi ( x̄ ) = 0.
Comme on l’a déjà dit précédemment, ceci est équivalent à dire que
αi 6= 0 ⇒ gi ( x̄ ) = 0.
αi > 0 ⇒ i ∈ I ( x̄ ).
Cette complémentarité stricte demande donc un peu plus, à savoir l’équivalence entre ces
deux propriétés.
Démonstration du Théorème V.44 sans inégalités. On commence par prouver ce résultat lors-
qu’on a seulement des contraintes d’égalité. On introduit alors le Laplacien :
q
L ( x ) = f ( x ) + ∑ β j h j ( x ),
j =1
qui vérifie f = L sur C. Puisque x̄ vérifie la CNO de KKT du 1er ordre, on peut écrire :
q
∇ L( x̄ ) = ∇ f ( x̄ ) + ∑ β j ∇h j ( x̄ ) = 0.
j =1
On voit alors que x̄ vérifie les conditions suffisantes d’optimalité du 2e ordre (sans contraintes)
vues dans le Théorème II.19, ce qui implique que x̄ est un minimiseur local de L. Donc,
pour tout x ∈ C au voisinage de x̄, on a
f ( x̄ ) = L( x̄ ) ď L( x ) = f ( x ).
Démonstration du Théorème V.44 : cas général. Maintenant passons au cas général avec des
inégalités, et montrons qu’on peut se ramener au cas d’égalités seules. Quitte a réordonner
les inégalités, et ce pour simplifier les notations, on va supposer que les premières corres-
pondent aux contraintes actives. Autrement dit, I ( x̄ ) = {1, . . . , p̄} avec p̄ ď p. On va
définir un nouveau problème dans R N + p̄ : on introduit
p̄ q
fˆ( x, z) = f ( x ), gi ( x ) + z2i ,
\ \
ĝi ( x, z) = ĥ j ( x, z) = h j ( x ), Ĉ = [ ĝi = 0] ∩ [ĥ j = 0].
i =1 j =1
On va s’intéresser au problème de minimiser fˆ sur Ĉ. Notons p que Ĉ n’est défini que par
des égalités ! De plus, il est facile de voir (en prenant zi = − gi ( x )) que
gi ( x ) ď 0 si et seulement si il existe zi ∈ R tel que ĝi ( x, zi ) = 0.
On en déduit alors que x est un minimiseur local de f sur C si et seulement si il existe
z ∈ R p̄ tel que ( x, z) soit minimiseur local de fˆ sur Ĉ.
Considérons maintenant le x̄ de notre théorème, et définissons z̄ ∈ R p̄ par z̄i = − gi ( x̄ ).
p
Nous allons montrer que ( x̄, z̄) est un minimiseur local de fˆ sur Ĉ, ce qui terminera la
preuve. Pour cela, il nous suffit de montrer que la condition suffisante du second ordre
pour les contraintes d’égalités est vérifiée puisque on vient de le prouver ! On voit en
particulier que si i ∈ I ( x̄ ) alors z̄i = 0. Grâce à notre hypothèse a), on peut écrire
q
∇ fˆ( x̄, ẑ) + ∑ αi ∇ ĝi ( x̄, z̄) + ∑ β j ∇ĥ j ( x̄, z̄)
i ∈ I ( x̄ ) j =1
q
∇ f ( x̄ ) + ∑ αi ∇ gi ( x̄ ) + ∑ j=1 β j ∇h j ( x̄ )
i ∈ I ( x̄ )
..
0N
=
. =
.
2αi z̄i 0 p̄
..
.
On voit donc que ( x̄, z̄) vérifie les conditions d’optimalité de KKT pour le problème de
minimiser fˆ sur Ĉ. On peut également écrire :
q
∇2 fˆ( x̄, ẑ) + ∑ αi ∇2 ĝi ( x̄, z̄) + ∑ β j ∇2 ĥ j ( x̄, z̄)
i ∈ I ( x̄ ) j =1
q
∇2 f ( x̄ ) + ∑ αi ∇2 gi ( x̄ ) + ∑ j=1 β j ∇2 h j ( x̄ ) 0
= i ∈ I ( x̄ )
0 2Diag(αi ).
On a ici une matrice diagonale par blocs, dont le premier bloc est défini positif à cause de
l’hypothèse b) ; et le deuxième bloc est la matrice diagonale Diag(αi ) qui est bien définie
positive au vu de la condition de complémentarité stricte c) . Donc cette grosse matrice
106 CHAPITRE V. OPTIMISATION SOUS CONTRAINTES
est bien définie positive. On voit donc que ( x̄, z̄) vérifie la condition suffisante du second
ordre pour le Théorème avec les contraintes d’égalité, que l’on a montré dans la première
partie de la preuve. On en déduit donc que ( x̄, z̄) est un minimiseur local de fˆ sur Ĉ, ce
qui implique que x̄ est un minimiseur local de f sur C.
Remarque V.46 (Sur une CNO de KKT du 2e ordre). Si on compare ces Théorèmes avec
ceux que l’on a obtenus dans le cas sans contrainte, on voit qu’il nous en manque un :
un analogue de la Condition Nécessaire d’Optimalité d’ordre 2 (cf. Théorème II.16). On
s’attend à ce qu’il existe un résultat disant que : si x̄ est un minimiseur local de f sur C, et
sous hypothèse que la contrainte soit régulière, alors non seulement la CNO de KKT du
1er ordre est satisfaite
p q
∇ f ( x̄ ) + ∑ αi ∇ gi ( x̄ ) + ∑ β j ∇h j ( x̄ ) = 0,
i =1 j =1
Le problème est qu’un tel résultat n’existe pas, malheureusement. Plus précisément :
• On peut trouver un contre-exemple avec un point qui est minimiseur local mais pour
lequel la matrice dans (V.11) n’est pas semi-définie positive (voir Exemple V.47 sui-
vant).
• On peut montrer un résultat un peu plus faible que (V.11), mais qui n’est pas vraiment
facile à utiliser en pratique : la matrice dans (V.11) est semi-définie positive dans les
directions tangentes à la contrainte . On ne s’étendra pas sur ce que cela veut dire, car
cela dépasse le programme de ce cours.
Exemple V.47 (Un contre-exemple à l’existence d’une CNO de KKT 2e du ordre). Soit
f ( x, y) = x2 + y2 et C = [h = 0] avec h( x, y) = y.
1) On a C = {( x, y) ∈ R2 | y = 0}, ce qui nous permet de voir que sur la contrainte,
f ( x, y) = x2 . On en déduit donc immédiatement que f admet un unique minimiseur
sur C, qui est ( x, y) = (0, 0).
2) On voit que la contrainte est qualifiée en (0, 0), puisque ∇ g(0, 0) = (0, 1)> 6= (0, 0)> .
Donc la CNO de KKT du 1er ordre s’applique, et on obtient que ∇ f (0, 0) + β∇ g(0, 0) =
0, pour un certain β ∈ R. Puisque ∇ f (0, 0) = (0, 0)> et ∇ g(0, 0) = (0, 1)> , on voit
immédiatement que le multiplicateur β est nul.
3) On peut calculer
2 2 2 0
∇ f (0, 0) + β∇ g(0, 0) = ,
0 −2
et on se rend compte que cette matrice n’est pas semi-définie positive.
V.III. ALGORITHMES POUR L’OPTIMISATION SOUS CONTRAINTES 107
On voit donc bien qu’une condition telle que (V.11) n’est pas vraie en général.
F IGURE V.19 – La projection n’est pas bien définie si C n’est pas convexe ! Ici deux en-
sembles C non convexes, une patate et un cercle (cercle 6= disque) pour lesquels le point
rouge peut trouver plus d’un point vert dans C qui minimise la distance.
V.III. ALGORITHMES POUR L’OPTIMISATION SOUS CONTRAINTES 109
Proposition V.51 (La projection est bien définie sur les convexes fermés). Soit C ⊂ R N un
ensemble non vide.
Démonstration. On écrit
i) Si on suppose que C est fermé, alors projC ( x ) est l’ensemble des minimiseurs d’une
fonction continue coercive sur un fermé. D’après le Théorème II.35, on sait que cet
ensemble de minimiseurs est non vide.
ii) Si on suppose de plus que C est convexe, alors on peut dire que x 0 7→ k x 0 − x k2 est
fortement convexe sur C. Donc d’après le Théorème III.38, on sait qu’il y a exactement
un minimiseur.
1) C = { x ∈ R N | k x k ď 1}
2) C = C1 × · · · × CN ⊂ R N , où C1 , ..., CN ⊂ R.
3) C = R+
N = { x = ( x , · · · , x ) ∈ R N | x ě 0}, parfois appelé l’orthant positif.
1 N i
4) C = {( x, y) ∈ R2 | y = 0}.
Le point projeté p de x sur C peut également se caractériser comme étant l’unique point
tel que le vecteur x − p forme un angle obtus6 avec tous les vecteurs entrants c − p, pour
c ∈ C (cf. Figures V.20 et V.21) :
(∀c ∈ C ) hc − p, x − pi ď 0. (V.12)
6 On rappelle que deux vecteurs x et y forment un angle obtus si et seulement si h x, yi ď 0.
110 CHAPITRE V. OPTIMISATION SOUS CONTRAINTES
Puisque ceci est vrai pour tout α ∈]0, 1[, on peut faire tendre α → 0, ce qui nous donne
bien
0 ď h x − p, p − ci.
Supposons maintenant que p ∈ C est un vecteur vérifiant (V.12), et montrons que c’est
projC ( x ). Par hypothèse, on a pour tout c ∈ C :
0 ě h x − p, c − pi = h x − p, c − x + x − pi = h x − p, c − x i + k x − pk2 .
0 ě −k x − pkkc − x k + k x − pk2 ⇒ 0 ě k x − pk − kc − x k.
Ceci étant vrai pour tout c ∈ C, on en déduit que p est la projection de x sur C.
h a, x i − b
projC ( x ) = x − a
k a k2
V.III. ALGORITHMES POUR L’OPTIMISATION SOUS CONTRAINTES 111
F IGURE V.22 – Projection sur une droite af- F IGURE V.23 – Projection sur un sous-espace
fine portée par a. vectoriel (ici un hyperplan). On peut voir
que les vecteurs x − p et c − p forment un
angle droit.
(∀c ∈ F ) hc, x − pi = 0.
(∀c ∈ F ) hc − p, x − pi ď 0.
(∀c ∈ F ) hc, x − pi ď 0.
(∀c ∈ F ) hc, x − pi = 0.
Exercice V.56. Soit F un sous-espace vectoriel de R N non vide, et soit p = projF . Montrer
que p est une application linéaire, et que p est la projection orthogonale sur F, au sens où :
p◦p = p et p ď 1.
112 CHAPITRE V. OPTIMISATION SOUS CONTRAINTES
Lemme V.57 (Non-expasion ferme de la projection). Soit C ⊂ R N convexe fermé non vide.
Alors la projection projC : R N → R N est fermement non-expansive :
(∀ x, y ∈ R N ) k projC (y) − projC ( x )k2 ď ky − x k2 − k(y − x ) − (projC (y) − projC ( x ))k2 .
Démonstration. (Voir [8, Proposition III.3.1.3]) Commençons par développer la norme au
carré, en faisant apparaitre les termes de projection :
k y − x k2
= k(y − x ) − (projC (y) − projC ( x )) + (projC (y) − projC ( x ))k2
= k(y − x ) − (projC (y) − projC ( x ))k2 + k projC (y) − projC ( x )k2
+2h(y − x ) − (projC (y) − projC ( x )), projC (y) − projC ( x )i.
On voit que le Lemme sera prouvé pourvu qu’on arrive à monter que le produit scalaire
est positif. Coupons ce terme en deux :
h(y − x ) − (projC (y) − projC ( x )), projC (y) − projC ( x )i
= −hy − projC (y), projC ( x ) − projC (y)i − h x − projC ( x ), projC (y) − projC ( x )i.
On voit alors que chacun de ces deux produits scalaires est négatif, grâce à la caractérisation
de la projection par les angles. D’où le résultat.
Théorème V.58 (La projection est 1-Lipschitzienne). Soit C ⊂ R N convexe fermé non vide.
Alors la projection projC : R N → R N est 1-Lipschitzienne (on dit aussi non-expansive) :
(∀ x, y ∈ R N ) k projC (y) − projC ( x )k ď ky − x k.
Démonstration. C’est une conséquence directe du Lemme de non-expansivité ferme V.57,
où on élimine le terme négatif du second membre et on enlève les carrés.
Remarque V.59 (Contraction des distances). Cela veut dire que si on prend deux points
puis qu’on les projette, les projections seront plus rapprochées que ne l’étaient les points
de départ. On peut bien voir ce phénomène sur les Figures V.15 et V.16.
On termine avec un résultat montrant que la projection est liée à la dérivée de la fonc-
tion distance.
Proposition V.60 (Gradient de la distance au carré). Soit C un ensemble convexe fermé non
vide, et f : R N → R définie par f ( x ) = 12 dist( x, C )2 . Alors f ∈ C11,1 (R N ), avec
∇ f ( x ) = x − projC ( x ).
V.III. ALGORITHMES POUR L’OPTIMISATION SOUS CONTRAINTES 113
Pour cela, on observe que la définition de la projection nous permet d’écrire que f ( x ) =
(1/2)k x − p x k2 = (1/2)k Ax k2 . On peut alors écrire
f (y) − f ( x ) − h Ax, y − x i
1 1
= k Ayk2 − k Ax k2 − h Ax, y − x i
2 2
1 1
= k Ayk − k Ax k2 − h Ax, Ay − Ax i − h Ax, py − p x i car x = Ax + p x
2
2 2
1
= k Ay − Ax k2 − h x − p x , py − p x i en réorganisant les termes.
2
Or ici on a k Ay − Ax k2 ě 0, et d’autre part via la caractérisation de la projection par
les angles (Proposition V.53), on a h x − p x , py − p x i ď 0. On a donc bien prouvé (V.14).
Maintenant on va conclure que (V.13) est vraie. Pour cela on écrit
f (y) − f ( x ) − h Ax, y − x i
ď −h Ay, x − yi − h Ax, y − x i avec (V.14) en échangeant les rôles de x, y
= h Ay − Ax, y − x i
ď k Ay − Ax kky − x k par Cauchy-Schwarz
ď ky − x k2 = o (ky − x k),
x̂k+1 = xk − ρ∇ f ( xk ).
En faisant cela, on obtient un point qui fait décroitre la valeur de f . Mais rien ne garantit
que x̂k+1 soit encore dans C ! Or c’est un problème puisque on cherche le minimiseur de
f sur C. On se retrouve donc avec un point x̂k+1 sur les bras, qui est bon du point de
vue de f , mais à priori mauvais vis-à-vis de C.
Une approche consiste alors à dire : au lieu de prendre x̂k+1 , on va chercher parmi les
points de C celui qui est le plus proche de x̂k+1 , autrement dit la projection de x̂k+1 sur C. Par
définition il sera dans la contrainte, et comme il sera pas trop loin de x̂k+1 , on espère
qu’il aura la même propriété de faire décroitre f (spoiler : oui).
2
xk+1 = ( xk − ρΦ> (Φxk − y))+ , ρ< .
k Φ k2
Vérifions maintenant que cet algorithme est raisonnable, au sens où les solutions du
problème sont des points stationnaires :
V.III. ALGORITHMES POUR L’OPTIMISATION SOUS CONTRAINTES 115
(∀c ∈ C ) h x ∗ − ρ∇ f ( x ∗ ) − x ∗ , c − x ∗ i ď 0.
Puisque ρ > 0, ceci est équivalent à montrer que
(∀c ∈ C ) h∇ f ( x ∗ ), c − x ∗ i ě 0.
Prenons donc un c ∈ C quelconque. On peut alors calculer
∗ ∗ f ( x ∗ + t(c − x ∗ )) − f ( x ∗ )
h∇ f ( x ), c − x i = lim ,
t →0 t
et cette fraction est bien positive ! En effet, pour t ∈]0, 1[ on a par convexité que x ∗ + t(c −
x ∗ ) ∈ C, et puisque x ∗ ∈ argminC f on a forcément f ( x ∗ + t(c − x ∗ )) ě f ( x ∗ ). D’où le
résultat.
Vérifions que le gradient projeté fait bien décroitre les valeurs de f :
(∀k ∈ N) f ( x k +1 ) ď f ( x k ).
d’où f ( xk+1 ) − f ( xk ) ď 0.
Nous énonçons maintenant le Théorème principal de cet algorithme :
k xk+1 − x ∗ k ď k( xk − ρ∇ f ( xk )) − ( x ∗ − ρ∇ f ( x ∗ ))k ď θ k xk − x ∗ k.
V.III. ALGORITHMES POUR L’OPTIMISATION SOUS CONTRAINTES 117
Démonstration. Admis. Une preuve est disponible dans la Section A.II.3 de l’Annexe.
Trouver x ∈ C := C1 ∩ · · · ∩ Cr . (V.17)
Pour ce genre de problèmes, typiquement chaque contrainte Ci est simple , alors que C
est plus compliquée.
Par exemple, on pourrait considérer que trouver la solution d’un système linéaire
Ax = b est difficile. Or cette égalité vectorielle est équivalente à vérifier des équations
réelles (on note ai les lignes de la matrice A) :
Ax = b ⇔ ∀i, h ai , x i = bi .
Or, trouver une solution de h ai , x i = bi est très facile pour chaque i ! On sait même projeter
sur cet hyperplan ! C’est trouver une solution commune qui est compliqué.
Un autre exemple consiste à dire que, ok, résoudre un système linéaire c’est facile, mais
que pour des problèmes concrets on a souvent des contraintes naturelles qui s’ajoutent.
Bien souvent, on veut que la solution de Ax = b soit un vecteur de coordonnées positives.
Autrement dit, on veut à la fois
N
Ax = b et x ∈ R+ .
Pas facile à priori ! Faut-il/Peut-on modifier le pivot de Gauss pour garantir des coeffi-
cients positifs ? (non)
Donc dans cette section on va proposer un algorithme capable de résoudre le problème
de faisabilité. L’idée est simple : on va projeter alternativement entre tous les Ci !
118 CHAPITRE V. OPTIMISATION SOUS CONTRAINTES
Démonstration. Ici on notera pC au lieu de projC pour simplifier. Soit ( xk )k∈N la suite
générée par l’algorithme de projection alternée, qui vérifie par définition xk+1 = pCr ◦
· · · ◦ pC1 ( xk ). On va avoir besoin de donner un nom à toutes les suites intermédiaires,
donc on définit pour tout k ∈ N et i = 1, . . . , r :
On en déduit que, pour tout i = 1, . . . , r, la suite (k x̂ki − ck)k∈N est décroissante, et que
toutes ces suites ont la même limite :
On en déduit également que les suites ( x̂ki )k∈N sont bornées, donc il existe une sous-suite
k n commune telle que toutes les sous-suites ( x̂ki n )k∈N soient convergentes. On notera x∞ i
i ∈ C puisque x i ∈ C et que les C sont fermés.
leur limite, dont on sait que x∞ i k i i
Maintenant, on utilise le Lemme V.57 avec x = x̂ki et y = c pour obtenir :
ce qui veut dire que x∞ i +1 = x i . Ceci étant vrai pour tout i, on en déduit que toutes ces
∞
limites de sous-suites sont en fait le même point, que l’on note c∞ , qui vérifie donc c∞ ∈ C.
On peut maintenant conclure, en observant maintenant que si on prend c = c∞ , alors
lim k x̂ki n − c∞ k = 0. Autrement dit, la constante ` dans l’équation (V.18) est nulle. Ceci
k n →+∞
implique donc que c’est bien toute la suite xki qui converge vers c∞ . En particulier, xk =
x̂kr −1 → c∞ .
Remarque V.71 (La projection alternée est un gradient projeté). Considérons le problème
de trouver un x ∈ C ∩ D 6= ∅, où C et D sont deux ensembles convexes fermés. Alors
ce problème est équivalent à minimiser f sur C, où f ( x ) = 21 dist( x, D )2 . D’après la Pro-
position V.60, on a pour cette fonction que Lip(∇ f ) = 1 et ∇ f ( x ) = x − projD ( x ). Alors
l’algorithme du gradient projeté s’écrit dans ce cas
On observe qu’en prenant un pas court ρ = 1, on obtient xk+1 = projC (projD ( xk )) qui est
exactement l’algorithme de la projection alternée pour une intersection de deux contraintes !
Qu’est-ce que cela implique du point de vue des vitesses de convergence ? Ici f n’est pas
fortement convexe7 donc on doit appliquer le Théorème V.67. On obtient alors que les
valeurs f ( xk ) = dist( xk , D ) tendent vers 0 avec une vitesse O( 1k ), et que les itérés tendent
vers une solution x ∗ ∈ C ∩ D. Mais on ne peut rien dire de plus sur la vitesse de k xk − x ∗ k,
ou de dist( xk , C ∩ D ), conformément à la Remarque V.70.
7A moins que D soit réduit à un singleton. Saurez-vous voir pourquoi c’est évident ?
120 CHAPITRE V. OPTIMISATION SOUS CONTRAINTES
Remarque V.72 (La projection alternée n’est pas un gradient projeté). En présence de
deux contraintes, on a vu dans la Remarque V.71 que la méthode de projection alternée
est un cas particulier du gradient projeté. Malheureusement cela n’est pas vrai en général.
En effet il est possible de montrer que la méthode de projection alternée pour r ě 3
contraintes ne peut en aucun cas être écrite comme un cas particulier de la méthode du
gradient projeté avec un choix intelligent de f .8
Remarque V.73 (Au delà du gradient projeté). Un des problèmes évidents de la méthode
du gradient projeté est qu’il faut savoir ... projeter ! Comme on l’a vu en début de cha-
pitre, la projection est très facile à calculer pour certains ensembles : boules euclidiennes,
l’orthant positif. Mais il n’existe pas de recette générale miracle pour projeter sur un
ensemble quelconque. Voici quelques classes de problèmes que l’on rencontre typique-
ment en pratique :
• Les problèmes de programmation linéaire9 , où f est affine, et la contrainte est définie
par des égalités et inégalités affines. Ces problèmes apparaissent naturellement dans
les sciences de la décision et de la planification. Un exemple célèbre est le problème du
transport optimal10 . Dans ce cas on pourra utiliser l’algorithme du simplexe11 (1947).
• Les problèmes de programation quadratique, où cette fois-ci f est quadratique12 (les
contraintes restent affines). Une famille d’algorithmes très efficaces (et même opti-
males en un certain sens) pour les résoudre sont les méthodes dites de point intérieur13
(1980-1999). Elles sont d’ailleurs si efficaces qu’elles permettent également de résoudre
des problèmes beaucoup plus difficiles (programmation semi-définie).
• Les problèmes de programmation convexe, où f est convexe et les contraintes sont
des inégalités convexes et égalités affines. Dans ce cas le problème est trop général,
mais selon la structure du problème on peut toujours trouver un algorithme adapté.
Citons par exemple la famille des méthodes dites d’éclatement (algorithmes du gra-
dient proximal, de Douglas-Rachford, ... ), très en vogue depuis les années 2000 pour
résoudre les problèmes de traitement d’image (défloutage d’image, augmenter la résolution,
diminuer le bruit, etc..). Ces méthodes sont en particulier très efficaces pour résoudre
8 C’est un résultat qui date de 2012, dû à J.-B. Baillon, P.L. Combettes et R. Cominetti.
9 https://fr.wikipedia.org/wiki/Optimisation_lin%C3%A9aire
10 https://images.math.cnrs.fr/Le-transport-optimal-numerique-et-ses-applications-Partie-1.
html?lang=fr
11 https://fr.wikipedia.org/wiki/Algorithme_du_simplexe
12 https://fr.wikipedia.org/wiki/Optimisation_quadratique
13 https://en.wikipedia.org/wiki/Interior-point_method
V.III. ALGORITHMES POUR L’OPTIMISATION SOUS CONTRAINTES 121
Remarque V.74 (Problème général). Ici on vient de voir que la méthode du gradient pro-
jeté converge si f est lisse, convexe, et C convexe. Que se passe-t-il si ces hypothèses ne
sont pas vérifiées ?
• f non convexe : Sans convexité, et même lorsqu’il n’y a pas de contrainte, cela se com-
plique. Déjà on sait que même si on converge on risque d’être coincé dans un minimi-
seur local voire un point critique (cf. x3 ). On sait également depuis longtemps (1950
environ) que sans convexité il est possible que l’algorithme du gradient ne converge
pas : les trajectoires peuvent tourner en rond.15 Mais récemment (2005-2015) on s’est
rendu compte que ce phénomène n’arrivait pas souvent . Pour des fonctions non-
convexes normales16 (polynomiales par exemple) la convergence vers un point
critique est garantie.
• C non convexe : Dans ce cas, la projection n’est plus définie de manière unique (cf.
Figure V.19). Mais on pourrait toujours implémenter l’algorithme en prenant à chaque
itération une projection quelconque. Dans ce cas on a les mêmes résultats que pour
f non convexe : la convergence vers un point critique du problème est garantie pour
des ensembles normaux .
14 https://fr.wikipedia.org/wiki/Lasso_(statistiques)
15 Les plus curieux pourront aller regarder ce GIF qui illustre ce fait avec une fonction non-convexe
connue sur le nom de mexican hat : https://raw.githubusercontent.com/Guillaume-Garrigos/
guillaume-garrigos.github.io/master/assets/maths/images/mex_trajectoire.gif
16 La définition de normale est un peu compliquée, mais pourrait être résumée par : sa définition ne
C = { x ∈ R N | g1 ( x ) ď 0, . . . , g p ( x ) ď 0, h1 ( x ) = 0, . . . , hq ( x )}
régulière
CSO KKT 2e ordre minimiseur local CNO KKT 1er ordre
si problème convexe
minimiseur global
Pour que l’implication minimiseur local =⇒ CNO KKT 1er ordre ait lieu, il faut que
la contrainte soit régulière en x̄, c’est-à-dire qu’elle vérifie l’une des deux propriétés :
Convexité(s) et Convergence de
méthodes de descente
Sommaire
A.I Un peu plus d’Analyse variationnelle . . . . . . . . . . . . . . . . . . . . . 124
A.I.1 Convexité(s) et monotonie(s) . . . . . . . . . . . . . . . . . . . . . . 124
A.I.2 Caractérisation de la convexité via la Hessienne . . . . . . . . . . . 126
A.I.3 Lipschitzianité et cocoercivité . . . . . . . . . . . . . . . . . . . . . . 127
A.II Convergence(s) de la méthode du gradient . . . . . . . . . . . . . . . . . . 130
A.II.1 Méthode du gradient : cas fortement convexe non C2 . . . . . . . . 130
A.II.2 Méthode du gradient : cas convexe . . . . . . . . . . . . . . . . . . . 132
A.II.3 Méthode du gradient projeté : cas convexe . . . . . . . . . . . . . . 137
A.II.4 Méthode du gradient optimal . . . . . . . . . . . . . . . . . . . . . . 139
Dans cette annexe nous commençons par montrer quelques caractérisations supplémentaires
de la convexité, forte convexité, et Lipschitzianité du gradient. Cela nous permet dans un
second temps de prouver des résultats laissés admis jusque là, ou tout simplement de
donner une preuve plus directe à certains Théorèmes :
123
124 ANNEXE A. ANNEXE : CONVEXITÉ(S) ET CONVERGENCE *
(∀ x, y ∈ R) x ď y ⇒ f ( x ) ď f (y).
Cette propriété est en fait équivalente à dire que y − x et f (y) − f ( x ) ont le même signe.
Autrement dit :
(∀ x, y ∈ R) ( f (y) − f ( x ))(y − x ) ě 0.
On peut alors étendre cette relation aux champs de vecteurs, et dire que F : R N → R N est
monotone si :
(∀ x, y ∈ R) h F (y) − F ( x ), y − x i ě 0.
On peut alors montrer (Proposition suivante) que la convexité d’une fonction f : R N −→
R est équivalente à la monotonie de son gradient ∇ f : R N −→ R N .
En sommant (1 − α) fois la relation (A.1) et α fois la relation (A.2), et en utilisant le fait que
(1 − α)( x − zα ) + α(y − zα ) = 0, on obtient l’inégalité de convexité.
ii) ⇒ iii) : On écrit
f (y) ě f ( x ) + h∇ f ( x ), y − x i
f ( x ) ě f (y) + h∇ f (y), x − yi.
f (y) − f ( x ) − h∇ f ( x ), y − x i
= g(y) − g( x ) − h∇ g( x ), y − x i + (µ/2)kyk2 − (µ/2)k x k2 − hµx, y − x i
= g(y) − g( x ) − h∇ g( x ), y − x i + (µ/2)ky − x k2 .
On conclut donc avec les Propositions III.30 et A.2.
i) ⇔ iii) On peut écrire :
h∇ f (y) − ∇ f ( x ), y − x i
= h∇ g(y) − ∇ g( x ), y − x i + µky − x k2 .
On conclut donc avec les Propositions III.30 et A.2.
126 ANNEXE A. ANNEXE : CONVEXITÉ(S) ET CONVERGENCE *
Proposition A.4 (Forte convexité via gradient II). Soit f ∈ Γµ (R N ) une fonction différentiable,
avec µ > 0. Alors les propriétés suivantes ont lieu :
1) (∀ x, y ∈ R N ) 1
2µ k∇ f ( y ) − ∇ f ( x )k
2 ě f (y) − f ( x ) − h∇ f ( x ), y − x i ;
2) (∀ x, y ∈ R N ) 1
µ k∇ f ( y ) − ∇ f ( x )k
2 ě h∇ f (y) − ∇ f ( x ), y − x i.
Démonstration. i) (voir [15, Theorem 2.1.10]) Soit x ∈ R N fixé, et soit φ(y) := f (y) −
h∇ f ( x ), yi. Puisque f ∈ Γµ (R N ) alors φ ∈ Γµ (R N ) aussi, comme somme d’un fonction
fortement convexe et d’une fonction convexe (car linéaire). On calcule ∇φ(y) = ∇ f (y) −
∇ f ( x ), et on en déduit que argminφ = { x }. On peut donc écrire d’après ii) que pour tout
y ∈ RN :
µ
φ( x ) = min φ(v) ě min φ(y) + h∇φ(y), v − yi + kv − yk2 .
v ∈R N v ∈R N 2
Or le terme de droite est un problème d’optimisation en v, fortement convexe, dont l’unique
solution v∗ vérifie la CNO du 1er ordre : ∇φ(y) + µ(v∗ − y) = 0. Autrement dit, v∗ =
y − µ1 ∇φ(y). On a donc
µ ∗
φ( x ) ě φ(y) + h∇φ(y), v∗ − yi + k v − y k2
2
1 1
= φ(y) − k∇φ(y)k2 + k∇φ(y)k2
µ 2µ
1
= φ(y) − k∇φ(y)k2
2µ
On a donc bien montré que
1
k∇φ(y)k2 ě φ(y) − φ( x ),
2µ
Théorème A.5 (Convexité via Hessienne). Soit f : U ⊂ R N → R, deux fois différentiable sur
U, et C ⊂ U convexe et ouvert. Alors les propriétés suivantes sont équivalentes :
i) f est convexe sur C, càd f ∈ Γ0 (C ) ;
A.I. UN PEU PLUS D’ANALYSE VARIATIONNELLE 127
ii) (∀ x ∈ C ) ∇2 f ( x ) 0.
Voici une preuve directe de ce résultat, qui ne passe pas par le cas univarié étudié dans
la Section III.I.3, mais utilise plutôt la monotonie du gradient :
Démonstration.
ii) ⇒ i) : Soit x ∈ C, et d ∈ R N quelconque ; il nous faut montrer que h∇2 f ( x )d, di ě 0.
D’après la Proposition I.78.iii), on a ∇2 f ( x ) = J (∇ f )( x ), donc :
où α ∈]0, 1[, et la dernière inégalité vient de l’hypothèse, et du fait que zα ∈ C par
convexité. On conclut donc avec la Proposition A.2.
Remarque A.7 (Cocoercivité). La propriété v) est bien plus forte et précise que la simple
monotonie de ∇ f (voir Proposition A.2.iii)). Cette propriété s’appelle la cocoercivité de
∇ f . Plus précisément, on dit que ∇ f est L1 -cocoercive. L’équivalence entre ∇ f est Lip-
schitzienne et ∇ f est cocoercive est connue sous le nom du Théorème de Baillon-
Haddad [16, Theorem 3.13].
Remarque A.8 (Dualité). Si on compare la Proposition A.6 avec les Propositions A.3 et
A.4, on voit qu’il y a beaucoup de propriétés similaires, mais en fait opposées. Par exemples
les termes en ∇ f (y) − ∇ f ( x ) s’échangent avec des termes en ky − x k et µ s’échange avec
1,1
L . C’est en fait une conséquence d’un principe de dualité entre Γµ (R ) et C 1 (R ), qui
1 N N
µ
n’est pas au programme.
iii) ⇒ iv) : Soit x, y ∈ R N , et posons g(y) = f (y) − h∇ f ( x ), yi. Puisque ∇ g(y) = ∇ f (y) −
∇ f ( x ), on en déduit que g ∈ CL1,1 (R N ). De plus, g est la somme d’une fonction convexe
et d’une forme linéaire, donc elle est convexe aussi. On voit que ∇ g( x ) = 0, donc x ∈
argmin g. On peut applique maintenant iii) à g, en les points y − L1 ∇ g(y) et y :
1 1 L 1
∇ g(y)) − g(y) − h∇ g(y), − ∇ g(y)i ď k − ∇ g(y)k2
g(y −
L L 2 L
1 1 1
⇔ g(y − ∇ g(y)) − g(y) + k∇ f (y) − ∇ f ( x )k2 ď k∇ f (y) − ∇ f ( x )k2
L L 2L
Puisque x ∈ argmin g, donc on obtient :
1 1
⇒ g( x ) − g(y) + k∇ f (y) − ∇ f ( x )k2 ď k∇ f (y) − ∇ f ( x )k2
L 2L
−1
⇔ f ( x ) − f (y) − h∇ f ( x ), x − yi ď k∇ f (y) − ∇ f ( x )k2 .
2L
iv) ⇒ v) : Il suffit d’utiliser iv) deux fois d’affilée en inversant les roles de x et y, et de faire
la somme.
A.I. UN PEU PLUS D’ANALYSE VARIATIONNELLE 129
µ L
(∀ x, y ∈ R N ) ky − x k2 ď f (y) − f ( x ) − h∇ f ( x ), y − x i ď ky − x k2 . (A.3)
2 2
Démonstration. On reprend (A.3) où les inégalités deviennent ici des égalités, et on conclut
avec b = ∇ f (0) et c = f (0).
Remarque A.11 (Γµ et CL1,1 combinés). Lorsque on a une fonction dans Γµ (R N ) ∩ CL1,1 (R N ),
on peut combiner leurs propriétés ! Par exemple en combinant Proposition A.6.v) et A.3.iii),
on obtient
µ 1
h∇ f (y) − ∇ f ( x ), y − x i ě ky − x k2 + k∇ f (y) − ∇ f ( x )k2 .
2 2L
Mais le fait est que l’on a ici en quelque sorte utilisé séparément la forte convexité et le
gradient Lipschitz. Lorsque les deux sont réunis, on peut obtenir des constantes un peu
meilleures (ce qui aura de l’importance par la suite).
Proposition A.12. Soit f ∈ Γµ (R N ) avec µ > 0, et soit L > µ. Alors les propriétés suivantes
sont équivalentes :
i) ∇ f est L-Lipschitzien.
ii) (∀ x, y ∈ R N ) x k2 + 1 2
µL
h∇ f (y) − ∇ f ( x ), y − x i ě µ+ L k y − µ+ L k∇ f ( y ) − ∇ f ( x )k .
µ
0 ď g(y) − g( x ) − h∇ g( x ), y − x i = f (y) − f ( x ) − h∇ f ( x ), y − x i − k y − x k2
2
Cas µ = L : Dans ce cas on a i) ⇔ g ∈ C01,1 (R N ), ce qui est équivalent à dire que ∇ g est
constante. D’autre part, ii) est équivalente à :
1 √ 1 √ 1 1
h √ (∇ f (y) − ∇ f ( x )), µ(y − x )i ě k µ(y − x )k2 + k √ (∇ f (y) − ∇ f ( x ))k2
µ 2 2 µ
1 √ 1
⇔ 0 ě k µ(y − x ) − √ (∇ f (y) − ∇ f ( x ))k2
2 µ
√ 1
⇔ µ(y − x ) = √ (∇ f (y) − ∇ f ( x ))
µ
⇔ ∇ g ( y ) = ∇ g ( x ),
cette dernière propriété voulant dire que ∇ g est constante.
Cas L > µ : On utilise la Proposition A.6.v) pour écrire que g ∈ CL1,1
−µ (R ) est équivalent
N
µL 1
h∇ f ( x ), x − x ∗ i ě k x − x ∗ k2 + k∇ f ( x )k2 .
µ+L µ+L
En insérant cette inégalité dans (A.4) (sur le terme proportionnel à α > 0), et en utilisant
la définition de α, on obtient :
+ ∗ 2 ∗ 2 µL 2 2 1
k x − x k ď k x − x k 1 − α2ρ + k∇ f ( x )k ρ − α2ρ
µ+L µ+L
∗
−2ρ(1 − α)h x − x , ∇ f ( x )i
= k x − x ∗ k2 (1 − µLρ2 ) − 2ρ(1 − α)h x − x ∗ , ∇ f ( x )i.
(∀ x ∈ R N ) µk x − x ∗ k2 ď h∇ f ( x ), x − x ∗ i ď Lk x − x ∗ k2 . (A.5)
Lρ2
+
f ( x ) − inf f ď f ( x ) − inf f − ρ − k∇ f ( x )k2 .
2
132 ANNEXE A. ANNEXE : CONVEXITÉ(S) ET CONVERGENCE *
Puisque f est fortement convexe, on peut utiliser la Proposition A.4.i) qui nous donne :
1 1
f ( x ) − inf f = f ( x ) − f ( x ∗ ) − h∇ f ( x ∗ ), x − x ∗ i ď k∇ f ( x ) − ∇ f ( x ∗ )k2 = k∇ f ( x )k2 .
2µ 2µ
En combinant ces deux dernières inégalités, et en utilisant le fait que ρ = α/L avec α ∈
]0, 2[, on obtient :
1 µ
f ( x + ) − inf f ď f ( x ) − inf f − α(2 − α)k∇ f ( x )k2 ď ( f ( x ) − inf f ) 1 − α(2 − α) .
2L L
On conclut avec le fait que α(2 − α) ∈]0, 1[.
Démonstration du Théorème IV.42 avec le bon θ. La preuve exacte de ce résultat est assez tech-
nique, et peut être trouvée dans [17, Theorem 3.3].
(∀ x, y ∈ R N ) kAρ x − Aρ yk ď k x − yk.
Démonstration. Si on regarde la preuve du Théorème IV.37 (dans le Chapitre IV ou dans
la Section A.II.1), on voit qu’elle marche encore si µ = 0 (ce qui est notre cas ici) et si
ρ ∈ [0, 2/L]. On en déduit donc que pour tout ρ ∈ [0, 2/L], Aρ est θ-Lipschitzienne, avec
k x k +1 − x ∗ k ď k x k − x ∗ k . (A.6)
Or le fait que cette suite soit décroissante ne veut pas dire qu’elle tend vers 0. Il va donc
falloir obtenir des inégalités plus précises pour améliorer (A.6).
Démonstration. On calcule :
1 1
k x + − x ∗ k2 − k x − x ∗ k2
2ρ 2ρ
1 1
= − k x − x+ k2 − h x − x+ , x+ − x ∗ i en développant les carrés
2ρ ρ
1
= − k x − x+ k2 − h∇ f ( x ), x+ − x ∗ i d’après la définition de x+ (A.7)
2ρ
1
= − k x − x+ k2 + h∇ f ( x ), x ∗ − x i − h∇ f ( x ), x+ − x i en faisant ± x.
2ρ
D’une part, on sait via la convexité de f et l’inégalité des hyperplans (Proposition III.13.ii))
que
h∇ f ( x ), x ∗ − x i ď f ( x ∗ ) − f ( x k )
L
−h∇ f ( x ), x+ − x i ď k x + − x k2 + f ( x ) − f ( x + ).
2
En combinant tout cela on en déduit que
1 1 L 1
k x + − x ∗ k2 − k x − x ∗ k2 ď f ( x ∗ ) − f ( x + ) + − k x + − x k2 .
2ρ 2ρ 2 2ρ
Démonstration du Théorème IV.44 pour un pas court. On suppose ici que ρL ∈]0, 1]. L’idée de
la preuve va être de montrer qu’une certaine énergie décroit au cours des itérations. On
connait déjà deux quantités qui décroissent : f ( xk ) − inf f (cf. Proposition IV.34), ainsi que
k xk − x ∗ k2 (cf. Lemme A.14). Dans cette preuve on va considérer une certaine combinaison
de ces deux quantités :
1
Ek := k ( f ( xk ) − inf f ) + ck xk − x ∗ k2 , avec c= . (A.8)
2ρ
Pour montrer que l’énergie Ek décroı̂t, nous allons montrer que sa variation est négative :
Ek+1 − Ek (A.9)
∗ 2 ∗ 2
= (k + 1)( f ( xk+1 ) − inf f ) − k( f ( xk ) − inf f ) + ck xk+1 − x k − ck xk − x k
= f ( xk+1 ) − inf f + k( f ( xk+1 − f ( xk )) + c k xk+1 − x ∗ k2 − k xk − x ∗ k2
∗ 2 ∗ 2
ď f ( xk+1 ) − inf f + c k xk+1 − x k − k xk − x k ,
134 ANNEXE A. ANNEXE : CONVEXITÉ(S) ET CONVERGENCE *
où dans la dernière inégalité on utilise le fait que f ( xk+1 ) − f ( xk ) ď 0 (cf. Proposition
IV.34). Avec le résultat du Lemme A.14 on obtient
k ( f ( xk ) − inf f ) ď Ek ď E0 = ck x0 − x ∗ k2 .
k x0 − x ∗ k2
(∀k ě 1) f ( xk ) − inf f ď .
2ρk
2h x, yi = k x k2 + kyk2 − k x − yk2
Le résultat suivant montre que la méthode du gradient est un peu mieux que 1-Lipschitzienne.
C’est un résultat analogue au Lemme V.57 pour la projection.
2−ρL
avec γ = ρL .
A.II. CONVERGENCE(S) DE LA MÉTHODE DU GRADIENT 135
k Aρ x − Aρ y k 2
= k(1 − α)( x − y) + α( Tx − Ty)k car Aρ = (1 − α) I + αT
= (1 − α)k x − yk + αk Tx − Tyk − α(1 − α)k( I − T ) x − ( I − T )yk2 .
2 2
(Lemme A.15)
D’une part, on sait que T = A2/L est 1-Lipschitzienne (Lemme A.13), donc on a
(1 − α )
α(1 − α)k( I − T ) x − ( I − T )yk2 = k( I − Aρ ) x − ( I − Aρ )yk2 .
α
En combinant toutes ces inégalités on conclut que
1−α
k Aρ x − Aρ y k 2 ď k x − y k 2 − k( I − Aρ ) x − ( I − Aρ )yk2 .
α
1− α 2−ρL
où α = ρL .
Démonstration du Théorème IV.44 pour un pas long. On suppose ici que ρL ∈ [1, 2[. Ici nous
allons considérer la même énergie qu’en (A.8), mais avec une constante différente :
ρL − 1
∗ 2 1
Ek := k ( f ( xk ) − inf f ) + ck xk − x k , avec c= 1+ > 0, (A.11)
2ρ γ
où γ > 0 est la constante apparaissant dans le Lemme A.16. Pour montrer que l’énergie
Ek décroı̂t, on commence comme pour le pas court et on obtient la même chose que (A.9) :
∗ 2 ∗ 2
Ek+1 − Ek ď f ( xk+1 ) − inf f + c k xk+1 − x k − k xk − x k . (A.12)
k x k +1 − x ∗ k 2 − k x k − x ∗ k 2 ď − γ k x k +1 − x k k 2 . (A.14)
γ
Posons σ := γ+ρL −1 . C’est un simple exercice que de vérifier que, puisque ρL ∈ [1, 2[,
alors γ > 0 et σ ∈]0, 1]. On va donc multiplier (A.13) par σ, et (A.14) par (1 − σ), pour
obtenir
k x k +1 − x ∗ k 2 − k x k − x ∗ k 2 (A.15)
2 2
ď −σ2ρ( f ( xk+1 ) − inf f ) + σ(ρL − 1)k xk+1 − xk k − (1 − σ )γk xk+1 − xk k
= −σ2ρ( f ( xk+1 ) − inf f ) + (σ(ρL − 1) − (1 − σ)γ) k xk+1 − xk k2 .
c k x0 − x ∗ k2
(∀k ě 1) f ( xk ) − inf f ď ,
k
1+(ρL−1)2
1
où ici c = 2ρ 2−ρL .
Démonstration. (Voir [16, Lemma 5.2]) D’après i), on sait que la suite xk est bornée. Donc il
existe une sous-suite convergente xnk → x∞ , avec x∞ ∈ C d’après ii). Puisque x∞ ∈ C on
peut utiliser i) pour dire que toute la suite k xn − x∞ k2 tend vers une limite, notons-là `. Si
c’est vrai pour toute la suite, ça l’est aussi pour notre sous-suite : k xnk − x∞ k2 → `. Or on
sait que k xnk − x∞ k2 → 0 ; donc ` = 0. D’où k xn − x∞ k2 → 0, et donc xn converge vers un
élément de C.
A.II. CONVERGENCE(S) DE LA MÉTHODE DU GRADIENT 137
Démonstration. Il suffit d’utiliser le fait que A = projC ◦Aρ , où projC et Aρ sont
1-Lipschitziennes (Théorème V.58 et Lemme A.13).
Pour un pas court on peut obtenir la même estimation que pour la méthode du gradient :
1 1 1 1
k x + − x ∗ k2 − k x − x ∗ k2 = − k x − x + k2 − h x − x + , x + − x ∗ i.
2ρ 2ρ 2ρ ρ
138 ANNEXE A. ANNEXE : CONVEXITÉ(S) ET CONVERGENCE *
Maintenant il nous faut exprimer comment x et x+ sont reliés. Pour cela on revient à la
définition x+ := projC ( x − ρ∇ f ( x )), et on applique la caractérisation de la projection par
les angles (Proposition V.53) pour écrire
h x ∗ − x+ , ( x − ρ∇ f ( x )) − x+ i ď 0
⇔ h x ∗ − x+ , x − x+ i ď ρh x ∗ − x+ , ∇ f ( x )i
1
⇔ − h x − x+ , x+ − x ∗ i ď −h x+ − x ∗ , ∇ f ( x )i.
ρ
On a donc obtenu la même inégalité qu’en (A.7). On peut donc continuer de la même
façon que dans la preuve du Lemme A.14, et conclure.
Démonstration du Théorème IV.44 pour un pas court. La preuve est exactement la même que
pour la méthode du gradient avec pas court (voir la Section A.II.2). La seule différence
est qu’il faudra utiliser les variations du Lemme A.19, et le fait que f ( xk ) est décroissante
(Proposition V.65).
kAx − Ayk2
= k projC ◦Aρ x − projC ◦Aρ yk2
ď kAρ x − Aρ yk2 − k( I − projC ) ◦ Aρ x − ( I − projC ) ◦ Aρ yk2
2 − ρL
ď k x − y k2 − k( I − Aρ ) x − ( I − Aρ )yk2 − k( I − projC ) ◦ Aρ x − ( I − projC ) ◦ Aρ yk2
ρL
Il nous reste à étudier le terme négatif du membre de droite. Pour simplifier les notations,
on pose u = ( I − Aρ ) x − ( I − Aρ )y et v = ( I − projC ) ◦ Aρ x − ( I − projC ) ◦ Aρ y, de telle
manière que le terme qui nous intéresse est :
2 − ρL
βkuk2 + kvk2 , où β = > 0.
ρL
A.II. CONVERGENCE(S) DE LA MÉTHODE DU GRADIENT 139
β 1 1
k u k2 + kvk2 = (1 − t)kuk2 + tkvk2 avec t = ∈ [0, 1]
1+β 1+β 1+β
= k(1 − t)u + tvk2 + t(1 − t)ku − vk2 (Lemme A.15)
ě t(1 − t)ku − vk2
= t(1 − t)k( I − A) x − ( I − A)yk2 ,
Démonstration du Théorème V.67 pour un pas long. On suppose ici que ρL ∈ [1, 2[. La preuve
est exactement la même que pour la méthode du gradient avec pas long (voir la Section
A.II.2). La première différence est qu’on utilisera les Lemmes A.20 et A.19 au lieu des A.16
et A.14. En particulier la valeur de γ va changer, ce qui ne change rien à la preuve, mis à
part la valeur de la constante c, qui vaut ici 2(2−L ρL) . La deuxième différence est que pour
une solution x ∗ ∈ argminC f , on a besoin du fait que Ax ∗ = x ∗ . Ceci a déjà été vérifié dans
la Proposition V.64.
Démonstration du Théorème IV.57 avec un θ quelconque. (Voir [14, Eq. (8.47), p.238]) Ici on note
ρk le pas optimal calculé à l’itération k. D’après le Lemme de Descente (IV.2), on sait que
pour tout ρ > 0 on a
L
f ( xk − ρ∇ f ( xk )) ď f ( xk ) + h∇ f ( xk ), −ρ∇ f ( xk )i + kρ∇ f ( xk )k2 .
2
Si on minimise le terme de gauche par rapport à ρ, on obtient par définition f ( xk+1 ). D’un
autre côté si on minimise le terme de droite par rapport à ρ, on voit que c’est un polynôme
du second degré en ρ. Il est alors facile de voir que le ρ optimal pour le membre de droite
est ρ = L1 , ce qui nous donne
1
f ( x k +1 ) ď f ( x k ) − k∇ f ( xk )k2 .
2L
140 ANNEXE A. ANNEXE : CONVEXITÉ(S) ET CONVERGENCE *
1
f ( xk ) − inf f ď k∇ f ( xk )k2 .
2µ
1 µ
f ( xk+1 ) − inf f ď f ( xk ) − inf f − k∇ f ( xk )k2 ď (1 − )( f ( xk ) − inf f ).
2L L
µ
D’où le résultat avec θ = 1 − L .
Démonstration du Théorème IV.57 avec le bon θ. Voir [6, Theorem 1.2].
Bibliographie
[3] V. B ECK , J. M ALICK , AND G. P EYR É, Objectif Agrégation, H&K, 2004.
[7] J.-B. H IRIART-U RRUTY, Optimisation et analyse convexe : Exercices et problèmes corrigés,
avec rappels de cours, EDP Sciences, Ulis, France, 2009.
[8] J.-B. H IRIART-U RRUTY AND C. L EMARECHAL, Convex Analysis and Minimization Al-
gorithms I : Part 1 : Fundamentals, Springer Science & Business Media, 1996.
[9] W. K ARUSH, Minima of functions of several variables with inequalities as side constraints,
M. Sc. Dissertation. Dept. of Mathematics, Univ. of Chicago, (1939).
141
142 BIBLIOGRAPHIE
[13] J.-L. L AGRANGE, Manière plus simple et plus générale de faire usage de la formule de
l’équilibre donnée dans la section deuxième, in Mécanique Analytique, vol. 1, 1788,
pp. 77–112.
[15] Y. N ESTEROV, Introductory Lectures on Convex Optimization, vol. 87, Springer Science
& Business Media, 2004.