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

231 vues73 pages

Introduction à l'optimisation mathématique

Ce document présente un cours d'optimisation. Il introduit des concepts clés comme les problèmes d'optimisation, l'existence et l'unicité de solutions, et la convexité. Différents exemples en une dimension sont également discutés.

Transféré par

Baye Diop

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

Formats disponibles

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

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

231 vues73 pages

Introduction à l'optimisation mathématique

Transféré par

Baye Diop

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

Formats disponibles

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

Université Paris Diderot L3 MIASHS – Année 2015-2016

Cours d’Optimisation

Matthieu Bonnivard (d’après le polycopié d’Olivier Bokanowski)

Références bibliographiques :
— Philippe G. Ciarlet, Introduction à l’analyse numérique matricielle et à l’optimi-
sation.
— Jean-Baptiste Hiriart-Urruty, Optimisation et analyse convexe (exercices cor-
rigés).
— Grégoire Allaire, Analyse numérique et optimisation, chap. 9 et 10.

1
2
Chapitre 1

Introduction à l’optimisation

1.1 Généralités. Exemple introductif

L’optimisation consiste en la recherche du minimum (ou du maximum) d’une cer-

taine quantité, appelée coût ou objectif. Dans ce cours, on supposera que le coût dépend
de N variables réelles, rassemblées en un vecteur x = (x1 , . . . , xN ) ∈ RN , et qui four-
nissent une valeur J(x) où J est une fonction de RN dans R. En général, les variables
x1 , . . . , xN ne seront pas autorisées à prendre n’importe quelle valeur, mais devront sa-
tisfaire des contraintes que l’on représentera par un sous ensemble K ⊂ RN . On écrira
les problèmes d’optimisation sous la forme générale suivante :

(P) inf J(x).

x∈K

On dit que problème (P) admet une solution s’il existe un choix de variables x0 ∈ K
tel que
∀x ∈ K J(x0 ) ≤ J(x).

On dit alors que x0 est un minimiseur (ou point de minimum) de J sur K, et que J(x0 )
est un minimum de J sur K.

Exemple 1.1. Un étudiant doit réviser pour ses examens. Il a 4 matières à passer et
dispose d’une semaine de révisions, ce qui représente 42 heures de travail (en comptant 6
jours et 7 heures par jour). Pour i = 1, . . . , 4, on note xi le nombre d’heures de révisions

3
pour la matière numéro i. L’ensemble K est alors décrit par
4
( )
X
K = x ∈ R4 , ∀1 ≤ i ≤ 4 xi ≥ 0, xi ≤ 42
i=1
On note M (x) la moyenne des notes (sur 20) obtenues par l’étudiant après avoir révisé xi
heures la matière numéro i. L’objectif est de maximiser M (x), ce qui revient à minimiser
la différence 20 − M (x). On peut donc formuler le problème d’optimisation suivant :
inf (20 − M (x))
x∈K
Remarque 1.1. Bien sûr, dans l’exemple précédent, on ne connaı̂t pas la formule
de M (x) de manière explicite ! De plus, il est évident que la moyenne obtenue ne
dépend pas seulement du nombre d’heures de révisions, mais de beaucoup d’autres
paramètres (assiduité en TD, concentration lors des révisions, qualité du sommeil la
veille des épreuves...). Le choix de la fonction coût découle d’un choix de modélisation
du phénomène étudié. Cependant, dans ce cours, les fonctions coût seront considérées
comme des données du problème.
Nous allons voir que la résolution d’un problème d’optimisation dépend en grande
partie des propriétés mathématiques de la fonction J. Pour l’illustrer, plaçons-nous en
dimension N = 1.

1.2 Quelques exemples en dimension N = 1

On considère un seul paramètre x ∈ R, et une fonction coût J : R → R. On choisit
K = R ou K = [c, d] un intervalle fermé non vide.
Exemple 1.2. Cas d’une fonction J générale (continue), qui n’a pas de min ni de max
sur R (par exemple, affine), mais un min et un max sur tout intervalle fermé borné.
Exemple 1.3. Cas d’une fonction discontinue, qui possède un inf sur un intervalle
fermé borné, mais n’atteint pas cet inf.
Exemple 1.4. Cas d’une fonction J convexe, mais pas strictement convexe (son graphe
contient un segment) : existence d’un minimum mais pas unicité.
Exemple 1.5. Cas d’une fonction strictement convexe, dérivable : le minimum sur R
est atteint au point x0 qui satisfait J 0 (x0 ) = 0. On dit que x0 est un point critique de
J.

4
Bilan. Face au problème (P),
— l’existence d’un minimum est liée à la continuité de J,
— l’unicité du minimiseur x0 est liée à la convexité (stricte) de J,
— l’équation satisfaite par x0 est associée à la dérivée de J.
Toutes ces propriétés joueront des rôles analogues en dimension N ; la dérivée sera
remplacée par les dérivées partielles ou dérivées directionnelles de J.

1.3 Rappels de calcul différentiel

On se place dans RN , muni de la norme euclidienne k · k et du produit scalaire
euclidien h·, ·i. Pour x ∈ RN et R > 0, on note BR (x) la boule ouverte de centre x et
de rayon R et B R (x) la boule fermée correspondante :

BR (x) = y ∈ RN ,

ky − xk < R
B R (x) = y ∈ RN ,

ky − xk ≤ R

Définition 1.1. 1. Un ensemble U ⊂ RN est ouvert si

∀x ∈ U ∃R > 0, B(x, R) ⊂ U

2. Un ensemble F ⊂ RN est fermé si son complémentaire RN \ F est ouvert.

Définition 1.2. Soit U ⊂ RN un ouvert et J : U → R une application. Soit u ∈ U .

1. On dit que J est différentiable au point u s’il existe une application linéaire
L ∈ L(RN , R) t.q. pour tout h ∈ RN t.q. u + h ∈ U ,

J(u + h) = J(u) + L(h) + o(khk).

La notation o(khk) signifie qu’il existe une fonction ε : RN → R t.q. limh→0 ε(h) =
0, et qui permette d’écrire le reste sous la forme o(khk) = khk ε(h).
Si L existe, elle est unique ; on la note L = DJ(u).
2. Soit d ∈ RN \ {0}. On dit que J admet une dérivée directionnelle dans la
direction d, au point u, si l’application t ∈ R 7→ J(u + td) est dérivable en 0. Si
c’est le cas, on note cette dérivée
∂J J(u + td) − J(u)
(u) := lim .
∂d t→0 t

5
Si d = ei est l’un des vecteurs de base de RN , on appelle cette dérivée direction-
nelle la i-ème dérivée partielle de J au point u, que l’on note
∂J J(u + tei ) − J(u) J(u1 , . . . , ui−1 , ui + t, ui+1 , . . . , uN ) − J(u1 , . . . , uN )
(u) := lim = lim .
∂xi t→0 t t→0 t
Proposition 1.1. Si J : U → R est différentiable au point u ∈ U , alors elle admet
des dérivées directionnelles en toute direction au point u (et en particulier, des dérivées
partielles). De plus, sa différentielle au point u s’écrit
N
X ∂J
∀h = (h1 , . . . , hN ) ∈ RN DJ(u)(h) = (u) hi .
∂xi
i=1

En introduisant le gradient de J au point u, défini par

T
∂J ∂J
∇J(u) = (u) . . . (u) ,
∂x1 ∂xN
on peut écrire de manière condensée

DJ(u)(h) = h∇J(u), hi. (1.1)

On montre que si J est différentiable au point u, alors ∇J(u) est l’unique vecteur de
RN t.q. la relation (1.1) soit vérifiée.

Remarque 1.2 (Calcul du gradient). Pour calculer le gradient de J au point u, il n’est

pas toujours nécessaire de calculer explicitement toutes les dérivées partielles. Une autre
méthode consiste à établir un développement limité de J sous la forme suivante :

J(u + h) = J(u) + hw, hi + o(khk)

où w ∈ RN est un certain vecteur fixé. Alors, on peut affirmer que J est différentiable
en u, et que
w = ∇J(u).

Exercice 1.1. Montrer que si J est différentiable en u, alors pour tout d ∈ RN \ {0},
sa dérivée directionnelle dans la direction d s’écrit
∂J
(u) = h∇J(u), di.
∂d

6
Chapitre 2

Existence de minimum,
convexité, unicité

Cadre général. On considère un ouvert U ⊂ RN et une fonction J : U → R (fonction

coût). On se donne un ensemble fermé non vide K ⊂ U et on s’intéresse au problème
d’optimisation suivant :
(P) inf J(x)
x∈K

On notera I = inf x∈K J(x) avec la convention suivante. Soit A := {J(x), x ∈ K} ; A

est une partie de R, non vide car K est non vide. On distingue deux cas de figure :
(i) si A n’est pas minorée, on pose I = −∞ ;
(ii) si A est minorée, elle possède une borne inférieure et on pose I = inf A ∈ R.
La première question que l’on se pose est de savoir si I est atteint, c’est-à-dire s’il existe
x0 ∈ K t.q. I = J(x0 ).

2.1 Existence de minimum

Définition 2.1 (Minimum global, minimum local). Soit x0 ∈ K. On dit que la fonction
J admet
(i) un minimum global sur K au point x0 , si

∀x ∈ K, J(x0 ) ≤ J(x);

7
(ii) un minimum local sur K au point x0 , si

∃R > 0, ∀x ∈ BR (x0 ) ∩ K, J(x0 ) ≤ J(x).

Pour établir l’existence de minimiseurs, la première étape consiste à approcher la

borne inférieure I à l’aide d’une suite de points xn ∈ K, qu’on appelle suite minimisante.

Définition 2.2. On appelle suite minimisante pour le problème (P) toute suite
(xn )n∈N à valeurs dans RN t.q.

∀n ∈ N, xn ∈ K et lim J(xn ) = I.
n→∞

Proposition 2.1. Pour tout problème (P), il existe au moins une suite minimisante.

Preuve. On introduit l’ensemble A := {J(x), x ∈ K}. Distinguons deux cas de figure :

(i) Si A n’est pas minorée, alors par convention, I = −∞. De plus, pour tout m ∈ R
il existe un point x ∈ K tel que J(x) < m. Pour tout n ∈ N, en prenant m = −n
on en déduit l’existence d’un point xn ∈ K tel que J(xn ) < −n. En passant à la
limite dans l’inégalité on obtient limn→∞ J(xn ) = −∞, donc (xn ) est une suite
minimisante.
(ii) Si A est minorée, alors elle possède une borne inférieure I (comme une partie
non vide et minorée de R). Alors par définition, pour tout ε > 0, il existe yε ∈ A
t.q. I ≤ yε < I + ε et par définition de A, il existe un xε ∈ K t.q. yε = J(xε ).
Ainsi pour tout ε > 0, il existe xε ∈ K t.q.

I ≤ J(xε ) < I + ε.

On l’applique en remplaçant ε par 1

n : pour tout n ∈ N∗ , il existe xn ∈ K t.q.
1
I ≤ J(xn ) < I +.
n
En passant à la limite quand n → ∞, on obtient que limn→∞ J(xn ) = I.

Pour conclure à l’existence d’un minimum global pour le problème (P), on aimerait
montrer que J(xn ) converge vers J(x), où x est un certain point de K ; on aurait
alors J(x) = I. En général, on n’aura pas la convergence de la suite (xn ) vers x, mais
seulement la convergence d’une suite extraite (xϕ(n) ), qui découlera de propriétés de
compacité. Le passage à la limite dans la suite numérique (J(xϕ(n) )) nécessitera quant
à lui la continuité de la fonction J au point x.

8
Théorème 2.1. Si K est un compact non vide de RN (i.e., un fermé borné), et si J
est continue en tout point de K, alors J admet un minimum sur K.

Preuve. Soit (xn )n∈N une suite minimisante. (xn ) est à valeurs dans K, qui est compact,
donc il existe x ∈ K et une suite extraite (xϕ(n) ) t.q. limn→∞ xϕ(n) = x. Comme J est
continue en x,
lim J(xϕ(n) ) = J(x).
n→∞
La suite (J(xϕ(n) )) étant une suite extraite de (J(xn )), elle converge vers la même limite,
d’où I = J(x).

Lorsque l’ensemble des contraintes K n’est pas compact, on pourra pallier cette
difficulté en considérant des fonctions J qui contraignent les suites minimisantes à rester
dans un ensemble compact de RN . On introduit pour cela la notion de fonction coercive.

Définition 2.3. On suppose U non borné. On dit que J est coercive (ou encore,
infinie à l’infini), si
lim J(x) = +∞.
x∈U,kxk→∞

Théorème 2.2. Soit K ⊂ RN t.q. (i) K est fermé, non vide, (ii) J est continue en
tout point de K, et (iii) J est coercive. Alors J admet un minimum global sur K.

Preuve.
L’infimum I de J sur K étant soit un réel, soit égal à −∞, on peut choisir un réel
M t.q. M > I. Par définition de la coercivité, il existe alors R > 0 t.q.

∀x ∈ U, kxk > R ⇒ J(x) ≥ M > I. (2.1)

Soit (xn )n∈N une suite minimisante. Par définition, limn→∞ J(xn ) = I ; comme M > I,
il existe donc un entier N t.q.

∀n ∈ N, n ≥ N ⇒ J(xn ) < M.

D’après (2.1), on en déduit que pour n ≥ N , kxn k ≤ R. Ainsi, la suite minimisante

(xn )n≥N est à valeurs dans K ∩ BR (0), qui est compact ; on peut donc conclure en
reprenant le raisonnement de la preuve du théorème 2.1.

9
2.2 Convexité et unicité du minimiseur
Soit U ⊂ RN un ouvert, J : U → R une application et K ⊂ U un ensemble non
vide.

Définition 2.4. On dit que l’ensemble K est convexe si

∀θ ∈ [0, 1], ∀(x, y) ∈ K 2 , (1 − θ)x + θy ∈ K.

Cela signifie que si deux points x, y sont dans K, alors le segment [x, y], qui relie ces
points, est contenu dans K.

Exemple 2.1. Les sous-ensembles convexes de R sont les intervalles.

Exercice 2.1. Soit N : RN → R+ une norme quelconque. Montrer que la boule unité
(fermée) pour cette norme est nécessairement convexe.

Définition 2.5. On suppose que K est convexe. On dit que

• l’application J est convexe sur K si

∀θ ∈ (0, 1), ∀(x, y) ∈ K 2 , J((1 − θ)x + θy) ≤ (1 − θ)J(x) + θJ(y)

• J est strictement convexe sur K si

∀θ ∈ (0, 1), ∀(x, y) ∈ K 2 , x 6= y ⇒ J((1 − θ)x + θy) < (1 − θ)J(x) + θJ(y)

• J est α-convexe sur K (pour un α ≥ 0), si

α
∀θ ∈ (0, 1), ∀(x, y) ∈ K 2 , J((1 − θ)x + θy) + θ(1 − θ)kx − yk2 ≤ (1 − θ)J(x) + θJ(y)
2
En particulier si J est α-convexe avec α > 0, elle est strictement convexe.

Exemple 2.2. x ∈ RN 7→ kxk est convexe mais pas strictement convexe.

Proposition 2.2. Si J est strictement convexe sur K, alors J admet au plus un mini-
miseur sur K.

Preuve. Par l’absurde : supposons que J, strictement convexe sur K, possède deux
minimiseurs distints, x et y, sur K. On note m la valeur commune du minimum :

10
m = J(x) = J(y). Soit z = 12 (x + y) le milieu du segment [x, y]. K étant convexe, z ∈ K
et par la stricte convexité de J,
1 1 1 1
J(z) = J( x + y) < J(x) + J(y) = m.
2 2 2 2
Cela contredit la définition du minimum de J sur K.

Critères de convexité pour des fonctions différentiables.

Proposition 2.3. On suppose que J est différentiable en tout point de K. On a

équivalence entre :
(i) J convexe sur K.
(ii) ∀(u, v) ∈ K 2 , J(v) ≥ J(u) + h∇J(u), v − ui.
(iii) ∀(u, v) ∈ K 2 , h∇J(v) − ∇J(u), v − ui ≥ 0.

Remarque 2.1. L’équation de l’hyperplan tangent au graphe de J, au point (u, J(u)) ∈

U × R, s’écrit

y = J(u) + h∇J(u), x − ui, pour x ∈ RN , y ∈ R.

La relation (ii) signifie géométriquement que le graphe de J est au-dessus de son hy-
perplan tangent en tout point.

Preuve. (i) ⇒ (ii) : Notons uθ := (1 − θ)u + θv = u + θ(v − u). Pour θ ∈]0, 1], on a
J(uθ ) ≤ (1 − θ)J(u) + θJ(v) = J(u) + θ(J(v) − J(u)), donc
1 θ→0+
J(v) − J(u) ≥ (J(uθ ) − J(u)) → h∇J(u), v − ui.
θ
(ii) ⇒ (i) : On a

J(u) ≥ J(uθ ) + h∇J(uθ ), u − uθ i (2.2)

J(v) ≥ J(uθ ) + h∇J(uθ ), v − uθ i. (2.3)

En sommant (1 − θ) fois la relation (2.2) et θ fois la relation (2.3), et en utilisant le fait

que (1 − θ)(u − uθ ) + θ(v − uθ ) = 0, on obtient l’inégalité de convexité.
(ii) ⇒ (iii) : On écrit

J(v) ≥ J(u) + h∇J(u), v − ui (2.4)

J(u) ≥ J(v) + h∇J(v), u − vi. (2.5)

11
En sommant on obtient l’inégalité désirée.
(iii) ⇒ (ii) : Soit g(t) := J(u + t(v − u)) pour t ∈ [0, 1]. On remarque que g 0 (t) =
h∇J(ut ), v − ui, et en particulier que g 0 (0) = h∇J(u), v − ui. Ainsi, par hypothèse,
1
g 0 (t) − g 0 (0) = h∇J(ut ) − ∇J(u), v − ui = h∇J(ut ) − ∇J(u), ut − ui ≥ 0.
t
D’autre part, comme g ∈ C([0, 1]) ∩ ∆(]0, 1[), d’après le théorème des accroissements
finis, il existe c ∈ (0, 1) tel que g(1)−g(0)
1 = g 0 (c) ≥ g 0 (0). Ainsi g(1) ≥ g(0) + g 0 (0), ce
qui donne l’inégalité désirée.

Il existe des critères analogues permettant de caractériser les fonctions différentiables

strictement convexes. C’est l’objet de la proposition suivante, dont la preuve est laissée
en exercice.

Proposition 2.4. On suppose que J est différentiable en tout point de K. Alors les
propriétés suivantes sont équivalentes :
(i) J strictement convexe sur K.
(ii) ∀(u, v) ∈ K 2 , u 6= v ⇒ J(v) > J(u) + h∇J(u), v − ui.
(iii) ∀(u, v) ∈ K 2 , u 6= v ⇒ h∇J(v) − ∇J(u), v − ui > 0.

Exercice 2.2. On suppose J différentiable en tout point de K. Soit α ≥ 0. Montrer les

équivalences suivantes :
α
J est α-convexe sur K ⇐⇒ ∀(u, v) ∈ K 2 , J(v) ≥ J(u) + h∇J(u), v − ui + kv − uk2
2
⇐⇒ ∀(u, v) ∈ K 2 , h∇J(v) − ∇J(u), v − ui ≥ αkv − uk2

Il existe aussi quelques critères de convexité portant sur la différentielle seconde de

Théorème 2.3. On suppose que K = RN . Soit J : RN → R, deux fois différentiable

sur RN . Alors

N N N 2
J est convexe sur R ⇐⇒ ∀u ∈ R , ∀h ∈ R , hD J(u)h, hi ≥ 0 .

Preuve. Voir le TD.

Attention, l’énoncé de l’implication (⇒) doit être adapté si on veut étudier la
convexité sur un sous-ensemble K de RN .

12
Exercice 2.3. On suppose J deux fois différentiable en tout point de K ⊂ RN . Soit
α ≥ 0. Montrer que

N 2 2
∀u ∈ K, ∀h ∈ R , hD J(u)h, hi ≥ αkhk =⇒ J est α-convexe sur K,

et que l’equivalence est vraie pour K = RN .

Exemple 2.3. x ∈ RN 7→ kxk2 est α = 2 convexe. En effet, sa matrice hessienne en

tout x est 2 fois la matrice identité.

Exercice 2.4. On suppose J deux fois différentiable en tout point de K. Montrer que

N 2
∀u ∈ K, ∀h ∈ R , hD J(u)h, hi > 0 =⇒ J est strictement convexe sur K.

Montrer que la réciproque est fausse (exemple : J(x) = x4 ).

Premières applications.

Proposition 2.5. Soit K un convexe fermé non vide de RN , contenu dans un ouvert
U . Soit J : U → R, différentiable en tout point de K. On suppose que J est α-convexe
sur K, avec α > 0. Alors J possède un unique minimiseur sur K.

Idée de la preuve : Soit u fixé dans K. De J α-convexe on déduit que pour tout
v ∈ K,
α
J(v) ≥ J(u) + h∇J(u), v − ui + kv − uk2
2
α kvk→∞
≥ J(u) − k∇J(u)kkv − uk + kv − uk2 → +∞.
2
Donc J est coercive, et admet un minimum sur K d’après le théorème 2.2. L’unicité du
minimiseur provient de la stricte convexité de J sur K.

Théorème 2.4 (projection sur un convexe fermé non vide). Soit K un convexe fermé
non vide de RN . Alors

∀u ∈ RN , ∃!ū ∈ K, kū − uk = min kv − uk

v∈K

On notera ū = ΠK (u) la projection de u sur K.

13
Preuve. ū, s’il existe, est caractérisé de manière équivalente par

ū ∈ K, et kū − uk2 = inf kv − uk2 .

v∈K

Il s’agit donc de la minimisation de la fonction J(v) = kv − uk2 sur K. Cette fonction

étant α-convexe (avec α = 2), on peut appliquer la proposition précédente.

14
Chapitre 3

Conditions d’optimalité :
généralités

On considère un ouvert U ⊂ RN , une application J : U → RN et un sous-ensemble

o
K ⊂ U . On note u un minimiseur local de J sur K (s’il existe), et K l’ensemble des
points intérieurs à K, c’est-à-dire
o
K = {x ∈ K, ∃R > 0, BR (x) ⊂ K} .

o
3.1 Généralités dans le cas u ∈K
Théorème 3.1. On suppose que J admet un minimum local en u, sur K. Si J est
o
différentiable en u et u ∈K , alors ∇J(u) = 0.

Preuve. J admet un minimum local en u, donc il existe R > 0 t.q.

∀v ∈ K, kv − uk ≤ R ⇒ J(v) ≥ J(u).
o
Comme u ∈K , quitte à réduire le rayon R, on peut supposer que BR (u) ⊂ K. Pour
montrer que ∇J(u) = 0, nous allons montrer que pour tout h ∈ RN \{0}, h∇J(u), hi = 0.
Par linéarité, il suffit de le montrer pour des vecteurs h de norme 1.
Soit h ∈ RN t.q. khk = 1. Soit r ∈ (0, R]. Alors le vecteur u + rh ∈ BR (u), et donc
J(u + rh) ≥ J(u), que l’on peut écrire
J(u + rh) − J(u)
≥ 0.
r

15
J étant différentiable en u, limr→0 1r (J(u + rh) − J(u)) = h∇J(u), hi, d’où en passant à
la limite dans l’inégalité précédente :
h∇J(u), hi ≥ 0.
Enfin, on peut remplacer h par −h et reprendre la démarche précédente pour obtenir
l’inégalité dans l’autre sens, ce qui donne l’égalité.

Définition 3.1. Soit A ∈ RN ×N une matrice symétrique. On dit que :

• A est positive (ou ”A ≥ 0”), si
∀x ∈ RN , hAx, xi ≥ 0.
• A est définie positive (ou ”A > 0”) si
∀x ∈ RN , x 6= 0 ⇒ hAx, xi > 0.
Proposition 3.1. Soit A ∈ RN ×N une matrice symétrique. Alors les propriétés suivants
sont équivalentes :
(i) A est définie positive.
(ii) ∃α > 0, ∀x ∈ RN hAx, xi ≥ αkxk2 .
Preuve. (ii) ⇒ (i) est immédiat. Pour montrer (i) ⇒ (ii), on considère l’application
f : RN → R, x 7→ hAx, xi.
P
Comme f (x) = i,j Aij xj xi , f est une fonction polynômiale en les coordonnéees
x1 , . . . , xN de x, elle est donc continue sur RN . Notons S la sphère unité : S =
y ∈ RN , kyk = 1 . S est compacte donc d’après le théorème 2.1, f admet un mi-

nimum global sur S : il existe donc y0 ∈ S t.q.

∀y ∈ S, hAy, yi ≥ hAy0 , y0 i.
On pose alors α = hAy0 , y0 i ; α > 0 car A est définie positive, et pour tout x ∈ RN \ {0},
en notant y = x/kxk (qui appartient à S),
hAx, xi = hA(ykxk), ykxki
= hkxk(Ay), kxkyi
= kxk2 hAy, yi
≥ kxk2 hAy0 , y0 i = αkxk2 .
(ii) étant également vérifiée en x = 0, cela conclut la preuve.

16
Remarque 3.1. D’après l’exercice 2.3, si J est deux fois différentiable en tout point
de K et si pour tout u ∈ K, D2 J(u) est définie positive, alors J est α-convexe pour un
α > 0.

Théorème 3.2 (Formules de Taylor à l’ordre 2). Soit u ∈ U et J : U → R une

application deux fois différentiable en u. On note D2 J(u) la matrice hessienne de J en
u, définie par
2
2 ∂ J
D J(u) = .
∂xi ∂xj 1≤i,j≤N

Alors on peut écrire la formule de Taylor-Young à l’ordre 2 au point u : il existe

une fonction η : RN → R t.q. limh→0 η(h) = 0 et

1
∀h ∈ RN u+h ∈ U ⇒ J(u+h) = J(u)+h∇J(u), hi+ hD2 J(u)h, hi+khk2 η(h). (3.1)
2

On peut également donner une formulation plus précise appelée formule de Taylor-
Lagrange :

1
∀h ∈ RN u+h ∈ U ⇒ ∃θ ∈]0, 1[, J(u+h) = J(u)+h∇J(u), hi+ hD2 J(u+θh)h, hi.
2
(3.2)

Théorème 3.3. On suppose que J admet un minimum local en u, sur K. Si J est 2 fois
o
différentiable en u et u ∈K , alors ∇J(u) = 0 et pour tout h ∈ RN , hD2 J(u)h, hi ≥ 0.

Preuve. On sait d’après le théorème 3.1 que ∇J(u) = 0. Il suffit de montrer que la
seconde propriété. D’après la formule de Taylor (3.1), on a pour tout h ∈ RN t.q.
u + h ∈ U,
1
J(u + h) − J(u) = hD2 J(u)h, hi + khk2 η(h) (3.3)
2
avec limh→0 η(h) = 0. Par l’absurde, supposons qu’il existe un vecteur x ∈ RN t.q.
hD2 J(u)x, xi < 0. Alors x est non nul et on peut définir le vecteur normalisé x = x/kxk,
o
qui vérifie également hD2 J(u)x, xi < 0. Puisque u ∈K , il existe R > 0 t.q. BR (u) ⊂ K.
Ainsi, pour tout 0 < ρ < R, u + ρx ∈ K donc d’après (3.3),

1
J(u + ρx) − J(u) = hD2 J(u)(ρx), ρxi + kρxk2 η(ρx),
2

17
qui s’écrit encore, par bilinéarité du produit scalaire et par homogénéité de la norme,
J(u + ρx) − J(u) 1
= hD2 J(u)x, xi + kxk2 η(ρx)
ρ2 2
1
= hD2 J(u)x, xi + η(ρx).
2
Enfin, limh→0 η(h) = 0 donc il existe R > 0 t.q.
1
∀h ∈ RN , khk < R ⇒ η(h) < − hD2 J(u)x, xi.
2
On en conclut que pour tout ρ ∈]0, min(R, R)[,
J(u + ρx) − J(u)
< 0.
ρ2
Cela contredit le fait que J possède un minimum local en u.
Remarque 3.2. On dira typiquement que ∇J(u) = 0 est une condition d’optimalité
d’ordre 1, et que la condition hD2 J(u)h, hi ≥ 0 pour tout h ∈ RN , est une condition
d’optimalité d’ordre 2. L’équation ∇J(u) = 0 est parfois appeléé ”équation d’Euler”.
o
Théorème 3.4 (Réciproque). On suppose J deux fois différentiable en u, u ∈K et
∇J(u) = 0. Alors :
(i) S’il existe α > 0 tel que pour tout h ∈ RN , hD2 J(u)h, hi ≥ αkhk2 , alors J admet un
minimum local en u.
(ii) S’il existe une boule BR (u) centrée en u, contenue dans K, telle que pour tout
v ∈ BR (u) et tout h ∈ RN , hD2 J(v)h, hi ≥ 0, alors J admet un minimum local en u.
Preuve. Cas (i). D’après la formule de Taylor-Young (3.1) (sachant que ∇J(u) = 0),
il existe une fonction η : RN → R t.q. limh→0 η(h) = 0 et

∀v ∈ U, J(v) − J(u) ≥ (α + η(v − u)) kv − uk2 . (3.4)

Comme η(h) → 0 quand h → 0, il existe R > 0 t.q.

∀h ∈ RN , khk ≤ R ⇒ η(h) ≥ −α.

D’après (3.4), on en déduit que pour tout v ∈ U t.q. kv − uk ≤ R, J(v) ≥ J(u).

Cas (ii). On applique la formule (3.2) sur la boule BR (u) : soit v ∈ BR (u), il existe
donc θ ∈]0, 1[ t.q.
1
J(v) = J(u) + hD2 J(u + θ(v − u))(v − u), v − ui.
2

18
Comme le point u+θ(v−u) appartient encore à la boule BR (u), l’hypothèse (ii) implique
hD2 J(u + θ(v − u))(v − u), v − ui ≥ 0, donc J(v) ≥ J(u).

3.2 Conditions d’optimalité dans le cas où K est convexe

Les résultats suivants sont fondamentaux dans ce cours.

Théorème 3.5 (CO1). Soit J : U → R et K ⊂ U un sous-ensemble convexe. On

suppose que J admet un minimum local sur K, au point u ∈ K, et que J est différentiable
en u. Alors
∀v ∈ K, h∇J(u), v − ui ≥ 0.

C’est une condition d’optimalité d’ordre 1.

Preuve. Soit v ∈ K \ {u}. Pour θ ∈]0, 1[, on note uθ := (1 − θ)u + θv = u + θ(v − u).
J admet un minimum local en u sur K donc il existe R > 0 t.q.

∀w ∈ K ∩ BR (u) J(w) − J(u) ≥ 0.

Par convexité de K, le point uθ appartient à K quel que soit θ ∈]0, 1[. De plus, si
θ < R/kv − uk, uθ ∈ BR (u), d’où :

R
∀θ ∈]0, min(1, )[ J(uθ ) − J(u) ≥ 0.
kv − uk

Le résultat s’en déduit par passage à la limite quand δ → 0, puisque

J(uθ ) − J(u)
h∇J(u), v − ui = lim .
θ→0+ θ

Théorème 3.6. Soit J : U → R, K ⊂ U un sous-ensemble convexe et u ∈ U . On

suppose J convexe sur K, et différentiable en u. Alors les conditions suivantes sont
équivalentes :
(i) J admet un minimum local sur K au point u ;
(ii)

u∈K
(3.5)
∀v ∈ K, h∇J(u), v − ui ≥ 0

19
(iii) J admet un minimum global sur K au point u.
On dira que la condition d’optimalité d’ordre 1 (3.5) caractérise la minimalité de u.

Preuve. On a déjà vu que si u ∈ K est un point de minimum local, alors on a (3.5).

Réciproquement, si l’on a (3.5), alors par convexité de J, pour tout v dans K :

J(v) ≥ J(u) + h∇J(u), v − ui ≥ J(u)

Donc J possède un minimum global en u sur K.

Remarque 3.3. On peut montrer que pour une fonction J convexe, l’équivalence entre
minimum local et minimum global reste valable sans hypothèse de différentiabilité de J
(voir le TD).

En application directe nous avons le résultat suivant.

Théorème 3.7 (Projection sur un convexe fermé). Soit u ∈ RN , et K ⊂ RN un convexe

fermé non vide.
(i) ∃!ū = ΠK (u) dans K, t.q. kū − uk = inf v∈K kv − uk.
(ii) ū est caractérisé par

hu − ū, v − ūi ≤ 0, ∀v ∈ K. (3.6)

(iii) De plus l’application u → ΠK (u) est 1-Lipschitzienne :

kΠK (u2 ) − ΠK (u1 )k ≤ ku2 − u1 k, ∀u1 , u2 ∈ RN .

Preuve. Voir le TD.

3.3 Le cône tangent TK (u)

On se place maintenant dans un cadre plus général, où K ⊂ RN est supposé
seulement fermé et non vide. Pour généraliser la propriété (3.5) lorsque K n’est plus
nécessairement convexe, on a besoin d’introduire la notion de cône tangent en un point
u ∈ K.
On rappelle que Γ ⊂ RN est un cône si

∀λ ≥ 0, ∀x ∈ Γ, λx ∈ Γ.

20
Définition 3.2. On appelle cône tangent en u, et on note TK (u), l’ensemble déterminé
par l’une des définitions équivalentes suivantes :

N
n→∞ un − u
TK (u) := d ∈ R ∃tn > 0, tn → 0, ∃un ∈ K, lim
=d (3.7)
n→∞ tn

n→∞
d ∈ RN ∃tn > 0, tn → 0, ∃dn ∈ RN , u + tn dn ∈ K et lim dn = d (3.8)

=
n→∞

N
n→∞
= d ∈ R ∃tn > 0, tn → 0, ∃un ∈ K, un = u + tn d + o(tn ) (3.9)

Une direction d ∈ TK (u) est appelée direction admissible.

Pour vérifier que les définitions (3.7)-(3.8)-(3.9) sont équivalentes, il suffit de poser
dn = untn−u et d’écrire u + tn dn = un ∈ K, ou encore un = u + tn d + tn (dn − d) =
u + tn d + o(tn ).

Interprétation. L’ensemble TK (u) contient en particulier les tangentes en u aux courbes

issues du point u et contenues dans K. Si une telle courbe est paramétrée par une ap-
plication régulière γ : R+ → RN , à valeurs dans K et t.q. γ(0) = u, en notant d = γ 0 (0),
on obtient par développement limité en t = 0 :

γ(t) = u + td + o(t) qd t → 0.

Étant donnée une suite (tn ) de réels t.q. tn > 0 et limn→∞ tn = 0, en définissant
un = γ(tn ), la suite (un ) est à valeurs dans k et vérifie

un = u + tn d + o(tn ) qd n → ∞.

Proposition 3.2. TK (u) est un cône fermé, non vide.

Preuve. TK (u) est non vide car il contient 0 (prendre un = u et (tn ) une suite quel-
conque). Si d ∈ TK (u), on considère des suites (tn ), (un ) comme dans la définition
(3.7). Pour tout λ > 0, il suffit alors de remplacer tn par t0n = tn /λ pour obtenir
limn→∞ unt0−u = λd, d’où λd ∈ K. TK (u) est donc un cône.
n
Montrons que TK (u) est fermé. Soit (dk )k∈N une suite de vecteurs de TK (u) convergeant
vers un vecteur d ∈ RN . Montrons que d ∈ TK (u). Comme d = limk→∞ dk et que chaque
dk s’écrit également comme une limite de suite, on va utiliser un argument diagonal.

21
Pour tout k ∈ N, on note (tk,n )n∈N une suite de réels strictement positifs convergeant
vers 0 et (uk,n )n∈N une suite de points de K t.q.
uk,n − u
lim = dk .
n→∞ tk,n
Le principe de l’argument diagonal est de construire à partir des valeurs uk,n , tk,n ,
dépendant de deux indices k, n, des suites uk,n(k) , tk,n(k) dépendant uniquement de k et
t.q.
uk,n(k) − u
lim tk,n(k) = 0 et lim = d. (3.10)
k→∞ k→∞ tk,n(k)
Pour cela, on considère une suite (εk )k∈N de réels strictement positifs et qui converge
vers 0. Par définition des limites, pour tout k ∈ N fixé, il existe un entier n(k) t.q.
uk,n(k) − u

0 < tk,n(k) ≤ εk et − dk ≤ εk .
tk,n(k)
Par inégalité triangulaire, on obtient alors
uk,n(k) − u uk,n(k) − u

∀k ∈ N t − d
≤ t
− dk
+ kd − dk k ≤ εk + kd − dk k.
k,n(k) k,n(k)

On en déduit (3.10) par passage à la limite quand k → ∞ dans les inégalités précédentes.

Exercice 3.1. Soit u ∈ K. Montrer que :

o
• si u ∈K , alors TK (u) = RN ;

• si K est convexe, alors TK (u) contient v − u, v ∈ K .

Définition 3.3. On appelle cône engendré par des vecteurs a1 , . . . , ap de RN , l’en-

semble noté Γ(a1 , . . . , ap ) et défini par :
p
X
Γ(a1 , . . . , ap ) := λi ai , λi ≥ 0 .
i=1

Exercice 3.2. Montrer que Γ(a1 , . . . , ap ) est un cône convexe fermé non vide. (Indica-
tion : le caractère fermé pourra être démontré en raisonnant par récurrence sur p.)

Définition 3.4. Étant donné un ensemble A ⊂ RN , on appelle cône polaire de A

(noté Ao ) l’ensemble

Ao := v ∈ RN , ∀a ∈ A, hv, ai ≤ 0 .

(3.11)

22
Théorème 3.8 (CO1). Soit u un point de minimum local de J sur K. On suppose J
différentiable en u. Alors

∀d ∈ TK (u), h∇J(u), di ≥ 0.

Au vu de la définition 3.4, cette propriété s’énonce également comme suit :

−∇J(u) ∈ TK (u)o . (3.12)

Preuve. Soit u un point de minimum local de J sur K et d ∈ TK (u). En reprenant les

notations des définitions (3.7)–(3.9), on écrit un − u = tn dn avec tn → 0 et dn → d. Par
définition du gradient de J en u, il existe une suite εn ∈ RN t.q. εn → 0 et

J(un ) − J(u) = h∇J(u), un − ui + kun − ukεn = tn h∇J(u), dn i + tn kdn kεn .

Or un ∈ K et un converge vers u, donc par définition du minimum local, il existe N ∈ N

t.q.
∀n ∈ N, n ≥ N ⇒ J(un ) − J(u) ≥ 0,

d’où l’on déduit, après division par tn > 0 dans l’égalité qui précède :

∀n ∈ N, n ≥ N ⇒ h∇J(u), dn i + kdn kεn ≥ 0.

Le résultat s’en déduit par passage à la limite car h∇J(u), dn i → h∇J(u), di et kdn kεn →
0.

Théorème 3.9 (CO2). Soit u un point de minimum local de J sur K. On suppose J

deux fois différentiable en u. Alors

soit h∇J(u), di > 0,
∀d ∈ TK (u),
soit h∇J(u), di = 0, et hD2 J(u)d, di ≥ 0

Un vecteur d vérifiant h∇J(u), di = 0 est appelé ”direction critique”.

Preuve. Soit u un point de minimum local de J sur K et u ∈ TK (u). D’après la

condition d’optimalité d’ordre 1, seul le cas h∇J(u), di = 0 est à considérer. On procède
comme dans la preuve précédente en écrivant un − u = tn dn , avec dn → d, tn → 0.

23
D’après la formule de Taylor-Young à l’ordre 2, il existe une suite εn ∈ RN t.q. εn → 0
et
1 1
J(u)−J(u) = hD2 J(u)(un −u), un −ui+kun −uk2 εn = t2n hD2 J(u)dn , dn i+t2n kdn k2 εn .
2 2
Par définition du minimum local, puisque un → u, on a pour n assez grand : J(un ) ≥
J(u). On en déduit après division par t2n dans l’égalité précédente : pour n assez grand,
1 2
hD J(u)dn , dn i + kdn k2 εn ≥ 0.
2
Puisque hD2 J(u)dn , dn i → hD2 J(u)d, di et kdn k2 εn → 0, on en déduit le résultat par
passage à la limite.

24
Chapitre 4

Algorithmes de minimisation sans

contrainte

Dans tout ce chapitre, nous allons considérer une fonction J : RN → R, que l’on
supposera α-convexe (pour un α > 0) et différentiable pour garantir l’existence d’un
unique u ∈ RN t.q.
∀v ∈ RN J(u) ≤ J(v)

(voir les résultats du chapitre 2). Rappelons que dans ce cas, le point u est caractérisé
par l’équation d’Euler :
∇J(u) = 0. (4.1)

Trouver u est donc équivalent à résoudre (4.1). Cependant, en général, il n’est pas
possible de déterminer une formule explicite pour u à partir du système d’équations (4.1)
(car ces équations peuvent être non linéaires par rapport aux coordonnées u1 , . . . , uN
du vecteur inconnu u). C’est pourquoi on est amené à chercher une valeur approchée
de u. Pour construire cette approximation, nous allons utiliser des algorithmes itératifs,
qui se présentent sous la forme d’algorithmes de descente.

4.1 Algorithmes itératifs et algorithmes de descente

Définition 4.1. Un algorithme itératif est défini par une application vectorielle
A : RN → RN qui génère une suite de vecteurs (u(n) )n∈N , à l’aide d’une construction de

25
la forme :

Choisir u(0) ∈ RN (phase d’initialisation de l’algorithme)

Calculer u(n+1) = A(u(n) ) (n-ième itération)

Ce que l’on espère, c’est que la suite (u(n) )n∈N converge vers le minimiseur u cherché ;
on dit alors que l’algorithme converge vers la solution du problème de minimisation. Si
un algorithme converge, on pourra mesurer son efficacité suivant deux critères :
— sa vitesse de convergence, qui mesure la rapidité avec laquelle la suite
(u(n) )n∈N converge vers le point u ;
— sa complexité calculatoire, qui mesure le coût des opérations nécessaires
pour obtenir une itération. Le coût global est alors donné par le coût d’une
itération multiplié par le nombre d’itérations nécessaires pour obtenir la solution
escomptée avec une certaine précision ε fixée a priori.
La précision ε est associée à un critère d’arrêt, permettant à l’algorithme de s’arrêter
et de fournir une valeur approchée u(n) du minimiseur, que l’on jugera acceptable .
Sachant que la solution exacte satisfait l’équation d’Euler (4.1), ce critère d’arrêt pourra
prendre, par exemple, la forme suivante :

k∇u(n) k ≤ ε. (4.2)

Ainsi, l’algorithme fournira comme résultat le premier vecteur u(n) obtenu, satisfaisant
la condition (4.2).
Dans ce chapitre, nous nous intéressons plus particulièrement à la vitesse de conver-
gence des algorithmes. Pour comparer ces vitesses de convergence, on introduit les
définitions suivantes.

Définition 4.2. Supposons connue une suite (u(n) )n∈N , obtenue à l’aide d’un algorithme
itératif, et telle que limn→∞ u(n) = u. Pour tout n ∈ N, on définit l’erreur e(n) à
l’itération n par
e(n) = ku − u(n) k.

• On dira que la vitesse de convergence de l’algorithme est linéaire si

∃C ∈ [0, 1[, ∀u(0) ∈ RN , e(n+1) ≤ Ce(n) . (4.3)

26
Cette propriété s’écrit de manière équivalente :

∃C ∈ [0, 1[, ∀u(0) ∈ RN , e(n) ≤ C n e(0) .

Pour cette raison, on dira également que si une méthode satisfait (4.3), la conver-
gence est géométrique (l’erreur se comporte comme une suite géométrique de
raison inférieure strictement à 1).
• La méthode sera dite d’ordre p si elle satisfait une relation du type

∃C ∈ [0, 1[, ∀u(0) ∈ RN , e(n+1) ≤ C(e(n) )p . (4.4)

Si p = 2, on dira que la vitesse de convergence est quadratique.

Algorithmes de descente. Les algorithmes que nous allons considérer pour les
problèmes d’optimisation ont la forme générale suivante :

u(0) étant donné, calculer u(n+1) = u(n) + ρ(n) d(n) . (4.5)

Le vecteur d(n) s’appelle la direction de descente, et le réel ρ(n) > 0 le pas de la méthode
à la n-ième itération. On pratique, on choisira la direction et le pas afin que l’inégalité
suivante soit satisfaite :
J(u(n+1) ) ≤ J(u(n) ).

De tels algorithmes sont appelés algorithmes de descente.

4.2 Algorithmes de gradient

Supposons que l’on cherche à définir un algorithme de descente suivant le procédé
(4.5). Partant d’une valeur u(n) , écrivons la formule de Taylor à l’ordre 1 pour J au
point u(n) :

J(u(n+1) ) = J(u(n) + ρ(n) d(n) ) = J(u(n) ) + h∇J(u(n) ), ρ(n) d(n) i + ρ(n) kd(n) k η(ρ(n) d(n) ),

où η : RN → R est une fonction vérifiant limh→0 η(h) = 0. Par linéarité du produit
scalaire, on peut donc écrire :
h i
J(u(n+1) ) − J(u(n) ) = ρ(n) h∇J(u(n) ), d(n) i + kd(n) k η(ρ(n) d(n) ) .

27
Étant donné que η tend vers 0 lorsque son argument tend vers 0, on peut supposer que,
pour ρ(n) suffisamment petit, le signe du second membre va être le même que le signe de
h∇J(u(n) ), d(n) i (rappelons que ρ(n) > 0). Pour s’assurer que J(u(n+1) ) − J(u(n) ) ≤ 0,
un choix possible pour d(n) est donc

d(n) = −∇J(u(n) ). (4.6)

On obtient alors :
h i
J(u(n+1) ) − J(u(n) ) = ρ(n) −k∇J(u(n) )k2 + k∇J(u(n) )k η(−ρ(n) ∇J(u(n) ))
h i
= −ρ(n) k∇J(u(n) )k k∇J(u(n) )k + η(−ρ(n) ∇J(u(n) )) .

Cette quantité sera négative si l’on choisit un pas ρ(n) suffisamment petit. En effet, on
peut supposer k∇J(u(n) )k > 0 (sinon u(n) = u et l’algorithme s’arrêterait), et alors il
existe un ρmax > 0 t.q. pour tout choix de ρ(n) t.q. 0 < ρ(n) < ρmax , η(−ρ(n) ∇J(u(n) )) >
−k∇J(u(n) )k, ce qui donne le résultat.
Les algorithmes de descente utilisant la direction (4.6) à chaque itération s’appellent
des algorithmes de gradient. Dans le raisonnement précédent, la borne supérieure
ρmax sur le pas dépend a priori de l’itération n, puisqu’elle dépend de la fonction
η (qui dépend elle-même de u(n) ) et de la norme de ∇J(u(n) ). Sous une hypothèse
supplémentaire sur le gradient de J, on peut en fait établir des bornes uniformes sur
ρ(n) permettant de garantir la convergence des algorithmes de gradient ; c’est l’objet du
théorème suivant.

Théorème 4.1. Soit J : RN → R une application différentiable, α-convexe pour un

α > 0. On suppose que ∇J : RN → RN est une application M -lipschitzienne, pour une
constante M > 0, c’est-à-dire :

∀u, v ∈ RN k∇J(u) − ∇J(v)k ≤ M ku − vk. (4.7)

On considère deux réels a, b t.q.

2α
0<a<b< ,
M2
et l’on se donne une suite de pas ρ(n) t.q.

∀n ∈ N ρ(n) ∈ [a, b].

28
Alors, pour toute valeur initiale u(0) ∈ RN , la méthode de gradient définie par l’itération

u(n+1) = u(n) − ρ(n) ∇J(u(n) )

converge ; de plus, la convergence est géométrique : il existe une constante 0 < C < 1,
dépendant uniquement de α, M, a et b, t.q.

∀n ∈ N, ku(n) − uk ≤ C n ku(0) − uk

Preuve. En utilisant la condition (4.1), on peut écrire

u(n+1) − u = (u(n) − u) − ρ(n) ∇J(u(n) )

h i
= (u(n) − u) − ρ(n) ∇J(u(n) ) − ∇J(u) .

Puisque pour tout vecteur v ∈ RN , kvk2 = hv, vi, on obtient en développant les produits
scalaires :

ku(n+1) −uk2 = ku(n) −uk2 −2ρ(n) h∇J(u(n) )−∇J(u), u(n) −ui+(ρ(n) )2 k∇J(u(n) )−∇J(u)k2

J étant α-convexe et différentiable, on a, d’après l’exercice 2.2,

h∇J(u(n) ) − ∇J(u), u(n) − ui ≥ αku(n) − uk2 ,

et d’après la condition de Lipschitz sur ∇J,

|∇J(u(n) ) − ∇J(u)k2 ≤ M 2 ku(n) − uk2 .

Puisque ρ(n) > 0, on en déduit l’estimation suivante :

ku(n+1) − uk2 ≤ 1 − 2αρ(n) + M 2 (ρ(n) )2 ku(n) − uk2 .

On note τ : R → R la fonction trinôme définie par τ (ρ) = 1 − 2αρ + M 2 ρ2 . Remarquons

tout d’abord que pour tout ρ > 0, τ (ρ) ≥ 0. En effet, son discriminant est égal à 4(α2 −
M 2 ), il est donc négatif puisque d’après les hypothèses faites sur J, on a nécessairement
α ≤ M . Pour s’en convaincre, on remarque que, en appliquant l’exercice 2.2 et l’inégalité
de Cauchy-Schwarz,

∀u, v ∈ RN αku − vk2 ≤ h∇J(u) − ∇J(v), u − vi

≤ k∇J(u) − ∇J(v)k ku − vk,

29
ce qui implique, d’après la condition (4.7) :

∀u, v ∈ RN αku − vk ≤ k∇J(u) − ∇J(v)k ≤ M ku − vk.

Le minimum de τ est atteint au point ρmin = Mα2 ; de plus, τ (0) = 1 et par symétrie,
2α 2α
τ(M 2 ) = 1. Ainsi, si l’on fixe 0 < a < b < M 2 ), on obtient pour tout ρ ∈ [a, b],

τ (ρ) ≤ max(τ (a), τ (b)) < 1.

En notant C = [max(τ (a), τ (b))]1/2 , on vérifie que pour toute suite (ρ(n) )n∈N à valeurs
dans [a, b],
∀n ∈ N ku(n+1) − uk ≤ Cku(n) − uk.

Corollaire 4.1 (convergence de l’algorithme de gradient à pas fixe). Soit J : RN → R

une application différentiable, α-convexe pour un α > 0. On suppose que ∇J : RN → RN
2α
est M -lipschitzienne. On fixe un pas constant ρ ∈]0, M 2 [. Alors, pour toute valeur initiale
(0) N
u ∈ R , la méthode de gradient à pas fixe, définie par l’itération

u(n+1) = u(n) − ρ∇J(u(n) )

converge ; de plus, la convergence est géométrique.

Une autre stratégie consiste à déterminer, s’il existe, un pas optimal à chaque
itération. En notant d(n) = −∇J(u(n) ) la direction de descente à l’itération n, cela
revient à déterminer un point sur la droite passant par u(n) et dirigée par d(n) , qui
minimise la valeur de J sur cette droite. Autrement dit, on cherche à chaque itération
n un pas ρ(n) ∈ R t.q.

J(u(n) + ρ(n) d(n) ) = min J(u(n) + ρd(n) ). (4.8)

ρ∈R

L’algorithme de gradient à pas optimal consiste alors, à partir d’une valeur initiale u(0) ,
à réaliser l’itération

u(n+1) = u(n) + ρ(n) d(n) , avec d(n) := −∇J(u(n) ),

et où ρ(n) est (si possible) défini par (4.8).

30
Théorème 4.2 (convergence de l’algorithme de gradient à pas optimal). Soit J : RN →
R, α-convexe, différentiable, t.q. ∇J soit M -lipschitzien. Pour tout point de départ
u0 ∈ RN , l’algorithme de gradient à pas optimal est bien défini, et converge vers l’unique
minimiseur u :
lim u(n) = u.
n→∞

Preuve. Notons que le minimiseur u est bien défini et caractérisé par ∇J(u) = 0 (cas
J est différentiable et α-convexe). On peut supposer que pour tout n ∈ N, d(n) 6= 0,
sinon l’algorithme converge en un nombre fini d’itérations. Pour tout n ∈ N, on définit
l’application gn : R → R, par

∀ρ ∈ R, gn (ρ) := J(u(n) + ρd(n) ).

Alors gn possède un unique minimiseur ρ(n) sur R. En effet,

— gn est continue sur R comme composée de la fonction affine ρ ∈ R 7→ u(n) +ρd(n) ∈
RN par la fonction continue J ;
— gn est coercive. Pour le voir, il suffit de remarquer que, puisque d(n) 6= 0,

lim ku(n) + ρd(n) k = +∞,

|ρ|→∞

et de combiner cette propriété avec la coercivité de J ;

— gn est strictement convexe sur R. En effet, soit ρ1 , ρ2 deux réels distincts et
θ ∈]0, 1[. Alors, en utilisant la stricte convexité de J,

gn ((1 − θ)ρ1 + θρ2 ) = J(u(n) + [(1 − θ)ρ1 + θρ2 ]d(n) )

= J((1 − θ)[u(n) + ρ1 d(n) ] + θ[u(n) + ρ2 d(n) ])
< (1 − θ)J(u(n) + ρ1 d(n) ) + θJ(u(n) + ρ2 d(n) ) = (1 − θ)gn (ρ1 ) + θgn (ρ2 ).

L’unicité du minimiseur ρ(n) découle alors du théorème 2.2 et de la proposition 2.2. De

plus, d’après les théorèmes 3.1 et 3.6, ρ(n) est caractérisé par la propriété :

gn0 (ρ(n) ) = 0.

Pour calculer gn0 , on fixe ρ ∈ R et h ∈ R \ {0}, et on écrit le quotient différentiel

gn (ρ + h) − gn (ρ) J(u(n) + (ρ + h)d(n) ) − J(u(n) + ρd(n) ) J((u(n) + ρd(n) ) + hd(n) ) − J(u(n) + ρd(n) )
= = ,
h h h

31
d’où en passant à la limite quand h → 0 :

gn0 (ρ) = h∇J(u(n) + ρd(n) ), d(n) i.

En appliquant cette formule avec ρ = ρ(n) , puisque d(n+1) = ∇J(u(n) + ρ(n) d(n) ), on en
déduit la propriété suivante :
hd(n+1) , d(n) i = 0. (4.9)

Ainsi, dans l’algorithme de gradient à pas optimal, deux directions de descente succes-
sives sont orthogonales.
Notons que J(un+1 ) ≤ J(u(n) ), par définition. Donc la suite (J(u(n) ))n∈N est décroissante
minorée (J est minorée par J(u)), donc convergente vers une limite notée `. D’autre
part, par α-convexité de J on a
α (n)
J(u(n) ) ≥ J(u(n+1) ) + h∇J(u(n+1) ), u(n) − u(n+1) i + ku − u(n+1) k2
2
De plus on remarque que h∇J(u(n+1) ), u(n) − u(n+1) i = −ρn hdn+1 , dn i = 0, et donc
α (n) n→∞
ku − u(n+1) k2 ≤ J(u(n) ) − J(u(n+1) ) → ` − ` = 0.
2
On a donc déja montré que ku(n) − u(n+1) k → 0.
Par ailleurs, comme h∇J(u(n) ), ∇J(u(n+1) )i = 0, en développant la norme au carré
et en utilisant la condition de Lipschitz sur ∇J,

M 2 ku(n) − u(n+1) k2 ≥ k∇J(u(n) ) − ∇J(u(n+1) )k2 = k∇J(u(n) )k2 + k∇J(u(n+1) )k2 ,

et donc
k∇J(u(n) )k ≤ M ku(n) − u(n+1) k.

Enfin, on l’α-convexité de J permet également d’écrire :

αku(n) − uk2 ≤ hu(n) − u, ∇J(u(n) ) − ∇J(u)i = hu(n) − u, ∇J(u(n) )i

≤ ku(n) − ukk∇J(u(n) )k

On en déduit finalement
1 M (n) n→∞
ku(n) − uk ≤ k∇J(u(n) )k ≤ ku − u(n+1) k → 0.
α α

32
4.3 Cas particulier : fonctionnelles quadratiques
Définition 4.3. On appelle fonctionnelle quadratique une application J : RN →
R de la forme
1
J(x) = hAx, xi − hb, xi,
2
où A ∈ R N ×N est une matrice symétrique et b ∈ RN .

Proposition 4.1. Soit A ∈ RN ×N une matrice symétrique, b ∈ RN et J : RN → R

la fonctionnelle quadratique associée. Alors J est indéfiniment dérivable et on a les
formules suivantes pour son gradient et sa matrice hessienne en tout point :

∀x ∈ RN , ∇J(x) = Ax − b, D2 J(x) = A.

Corollaire 4.2. Soit A ∈ RN ×N une matrice symétrique, b ∈ RN et J : RN → R la

fonctionnelle quadratique associée. On suppose de plus que A est définie positive.
On note λ1 (resp. λN ) la plus petite (resp., la plus grande) valeur propre de A. Alors J
est α-convexe pour la constante α = λ1 et ∇J est M − lipschitzien pour la constante
M = λN .

Preuve. Voir le TD.

Remarque 4.1. Une fonctionnelle quadratique associée à une matrice A symétrique

définie positive est parfois appelée fonctionnelle quadratique elliptique.

Remarque 4.2. En vertu du corollaire 4.2, on peut donc appliquer les algorithmes de
gradient à pas fixe ou à pas optimal pour la minimisation d’une fonctionnelle quadra-
tique elliptique. Cependant, en utilisant la linéarité du gradient, on peut montrer que,
dans ce cas, l’algorithme de gradient à pas fixe converge pour une plage plus large de
choix possibles de ρ que celle obtenue au théorème 4.1 (voir le TD).

4.3.1 Calcul du pas optimal pour l’algorithme de gradient

Soit A ∈ RN ×N une matrice symétrique définie positive, b ∈ RN et J : RN → R
définie par J(x) = 21 hAx, xi − hb, xi pour tout x ∈ RN . On se donne une valeur initiale
u(0) ∈ RN et on applique l’algorithme de gradient à pas optimal à la minimisation de
la fonctionnelle J sur RN . Pour chaque n ∈ N, on réalise donc l’itération

u(n+1) = u(n) + ρ(n) d(n) , avec d(n) := −(Au(n) − b),

33
où ρ(n) est défini par (4.8). Montrons que ρ(n) peut, dans ce cas, se calculer par une
formule explicite. En effet, on a vu dans la preuve du théorème 4.2, que deux directions
de descente successives étaient orthogonales (relation (4.9)), ce qui s’écrit également

h∇J(u(n+1) ), ∇J(u(n) )i = 0.

En utilisant l’expression de u(n+1) et la formule du gradient de J, on obtient donc

D E
0 = A u(n) − ρ(n) (Au(n) − b) − b, Au(n) − b
D E
= Au(n) − b − ρ(n) A Au(n) − b , Au(n) − b
D E
= kAu(n) − bk2 − ρ(n) A(Au(n) − b), Au(n) − b

= kd(n) k2 − ρ(n) hAd(n) , d(n) i.

On peut supposer d(n) 6= 0 (sinon cela signifie que ∇J(u(n) ) = 0, c’est-à-dire que u(n) = u
et il est inutile de calculer le pas ρ(n) suivant), et donc hAd(n) , d(n) i =
6 0 puisque A est
(n)
définie positive. Ainsi, ρ s’exprime par la formule
kd(n) k2
ρ(n) = . (4.10)
hAd(n) , d(n) i

4.3.2 Choix de la direction de descente d(n) . La notion de direction

conjuguée
Nous allons voir sur un exemple que le choix de la direction de descente d(n) =
−∇J(u(n) ) n’est pas forcément le plus efficace. On se place en dimension N = 2 et ! on
1 0
définit la fonctionnelle J : (x, y) ∈ R2 7→ 21 (x2 +2y 2 ), associée à la matrice A = .
0 2
Le gradient de J est défini en tout point (x, y) ∈ R2 par
! !
x x
∇J(x, y) = =A .
2y y

Le minimum de J sur R2 est clairement atteint au point (0, 0). Examinons les premières
étapes de l’algorithme de gradient à pas optimal. On se donne un premier point u(0) =
(x(0) , y (0) )T et on définit la direction de descente
!
(0) (0) (0) −x(0)
d = −∇J(u ) = −Au = .
−2y (0)

34
Le point suivant u(1) est sur la droite passant par u(0) et dirigée par d(0) , c’est-à-dire
l’ensemble des points de la forme (x(0) − ρx(0) , y (0) − 2ρy (0) ) pour un ρ ∈ R. Cette droite
passera par la solution exacte u = (0, 0), si et seulement si il existe ρ ∈ R t.q.

x(0) − ρx(0) = 0 et y (0) − 2ρy (0) = 0.

On voit que c’est possible uniquement si l’une des valeurs x(0) ou y (0) est nulle. Ainsi, si
l’on part d’un point u(0) qui n’est pas sur l’un des axes Ox ou Oy, le point suivant u(1)
ne coı̈ncidera pas avec la solution exacte. En utilisant la formule (4.10), on peut montrer
que ce phénomène se reproduit à chaque itération ; plus précisément, si l’on part d’un
u(0) t.q. x(0) 6= 0 et y (0) 6= 0, alors à chaque itération n, le point u(n) = (x(n) , y (n) ) vérifie
également x(n) 6= 0 et y (n) 6= 0. Par conséquent, l’algorithme ne pourra pas atteindre la
valeur exacte du minimiseur u = (0, 0) en un nombre fini d’itérations.
Pourtant, en partant par exemple de la valeur u(1) , la meilleure direction à choisir
pour poursuivre la descente est la direction du vecteur u(1) lui-même (puisque la droite
correspondasnte passe par l’origine). Nous allons voir que cette direction vérifie une
propriété remarquable. Reprenons pour cela la formule (4.10). Elle nous permet d’écrire
l’expression suivante :
kd(0) k2
u(1) = u(0) − d(0) .
hAd(0) , d(0) i

Puisque d(0) = −Au(0) , on peut alors calculer hAu(1) , d(0) i :

kd(0) k2
hAu(1) , d(0) i = hAu(0) , d(0) i − hAd(0) , d(0) i
hAd(0) , d(0) i
= kd(0) k2 − kd(0) k2
= 0.

Ainsi, on pourra utiliser une autre direction de descente que celle du gradient au point
u(1) ; cette direction d(1) , colinéaire à u(1) , pourra être définie (au signe près) par

d(1) 6= 0, hAd(1) , d(0) i = 0.

Une telle direction d(1) vérifiant hAd(1) , d(0) i = 0 s’appelle une direction conjuguée
à la direction d(0) , relativement à la matrice A.

35
4.4 Méthode du gradient conjugué
Dans toute cette section, on considère une fonctionnelle quadratique elliptique
1
J : x ∈ RN 7→ hAx, xi − hb, xi
2
où A ∈ RN ×N est une matrice symétrique définie positive et b ∈ RN est un vecteur fixé.
Nous avons vu que les méthodes de gradient consistent, à partir d’un point u(n)
calculé à l’itération n, à chercher le point suivant u(n+1) sur la droite passant par u(n) et
dirigée par d(n) = −∇J(u(n) ). Ainsi, seule l’information fournie par le gradient de J à
l’étape n est utilisée pour déterminer la prochaine direction de descente. Le principe de
la méthode du gradient conjugué consiste, au contraire, à utiliser tous les gradients cal-
culés précédemment par l’algorithme ∇J(u(0) ), ∇J(u(1) ), . . . , ∇J(u(n) ) pour déterminer
la prochaine direction de descente.

Principe de l’algorithme de gradient conjugué. Un vecteur initial u(0) ayant été

donné, supposons les vecteurs u(1) , u(2) , . . . , u(n) déjà calculés. On peut faire l’hypothèse

∇J(u(k) ) 6= 0, 0 ≤ k ≤ n,

sinon la valeur exacte du minimiseur aurait déjà été atteinte. Pour k = 0, 1, . . . , n, appe-
lons Gn le sous-espace de RN engendré par les gradients ∇J(u(0) ), ∇J(u(1) ), . . . , ∇J(u(n) ) ;
c’est donc un sous-espace de dimension au plus n + 1. L’idée de la méthode consiste à
définir le vecteur suivant u(n+1) comme le minimiseur de J sur le plan affine passant
par u(n) et dirigé par Gn . Ainsi, en notant u(n) + Gn ce plan affine,
n
( )
X
u(n) + Gn := {u(n) + w; w ∈ Gn } = u(n) + δk ∇J(u(k) ) ; δk ∈ R, 0 ≤ k ≤ n ,
k=0

le point u(n+1) vérifie :

u(n+1) ∈ (u(n) + Gn ) et J(u(n+1) ) = min J(v). (4.11)

v∈u(n) +Gn

L’ensemble u(n) + Gn étant fermé et convexe, et J étant coercive et strictement convexe,

le problème de minimisation ci-dessus admet une solution unique.
On peut prévoir d’ores et déjà que la définition (4.11) fournira une valeur J(u(n+1) )
inférieure à celle que l’on aurait obtenue en appliquant une itération de la méthode

36
de gradient à pas optimal. En effet, la droite {u(n) − ρ∇J(u(n) ), ρ ∈ R} =: u(n) +
Vect(∇J(u(n) )) sur laquelle on minimise J pour mettre à jour le point u(n) dans la
méthode de gradient à pas optimal, est contenue dans le plan u(n) +Gn ; par conséquent,
n o n o
min J(v), v ∈ u(n) + Gn ≤ min J(v), v ∈ u(n) + Vect(∇J(u(n) )) .

Cependant, pour que la définition (4.11) soit applicable en pratique, il faut s’assurer
que le problème de minimisation associé, qui porte sur n + 1 variables δ0 , δ1 , . . . , δn ,
soit facile à résoudre. Nous allons voir que c’est le cas, et que sa résolution repose sur
l’utilisation des directions conjuguées associées à la matrice A.
Remarquons tout d’abord que les solutions des problèmes successifs de minimisation

u(k+1) ∈ (u(k) + Gk ) et J(u(k+1) ) = min J(v) = min J(u(k) + w), 0 ≤ k ≤ n,

v∈u(k) +Gk w∈Gk
(4.12)
vérifient
h∇J(u(k+1) ), wi = 0 pour tout w ∈ Gk . (4.13)

En effet, pour w ∈ Gk , puisque Gk est un espace vectoriel et que u(k+1) ∈ (u(k) + Gk ),

on a également, pour tout t > 0, u(k+1) + tw ∈ (u(k) + Gk ). Par définition du minimum,
on peut donc écrire
J(u(k+1) + tw) − J(u(k+1) )
0≤
t
et passer à la limite quand t → 0, ce qui donne h∇J(u(k+1) ), wi ≥ 0. En remplaçant
w par −w (ce qui est autorisé car Gk est un espace vectoriel), on obtient l’inégalité
contraire, d’où (4.13). En particulier, on peut donc écrire :

h∇J(u(k+1) ), ∇J(u(l) )i = 0, 0 ≤ l ≤ k ≤ n,

c’est-à-dire que les gradients ∇J(u(k) ), 0 ≤ k ≤ n + 1 sont deux à deux orthogonaux.

Remarque 4.3. Cette propriété est plus forte que la propriété (4.9) établie pour l’al-
gorithme de gradient à pas optimal, où seulement deux gradients consécutifs sont or-
thogonaux.

Cette orthogonalité montre, en particulier, que les gradients ∇J(u(0) ), ∇J(u(1) ), . . . , ∇J(u(n) )
forment une famille libre (on a supposé qu’ils étaient tous non nuls). Cela implique que
l’algorithme converge en au plus N itérations : en effet, si les N premiers vecteurs

37
∇J(uk ), 0 ≤ k ≤ N − 1 sont différents de zéro, alors nécessairement le vecteur sui-
vant ∇J(u(N ) ) est nul, sinon le sous-espace GN ⊂ RN contiendrait N + 1 vecteurs
indépendants. Par conséquent, ∇J(uN ) = 0 et donc uN = u.
Supposons que, à partir d’un vecteur initial u(0) , on ait construit les vecteurs u(1) , . . . , u(n)
en résolvant les problèmes de minimisation successifs définis par (4.12). Pour tout
0 ≤ k ≤ n, on note ∆(k) := u(k+1) − u(k) la différence entre deux approximations
successives. Par construction, chaque vecteur ∆(k) appartient au sous-espace Gk , dont
il existe k + 1 paramètres réels δ0k , δ1k , . . . , δkk t.q.
k
X
(k)
∆ = δlk ∇J(u(l) ).
l=0

Nous allons montrer que ces vecteurs sont conjugués par rapport à la matrice A.

Définition 4.4. Soit A ∈ RN ×N une matrice symétrique. On dit que des vecteurs
w(0) , w(1) , . . . , w(n) de RN sont conjugués par rapport à la matrice A s’ils vérifient :

w(k) 6= 0, 0 ≤ k ≤ n, et hAw(l) , w(m) i = 0, 0 ≤ m < l ≤ n.

Remarque 4.4. Si l’on suppose de plus que A est définie positive, alors l’application

(x, y) ∈ RN 7→ hAx, yi ∈ R

définit un produit scalaire sur RN (le produit scalaire usuel correspondant au choix
A = IN ). Une famille de vecteurs non nuls est donc conjuguée par rapport à A si elle est
orthogonale pour ce produit scalaire ; en particulier, elle forme donc une famille libre.

Montrons que les vecteurs ∆(k) introduits plus haut sont conjugués par rapport à
A. En utilisant l’expression de ∇J, on remarque que

∀v, w ∈ RN ∇J(v + w) = A(v + w) − b = ∇J(v) + Aw,

ce qui permet d’écrire

∇J(u(k+1) ) = ∇J(u(k) + ∆(k) ) = ∇J(u(k) ) + A∆(k) , 0 ≤ k ≤ n.

En utilisant l’orthogonalité des gradients ∇J(u(k) ), 0 ≤ k ≤ n, et en développant le

produit scalaire, on obtient

0 = h∇J(u(k+1) ), ∇J(u(k) )i = k∇J(u(k) )k2 + hA∆(k) , ∇J(u(k) )i, 0 ≤ k ≤ n.

38
Comme on a supposé ∇J(u(k) ) 6= 0, on en déduit que hA∆(k) , ∇J(u(k) )i = 6 0 et donc
(k)
∆ 6= 0 pour tout 0 ≤ k ≤ n.
D’autre part, en écrivant u(k+1) = u(k) + ∆(k) , on calcule de la même manière

0 = h∇J(u(k+1) ), ∇J(u(l) )i = h∇J(u(k) ), ∇J(u(l) )i+hA∆(k) , ∇J(u(l) )i, 0 ≤ l < k ≤ n,

ce qui donne
hA∆(k) , ∇J(u(l) )i = 0, 0 ≤ l < k ≤ n.

Pour un entier m t.q. 0 ≤ m < k ≤ n, chaque vecteur ∆(m) ∈ Gm est une combinaison
linéaire des vecteurs ∇J(u(l) ), pour 0 ≤ l ≤ m. Par conséquent, l’égalité précédente
entraı̂ne
hA∆(k) , ∆(m) i = 0, 0 ≤ m < k ≤ n.

On peut montrer que la conjugaison par rapport à A des directions de descente

∆(k) , permet, à chaque itération n, de déterminer la direction de descente suivante et
de résoudre le problème de minimisation (4.11) par des formules explicites. On aboutit
aux expressions suivantes.

Définition 4.5 (Algorithme de gradient conjugué). Soit A ∈ RN ×N une matrice

symétrique définie positive, b ∈ RN et J la fonctionnelle quadratique associée. L’al-
gorithme de gradient conjugué est le suivant. On se donne un point initial u(0) .
Si ∇J(u(0) ) 6= 0, on définit d(0) = −∇J(u(0) ), et tant que ∇J(u(n) ) 6= 0, on réalise
l’itération :

k∇J(u(n) )k2 (n−1)

d(n) = −∇J(u(n) ) + d ,
k∇J(u(n−1) )k2
k∇J(u(n) )k2
ρ(n) = ,
hAd(n) , d(n) i
u(n+1) = u(n) + ρ(n) d(n) .

39
40
Chapitre 5

Contraintes d’égalité

Les contraintes d’égalité considérées sont du type

N
K := x ∈ R , ϕ1 (x) = 0, . . . , ϕp (x) = 0 (5.1)

où les fonctions ϕi : RN → R sont données, et où p est un entier ≥ 1 qui représente le
nombre de contraintes. On définira aussi la fonction à valeurs vectorielles ϕ : RN → Rp ,
par  
ϕ1 (x)
 .. 
ϕ(x) :=  . 

ϕp (x)
Contraintes d’égalité affines. Il s’agit du cas particulier où chaque ϕi est affine :
il existe des coefficients (cij ) et (fi ) t.q.
N
X
ϕi (x) = cij xj − fi .
j=1

En particulier en notant x = (x1 . . . xN )T et

   
c11 · · · c1N f1
 . ..   . 
C :=  . et f :=  . 
 . .  . , (5.2)


cp1 · · · cpN fp
on a l’égalité dans Rp :
ϕ(x) = Cx − f.

41
K est donc un sous-espace affine de RN dirigé par le sous-espace vectoriel {w ∈
RN , Cw = 0}. En effet, si x, y ∈ K, leur différence x − y vérifie C(x − y) = 0. En
particulier, on peut vérifier facilement que pour le cas de contraintes d’égalité affines,
K est convexe.

5.1 Cas des contraintes d’égalité affines

Étant donné un ensemble A ⊂ RN , on notera A⊥ son orthogonal, défini par

A⊥ := {x ∈ RN , ∀a ∈ A, hx, ai = 0}.

Rappelons que pour tout ensemble A, son orthogonal A⊥ est un sous-espace vectoriel
de RN .

Lemme 5.1. Lorsque K est affine, le cône tangent en tout point u de K est un espace
vectoriel donné par

TK (u) = {d ∈ RN , Cd = 0} = {∇ϕ1 , . . . , ∇ϕp }⊥ .

Preuve. On commence par établir que TK (u) = {d ∈ RN , Cd = 0}. Pour cela, on

procède par double inclusion.
— Soit d ∈ TK (u) ; d’après la définition 3.2, il existe des suites un ∈ K et tn > 0
t.q.
un − u
lim tn = 0 et lim = d.
n→∞ n→∞ tn
Puisque un , u ∈ K, C(un − u) = 0 donc par linéarité,

un − u
C =0 pour tout n.
tn

En passant à la limite quand n → ∞, on obtient Cd = 0.

— Réciproquement, soit d ∈ RN t.q. Cd = 0. Montrons que d ∈ TK (u). Pour tout
n ∈ N∗ , on pose tn = n1 et on définit un = u + n1 d. Puisque Cd = 0, on vérifie
que Cun = Cu = f , ce qui montre que la suite (un )n∈N∗ est à valeurs dans K.
Par conséquent, d ∈ TK (u).

42
Pour conclure la preuve, on observe enfin que ∇ϕi (x) = (ci1 . . . ciN )T , donc (Cd)i =
h∇ϕi , di. Ainsi
Cd = 0 ⇔ ∀i = 1, . . . , p, h∇ϕi , di = 0.
L’ensemble des vecteurs d ∈ RN tels que Cd = 0 est donc exactement l’ensemble des
vecteurs orthogonaux à tous les vecteurs ∇ϕ1 , . . . , ∇ϕp , d’où le résultat.
Notons au passage les identités suivantes :
 
h∇ϕ1 , di
..
C ≡ [∇ϕ1 , . . . , ∇ϕp ]T ,
 
Cd =   . ,

h∇ϕp , di
et encore
C T = [∇ϕ1 , . . . , ∇ϕp ] .

Théorème 5.1 (multiplicateurs de Lagrange, contraintes d’égalité affines).

Soit K un ensemble d’égalités affines. Si J est différentiable en u ∈ K et si u est un
minimum local de J sur K, alors

∃λ ∈ Rp , ∇J(u) + C T λ = 0 (5.3a)
Cu − f = 0. (5.3b)

On dit que les composantes du vecteur λ = (λ1 . . . λp )T sont les multiplicateurs de La-
grange associés aux contraintes ϕi (x) = 0. Les conditions (5.3) constituent les condi-
tions d’optimalité d’ordre 1 du problème de minimisation. Elles s’écrivent de manière
équivalente
p
X
p
∃λ ∈ R , ∇J(u) + λi ∇ϕi (u) = 0 (5.4a)
i=1
ϕ(u) = 0. (5.4b)

Preuve. Nous avons établi au chapitre 3 que pour un problème général d’optimisation
sous contraintes, les conditions d’optimalité d’ordre 1 s’écrivaient : pour tout d ∈ TK (u),

h−∇J(u), di ≤ 0.

Mais comme ici TK (u) est un espace vectoriel, on a aussi −d ∈ TK (u) et donc

h−∇J(u), −di ≤ 0.

43
En combinant les deux inégalités, on obtient

∀d ∈ TK (u), h−∇J(u), di = 0

Ainsi,
−∇J(u) ∈ TK (u)⊥ ≡ {∇ϕ1 , . . . , ∇ϕp }⊥⊥

Rappelons alors le resultat suivant :

Lemme 5.2 (Théoreme du bi-orthogonal ). Pour tout sous-ensemble A non

vide de RN ,
A⊥⊥ = Vect(A)

Preuve du lemme 5.2. En exercice. On pourra montrer les propriétés suivantes :

— A ⊂ A⊥⊥ ;
— A⊥ = (Vect(A))⊥ ;
— Vect(A) et A⊥ sont en somme directe (pour cela, utiliser une base orthonormale
de Vect(A) et la projection orthogonale de RN sur Vect(A)) ;
pour en déduire que Vect(A) ⊂ A⊥⊥ et conclure par un argument de dimension.
Fin de la preuve du théorème 5.1. Ainsi −∇J(u) ∈ Vect{∇ϕ1 , . . . , ∇ϕp }, donc il
existe des réels λ1 . . . , λp t.q.

p
X
−∇J(u) = λi ∇ϕi (u).
i=1

Par ailleurs, en notant λ = (λ1 , . . . , λp )T ∈ Rp , on peut écrire

p
X
∇ϕi (u)λi = [∇ϕ1 (u), . . . , ∇ϕp (u)] λ ≡ C T λ.
i=1

Cela conclut la preuve pour les deux versions (5.3) et (5.4).

Exercice 2.
Soit J(x) = 21 hAx, xi − hb, xi, où A est une matrice symétrique définie positive.
Écrire les conditions d’optimalité du théorème des multiplicateurs de Lagrange dans ce
cadre ; montrer qu’on obtient un système linéaire en les inconnues (u, λ).

44
5.3 Cas de contraintes d’égalité quelconques
Le cas général est plus difficile mais va conduire, sous des hypothèses adéquates
(dites de qualification des contraintes ), à des conditions d’optimalité similaires. On
considère dans cette section que les fonctions ϕ1 , . . . , ϕp : RN → R, sont de classe C 1 .

Définition 5.1. On dira que les contraintes d’égalité (5.1) sont qualifiées en u ∈ K
si l’une des conditions suivantes est satisfaite :
• soit les contraintes sont linéaires : chaque fonction ϕi est affine ;
• soit la famille {∇ϕ1 (u), . . . , ∇ϕp (u)} est libre.

Théorème 5.2. Soit u un point de K, un minimiseur local de J sur K. On suppose que

J est différentiable en u et que les contraintes sont qualifiées en u. Alors le théorème
des multiplicateurs de Lagrange est encore valable :
p
X
∃λ ∈ Rp , ∇J(u) + λi ∇ϕi (u) = 0 (5.5a)
i=1
ϕ(u) = 0. (5.5b)

Preuve. Le coeur de la démonstration repose sur la caractérisation

TK (u) = {∇ϕ1 (u), . . . , ∇ϕp (u)}⊥ .

L’inclusion ⊂ est facile à montrer ; la réciproque nécessite l’usage du théorème des

fonctions implicites. Le détail de la preuve est fait dans le Complément 5.4. Le reste de
la preuve est similaire au cas des contraintes affines.

5.4 Complément : preuve du Théorème 5.2

On suppose que d ∈ {∇ϕ1 (u), . . . , ∇ϕp (u)}⊥ (c’est-à-dire h∇ϕi (u), di = 0 pour tout
i), et on désire montrer que d ∈ TK (u). Notons que la matrice jacobienne Dϕ est une
matrices p × N , qui s’écrit
 
∇ϕTi
∂ϕi  . 
Dϕ = = . .
∂xj ij  . 
∇ϕTp

45
Donc par hypothèse on a
 
h∇ϕi (u), di
 .. 
Dϕ(u) · d = 
 . =0

h∇ϕp (u), di

Le cas où les p contraintes sont toutes affines ayant déjà été traité, on suppose donc
que les gradients ∇ϕ1 (u), . . . , ∇ϕp (u) sont linéairement indépendants (ce qui impose en
particulier que N ≥ p, puisque les gradients forment une famille llibre de p vecteurs
de RN ). Cela signifie que la matrice Dϕ, dont les p lignes sont formées de vecteurs
linéairement indépendants, est de rang p. Par conséquent, Dϕ contient également p
vecteurs colonnes indépendants. Quitte à réordonner les coordonnées, on peut donc
supposer que les p premiers vecteurs colonnes de Dϕ(u) forment une famille libre dans
Rp .
Notons pour un vecteur x de RN , x = (x1 , x2 ) où x1 contient les p premières com-
posantes de x et x2 les N − p autres (N − p ≥ 0). En particulier, ϕ(x) = ϕ(x1 , x2 ), et on
peut noter D1 ϕ et D2 ϕ les dérivées par rapport aux coordonnées x1 et x2 respective-
ment. L’hypothese d’indépendance des gradients revient donc à dire que D1 ϕ(u) est une
matrice inversible. D’après le théorème des fonctions implicites il existe des voisinages
de u1 et de u2 et une fonction Ψ de classe C 1 t.q., dans ces voisinages,

ϕ(x1 , x2 ) = 0 ⇔ x1 = Ψ(x2 ).

En particulier, u1 = Ψ(u2 ).
Afin de construire une suite xn dans K, on procède en posant d’abord
1 2
x2n = u2 + d ,
n
et
x1n = Ψ(x2n ).

Par construction, on a donc xn ∈ K pour n assez grand. Ensuite, par développement

limité,
1 1
D2 Ψ(u2 )d2 + o( ).
x1n = Ψ(u2 ) +
n n
1 1 2 2 1
= u + D2 Ψ(u )d + o( ).
n n

46
Montrons que

D2 Ψ(u2 )d2 = d1 . (5.6)

On aura ainsi xn = u + n1 d + o( n1 ), avec xn ∈ K, et donc d ∈ TK (u).

D’abord, on a
!
d1
0 = Dϕ(u)d = [D1 ϕD2 ϕ] = D1 ϕ(u)d1 + D2 ϕ(u)d2 . (5.7)
d2

De l’identité ϕ(Ψ(x2 ), x2 )) = 0, en différentiant en u2 , on obtient

D1 ϕ(u)D2 Ψ(u2 ) + D2 ϕ(u) = 0. (5.8)

On applique cette dernière identité à d2 , et en identifiant avec (5.7), et en simplifiant

par D1 ϕ(u) qui est inversible, on obtient l’identité désirée (5.6).

47
48
Chapitre 6

Contraintes d’inégalité,
contraintes mixtes

On considère des contraintes d’inégalité du type

N
K := x ∈ R , ϕ1 (x) ≤ 0, . . . , ϕp (x) ≤ 0 (6.1)

où ϕi : RN → R, et où p est un entier ≥ 1 qui représente le nombre de contraintes. On

notera aussi la fonction ϕ : RN → Rp , définie par ϕ(x) := (ϕ1 (x) . . . ϕp (x))T .
On utilisera la notation X ≤ Y , pour deux vecteurs X = (xi ) et Y = (yi ), lorsque
xi ≤ yi , ∀i, ainsi que la notation X ≤ 0 pour dire que xi ≤ 0, ∀i. Ainsi, l’ensemble K
s’écrira K ≡ {x ∈ RN , ϕ(x) ≤ 0}.
Contraintes d’inégalité affines. Il s’agit du cas particulier où chaque ϕi est affine : il
existe des coefficients (cij ) et (fi ) t.q. ϕi (x) = N
P
j=1 cij xj − fi . En particulier en notant
T
x = (x1 , . . . , xN ) et C = (cij ), f = (fi ), on a

K ≡ {x ∈ RN , Cx − f ≤ 0}.

Définition 6.1. Pour u ∈ K, on note A(u) := {i ∈ {1, . . . , p}, ϕi (u) = 0} l’ensemble

des contraintes actives, ou saturées .

Il sera important de distinguer

— les contraintes actives (ϕi (u) = 0),
— les contraintes inactives (ϕi (u) < 0).

49
6.1 Cas des contraintes d’inégalité affines
On note que si K est un ensemble de contraintes d’inégalité affines, alors K est un
convexe.

Lemme 6.1. (i) De manière générale (K quelconque), on a

TK (u) ⊂ {∇ϕi (u), i ∈ A(u)}o

(ii) Lorsque K est affine, on a

TK (u) = {∇ϕi (u), i ∈ A(u)}o

On peut dire que le cône des directions admissibles, en tout point u de K, est le polaire
des gradients des contraintes actives .

Preuve du lemme 6.1.

Cas (i) : soit d ∈ TK (u) et i ∈ A(u), il faut montrer que hd, ∇ϕi (u)i ≤ 0. d ∈ TK (u)
donc il existe des suites tn & 0, un ∈ K t.q. limn→∞ untn−u = d. En notant dn = untn−u
et en utilisant le fait que un ∈ K et un développement de Taylor de ϕi en u, dans la
direction dn , on obtient :

0 ≥ ϕi (un ) = ϕi (u + tn dn )
= ϕi (u) + tn h∇ϕi (u), dn i + o(tn ).

Or i ∈ A(u) donc ϕi (u) = 0, d’où la relation

ϕi (un )
h∇ϕi (u), dn i = + o(1).
tn

Comme ϕi (un ) ≤ 0 et que limn→∞ h∇ϕi (u), dn i = h∇ϕi (u), di, le résultat s’en déduit
par passage à la limite dans l’égalité précédente.
Cas (ii) : il s’agit de montrer que l’inclusion réciproque est vraie, dans le cas d’inégalités
affines. Soit donc d ∈ {∇ϕi (u), i ∈ A(u)}o . On définit un = u + n1 d (ce qui correspond
au choix tn = n1 , dn = d pour vérifier la définition de TK (u)). Vérifions que pour n
assez grand, un ∈ K. Considérons tout d’abord le cas des contraintes inactives. Soit
j ∈ {1, . . . , p}\A(u) ; ϕj (u) < 0 et un → u donc par continuité, il existe un entier Nj ∈ N

50
t.q. pour tout n ≥ Nj , ϕj (un ) < 0. En prenant N = max {Nj , j ∈ {1, . . . , p} \ A(u)},
on a donc :
∀n ∈ N, n ≥ N ⇒ ∀j ∈ {1, . . . , p} \ A(u), φj (un ) < 0.
Pour le cas des contraintes actives, on remarque que pour des contraintes affines, la
formule de développement de Taylor utilisée dans le cas précédent devient exacte (c’est-
à-dire sans terme de reste) : si i ∈ A(u), ϕi (u) = 0 et on peut écrire le développement
suivant :
1
ϕi (un ) = h∇ϕi (u), di ≤ 0
n
puisque d appartient au cône polaire des directions admissibles. On en déduit que pour
tout n ≥ N , un ∈ K.

Pour exprimer la condition d’optimalité −∇J(u) ∈ TK (u)o , on aura donc besoin

de décrire un bipolaire , c’est-à-dire le cône polaire d’un cône polaire. Rappelons la
notation :
Xp
Γ(a1 , . . . , ap ) := { λi ai , λi ≥ 0}.
i=1
Lemme 6.2 (de Farkas - ou Théorème du bipolaire ). Pour tout a1 , . . . , ap dans
RN , on a
(a1 , . . . , ap )oo = Γ(a1 , . . . , ap )
Pour la preuve de ce résultat, nous avons besoin de deux résultats préliminaires.
Lemme 6.3. (Théorème de séparation.) Soit K un convexe fermé non vide de RN , et
u∈/ K. Alors il existe d ∈ RN , ∃b ∈ R,

hd, ui < b < hd, xi ∀x ∈ K.

(On dit que l’hyperplan hd, xi = b sépare u de K.)

Preuve. Soit p = ΠK (u), la projection de u sur K. u ∈
/ K donc p 6= u. Soit d := p − u
(donc d 6= 0). On a

∀x ∈ K, 0 ≥ (x − p, u − p) = −(d, x − p).

Donc
(x, d) ≥ (d, p) = (d, d) + (u, d).
Au final, on choisit b = 12 (d, d) + (u, d) : on vérifie que (x, d) > b, et b > (u, d).

51
Lemme 6.4. Γ(a1 , . . . , ap ) est fermé

Preuve. Peut se faire par récurrence sur p.

Preuve du Lemme 6.2 : D’abord on vérifie facilement l’inclusion Γ(a1 , . . . , ap ) ⊂

{a1 , . . . , ap }oo . Réciproquement, on considère K := Γ(a1 , . . . , ap ). C’est un convexe,
fermé, non vide (0 ∈ K). Supposons (par l’absurde) l’existence d’un élément u, u ∈ /K
oo N
et u ∈ {a1 , . . . , ap } . D’après le Théorème de séparation, ∃d ∈ R , b ∈ R,

hd, vi > b > hd, ui, ∀v ∈ K. (6.2)

Notons que
(i) hd, ui < 0 car on peut prendre v = 0 ∈ K dans (6.2).
(ii) Aussi, ∀λ ≥ 0, λai ∈ K donc

b < hd, λai i = λhd, ai i.

A la limite λ → +∞, cela implique que hd, ai i ≥ 0. Donc

−d ∈ {a1 , . . . , ap }o .

(iii) Par définition, puisque u ∈ {a1 , . . . , ap }oo , on a donc h−d, ui ≤ 0, soit 0 ≤ hd, ui.
C’est en contradiction avec (i).
Voici un premier énoncé du Théorème de Karush, Kuhn et Tucker ou ”KKT”, dans
le cas simplifı́é de contraintes d’inégalité affines. (Le théorème général de KKT concerne
en fait les contraintes mixtes et sera vu plus loin.)

Théorème 6.1 (Karush, Kuhn et Tucker, cas d’inégalités affines). Soit K un

ensemble d’inégalités affines. On suppose que u est un minimiseur de J sur K, et que
J est différentiable en u ∈ K. Alors

∃λ = (λ1 , . . . , λp )T ∈ Rp , ∇J(u) + C T λ = 0 (6.3a)

λ ≥ 0, Cu − f ≤ 0, (6.3b)
∀i = 1, . . . , p, (Cu − f )i = 0 ou λi = 0. (6.3c)

On dira encore que λ = (λ1 , . . . , λp )T sont des multiplicateurs. L’ensemble des conditions
(6.3) représentent les conditions d’optimalité d’ordre 1 du problème de minimisation.

52
Elles s’écrivent de manière équivalente
p
X
T p
∃λ = (λ1 , . . . , λp ) ∈ R , ∇J(u) + λi ∇ϕi (u) = 0 (6.4a)
i=1
λ ≥ 0, ϕ(u) ≤ 0, (6.4b)

hϕ(u), λi = 0. (6.4c)

Preuve. On a vu que pour u, point de minimum local de J sur K : (∇J(u), d) ≥ 0

∀d ∈ TK (u), soit, d’après le Lemme 6.1 et le Lemme de Farkas 6.2 :
oo
o
−∇J(u) ∈ TK (u) = ∇ϕi (u), i ∈ A(u)

∈ Γ{ϕi (u), i ∈ A(u)}.

Donc il existe (λ1 , . . . , λp ) ∈ (R+ )p t.q.

p
X
−∇J(u) = λi ∇ϕi (u),
i=1

où l’on a choisi simplement λi = 0 si i ∈

/ A(u). En particulier, on a donc soit ϕi (u) = 0,
soit ϕi (u) < 0 et dans ce cas i ∈
/ A(u) et donc λi = 0. Cela implique aussi que
X
hλ, ϕ(u)i = λi ϕi (u) = 0,
i

ce qui conclut la preuve des relations (6.4). Pour obtenir l’écriture vectorielle (6.3), on
utilise le fait que i λi ∇ϕi (u) = C T λ pour λ = (λ1 , . . . , λp )T .
P

6.2 Cas général - contraintes d’inégalité

Définition 6.2 (qualification des contraintes). Soit u ∈ K. On suppose ici que les
fonctions ϕi sont différentiables en u. On dira que les contraintes sont qualifiées en u
si

N soit h∇ϕi (u), wi < 0,
∃w ∈ R , ∀i ∈ A(u), (6.5)
soit h∇ϕi (u), wi = 0, et ϕi affine.

53
Géométriquement, ∇ϕi (u) représente la normale sortante à la courbe ϕi (v) = 0, en
v = u (normale dirigée suivant la région ou ϕi > 0). Donc cela revient à supposer qu’on
a un vecteur w qui est rentrant pour les contraintes (actives) d’inégalité, et strictement
rentrant par rapport aux contraintes d’inégalité (actives) non affines.

Théorème 6.2 (CO1, contraintes générales d’inégalité). On suppose que u est un point
de minimum local de J sur K, que J, ϕ1 , . . . , ϕp sont différentiables en u et que les
contraintes sont qualifiées en u. Alors les conclusions du théorème KKT, (6.4), restent
valables.

Preuve. Toute la preuve repose sur la caractérisation suivante.

TK (u) = {∇ϕi (u), i ∈ A(u)}o . (6.6)

Pour le vérifier, notons W l’ensemble de droite. On a déjà vu que TK (u) ⊂ W (Lemme

6.1). Réciproquement, prenons d ∈ W : on a

hd, ∇ϕi (u)i ≤ 0, ∀i t.q. ϕi (u) = 0. (6.7)

Pour montrer que d ∈ TK (u), nous allons procéder indirectement : en considérant un

vecteur w vérifiant les propriétés (6.5), nous allons montrer que pour λ > 0 fixé, d+λw ∈
TK (u). Comme TK (u) est fermé, en passant à la limite quand λ → 0, on conclura alors
que la direction limite d appartient également à TK (u).
Ainsi, soit w un vecteur vérifiant (6.5) et soit λ > 0 ; on introduit la suite un =
u + n1 (d + λw). Montrons que pour n assez grand, un ∈ K.
/ A(u) alors ϕi (u) < 0 et donc ϕi (u + n1 (d + λw)) < 0 pour n assez grand.
Si i ∈
Si i ∈ A(u) : ϕi (u) = 0. Premier sous-cas : h∇ϕi (u), wi < 0 : alors, en utilisant (6.7),
1 1
ϕi (un ) = ϕi (u) + h∇ϕi (u), d + λwi + o( ),
n n
1
≤ λh∇ϕi (u), wi + o(1) .
n
Ansi ϕi (un ) < 0 pour n assez grand. Deuxième sous-cas : h∇ϕi (u), wi = 0 avec ϕi affine.
Alors
1
ϕi (un ) = ϕi (u) + h∇ϕi (u), d + λwi (car ϕi est affine)
n
1
= h∇ϕi (u), di ≤ 0.
n

54
On en déduit que pour n assez grand, ∀i, ϕi (un ) ≤ 0. Cela montre que d + λw ∈ TK (u).
On conclut alors que d ∈ TK (u), ce qui conclut la preuve de (6.6), et du Théorème 6.2.

6.3 Contraintes mixtes

On considère maintenant le cas le plus général des contraintes mixtes :

N
K := x ∈ R , ϕi (x) = 0, 1 ≤ i ≤ p, ψj (x) ≤ 0, 1 ≤ j ≤ q (6.8)

où ϕi , ψj : RN → R, avec p, q ≥ 0 entiers qui représentent le nombre de contraintes

d’égalité ou d’inégalité, respectivement. On notera aussi les fonctions ϕ : RN → Rp et
ψ : RN → Rq :

ϕ(x) := (ϕ1 (x), . . . , ϕp (x))T , ψ(x) := (ψ1 (x), . . . , ψp (x))T ,

de sorte que K = {x, ϕ(x) = 0 et ψ(x) ≤ 0}.

Le cas particulier des contraintes affines (mixtes) s’écrit alors

K = {x, Cx − f = 0, Dx − g ≤ 0},

pour des matrices C ∈ Rp×N , f ∈ Rp et D ∈ Rq×N , g ∈ Rq .

Nous allons pouvoir écrire les conditions d’optimalité pour un minimum sous contraintes
mixtes, dans deux cas : soit dans le cas des contraintes affines, soit dans un cadre général
sous une hypothèse de qualification des contraintes. Le résultat final sera le Théorème
de Karush, Kuhn et Tucker.

Définition 6.3 (qualification des contraintes). Soit u ∈ K. On suppose que les fonctions
ϕi sont de classe C 1 au voisinage de u, et les ψj sont différentiables en u. On dira que
les contraintes sont qualifiées en u si : soit toutes les contraintes sont affines, soit il
existe un vecteur w ∈ RN ,

• {∇ϕ1 (u), . . . , ∇ϕp (u)} libre, (6.9)

et h∇ϕi (u), wi = 0, ∀1 ≤ i ≤ p, (6.10)

soit h∇ψi (u), wi < 0,
• ∀i ∈ A(u), (6.11)
soit h∇ψi (u), wi = 0, et ψi affine.

55
Géométriquement cela revient à supposer qu’on a un vecteur w qui est tangent aux
contraintes d’égalité, et rentrant pour les contraintes d’inégalité (strictement rentrant
si ψi n’est pas affine).
On remarque que si toutes les contraintes sont affines, alors tout point u de K est
qualifié.

Lemme 6.5. Si les contraintes sont qualifiées en un point u ∈ K (et en particulier

pour des contraintes affines), on a

TK (u) = {∇ϕi (u), 1 ≤ i ≤ p}⊥ ∩ {∇ψj (u), j ∈ A(u)}o . (6.12)

Preuve. On commence par vérifier l’inclusion ⊂. Ensuite, pour l’inclusion réciproque :

la preuve est simple dans le cas affine ; dans le cas général, on procède comme dans la
preuve du Théorème 5.2, et de celle du Théorème 6.2. En supposant que d est dans
l’ensemble de droite de (6.12), on pose d0 = d + λw pour un λ > 0. On construit une
suite un vérifiant ϕi (un ) = 0, un = u + n1 d0 + o( n1 ). Enfin on vérifie que cette suite vérifie
aussi ψj (un ) ≤ 0, pour n assez grand. Ainsi d + λw ∈ TK (u), pour tout λ > 0, et on
conclut à d ∈ TK (u).

Théorème 6.3 (Karush, Kuhn et Tucker, cas mixte). Soit K un ensemble de

contraintes mixtes comme défini par (6.8). On suppose que u est un point de minimum
de J sur K, J est différentiable en u ∈ K, et les contraintes sont qualifiées en u. Alors

∃λ = (λ1 , . . . , λp )T ∈ Rp , µ = (µ1 , . . . , µq )T ∈ Rq , (6.13a)

X p Xq
∇J(u) + λi ∇ϕi (u) + µj ∇ψj (u) = 0,
i=1 j=1
ϕi (u) = 0, ∀1 ≤ i ≤ p, (6.13b)
µj ≥ 0, ψj (u) ≤ 0, et µj ψj (u) = 0, ∀1 ≤ j ≤ q. (6.13c)

On dira encore que les λ = (λ1 , . . . , λp )T et µ = (µ1 , . . . , µq )T sont des multiplicateurs.

L’ensemble des conditions (6.3) représentent les conditions d’optimalité d’ordre 1 du
problème de minimisation, ou conditions (KKT).

Preuve. On remarque que

TK (u) = {∇ϕi (u), 1 ≤ i ≤ p}⊥ ∩ {∇ψj (u), j ∈ A(u)}o

= {(∇ϕi (u), −∇ϕi (u))1≤i≤p , (∇ψj (u))j∈A(u) }o ,

56
et donc, d’après le lemme de Farkas 6.2,

o
−∇J(u) ∈ TK (u) = Γ ± ∇ϕi (u)1≤i≤p , (∇ψj (u))j∈A(u)

En particulier il existe des coefficients λ1i , λ2i ≥ 0 et µj ≥ 0 t.q.

X X
−∇J(u) = λ1i ∇ϕi (u) + λ2i (−∇ϕi (u)) + µj ∇ψj (u)
i j∈A(u)
X X
= λi ∇ϕi (u) + µj ∇ψj (u).
i j∈A(u)

On conclut comme dans le cas des contraintes d’inégalité.

Théorème 6.4. Réciproquement, si les conditions (KKT) sont satisfaites, si J est

convexe sur K, si les ϕi sont affines et les ψj sont convexes (avec J, ψ1 , . . . , ψq différentiables
en u ∈ K), alors u est un minimiseur global de J sur K.

Preuve. Posons
X X
L(v, α, β) := J(v) + αi ϕi (v) + βj ψj (v),
i j

aussi appelé Lagrangien du problème. On a v → L(v, λ, µ) convexe, puisque J convexe,

P P
v → i αi ϕi (v) est affine donc convexe, et les µj ≥ 0 donc j βj ψj (v) est convexe.
Enfin la somme de fonctions convexes est convexe. De plus, ∇v L(u, λ, µ) = ∇J(u) +
Pp Pq
i=1 λi ∇ϕi (u) + j=1 µj ∇ψj (u) = 0 d’après KKT. Ainsi, u est un minimiseur global
N
de L sur R :
L(u, λ, µ) ≤ L(v, λ, µ), ∀v ∈ RN .

Mais par ailleurs, au vu des conditions (KKT), on a J(u) = L(u, λ, µ), et pour v dans
K on voit que L(v, λ, µ) ≤ J(v) (en utilisant que µ ≥ 0). Ainsi J(u) ≤ J(v) pour tout
v ∈ K.

57
58
Chapitre 7

Algorithmes de minimisation
pour les problèmes avec
contraintes

7.1 Algorithme de gradient projeté

On suppose que K ⊂ RN est un convexe fermé non vide, et J : RN → R. On cherche

à minimiser la fonctionnelle J sur K. On suppose J différentiable.

Algorithme de Gradient Projeté (GP)

On prend un point de départ u0 ∈ RN . On se donne un pas fixe ρ > 0.
On itère sur n ≥ 0 :
un+1 = ΠK (un − ρ∇J(un ))

Théorème 7.1. Soit J : RN → R, α-convexe, différentiable, avec ∇J : M -lipschitzien

pour un M > 0.
(i) Il existe un unique minimiseur u de J sur K, et, pour tout ρ > 0, ce minimiseur est
caractérisé par

u = ΠK (u − ρ∇J(u)). (7.1)

59
2α 0 N
(ii) Si ρ ∈]0, M 2 [, alors pour tout u ∈ R , l’algorithme (GP) converge vers u :

lim un = u.
n→∞

(iii) Enfin, la convergence est linéaire : ∃0 ≤ R < 1, ∃C ≥ 0, kun −uk ≤ CRn (∀n ≥ 0).

On pourrait aussi décider de faire varier le pas à chaque itération, et proposer une
méthode de gradient à pas optimal projeté.

Preuve. (i) : Comme J est α-convexe et différentiable, le minimiseur u de J sur K est

bien défini et unique. De plus il vérifie u ∈ K et la condition d’optimalité

h∇J(u), v − ui ≥ 0, ∀v ∈ K. (7.2)

On en déduit que u ∈ K et

hu − ρ∇J(u) − u, v − ui ≤ 0, ∀v ∈ K.

Ces deux propriétés caractérisent le fait que

u = ΠK (u − ρ∇J(u)). (7.3)

Réciproquement, cette relation est équivalente à (7.2). Comme J est convexe, cette
condition implique que u est un minimiseur global de J sur K.
(ii)-(iii) : On peut faire la différence entre le schéma et (7.3). En utilisant le fait
que ΠK est 1-lipschitzienne,

kun+1 − uk2 = kΠK (un − ρ∇J(un )) − ΠK (u − ρ∇J(u))k2 (7.4)

≤ k(un − ρ∇J(un )) − (u − ρ∇J(u))k2 (7.5)

La fin de la preuve est la même que pour la méthode de gradient à pas fixe.

Le problème du schéma est qu’il faut pouvoir calculer ΠK . Si ΠK est facilement
calculable, on peut utiliser l’algorithme de gradient projeté (voir section 7.2). Sinon, on
verra d’autres algorithmes à la section 7.3.

60
7.2 Cas particuliers de projections
Lemme 7.1. Si A ⊂ Rp et B ⊂ Rq sont deux ensembles convexes fermés non vides, et
(x, y) ∈ Rp × Rq :
ΠA×B ((x, y)) = (ΠA (x), ΠB (y)).

Ceci se généralise facilement à un produit :

ΠA1 ×···×Ak ((x1 , . . . , xk )) = (ΠA1 (x1 ), . . . , ΠAk (xk )).

Lemme 7.2. Si −∞ ≤ a ≤ b ≤ +∞,


 a si x ≤ a

Π[a,b] (x) = x si x ∈ [a, b] = min(max(x, a), b).

b si x > b


Corollaire : Projection sur un parallelépipède. Si K = N

Q
i=1 [ai , bi ] et x = (xi )1≤i≤N ,
alors
ΠK (x) = Π[ai ,bi ] (xi ) ≡ min(max(xi , ai ), bi )
1≤i≤N 1≤i≤N

Dans le cas particulier où K = (R+ )p , on obtient ΠK (x) = max(x, 0) = max(xi , 0) .
1≤i≤N
En conclusion, si K est particulier (un parallèlépipède, une boule), on peut savoir
calculer ΠK (x) et l’algorithme de gradient projeté est envisageable. Dans le cas général,
on ne sait pas calculer ΠK (x) et il faut recourir à d’autres méthodes.

7.3 Algorithme d’Uzawa : contraintes d’égalité

On considère le cas de p contraintes d’égalité affines

K := {x, Cx − f = 0}.

Dans ce cas, les conditions d’optimalité s’écrivent

∃λ ∈ Rp , ∇J(u) + C T λ = 0 (7.6a)
Cu − f = 0 (7.6b)

61
On réécrit ces équations, pour un ρ > 0, sous la forme

∃λ ∈ Rp , ∇J(u) + C T λ = 0 (7.7a)
λ = λ + ρ(Cu − f ). (7.7b)

Cette dernière forme suggère alors l’algorithme suivant.

Algorithme d’Uzawa (U1), contraintes d’égalité affines

On prend un multiplicateur de départ λ0 ∈ Rp . On fixe un pas ρ > 0.
Puis on itère sur n ≥ 0 :
(i) Calculer un t.q. ∇J(un ) + C T λn = 0.
(ii) Calculer λn+1 = λn + ρ(Cun − f ).

Pour que l’algorithme soit bien défini il faudra montrer l’existence d’un vecteur un
solution de (i).

Théorème 7.2 (Cas de contraintes d’égalité affines). Soit J : RN → R, α-convexe,

différentiable, et un ensemble de contraintes K := {x, Cx − f = 0}, supposé non vide.
(i) Il existe un unique minimiseur u de J sur K.
2α 0
(ii) Pour tout ρ ∈]0, kCk 2 [, pour tout λ de départ, l’algorithme d’Uzawa (U1) converge :

limn→∞ un = u.
(iii) Si, de plus, C est surjective et si ∇J est continue, alors on a aussi la convergence
de λn vers un unique λ solution de (7.7a).

Preuve. (i) est classique. (ii). Commençons par vérifier l’existence de un . On introduit
pour cela une fonction L : RN × Rp → R, appelée lagrangien du problème, et définie
par :
∀(v, µ) ∈ RN × Rp L(v, µ) = J(v) + hµ, Cv − f i.

Supposons λn connu, et considérons l’application

v ∈ RN 7→ L(v, λn ) = J(v) + hλn , Cv − f i.

C’est une fonction strictement convexe de v ; en effet, J est strictement convexe et les
contraintes étant affines, le terme hλn , Cv − f i est également une fonction affine de v et
en particulier c’est une fonction convexe de v. De plus, λn étant fixé, la fonction v 7→

62
L(v, λn ) est coercice car J est coercive, avec une croissance quadratique à l’infini (car α-
convexe), et les contraintes sont des fonctions affines donc à croissance linéaire à l’infini.
Ainsi L(·, λn ) possède un unique minimiseur un sur RN , caractérisé par ∇v L(un , λn ) =
0, c’est-à-dire
∇J(un ) + C T λn = 0.

Cela prouve l’existence et l’unicité de un .

Travaillons ensuite sur la convergence des λn :

kλn+1 − λk2 = k(λn + ρ(Cun − f )) − (λ + ρ(Cu − f ))k2

= kλn − λ + ρC(un − u)k2
= kλn − λk2 + 2ρhλn − λ, C(un − u)i + ρ2 kC(un − u)k2 .

On a d’une part kC(un − u)k2 ≤ kCk2 kun − uk2 , d’autre part, en utilisant les relations
sur les gradients et l’α-convexité de J :

hλn − λ, C(un − u)i = hC T (λn − λ), un − ui

= −h∇J(un ) − ∇J(u), un − ui ≤ −αkun − uk2 .

Ainsi,

kλn+1 − λk2 ≤ kλn − λk2 − γkun − uk2 , (7.8)

avec
γ := ρ(2α − ρkCk2 ).
2α
En particuliern si 0 < ρ < kCk 2 , on a γ > 0.
n 2
La suite n → kλ − λk est alors décroissante, minorée (par 0), donc convergente
vers une limite notée `. Ensuite on renverse l’inégalité (7.8) pour écrire
n→∞
γkun − uk2 ≤ kλn − λk2 − kλn+1 − λk2 → ` − ` = 0

Cela démontre la convergence de la suite un vers u, mais pas nécessairement la conver-

gence de la suite λn .
(iii) C T est alors injective ; en effet, C est surjective signifie que l’application X ∈
RN 7→ CX ∈ Rp est surjective, ou encore que rg(C) = p ; ainsi rg(C T ) = rg(C) = p et
donc, d’après le théorème du rang, dim(KerC T ) + rg(C T ) = p d’où dim(KerC T ) = 0.

63
Par conséquent CC T est inversible ; en effet, c’est une matrice carrée dont le noyau est
réduit à 0 (si un vecteur X ∈ RN vérifie CC T X = 0, alors kC T Xk2 = hC T X, C T Xi =
hX, CC T Xi = 0, donc C T X = 0 et X = 0 puisque C T est injective). En utilisant la
relation C T λn = −∇J(un ), on en déduit CC T λn = −C∇J(un ) et donc

λn = −(CC T )−1 C ∇J(un ).

Comme un → u, par continuité de ∇J, on obtient la convergence des λn vers un vecteur

λ ∈ Rp . Enfin par passage à la limite dans la relation ∇J(un ) + C T λn = 0, on en
déduit que λ satisfait (7.7a) (l’unicité d’un tel λ s’obtient en écrivant comme ci-dessus,
λ = −(CC T )−1 C ∇J(u), ce qui définit λ de manière unique puisque u est également
défini de manière unique).

7.4 Algorithme d’Uzawa : contraintes d’inégalité

7.4.1 Contraintes d’inégalité affines
On considère le cas de p contraintes d’inégalités affines

K := {x, Cx − f ≤ 0}.

Rappelons que si u est un point de minimum local de J sur K, et si J est différentiable

en u, alors on peut écrire les conditions (KKT) sous la forme suivante :

∃λ ∈ Rp , ∇J(u) + C T λ = 0 (7.9a)
λ ≥ 0, Cu − f ≤ 0, hλ, Cu − f i = 0. (7.9b)

Le lemme suivant permet de réécrire le deuxième jeu d’équations sur λ de manière

plus compacte :

Lemme 7.3. Soit F := (R+ )p , et ρ > 0. Pour tout λ ∈ Rp , C ∈ Rp×N et f ∈ Rp , on a

λ ≥ 0, Cu − f ≤ 0, hλ, Cu − f i = 0 ⇐⇒ λ = ΠF (λ + ρ(Cu − f )).

Preuve. On procède par double implication. Supposons que λ ≥ 0, Cu − f ≤ 0 et

hλ, Cu − f i = 0, et montrons que λ = ΠF (λ + ρ(Cu − f )). Comme λ ≥ 0, λ ∈ F ; il
s’agit donc de montrer que pour tout µ ∈ F ,

hλ − λ + ρ(Cu − f ) , λ − µi ≤ 0.

64
Or,

hλ − λ + ρ(Cu − f ) , λ − µi = −hρ(Cu − f ), λ − µi
= −ρhCu − f, λi + ρhCu − f, µi ≤ 0

puisque hCu − f, λi = 0, ρ > 0, Cu − f ≤ 0 et µ ≥ 0.

Réciproquement, supposons que λ = ΠF (λ + ρ(Cu − f )) ; alors λ ≥ 0 et pour tout
µ ≥ 0,
−hρ(Cu − f ), λ − µi ≤ 0 donc hCu − f, λ − µi ≥ 0.

En prenant µ = 0 ∈ Rp (resp. µ = 2λ), on obtient hCu − f, λi ≥ 0 (resp. hCu − f, −λi ≥

0), d’où hCu − f, λi = 0. Enfin, d’après la formule de projection sur F = (R+ )p , on peut
écrire pour chaque i ∈ {1, . . . , p},

λi = max(λi + ρ(Cu − f )i , 0).

En particulier, λi ≥ λi + ρ(Cu − f )i donc (Cu − f )i ≤ 0. Cela montre que Cu − f ≤ 0.

Ainsi on peut réécrire les conditions d’optimalité sous la forme suivante, pour tout
ρ>0:

∃λ ∈ Rp , ∇J(u) + C T λ = 0 (7.10a)
λ = ΠF (λ + ρ(Cu − f )). (7.10b)

Cela suggère alors l’algorithme suivant.

Algorithme d’Uzawa (U2), contraintes d’inégalité affines

On prend un multiplicateur de départ λ0 ∈ (R+ )p . On fixe un pas ρ > 0.
Puis on itère sur n ≥ 0 :
(i) Calculer un t.q. ∇J(un ) + C T λn = 0
(ii) Calculer λn+1 = ΠF λn + ρ(Cun − f ) .

Théorème 7.3 (Cas de contraintes d’inégalité affines). Soit J : RN → R, α-convexe,

différentiable, et un ensemble de contraintes K := {x ∈ RN , Cx − f ≤ 0}, supposé non
vide.
(i) Il existe un unique minimiseur u de J sur K.

65
2α 0
(ii) Pour tout ρ ∈]0, kCk 2 [, pour tout λ de départ, l’algorithme d’Uzawa (U2) est bien

défini et converge : limn→∞ un = u.

(iii) Si, de plus, C est surjective et ∇J est continue, alors on a aussi la convergence de
la suite λn vers un unique λ solution de (7.10a).

Preuve. La preuve est pratiquement identique à celle du théorème 7.2 ; la seule différence
provient de la projection sur F , qui cependant n’a pas d’influence sur la convergence de
un , comme on le remarque en écrivant :

kλn+1 − λk2 = kΠF (λn + ρ(Cun − f )) − ΠF (λ + ρ(Cu − f ))k2

≤ k(λn + ρ(Cun − f )) − (λ + ρ(Cu − f ))k2

(puisque la projection ΠF est une application 1-lipschitzienne).

7.4.2 Contraintes d’inégalité convexes

On considère maintenant le cas de contraintes de la forme

K := {x ∈ RN , ϕi (x) ≤ 0, 1 ≤ i ≤ p},

où chaque contrainte ϕi : RN → R est supposée convexe. On note ϕ(x) = (ϕ1 (x), . . . , ϕp (x))T ,
de sorte que K s’écrive aussi {x, ϕ(x) ≤ 0}.
Rappelons que si u est un point de minimum local de J sur K, avec J, ϕi différentiables
en u, et si les contraintes sont qualifiées en u, alors on peut écrire les conditions (KKT)
sous la forme suivante :
p
X
p
∃λ ∈ R , ∇J(u) + λi ∇ϕi (u) = 0 (7.11a)
i=1
λ ≥ 0, ϕ(u) ≤ 0, hλ, ϕ(u)i = 0. (7.11b)

Le lemme suivant permet de réécrire le deuxième jeu d’équations sur λ de manière

plus compacte :

Lemme 7.4. Soit F := (R+ )p , et ρ > 0. Pour tout λ ∈ Rp et ϕ(u) ∈ Rp , on a

λ ≥ 0, ϕ(u) ≤ 0, hλ, ϕ(u)i = 0 ⇐⇒ λ = ΠF (λ + ρϕ(u)).

66
Preuve. La preuve est identique à celle du lemme 7.3, où Cu − f est remplacé par ϕ(u).

Ainsi on peut réécrire les conditions d’optimalité sous la forme suivante, pour tout
ρ>0:
p
X
p
∃λ ∈ R , ∇J(u) + λi ∇ϕi (u) = 0 (7.12a)
i=1
λ = ΠF (λ + ρϕ(u)). (7.12b)

Ceci suggère alors l’algorithme suivant.

Algorithme d’Uzawa (U2), contraintes d’inégalités convexes

On prend un multiplicateur de départ λ0 ∈ (R+ )p . On fixe un pas ρ > 0.
Puis on itère sur n ≥ 0 :
(i) Calculer un t.q. ∇J(un ) + pi=1 λni
∇ϕi (un ) = 0
P

(ii) Calculer λn+1 = ΠF λn + ρϕ(un ) .

Pour que l’algorithme soit bien défini il faudra montrer l’existence d’un vecteur un
solution de (i).

Théorème 7.4 (Cas de contraintes d’inégalité convexes). Soit J : RN → R, α-convexe,

différentiable, et un ensemble de contraintes K := {x ∈ RN , ϕi (x) ≤ 0, i = 1, . . . , p}
avec ϕi convexes, différentiables. On suppose de plus que l’application x ∈ RN 7→
ϕ(x) := (ϕ1 (x), . . . , ϕp (x))T est M -lipschitzienne. On suppose enfin que les contraintes
sont qualifiées au point u.
(i) Il existe un unique minimiseur u de J sur K.
2α 0 de départ, l’algorithme d’Uzawa (U2) est bien
(ii) Pour tout ρ ∈]0, M 2 [, pour tout λ

défini et converge : lim un = u.

(iii) Si, de plus, la matrice C(u) = [∇ϕ1 (u), . . . , ∇ϕp (u)]T est surjective, et si J et ϕ
sont de classe C 1 , alors on a aussi la convergence de la suite λn .

Preuve. (i) est classique.

(ii). Commençons par vérifier l’existence de un . On note que L(v, λn ) = J(v)+ i λni ϕi (v)
P

est une fonction strictement convexe de v, car J est strictement convexe, les contraintes
ϕi sont convexes et les λni sont positifs. Elle est coercice car J l’est, avec une croissance

67
quadratique à l’infini (car α-convexe), et les ϕi sont à croissance au plus linéaire à l’infini
(car Lipschitz). Ainsi L(., λn ) possède un unique minimiseur un sur RN , caractérisé par
∇v L(un , λn ) = 0, soit
Xp
n
∇J(u ) + λni ∇ϕi (un ) = 0.
i=1

(Ce qui prouve donc l’existence et l’unicité de un .)

Remarquons que par définition du minimiseur un ,

∀v ∈ RN L(un , λn ) ≤ L(v, λn ),

c’est-à-dire

∀v ∈ RN J(un ) + hλn , ϕ(un )i ≤ J(v) + hλn , ϕ(v)i. (7.13)

Soit w ∈ RN et t ∈]0, 1[ ; en appliquant (7.13) avec v = un + t(w − un ), on obtient

p
X
n n n
J(u + t(w − u )) − J(u ) + λni (ϕi (un + t(w − un )) − ϕi (un )) ≥ 0. (7.14)
i=1

Mais par convexité des ϕi ,

ϕi (un + t(w − un )) − ϕi (un ) ≤ t(ϕi (w) − ϕi (un )).

D’après (7.14), on en déduit :

p
X
J(un + t(w − un )) − J(un ) + t λni (ϕi (w) − ϕi (un )) ≥ 0.
i=1

En divisant par t et en passant à la limite quand t → 0, on obtient :

p
X
N n n
∀w ∈ R h∇J(u ), w − u i + λni (ϕi (w) − ϕi (un )) ≥ 0. (7.15)
i=1

Considérons à présent le point u et le vecteur λ ; d’après les conditions (KKT), ils

vérifient la relation
p
X
∇J(u) + λi ∇ϕi (u) = 0. (7.16)
i=1

68
P
En définissant comme plus haut le lagrangien L(v, λ) = J(v) + i λi ϕi (v), on constate
que la relation (7.16) s’écrit ∇v L(u, λ) = 0, ce qui montre que u est le minimiseur
unique de l’application v 7→ L(v, λ), sur RN (l’existence et l’unicité d’un tel minimiseur
s’obtiennent par les mêmes arguments que pour l’application v 7→ L(v, λn )). On a donc :

∀v ∈ RN L(u, λ) ≤ L(v, λ).

En appliquant le même raisonnement que précédemment, on en déduit

p
X
∀w ∈ RN h∇J(u), w − ui + λi (ϕi (w) − ϕi (u)) ≥ 0. (7.17)
i=1

En prenant w = u dans (7.15), w = un dans (7.17), on obtient

p
X
N n n
∀w ∈ R h∇J(u ), u − u i + λni (ϕi (u) − ϕi (un )) ≥ 0.
i=1
X p
∀w ∈ RN h∇J(u), un − ui + λi (ϕi (un ) − ϕi (u)) ≥ 0.
i=1

En sommant, on en déduit
p
X
h∇J(u) − ∇J(un ), un − ui + (λi − λni )(ϕi (un ) − ϕi (u)) ≥ 0.
i=1

En utilisant l’α-convexité de J, on en déduit finalement

hλn − λ, ϕ(un ) − ϕ(u)i ≤ −h∇J(un ) − ∇J(u), un − ui

≤ −αkun − uk2 . (7.18)

Nous allons utiliser l’estimation (7.18) pour démontrer la convergence de la suite

kλn− λk. Pour cela, on écrit :
2
kλn+1 − λk2 = ΠF λn + ρϕ(un ) − ΠF λ + ρϕ(u)

≤ k(λn + ρϕ(un )) − (λ + ρϕ(u))k2

≤ k(λn − λ) + ρ(ϕ(un ) − ϕ(u))k2
≤ kλn − λk2 + 2ρhλn − λ, ϕ(un ) − ϕ(u)i + ρ2 M 2 kun − uk2
≤ kλn − λk2 − 2αρkun − uk2 + ρ2 M 2 kun − uk2
≤ kλn − λk2 − γkun − uk2

69
en utilisant le caractère Lipschitz de ϕ et l’inégalité (7.18) avec

γ := ρ(2α − ρM 2 ).

On conclut alors exactement comme pour la convergence de l’algorithme (U1). On

obtient donc la convergence de la suite un , mais pas nécessairement celle de la suite λn .
(iii) Si les fonctions ϕi sont de classe C 1 , alors l’application v ∈ RN 7→ C(v) est
continue (rappelons que la matrice C(v) est définie par C(v) = [∇ϕ1 (v), . . . , ∇ϕp (v)]T ).
De plus (voir la preuve de la convergence de l’algorithme d’Usawa pour le cas des
contraintes d’égalité affines), C(u) étant surjective, la matrice C(u)T est injective, et
dans ce cas, la matrice C(u)C(u)T est inversible. Par conséquent, son déterminant est
non nul. Par continuité du déterminant et de l’application v ∈ RN 7→ C(v)C(v)T ,
puisque det(C(u)C(u)T ) 6= 0, la convergence de un vers u entraı̂ne que pour n assez
grand, on a également det(C(un )C(un )T ) 6= 0, c’est-à-dire que la matrice C(un )C(un )T
est inversible.
Or, la relation
p
X
n
∇J(u ) + λni ∇ϕi (un ) = 0
i=1

s’écrit
∇J(un ) + C(un )T λn = 0,

d’où
C(un )∇J(un ) + C(un )C(un )T λn = 0.

Pour n assez grand, la matrice C(un )C(un )T est inversible, ce qui permet d’exprimer
λn sous la forme suivante :

λn = −(C(un )C(un )T )−1 C(un )∇J(un ).

Comme un → u, on en déduit par continuité la convergence des λn vers une limite λ∗

qui s’écrit
λ∗ = −(C(u)C(u)T )−1 C(u)∇J(u).

En passant à la limite dans la relation

∇J(un ) + C(un )T λn = 0,

70
on obtient (par continuité des dérivées partielles de J)

∇J(u) + C(u)T λ∗ = 0.

Ainsi λ∗ est solution de (7.12a) ; c’est même l’unique solution du système, puisque par
injectivité de C(u)T , si un vecteur µ∗ satisfait ∇J(u) + C(u)T µ∗ = 0, alors C(u)T µ∗ =
C(u)T λ∗ et donc µ∗ = λ∗ .

7.5 Méthode de pénalisation

On considère une fonctionnelle J, continue, coercive sur un ensemble de contraintes
K, où K ⊂ RN est supposé fermé et non vide. On considère le problème d’optimisation
sous contrainte suivant :

inf J(v) (7.19)

v∈K

On introduit une fonction ϕ : RN → R, continue, telle que, pour tout v dans RN :

ϕ(v) ≥ 0,

et
ϕ(v) = 0 ⇔ v ∈ K.

On considère enfin pour tout n ∈ N∗ et v ∈ RN , la fonctionnelle

Jn (v) := J(v) + nϕ(v), (7.20)

et le problème pénalisé correspondant, sur RN :

inf Jn (v). (7.21)

v∈RN

L’avantage du problème pénalisé (7.21) est qu’il s’agit d’un problème de minimisation
sans contrainte (posé sur RN ).
Exemples type de pénalisations :
1. Pour K := {v, Cv − f = 0}, ϕ(v) := kCv − f k2 .
2. Pour K := {v, Cv − f ≤ 0}, ϕ(v) := k max(Cv − f, 0)k2 .

71
On a alors le résultat suivant.

Théorème 7.5. On suppose que (7.19) admet un unique minimiseur noté u. On suppose
que pour tout n ∈ N∗ , un est un point de minimum du problème (7.21) sur RN . Alors

lim un = u.
n→∞

Preuve. Comme un est un minimiseur pour (7.21) sur RN , on a en particulier Jn (un ) ≤

Jn (u), c’est-à-dire

J(un ) + nϕ(un ) ≤ J(u) (7.22)

(puisque u ∈ K on a ϕ(u) = 0). Comme ϕ ≥ 0, on en déduit que J(un ) ≤ J(u) et

donc que J(un ) est une suite bornée. Comme J est coercive, cela implique que un est
également une suite bornée.
Pour démontrer la convergence de la suite (un ), on va procéder indirectement en
considérant des sous-suites convergentes. On rappelle pour cela un lemme de topologie :

Lemme 7.5. Soit (vn ) une suite à valeurs dans RN , telle que de toute suite extraite,
on puisse extraire une sous-suite convergente vers une même limite v ∈ RN . Alors toute
la suite (vn ) est convergente, et de limite v.

Soit (unk ) une sous-suite de (un ). Comme unk est bornée dans RN , on peut à nouveau
en extraire une sous-suite convergente, vers un v ∈ RN . (On note encore unk cette sous-
suite.) Tout d’abord
J(unk ) ≤ J(u),

donc par continuité de J et en passant à la limite,

J(v) ≤ J(u).

D’autre part, on a aussi d’après (7.22),

1 C
ϕ(unk ) ≤ (J(u) − J(unk )) ≤ .
nk nk

Ainsi, à la limite,
ϕ(v) ≤ 0.

72
On en déduit donc que ϕ(v) = 0, c’est-à-dire v ∈ K. Comme J(v) ≤ J(u), par unicité
du minimiseur pour le problème (7.19), cela implique que v = u. D’apres le lemme
précédent, on conclut donc que tout la suite (un ) converge vers u.

Estimation d’erreur. On peut dans certains cas estimer l’erreur faite sur le problème
pénalisé, en fonction de n ; par exemple, dans le cas de contraintes d’égalité K :=
{v, Cv−f = 0}. On considère ϕ(v) = 12 kCv−f k2 ; un calcul donne ∇ϕ(v) = C T (Cv−f ).
Supposons J différentiable. La condition d’optimalité pour un s’écrit alors

∇J(un ) + nC T (Cun − f ) = 0.

De plus Cu − f = 0 donc on a également C T (Cu − f ) = 0. Ainsi, on obtient

1
C T C(un − u) = − ∇J(un ).
n
Si C T C est inversible (ce qui est équivalent à supposer C injective), alors après multi-
plication par (C T C)−1 on obtient
1 c0
kun − uk ≤ k(C T C)−1 k k∇J(un )k ≤ ,
n n
où c0 est une constante (k∇J(un )k est bornée car un est une suite bornée).

Vous aimerez peut-être aussi

Conditions d'Optimalité en Optimisation
Pas encore d'évaluation
Conditions d'Optimalité en Optimisation
110 pages
Chapitre 1
Pas encore d'évaluation
Chapitre 1
16 pages
Optim PDF
Pas encore d'évaluation
Optim PDF
22 pages
Fiche Ao 101
Pas encore d'évaluation
Fiche Ao 101
10 pages
L3MIASHS AnalyseAvancée2
Pas encore d'évaluation
L3MIASHS AnalyseAvancée2
23 pages
Introduction Analyse Appliquée
Pas encore d'évaluation
Introduction Analyse Appliquée
92 pages
Opti l3
Pas encore d'évaluation
Opti l3
49 pages
Slides I
Pas encore d'évaluation
Slides I
21 pages
Introduction à l'optimisation convexe
Pas encore d'évaluation
Introduction à l'optimisation convexe
21 pages
Poly Optimisation
Pas encore d'évaluation
Poly Optimisation
72 pages
Polycopie Optimisation Licence SSD Et MID
Pas encore d'évaluation
Polycopie Optimisation Licence SSD Et MID
44 pages
Cours Optimisation
100% (1)
Cours Optimisation
43 pages
Part Ioral
Pas encore d'évaluation
Part Ioral
68 pages
Cours Opti
Pas encore d'évaluation
Cours Opti
31 pages
219 - Extremums. Existence, Caracterisation, Recherche. Exemples Et Applications.
Pas encore d'évaluation
219 - Extremums. Existence, Caracterisation, Recherche. Exemples Et Applications.
2 pages
Optimisation : Théorie et Applications
Pas encore d'évaluation
Optimisation : Théorie et Applications
7 pages
Support - cours-PM-Licence (1) Optimisation Casa
Pas encore d'évaluation
Support - cours-PM-Licence (1) Optimisation Casa
36 pages
Optimisation Mathématique FST Tanger
Pas encore d'évaluation
Optimisation Mathématique FST Tanger
12 pages
Cours Opt NL
Pas encore d'évaluation
Cours Opt NL
40 pages
Introduction à l'optimisation mathématique
100% (1)
Introduction à l'optimisation mathématique
45 pages
Optimisation
Pas encore d'évaluation
Optimisation
63 pages
Algorithmes d'Optimisation Différentiable
Pas encore d'évaluation
Algorithmes d'Optimisation Différentiable
44 pages
Poly Optimisation
Pas encore d'évaluation
Poly Optimisation
46 pages
Poly MAp I3
Pas encore d'évaluation
Poly MAp I3
52 pages
219 - Extremums: Existence, Caract Erisation, Recherche. Exemples Et Applications
Pas encore d'évaluation
219 - Extremums: Existence, Caract Erisation, Recherche. Exemples Et Applications
4 pages
TD4 ENSTA Corrigé
Pas encore d'évaluation
TD4 ENSTA Corrigé
5 pages
Transp Optim 2018
Pas encore d'évaluation
Transp Optim 2018
38 pages
Cours Optimisation
100% (2)
Cours Optimisation
39 pages
Poly Modélisation
Pas encore d'évaluation
Poly Modélisation
41 pages
I-Existence Et Unicité: 2 - Convexité
100% (1)
I-Existence Et Unicité: 2 - Convexité
4 pages
Leçon 219 Extrema, Existence, Caractérisations, Recherche, Exemples Et Applications
Pas encore d'évaluation
Leçon 219 Extrema, Existence, Caractérisations, Recherche, Exemples Et Applications
8 pages
Mines Ponts MP 2003 Maths 2 Corrige
Pas encore d'évaluation
Mines Ponts MP 2003 Maths 2 Corrige
4 pages
Methode Du Gradient Conjugue-1
Pas encore d'évaluation
Methode Du Gradient Conjugue-1
3 pages
Optimisation Convexe: Concepts et Applications
Pas encore d'évaluation
Optimisation Convexe: Concepts et Applications
4 pages
Poly 2022
Pas encore d'évaluation
Poly 2022
69 pages
Introduction à l'Optimisation Non Linéaire
Pas encore d'évaluation
Introduction à l'Optimisation Non Linéaire
22 pages
20 MP Mathc Sujet
Pas encore d'évaluation
20 MP Mathc Sujet
12 pages
X-Cachan 2023 PSI Mathématiques Ea
Pas encore d'évaluation
X-Cachan 2023 PSI Mathématiques Ea
5 pages
Cours Galerne
Pas encore d'évaluation
Cours Galerne
38 pages
Cours sur l'Optimisation Dynamique
Pas encore d'évaluation
Cours sur l'Optimisation Dynamique
91 pages
Partiel1920 Corr
Pas encore d'évaluation
Partiel1920 Corr
7 pages
Introduction à l'optimisation mathématique
Pas encore d'évaluation
Introduction à l'optimisation mathématique
11 pages
Exam2021 Map435 Cor Copie
Pas encore d'évaluation
Exam2021 Map435 Cor Copie
11 pages
Introduction à l'optimisation convexe
Pas encore d'évaluation
Introduction à l'optimisation convexe
44 pages
Sceance 2
Pas encore d'évaluation
Sceance 2
29 pages
Analyse Convexe Cours Mathinfo Ens
100% (1)
Analyse Convexe Cours Mathinfo Ens
4 pages
Chapitre 1et 2-OptimisationAvecContraintes
Pas encore d'évaluation
Chapitre 1et 2-OptimisationAvecContraintes
30 pages
Cours Optim M1SAF
Pas encore d'évaluation
Cours Optim M1SAF
65 pages
Cours Optim M1SAF
Pas encore d'évaluation
Cours Optim M1SAF
65 pages
Optimisation et Programmation Dynamique
Pas encore d'évaluation
Optimisation et Programmation Dynamique
69 pages
Fonctions de Plusieurs VariablesChap1,2,3
Pas encore d'évaluation
Fonctions de Plusieurs VariablesChap1,2,3
51 pages
Cours d'Optimisation Mathématique
Pas encore d'évaluation
Cours d'Optimisation Mathématique
51 pages
PC01 Correction
Pas encore d'évaluation
PC01 Correction
6 pages
Examen de Modélisation Mathématique
100% (1)
Examen de Modélisation Mathématique
6 pages
Optimisation Mathématique Avancée
Pas encore d'évaluation
Optimisation Mathématique Avancée
55 pages
Exam2021 - Map435 - Cor - Copie (2 Files Merged)
Pas encore d'évaluation
Exam2021 - Map435 - Cor - Copie (2 Files Merged)
12 pages
Poly Optimisation
Pas encore d'évaluation
Poly Optimisation
45 pages
Poly Cours
Pas encore d'évaluation
Poly Cours
142 pages
Analyse des fonctions fortement convexes
Pas encore d'évaluation
Analyse des fonctions fortement convexes
61 pages
Apprendre Format Tablette
100% (4)
Apprendre Format Tablette
82 pages
Exercices de Mecanique Des Sols
100% (1)
Exercices de Mecanique Des Sols
75 pages
Résultats Examens Liants-Bétons 2018/19
Pas encore d'évaluation
Résultats Examens Liants-Bétons 2018/19
18 pages
Précision - Théorie Des Erreurs - Tolérances - Cours Complet - V2
Pas encore d'évaluation
Précision - Théorie Des Erreurs - Tolérances - Cours Complet - V2
23 pages
Lettre de Motivation Pour Ecole D'ingénieur
67% (3)
Lettre de Motivation Pour Ecole D'ingénieur
1 page
Dakar, Le 01 Ma-WPS Office
Pas encore d'évaluation
Dakar, Le 01 Ma-WPS Office
2 pages
TD Statique
Pas encore d'évaluation
TD Statique
9 pages
TD 1
Pas encore d'évaluation
TD 1
9 pages
Vrai Rapport
Pas encore d'évaluation
Vrai Rapport
27 pages
Essai Tassement
Pas encore d'évaluation
Essai Tassement
10 pages
Demande de Stage
100% (1)
Demande de Stage
1 page
Demande de Stage
100% (1)
Demande de Stage
1 page
Corrigé CNC 2011 MP Maths 1
Pas encore d'évaluation
Corrigé CNC 2011 MP Maths 1
8 pages
Evn Psi MP Light
Pas encore d'évaluation
Evn Psi MP Light
40 pages
2bac PC SVT Série 02 Dérivation Et Ses Application - Étude de Fonctions
Pas encore d'évaluation
2bac PC SVT Série 02 Dérivation Et Ses Application - Étude de Fonctions
6 pages
Cour Etude Des Fonctions PCMA - 070617
Pas encore d'évaluation
Cour Etude Des Fonctions PCMA - 070617
3 pages
Série Expo
Pas encore d'évaluation
Série Expo
3 pages
EP1 Math 2018 Corrige
Pas encore d'évaluation
EP1 Math 2018 Corrige
17 pages
Corrigé du pré-sujet de probabilités 2014
Pas encore d'évaluation
Corrigé du pré-sujet de probabilités 2014
4 pages
FASCICULE AMESAT Licence 1
Pas encore d'évaluation
FASCICULE AMESAT Licence 1
229 pages
Probl Mes D Veloppements Limit S
Pas encore d'évaluation
Probl Mes D Veloppements Limit S
3 pages
Chap4 Evn
Pas encore d'évaluation
Chap4 Evn
58 pages
9 Intégration Sur Un Intervalle Quelconque-2
Pas encore d'évaluation
9 Intégration Sur Un Intervalle Quelconque-2
4 pages
Derivation Et Etude Des Fonctions Exercices Non Corriges 2
100% (3)
Derivation Et Etude Des Fonctions Exercices Non Corriges 2
11 pages
Cours LN 4 SC 2023 L
Pas encore d'évaluation
Cours LN 4 SC 2023 L
9 pages
Exercices Maths 2bac SM International FR 2 6
100% (1)
Exercices Maths 2bac SM International FR 2 6
3 pages
Théorèmes de Baire et Continuité
Pas encore d'évaluation
Théorèmes de Baire et Continuité
4 pages
Sujet de Révision N°3 - Corrigé
Pas encore d'évaluation
Sujet de Révision N°3 - Corrigé
8 pages
Cours de Maths Terminale D - Préparation Bac
95% (22)
Cours de Maths Terminale D - Préparation Bac
39 pages
Compte Rendus Matlab Youness Ait Laasri-1
Pas encore d'évaluation
Compte Rendus Matlab Youness Ait Laasri-1
35 pages
Concours ISE 2023 : Infos et Conditions
Pas encore d'évaluation
Concours ISE 2023 : Infos et Conditions
13 pages
Etude de Fonctions 3eme Maths Kooli M H 1
Pas encore d'évaluation
Etude de Fonctions 3eme Maths Kooli M H 1
6 pages
c1 4m 2023 2024 LPBT
Pas encore d'évaluation
c1 4m 2023 2024 LPBT
3 pages
Épreuve Maths Tle D: Polynômes et Fonctions
Pas encore d'évaluation
Épreuve Maths Tle D: Polynômes et Fonctions
2 pages
Copie de Cours Integrales A Parametre
Pas encore d'évaluation
Copie de Cours Integrales A Parametre
12 pages
BB1 Corrigé
Pas encore d'évaluation
BB1 Corrigé
7 pages
Z MPSI2 Exos
Pas encore d'évaluation
Z MPSI2 Exos
108 pages
Analys 1 A
Pas encore d'évaluation
Analys 1 A
74 pages
(Réviser Son Bac - Mathématiques Terminale, Série S-Essentiels PDF
Pas encore d'évaluation
(Réviser Son Bac - Mathématiques Terminale, Série S-Essentiels PDF
62 pages
Corrigé CCP Maths 1 MP 2000 : Analyse et Banach
Pas encore d'évaluation
Corrigé CCP Maths 1 MP 2000 : Analyse et Banach
4 pages
Limites de Suites : Exercices Corrigés
100% (3)
Limites de Suites : Exercices Corrigés
15 pages
TNS Gele
Pas encore d'évaluation
TNS Gele
195 pages