COURS OPTIMISATION

Cours lISFA, en M1SAF

Ionel Sorin CIUPERCA

Table des matires

1 Introduction
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Le problme gnral doptimisation . . . . . . . . . . . . . . . . . . . . . .
2 Quelques rappels de calcul diffrentiel, analyse
2.1 Rappel calcul diffrentiel . . . . . . . . . . . . .
2.1.1 Quelques Notations . . . . . . . . . . . .
2.1.2 Rappel gradient et hessienne . . . . . .
2.1.3 Rappel formules de Taylor . . . . . . . .
2.2 Convexit . . . . . . . . . . . . . . . . . . . . .
2.2.1 Rappel fonctions convexes . . . . . . . .
2.2.2 Fonctions elliptiques, fonctions coercives
2.2.3 Exemples des fonctions elliptiques . . . .
2.3 Conditions ncssaires de minimum . . . . . . .
2.4 Existence et unicit dun point de minimum . .

convexe et
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .

3 Optimisation sans contraintes

3.1 Mthodes de relaxation . . . . . . . . . . . . . . .
3.1.1 Description de la mthode . . . . . . . . .
3.1.2 Cas particulier des fonctions quadratiques
3.2 Mthodes de gradient . . . . . . . . . . . . . . . .
3.2.1 Mthodes de gradient pas optimal . . . .
3.2.2 Autres mthodes du type gradient . . . . .
3.3 La mthode des gradients conjugus . . . . . . . .
3.3.1 Le cas quadratique . . . . . . . . . . . . .
3.3.2 Cas dune fonction J quelconque . . . . .

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

extremum
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .

.
.
.
.
.
.
.
.
.
.

5
5
5
6
9
9
9
12
14
15
18

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

20
21
21
24
25
26
27
30
30
35

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

4 Optimisation avec contraintes

4.1 Rappel sur les multiplicateurs de Lagrange . . . . . . . . . . . . . . . . . .
4.2 Optimisation sous contraintes dingalits . . . . . . . . . . . . . . . . . . .
4.2.1 Conditions doptimalit de premier ordre : multiplicateurs de KarushKuhn-Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.2 Thorie gnrale du point selle . . . . . . . . . . . . . . . . . . . . .
2

4
4
4

36
37
38
39
46

4.3

4.2.3 Applications de la thorie du point selle loptimisation

4.2.4 Le cas convexe . . . . . . . . . . . . . . . . . . . . . . .
Algorithmes de minimisation avec contraintes . . . . . . . . . .
4.3.1 Mthodes de relaxation . . . . . . . . . . . . . . . . . . .
4.3.2 Mthodes de projection . . . . . . . . . . . . . . . . . . .
4.3.3 Mthodes de pnalisation exterieure . . . . . . . . . . . .
4.3.4 Mthode dUzawa . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

48
49
51
51
52
56
58

Chapitre 1
Introduction
1.1

Motivation

Voir cours en amphi

1.2

Le problme gnral doptimisation

On se donne :
1. Une fonction J : IRn 7 IR (fonction cot)
2. Un ensemble U IRn (ensemble des contraintes)
On cherche minimiser J sur U , cest dire, on cherche x U tel que
J(x ) = min J(x)
xU

ou quivalent
J(x ) J(x),

x U.

Chapitre 2
Quelques rappels de calcul diffrentiel,
analyse convexe et extremum
2.1

Rappel calcul diffrentiel

2.1.1

Quelques Notations

1. Pour tout n IN , IRn dsigne lespace euclidien IR IR IR ( produit n fois).

En gnral un vecteur x IRn sera not x = (x1 , x2 , xn )T (vecteur colonne).
2. On note e1 , e2 , en les lments de la base canonique de IRn , o ei est le vecteur
de IRn donn par :

0
si
j 6= i
(ei )j = ij =
,
i, j = 1, 2 n
(2.1)
1
si
j=i
(symboles de Kronecker).
3. Pour tous x, y IRn on note par < x, y > IR le produit scalaire de x et y, qui
est donn par
n
X
< x, y >=
xi yi .
i=1
n

4. Pour tout x IR on note par kxk 0 la norme euclidienne de x, donne par

v
u n
uX

x2i .
kxk = < x, x > = t
i=1

Pour tous x IRn et r > 0 on notera par B(x, r) la boule ouverte du centre x et
rayon r, donne par
B(x, r) = {y IRn ,
5

ky xk < r}.

5. Si a, b IRn on note [a, b] le sous-ensemble de IRn donn par

[a, b] = {a + t(b a) (1 t)a + tb, t [0, 1]}.
Lensemble [a, b] est aussi appell le segment reliant a b.
Remarques :
[a, b] = [b, a] (Exo !)
Si a, b IR avec a < b alors on retrouve le fait que [a, b] dsigne lintervalle des
nombres x IR tels que a x b.
6. On a
x IRn , y IRm , B Mm,n (IR)

< Bx, y > = < x, By >

7. Rappellons aussi lingalit de Cauchy-Schwarz :

| < x , y > | kxk kyk x, y IRn .

2.1.2

Rappel gradient et hessienne

Soit IRn un ouvert et f : IR.

1. On dit que f est de classe C m sur (f C m ()) si toutes les drives partielles
jusqu lordre m existent et sont continues.
2. Pour tout x et tout i {1, 2, , n} on note (quand )
f
1
(x) = lim [f (x + tei ) f (x)].
t 70 t
xi
(cest la drive partielle de f en x de direction xi .)
3. Pour tout x on note (quand )

f (x) =
(le gradient de f en x).
On note aussi
Jf (x) =

f f
f
,
,
x1 x2
xn

T

f f
f
,
,
x1 x2
xn

IRn ,

IRn ,

(la Jacobienne de f en x). On a

f = (Jf )T
4. Pour tous x et h IRn on note (quand )
f
1
(x) = lim [f (x + th) f (x)] = g 0 (0).
t 70 t
h
6

(cest la drive directionnelle de f en x de direction h) o on a not g(t) =

f (x + th).
Remarques :
i) f
(x) = 0
0
f
f
ii) x
(x) = e
(x)
i
i
Nous rappellons aussi la formule :

f
(x) = < f (x), h >,
h

x h IRn .

5. Pour x on note (quand ) 2 f (x) = la matrice carre Mn (IR) donne par

2 f (x)

ij

2f
(x),
xi xj

i, j = 1, 2, n.

(2 f (x) sappelle aussi la matrice hessienne de f en x).

Remarque : Si f C 2 () alors 2 f (x) est une matrice symmtrique x
(cest le Thorme de Schwarz).
Proposition 2.1. (Gradient de la compose) Supposons quon deux ouverts IRn et
U IR et deux fonctions f : 7 IR et g : U 7 IR avec en plus f () U (on peut alors
dfinir g f : 7 IR). Supposons que f, g sont de classe C 1 . Alors g f est aussi de classe
C 1 avec en plus
(g f )(x) = g 0 (f (x))f (x) x .
Preuve trs facile !
Proposition 2.2. (lien entre et 2 )
a) La i - me ligne de 2 f (x) est la Jacobienne du i - me lment de f .
b) On a
2 f (x)h = < f (x), h >, x , h IRn .
Dmonstration. a) vidente
b) On a :

< f (x), h >=

xi
xi

n
X
f
(x)hj
x
j
j=1

n
X


2f
=
(x)hj = 2 f (x)h i .
xi xj
j=1

Quelques exemples importantes :

1. Si f : IRn IR est une fonction constante alors f = 2 f = 0.

2. Soit f : IRn IR dfinie par

f (x) = < a , x >

x IRn ,

o a IRn est un vecteur donn (cest dire, f est une fonction linaire). Alors on
f
calcule facilement : x
= ak , donc
k
f = a
(le gradient est constant).
Ceci nous donne
2 f = 0.
3. Soit f : IRn IR donne par
f (x) = < Ax , x >

x IRn ,

o A Mn (IR) est un matrice carre, relle, de taille n (cest dire, f est la fonction
quadratique associe la matrice A). Alors pour un p {1, 2, n} fix, on peut
crire
n
n
n
n
X
X
X
X
2
Aij xi xj
Aip xi xp +
Apj xp xj +
Aij xi xj = App xp +
f (x) =
i,j=1

i=1,i6=p

j=1,j6=p

i,j=1,i6=p,j6=p

ce qui nous donne

n
n
n
n
X
X
X
X
f
Aip xi =
Apj xj +
Aip xi = (Ax)p +(AT x)p .
Apj xj +
= 2App xp +
xp
j=1
i=1
i=1,i6=p
j=1,j6=p

Nous avons donc obtenu :

f (x) = (A + AT )x,

x IRn .

On peut aussi crire

n

X
f
(x) =
(A + AT )ik xk ,
xi
k=1

i = 1, , n.

On a alors immdiatement :
2f
(x) = (A + AT )ij ,
xi xj

i, j = 1, , n.

cest dire
2 f (x) = A + AT ,

x IRn

(donc la hessienne de f est constante).

Remarque : En particulier, si A est symmtrique (cest dire A = AT ) alors
< Ax , x > = 2Ax,

x IRn .

2 < Ax , x > = 2A,

x IRn .

2.1.3

Rappel formules de Taylor

Proposition 2.3. (sans preuve)

Soit IRn ouvert, f : 7 IR, a et h IRn tels que [a, a + h] . Alors :
1. Si f C 1 () alors R
1
i) f (a + h) = f (a) + 0 < f (a + th), h > dt
(formule de Taylor lordre 1 avec reste intgral).
ii) f (a + h) = f (a)+ < f (a + h), h > avec 0 < < 1
(formule de Taylor - Maclaurin lordre 1)
iii) f (a + h) = f (a)+ < f (a), h > +o(khk)
(formule de Taylor - Young lordre 1)
2. Si f C 2 () alors
R1
i) f (a + h) = f (a)+ < f (a), h > + 0 (1 t) < 2 f (a + th)h, h > dt
(formule de Taylor lordre 2 avec reste intgral).
ii) f (a + h) = f (a)+ < f (a), h > + 21 < 2 f (a + h)h, h > avec 0 < < 1
(formule de Taylor - Maclaurin lordre 2)
iii) f (a + h) = f (a)+ < f (a), h > + 21 < 2 f (a)h, h > +o(khk2 )
(formule de Taylor - Young lordre 2).
Remarque : Dans la proposition prcdente la notation o(khkk ) pour k IN signifie
une expression qui tend vers 0 plus vite que khkk (cest dire, si on la divise par khkk , le
rsultat tend vers 0 quand khk tend vers 0).

2.2
2.2.1

Convexit
Rappel fonctions convexes

Dfinition 2.4. Un ensemble U IRn est dit convexe si x, y U on a [x, y] U

(quelque soit deux points dans U , tout le segment qui les unit est dans U ).
Dfinition 2.5. Soit U IRn un ensemble convexe et f : U IR une fonction.
1. On dit que f est convexe sur U si
f (tx + (1 t)y) tf (x) + (1 t)f (y),

x, y U, t [0, 1]

2. On dit que f est strictement convexe sur U si

f (tx + (1 t)y) < tf (x) + (1 t)f (y),

x, y U avec x 6= y, t ]0, 1[.

3. On dit que f est concave (respectivement strictement concave) si f est convexe

(respectivement strictement convexe).

Remarque : Il est facile de voir que toute fonction strictement convexe est convexe,
mais que la rciproque nest pas vraie en gnral.
Par exemple une application affine f (x) = Ax + b est convexe (et aussi concave) mais elle
nest pas strictement convexe (ni strictement concave).
On montre facilement le rsultat utile suivant :
Proposition 2.6. Soit U IRn un ensemble convexe, p IN , f1 , f2 , , fp : U IR des
fonctions convexes et 1 , 2 , , n des constantes strictement positives.
Posons f = 1 f1 + 2 f2 + p fp . Alors on a :
a) La fonction f est convexe (donc toute combinaison linaire avec des coefficients strictement positifs de fonctions convexes est convexe).
a) Si au moins une des fonctions f1 , , fp est strictement convexe alors f est strictement
convexe.
Dmonstration. Laisse en exercice !
Il est en gnral difficile de vrifier la convexit dune fonction en utilisant uniquement
la dfinition (essayez avec f (x) = x2 ou avec f (x) = x4 !) La proposition suivant donne
des critres de convexit plus faciles utiliser pour montrer la convexit ou la convexit
stricte dune fonction.
Proposition 2.7. Soit IRn ouvert, U avec U convexe et f : 7 IR une fonction.
Alors on a :
Partie I (caractrisation de la convexit avec ).
Supposons que f est de classe C 1 . Alors
1. f est convexe sur U si et seulement si :
f (y) f (x) + < f (x), y x >,

x, y U

2. f est strictement convexe sur U si et seulement si :

f (y) > f (x) + < f (x), y x >,

x, y U avec x 6= y.

3. f est convexe sur U si et seulement si f est monotone sur U , cest dire

< f (y) f (x) , y x > 0 x, y U.
4. Si f est strictement monotone sur U (cest dire :
< f (y) f (x) , y x > > 0 x, y U
alors f est strictement convexe sur U .
Partie II (caractrisation de la convexit avec 2 ).
Supposons que f est de classe C 2 . Alors
10

avec x 6= y

1. f est convexe sur U si et seulement si :

< 2 f (x)(y x), y x > 0,

x, y U

2. Si
< 2 f (x)(y x), y x > > 0,

x, y U avec x 6= y

alors f est strictement convexe sur U .

Remarques :
1. Dans le cas particulier o = U = IRn alors les deux ingalits de la Partie II de
la proposition prcdente peuvent scrire :
< 2 f (x)h, h > 0,

x, h IRn

et respectivement
< 2 f (x)h, h > > 0,

x, h IRn , avec h 6= 0.

2. Dans le cas particulier n = 1 et un intervalle ouvert dans IR, on a 2 f (x) = f 00 (x),

donc < 2 f (x)(y x), y x >= f 00 (x)(y x)2 . Alors les deux ingalits de la Partie
II de la proposition prcdente peuvent scrire :
f 00 (x) 0,

x U

f 00 (x) > 0,

x U.

et respectivement
On rtrouve un rsultat bien connu !
Exemple : Soit f : IR IR donne par f (x) = x2 . Comme f (x) = f 0 (x) = 2x on a
x, y IR :
f (y)f (x) < f (x), yx >= y 2 x2 2x(yx) = y 2 +x2 2xy = (yx)2 > 0 si x 6= y
et ceci montre la stricte convexit de cette fonction, en utilisant la Partie I2) de la
proposition prcdente.
On peut aussi utiliser la Partie I4) :
< f (y) f (x), y x > = 2(y x)2 > 0 si y 6= x
donc f est strictement convexe.
Cest encore plus facile si on utilise la Partie II :
f 00 (x) = 2 > 0
donc f est strictement convexe.
11

2.2.2

Fonctions elliptiques, fonctions coercives

Dfinition 2.8. Soit f : IRn IR. On dit que f est une fonction elliptique si elle est de
classe C 1 et si > 0 telle que
x, y IRn .

< f (x) f (y) , x y > kx yk2 ,

Dfinition 2.9. Soit IRn un ensemble non born et f : IR. On dit que f est
coercive sur si on a
lim
f (x) = +.
x,kxk7+

Proposition 2.10. Soit f : IRn IR une fonction elliptique. Alors elle est strictement
convexe et coercive. Elle vrifie en plus lingalit :

f (y) f (x) + < f (x), y x > + ky xk2 ,

2

x, y IRn .

(2.2)

Dmonstration. Montrons dabord lingalit (2.2).

On utilise la formule de Taylor lordre 1 avec reste intgral. On a
Z 1
< f (x + t(y x)), y x > dt
f (y) = f (x) +
0

ce qui nous donne

Z

< f (x + t(y x)) f (x) , t(y x) >

f (y) f (x) < f (x), y x > =

0

1
dt.
t

En utilisant le fait que f est elliptique on dduit :

< f (x + t(y x)) f (x) , t(y x) > kt(y x)k2
ce qui nous donne (car t > 0) :
f (y) f (x) < f (x), y x > ky xk

t dt =
0

ky xk2
2

ce qui prove (2.2).

Montrons la stricte convexit de f : de la dfinition de lellipticit on dduit :
< f (x) f (y) , x y > > 0,

x, y IRn avec x 6= y.

ce qui nous donne la convexit stricte de f , comme consquence de la Partie I4 de la

Proposition 2.7 (autre mthode : utiliser (2.2) et la Partie I2 de la Proposition 2.7).
Montrons la coercivit de f .
En prennant x = 0 en (2.2) on obtient

f (y) f (0)+ < f (0), y > + kyk2 .

2
12

(2.3)

Nous utilisons lingalit de Cauchy-Schwarz

| < f (0), y > | kf (0)k kyk
qui nous donne
y IRn .

< f (0), y > kf (0)k kyk,

En utilisant cette dernire ingalit en (2.3) on dduit
f (y) f (0) kf (0)k kyk +

kyk2
2

ce qui nous donne

f (y) 7 + si kyk 7 +.
La preuve de la proposition est alors termine.
Proposition 2.11. (Caractrisation de lellipticit avec 2 )
Soit f une fonction de classe C 2 . Alors f est elliptique si et seulement si > 0 tel que
< 2 f (x)h, h > khk2 ,

x, h IRn .

(2.4)

Dmonstration. a) Supposons que f est elliptique et montrons (2.4). Soit h IRn fix et
notons g : IRn 7 IR la fonction donne par g(x) = < f (x), h >, x IRn . Nous avons
en utilisant aussi la Proposition 2.2 :
< 2 f (x)h, h > = < g(x), h > =

< f (x + th), h > < f (x), h >

g
(x) = lim
t70
h
t

En utilisant la bilinarit du produit scalaire et ensuite le fait que f est elliptique, on

obtient :
< f (x + th) f (x) , th >
kthk2

= khk2
t70
t2
t2

< 2 f (x)h, h > = lim

ce qui nous donne (2.4) avec = .

b) Supposons maintenant que (2.4) est satisfaite et montrons que f est elliptique. Soient
x, y IRn fixes arbitraires, et considrons la fonction g1 : IRn 7 IR donne par
g1 (z) = < f (z) , x y >, z IRn . Alors
< f (x) f (y) , x y > = g1 (x) g1 (y) = < g1 (y + (x y)) , x y >
avec ]0, 1[ (on a utilis lune des formules de Taylor).
Dautre part, nous avons
g1 (z) = 2 f (z)(x y)
et ceci nous permet de dduire, en utilisant aussi (2.4) :
< f (x) f (y) , x y > = < 2 f (y + (x y))(x y) , x y > kx yk2 .
On a donc obtenu lellipticit de f avec = .
13

On a aussi le rsultat suivant :

Proposition 2.12. Soit p IN , f1 , f2 , , fp : IRn IR des fonctions de classe C 1 et
convexes et 1 , 2 , , n des constantes strictement positives.
Si au moins une des fonctions f1 , , fp est elliptique alors f 1 f1 + 2 f2 + p fp est
elliptique.
Dmonstration. Soit i {1, 2, p} tel que fi soit elliptique. Alors il existe > 0 tel que
< fi (y) fi (x) , y x > kx yk2

x, y IRn .

Dautre part, comme tous les fk sont convexes on a

< fk (y) fk (x) , y x > 0 x, y IRn ,

k 6= i.

En multipliant la premire ingalit par i et les autres par k et en sommant en k, on

obtient immdiatement le rsultat.

2.2.3

Exemples des fonctions elliptiques

1. Si n = 1 :
Toute fonction f : IR IR de classe C 2 et satisfaisant :
> 0,

f 00 (x) ,

x IR

est une fonction elliptique (cest une consquence immdiate de la Proposition 2.11).
Exemples :
i) f (x) = ax2 + bx + c avec a > 0
ii) f (x) = x2 + sin (x) (car f 00 (x) = 2 sin (x) 1, x IR).
2. Le cas gnral (n IN )
Soit f : IRn IR donne par
f (x) =

1
< Ax , x > < b, x > + c,
2

x IRn

(2.5)

avec A Mn (IR) une matrice carre relle et symmtrique de taille n, avec b IRn
un vecteur et c IR un scalaire (on appelle encore, par abus de language, fonction
(ou forme) quadratique une fonction de ce type). On calcule facilement :
f (x) = Ax b
2 f (x) = A
(donc la hessienne de f est constante).
Comme A est symmtrique alors on sait que toutes les valeurs propres de A sont
relles et que
< Ah , h > min khk2 , h IRn
14

o min IR est la plus petite valeur propre de A.

Rmarquons que lingalit prcdente devient galit si h est un vecteur propre
associ la valeur propre min .
Rappellons aussi que A est une matrice dfinie positive si et seulement si min > 0.
(par dfinition une matrice carre rlle B Mn (IR) est dfinie positive si
< Bx, x > > 0, x IRn , x 6= 0).
En utilisant la Proposition 2.11 on dduit que f est une fonction elliptique si et
seulement si A est une matrice dfinie positive.
(Voir des exemples concrtes en TD).

2.3

Conditions ncssaires de minimum

Dfinition 2.13. Soit U IRn , u U et f : U IR.

1. On dit que u est un point de minumum absolu (ou global) de f sur U si
f (u) f (u ),

u U.

2. On dit que u est un point de minumum relatif (ou local) de f sur U si V voisinage
de u dans IRn , tel que
f (u) f (u ), u U V.
3. On dit que u est un point de maximum absolu (respectivement relatif) de f sur U
si u est un point de minumum absolu (respectivement relatif) de f sur U .
4. On dit que u est un point dextremum absolu (respectivement relatif) de f sur U
si u est : soit un point de minumum absolu (respectivement relatif) de f sur U , soit
un point de maximum absolu (respectivement relatif) de f sur U .
Dans toute la suite du cours on parlera uniquement de la minimisation dune fonction
f ; pour la maximisation, faire la minimisation de la fonction f .
Remarques :
- Un point de minimum absolu est clairement un point de minimum relatif.
- Si on dit simplement minimum on comprends minimum absolu.
On va commencer par le lemme suivant :
Lemme 2.14. Soit U IRn , a IRn et u un lment appartenant lintrieur de U

(u U ). Alors les deux assertions suivantes sont quivalentes :

1.
< a , u u > 0,

u U.

(2.6)

2.
a = 0.

15

(2.7)

Dmonstration. Limplication (2.7) (2.6) est vidente. Pour montrer limplication inverse, soit w IRn arbitraire, avec w 6= 0. Alors il existe 0 > 0 telle que
u + w U,

[0 , 0 ]

r
(il suffit de prendre 0 = 2kwk
o r > 0 est tel que B(u , r) U ). Alors en prennant
u + w la place de u dans (2.6) on dduit

< a , w > 0,

[0 , 0 ].

En prennant dabord = 0 et ensuite = 0 dans lingalit prcdente, on dduit

< a, w > = 0

et ceci quelque soit w IRn , w 6= 0.

(2.8)

Comme lgalit prcdente est videmment valable aussi pour w = 0 alors elle est valable
pour tout w IRn . Ceci donne immdiatement (2.7) (il suffit de prendre w = a dans
(2.8)).
On utilisera dans la suite la dfinition suivante :
Dfinition 2.15. Soit U IRn un ensemble et u U . On dit que w IRn est une
direction admissible pour u en U sil existe t0 > 0 tel que u + tw U t [0, t0 ].
Exemples :

1. Si u U alors tout vecteur w IRn est une direction admissible pour u en U .

2. Si U est convexe alors pour tout v U le vecteur v u est une direction admissible
pour u en U . (Preuve : prendre t0 = 1 dans la dfinition prcdente).
Lemme 2.16. Soit IRn un ouvert, U , f : IR une fonction de classe C 1 et
u U un point de minimum relatif de f sur U . Soit w IRn une direction admissible
pour u en U . Alors
< f (u ) , w > 0.
Dmonstration. Soit V un voisinage de u en IRn tel que
f (u) f (u ),

u U V.

u + tw V,

t [t1 , t1 ]

(2.9)

Soit t1 > 0 tel que

r
o r > 0 est tel que B(u , r) V ; pour w = 0
(pour w 6= 0 il suffit de prendre t1 = 2kwk
tout t1 convient).
Dautre part on a
u + tw U, t [0, t0 ]

16

o t0 est comme dans la Dfinition 2.15.

On dduit alors de (2.9)
f (u + tw) f (u ) 0,

t [0, min {t0 , t1 }].

En divisant par t et en passant la limite pour t 0, t > 0, on obtient :

f
(u ) 0
w
ce qui est exactement lingalit demande.
Nous pouvons alors noncer :
Thorme 2.17. Soit IRn un ouvert, U un ensemble convexe et f : IR une
fonction de classe C 1 . Soit u U un point de minimum relatif de f sur U . Alors
1.
< f (u ) , u u > 0,

u U

(2.10)

(cest linquation dEuler).

2. Si en plus u est dans lintrieur de U (u U ) alors la condition (2.10) est quivalente au

f (u ) = 0
(2.11)
(cest lquation dEuler).
Dmonstration. 1. Cest une consquence immdiate du Lemme 2.16 et du fait que u u
est une direction admissible pour u en U (car U est convexe).
2. Cette partie est une consquence immdiate du Lemme 2.14 avec a = f (u ).
Remarques :
1. Ces relations respectives ((2.10) et (2.11) ) donnent seulement des conditions ncssaires de minimum relatif, qui ne sont pas en gnral suffisantes.
2. Si U est un ensemble ouvert (par exemple si U est lespace entier, U = IRn ) alors u
est forcment dans lintrieur de U et donc lquation dEuler (2.11) peut tre utilise
comme condition ncessaire de minimum relatif.
Le rsultat suivant nous donne aussi des conditions suffisantes de minimum :
Thorme 2.18. Soit IRn ouvert, U un ensemble convexe, f : IR une
fonction de classe C 1 et convexe et u U . Alors les trois assertions suivantes sont
quivalentes :
1. u est un point de minimum absolu de f sur U
2. u est un point de minimum relatif de f sur U
3. < f (u ) , u u > 0,

u U.
17

Dmonstration. 1. 2. est vidente et 2. 3. est une consquence immdiate du Thorme 2.17.

Montrons 3. 1. Grce la convexit de f et la Partie I1) de la Proposition 2.7 nous
avons
f (u) f (u ) < f (u ) , u u > u U.
De 3. nous obtenons alors 1.

Remarque : Dans le cas o u U alors lassertion 3. du Thorme 2.18 peut tre

remplace (grce au Lemme 2.14) par lquation dEuler :
f (u ) = 0.

2.4

Existence et unicit dun point de minimum

Thorme 2.19. (Existence)

Soit U IRn un ensemble non-vide et ferm et f : U IR une fonction continue. On
suppose
Soit U est born
Soit U est non borne et f est une fonction coercive sur U .
Alors il existe au moins un point de minimum de f sur U (cest dire, u U tel que
f (u ) f (u), u U )
Dmonstration. On distingue deux cas :
Cas 1) Lensemble U est born.
Alors comme U est aussi ferm, U est compact. Comme f est continue, le Thorme de
Weierstrass nous assure que f est borne sur U et elle atteint ses bornes. Donc il existe au
moins un point de minimum absolu de f sur U .
Cas 2) Lensemble U est non born.
Soit a U et considrons lensemble
E = {x U, f (x) f (a)}

Remarque : a E.

Il est facile de montrer :

1. E est ferm
(car E = f 1 (] , f (a)]), donc E est limage inverse dun intervalle ferm par une
fonction continue)
2. E est born
(supposons le contraire : alors il existe une suite xk E avec kxk k + pour
k +. Comme f est coercive sur U , ceci entrainne f (xk ) 7 + ce qui est
absurde, car f (xk ) f (a), k IN. )
On dduit alors que E est un ensemble compact dans IRn . Du Thorme de Weierstrass,
u E tel que
f (u ) f (u), u E.
18

Mais dautre part, on a

f (u ) < f (u),

u U E

(car f (u ) f (a) < f (u), u U E ).

Ceci prouve que u est un point de minumum absolu de f sur U , ce qui finit la preuve.
Thorme 2.20. (Unicit)
Soit U IRn un ensemble convexe et f : U IR une fonction strictement convexe. Alors
il existe au plus un point de minimum de f sur U .
Dmonstration. On va raisonner par absurd. Soient u1 , u2 U avec u1 6= u2 deux points
de minimum de f sur U . Nous avons donc :
f (u1 ) = f (u2 ) f (u),

u U.

(2.12)

Comme f est strictement convexe, on a



1
1
1
1
u1 + u2 < f (u1 ) + f (u2 ) = f (u1 )
f
2
2
2
2
(car f (u1 ) = f (u2 )) et ceci contredit (2.12).
Corollaire 2.21. (Existence et unicit)
Soit U IRn un ensemble ferm et convexe et f : IRn IR une fonction elliptique. Alors
il existe un unique point de minimum de f sur U .
Dmonstration. Existence : Remarquons dabord que f est continue, car elle est C 1 . On
a alors deux situations :
1. Si U est born alors lexistence est immdiate du Thrme 2.19.
2. Si U est non born alors comme consquence de la Proposition 2.10 f est coercive
sur IRn donc sur U ; alors lexistence rsulte encore du Thrme 2.19.
Unicit : Toujours de la Proposition 2.10 on dduit que f est strictement convexe. Alors
lunicit est une consquence immdiate du Thrme 2.20.

19

Chapitre 3
Optimisation sans contraintes
On considre ici le cas particulier o lensemble de contraintes U est lespace entier IRn .
On va donc considrer le problme de minimisation :
minn J(u)

(3.1)

uIR

o J : IRn 7 IR est une fonction donne.

Cest un problme de minimisation sans contraintes.
Le problme (3.1) peut scrire
Trouver u IRn

J(u ) J(u),

tel que

u IRn .

(3.2)

On supposera que u existe (ventuellement quil est unique) et on se propose de trouver

une approximation numrique de u , en construisant une suite {u(k) }kIN IRn telle
que
u(k) 7 u pour k 7 +.
Remarque : Si J C 1 alors u satisfait ncessairement lquation dEuler
J(u ) = 0
(vu en Chapitre 2).
Rappel : Si en plus J est convexe alors lquation dEuler est aussi une condition suffisante
de minimum. Si en plus J est strictement convexe, alors u est unique.
Alors une mthode numrique qui peut tre envisage cest de rsoudre numriquement
lquation dEuler, qui est en fait un systme de n quations avec n inconnues, du type
Trouver u IRn

tel que F (u) = 0

o F : IRn IRn est une fonction donne (ici F = J).

On peut utiliser la mthode numrique de Newton-Raphson (vue dj en L3 en dimension
1 ?)
En particulier si J est donne par
J(x) =

1
< Ax , x > < b , x > + c
2
20

avec A matrice symmtrique, b vecteur et c scalaire (cest dire, J est quadratique) alors
nous avons J(u) = Aub, et lquation dEuler devient un systme algbrique linaire
Au = b.
On peut utiliser alors toute mthode numrique connue (vue en L3).
On se propose ici de donner dautres mthodes numrique qui sont spcifiques loptimisation. Ces mthodes consitent construire la suite approximante {u(k) } par reccurence,
cest dire : on se donne un point initial u(0) IRn et on construit u(k+1) comme une
fonction de u(k) . Lexpression gnrale de u(k+1) sera
u(k+1) = u(k) + k d(k)

(3.3)

avec d(k) IRn des vecteurs quon appelle directions de descente et k IR des scalaires
quon appelle facteurs de descente. Ces noms viennent du fait quon cherchera toujours
avoir (entre autres)
J(u(k+1) ) < J(u(k) ), k IN
(3.4)
(la suite {J(u(k) )} doit tre strictement dcroissante).
Lalgorithme associ est en gnral de la forme :
pas 1. Faire k = 0, choisir u(0) IRn (par exemple u(0) = 0) , choisir kmax IN assez
grand (par exemple kmax = 1000).
pas 2. Tant que ((test arrt est faux) et (k < kmax ) ) faire u(k+1) = u(k) + k d(k) et
k =k+1
pas 3. Si (test arrt est vrai) alors u(k) est une approximation du point de minimum
recherch. Sinon, la mthode na pas converg.
Comme test arrt on choisit le plus souvent : J(u(k) = 0 (en pratique le test sera :
kJ(u(k) k  o  est un nombre strictement positiv et petit, qui reprsente un niveau
de tolrance admis, fixer au dbut (par exemple  = 106 )).
Il y a un grand nombre de mthodes numriques de minimisation, suivant le choix qui
est fait pour d(k) et k .

3.1
3.1.1

Mthodes de relaxation
Description de la mthode

Cette mthode consiste faire le choix suivant pour les directions de descente :
d(0) = e1 ,

d(1) = e2 , d(n1) = en

ensuite on recommence
d(n) = e1 ,

d(n+1) = e2 , d(2n1) = en
21

et ainsi de suite ...

(rappellons que {e1 , e2 , en } sont les vecteurs de la base canonique de IRn ).
Donc en gnral on a :
d(k) = el
si et seulement si l est le rest de la division de k + 1 par n.
On prend ensuite les facteurs k IR tels que
J(u(k) + k d(k) ) = min J(u(k) + d(k) ),
IR

k IN

(3.5)

(en supposant que ces minimum existent).

Finalement on pose
u(k+1) = u(k) + k d(k) .
Cest la mthode (ou lalgorithme) de relaxation.
On peut crire cet algorithme de la manire quivalente suivante :
(k)
(k)
(k)
On suppose connu le vecteur u(k) = (u1 , u2 , un )T et on calcule
(k+1)
(k+1)
(k+1)
u(k+1) = (u1
, u2
, un )T en n pas successifs par les formules suivantes :
(k+1)

J(u1
(k+1)

J(u1

(k+1)

, u2

(k+1)

J(u1

(k)

(k)

(k)
, u2 , u(k)
n ) = min J(y, u2 , un )
yIR
(k)

(k+1)

, u3 u(k)
n ) = min J(u1
yIR
...

(k+1)

, u(k+1)
) = min J(u1
n
yIR

(k)

, y, u3 un(k) )
(k+1)

, un1 , y)

Ci-dessus on a utilis le fait que (par exemple)

(k)

(k)

(k)

(k)
min J(u1 + , u2 , u(k)
n ) = min J(y, u2 , un ),
yIR
IR
(k)

galit obtenue en faisant le changement de variable y = u1 + .

Le but dans la suite est de dmontrer que lalgorithme de relaxation est bien dfini, au
moins dans le cas dune fonction elliptique. Pour cela montrons dabord le rsultat suivant :
Proposition 3.1. Soit f : IRn IR et a, b IRn . Dfinissons la fonction g : IR 7
IR, g(t) = f (a + tb), t IR. Alors on a :
1. Si f est convexe alors g est convexe.
2. Si f est strictement convexe et b 6= 0 alors g est strictement convexe.
3. Si f est elliptique et b 6= 0 alors g est elliptique.

22

Dmonstration.

1. Soient t1 , t1 IR, [0, 1]. Alors

g(t1 + (1 )t2 ) = f (a + [t1 + (1 )t2 ]b) = f ((a + t1 b) + (1 )(a + t2 b))

(on a utilise lgalit : a = a + (1 )a).
Avec la convexit de f on obtient
g(t1 + (1 )t2 ) f (a + t1 b) + (1 )f (a + t2 b) = g(t1 ) + (1 )g(t2 )
ce qui donne le rsultat.
2. Cest pareil quen 1. avec t1 6= t2 et ]0, 1[. Comme b 6= 0 alors a + t1 b 6= a + t2 b et
donc on peut remplacer dans la dmonstration prcdente "" par "<".
3. Soient t1 , t2 IR. On a
[g 0 (t1 ) g 0 (t2 )] (t1 t2 ) = [< f (a + t1 b) , b > < f (a + t1 b) , b >] (t1 t2 ) =
= < f (a + t1 b) < f (a + t2 b) , (t1 t2 )b > kbk2 (t1 t2 )2
ce qui montre le rsultat, car kbk2 > 0.
Corollaire 3.2. Soit f : IRn IR et a1 , a2 , ai1 , ai+1 , an IR, i {1, 2, n}
donnes. Soit g : IR 7 IR dfinie par
g(t) = f (a1 , a2 , ai1 , t, ai+1 , an )
(fonction partielle par rapport la i-me variable).
Alors on a :
1. Si f est convexe alors g est convexe
2. Si f est strictement convexe alors g est strictement convexe
3. Si f est elliptique alors g est elliptique.
Dmonstration. Il suffit dappliquer la Proposition 3.1 avec a = (a1 , a2 , ai1 , 0, ai+1 , an ), b =
ei 6= 0.
Le rsultat thorique principal de cette section est la suivant :
Thorme 3.3. Soit J : IRn IR une fonction eliptique. Alors la mthode de relaxation
est bien dfinie et elle converge (cest dire, pour tout u(0) IRn la suite u(k ) construit
par cet algorithme converge vers lunique point de minimum de J).
Dmonstration. Du Corollaire 3.2 on dduit que la fonction
(k+1)

y IR J(u1

(k+1)

, ui1 , y, uki+1 , ukn ) IR

est une fonction elliptique (car f est elliptique). On dduit alors quil existe un unique
point de minimum de cette fonction, ce qui montre que lalgorithme de relaxation est bien
dfini. La convergence de u(k) est admise.
Remarque : Cette mthode de relaxation est interessante si ces minimisations sur IR
peuvent ce faire de manire exacte.
23

3.1.2

Cas particulier des fonctions quadratiques

Dans ce paragraph nous supposons que J : IRn IR est donne par

J(x) =

1
< Ax , x > < b , x > + c
2

(3.6)

avec A Mn (IR) matrice SDP (cest dire matrice symmtrique et dfinie positive),
b IRn , c IR (donc cest une forme quadratique associe une matrice SDP ).
On a besoin de calculer y IR tel que
min g(y) = g(y )
yIR
o la fonction g : IR 7 IR est dfinie par
(k+1)

g(y) = J(u1
(k+1)

(k+1)

(k+1)

(k)

, ui1 , y, ui+1 , u(k)

n )

(k)

(k)

avec u1
, ui1 , ui+1 , un IR donnes.
Pour faciliter lcriture, faisons les notations suivantes :
(k+1)

v1 = u1

(k+1)

, v2 = u2

(k)

(k+1)

, vi1 = ui1 , vi+1 = ui+1 , vn = un(k)

Comme J est elliptique alors g est aussi elliptique, donc y existe et est unique ; y est
lunique solution de lquation dEuler
g 0 (y ) = 0.
Mais g 0 (y) nest autre que

J
(v , v , vi1 , y, vi+1 , vn )
xi 1 2

g (y) =

n
X

ce qui nous donne

Aij vj + Aii y bi .

j=1,j6=i

Donc on doit rsoudre en y IR :

n
X

Aij vj + Aii y bi = 0

j=1,j6=i

ce qui nous donne

1
y =
Aii

n
X

bi

!
Aij vj

j=1,j6=i

Remarque : On a Aii > 0 car Aii =< Aei , ei > > 0 (A est SDP).
On a donc montr :
24

Proposition 3.4. Dans le cas o J est donne par (3.6) (J quadratique avec A une matrice
SDP) la mthode de relaxation scrit :
!
n
X
1
(k+1)
(k)
u1
=
b1
A1j uj
A11
j>1
!
n
X
1
(k+1)
(k+1)
(k)
u2
=
b2 A21 u1

A1j uj
A22
j>2
(k+1)

ui

1
Aii

!
n
n
X
X
(k+1)
(k)
bi
Aij uj

Aij uj
j<i

j>i

u(k+1)
n

1
=
Ann

bn

n
X

!
(k+1)
Anj uj

j<n

En plus la mthode converge (cest une consquence du Thorme 3.3).

Remarque : Lalgorithme ci-dessus nest autre que lalgorithme de Gauss-Seidel (vu
en L3) pour la rsolution numrique du systme linaire
Ax = b.
Ceci sexplique par le fait que le point de minimum u de J satisfait lquation dEuler
J(u ) = 0 qui devient dans le cas J quadratique : Au = b.

3.2

Mthodes de gradient

Ide : prendre comme direction de descente :

d(k) = J(u(k) )
Justification : J(u(k) ) est orthogonal la ligne du niveau de J dans le point u(k) et la
fonction J diminue dans la direction J(u(k) ). Cette afirmation se justifie par le calcul
suivant, o on utilise un dveloppement de Taylor :


J u(k) J(u(k) ) = J(u(k) )+ < J(u(k) ) , J(u(k) ) > + o()
(on suppose que J est de classe C 1 ). Nous avons alors :


J u(k) J(u(k) ) J(u(k) ) = kJ(u(k) )k2 + o().
Le membre de droite de lgalit prcdente est < 0 si > 0 avec assez petit et
J(u(k) ) 6= 0.
Les mthodes de gradient sont dfinis alors par les relations :
u(k+1) = u(k) k J(u(k) )
o les facteurs de descente k IR sont choisir.
Il y a plusieurs mthodes de gradient suivant le choix que nous faisons pour k .
25

(3.7)

3.2.1

Mthodes de gradient pas optimal

La mtode est la suivante : u(k+1) est donne par (3.7) o k IR est tel que




J u(k) k J(u(k) ) = min J u(k) J(u(k) )
IR

(3.8)

(en supposant quun tel minimum existe).

Remarque : Nous faisons litration (3.7) dans le cas o J(u(k) ) 6= 0, donc le problme
de minimisation (3.8) a un sens.
On a le rsultat suivant :
Thorme 3.5. Soit J : IRn 7 IR une fonction elliptique. Alors la mthode de gradient
pas optimal donne par (3.7) et (3.8) est bien dfinie et converge.
Dmonstration. Comme consquence de la Proposition 3.1 la fonction


IR 7 J u(k) J(u(k) IR
est une fonction elliptique, donc il existe un unique point de minimum de cette fonction.
Ceci montre que la mthode de gradient pas optimal est bien dfinie.
La convergence est admise !
Cas particulier : fonctions quadratiques.
On suppose ici J comme dans le paragraph 3.1.2 (donc J quadratique associe une
matrice SDP).
Nous devons calculer k IR qui minimise la fonction g : IR 7 IR donne par


g() = J u(k) J(u(k) .
Alors k satisfait ncessairement
g 0 (k ) = 0.
Un calcul simple nous donne


g 0 () = < J u(k) J(u(k) , J(u(k) ) >
cest dire, comme J(u(k) ) = Au(k) b




g 0 () = < A u(k) J(u(k) ) b , Au(k) b >= kAu(k) bk2 + < A Au(k) b , Au(k) b >

On obtient alors

kAu(k) bk2
(3.9)
< A (Au(k) b) , Au(k) b >


Rmarquons quon a < A Au(k) b , Au(k) b > > 0 (car A est SDP et Au(k) b =
J(u(k) ) 6= 0).
k =

26

Donc la mthode de gradient pas optimal dans le cas J quadratique est :

u(k+1) = u(k) k Au(k) b
avec k donnes par (3.9) (valable uniquement pour Au(k) b 6= 0).
Remarque : Comme g 0 (k ) = 0, on dduit immdiatement
< J(u(k+1) ) , J(u(k) ) > = 0.

3.2.2

(3.10)

Autres mthodes du type gradient

Si J nest pas quadratique, il peut tre difficile de trouver k solution de (3.8). Quand
on ne peut pas calculer k de manire exacte, il faut utiliser chaque pas k une mthode
numrique pour approcher k , ce qui alourdit les calculs. On peut se satisfaire uniquement
dune estimation assez large pour k . Le rsultat suivant nous donne un intervalle tel que
si tous les k se trouvent dans cet intervalle, alors la mthode du gradient converge :
Thorme 3.6. Soit J : IRn IR une fonction elliptique (cest dire, J C 1 et > 0
telle que
< J(x) J(y) , x y > kx yk2 , x, y IRn )
et telle que J soit lipschitzienne (cest dire : M > 0 tel que
kJ(x) J(y)k M kx yk,

x, y IRn

).

Supposons que la suite {k }kIN IR satisfait la proprit suivante : il existe a1 , a2 avec

2
tels que
0 < a1 a2 < M
2
a1 k a2 , k IN.
(3.11)
Alors la mthode gnrale de gradient (3.7) converge et la convergence est au moins gomtrique, cest dire : [0, 1[ tel que
ku(k) u k k ku(0) u k,

k IN

o u est lunique point de minimum de J sur IRn .

Dmonstration. Nous savons que u est lunique solution de lquation
J(u ) = 0.
Notre but est de montrer que u(k) u 0 pour k +. Nous avons :


u(k+1) u = u(k) k J(u(k) ) u = u(k) u k J(u(k) ) J(u ) .
Utilisons la formule : kx yk2 = kxk2 + kyk2 2 < x, y > pour tous x, y IRn . Nous avons
ku(k+1) u k2 = ku(k) u k2 +2k kJ(u(k) )J(u )k2 2k < u(k) u , J(u(k) )J(u ) > .
27

En utilisant lellipticit de J et le fait que J est lipschitzienne, nous obtenons

ku(k+1) u k2 ku(k) u k2 + M 2 2k ku(k) u k2 2k ku(k) u k2
cest dire
ku(k+1) u k2 (1 2k + M 2 2k )ku(k) u k2 .

(3.12)

Considrons maintenant la fonction : IR IR donne par

() = 1 2 + M 2 2 .
Le but est de montrer quil existe [0, 1[ tel que
() 2

[a1 , a2 ].

(3.13)

2
Comme (0) = ( M
2 ) = 1 on voit facilement que

() < 1 ]0,

2
[.
M2

(3.14)

Notons alors
1 = max ().
[a1 ,a2 ]

Le Thorme de Weierstrass nous dit que le maximum de est atteint sur [a1 , a2 ] et on
dduit de (3.14) que
1 < 1.
Notons maintenant
2 = max {1 , 0} 1

et il est claire que 2 [0, 1[. On peut alors poser = 2 et on a

0 < 1.
Comme 1 2 on dduit de la dfinition de 1 que (3.13) est satisfaite.
On obtient alors
(k ) 2
ce qui avec (3.12) nous donne
ku(k+1) u k ku(k) u k,

k IN.

Par reccurence, nous dduisons k IN :

ku(k) u k ku(k1) u k 2 ku(k2) u k k ku(0) u k
ce qui nous donne le rsultat attendu.

28

Dfinition :
Une mthode de gradient du type (3.7) est dite pas constant (ou fixe) si k est constant
(indpndant du k). Dans le cas contraire, elle est dite pas variable.
Remarque :
On dduit du Thorme 3.6 que si est tel que
0<<

2
M2

alors la mthode de gradient pas fixe

u(k+1) = u(k) J(u(k) )
est convergente (choisir a1 = a2 = dans le Thorme 3.6).
Cest la mthode de gradient la plus simple utiliser.
Inconvenient : En gnral il est difficile de connatre et M (en supposant quils existent).
Alors dans la pratique on prends un assez petit pour tre sur davoir la convergence. Mais
dans ce cas la convergence peut tre trs lente !
Un exemple o on peut calculer et M : Si J est quadratique avec une matrice A
qui est SDP. Alors on peut prendre = min > 0 (la plus petite valeur propre de A) et
M = kAk2 = (A) = max > 0 (la plus grande valeur propre de A).
Une alternative : une algorithme bas sur la recherche linaire.
Cette mthode pour trouver k est une mthode intermdiaire entre lalgorithme de gradient pas optimal et un algorithme de gradient pas constant. Le principe en este le
suivant :
On note g : IR IR la fonction donne par
g() = J(u(k) J(u(k) )).
On cherche r > 0 et s IN, s 2, tels que
g(0) > g(r) > g(2r) > > g(sr)
et
g(sr) g((s + 1)r)
(pour tout r > 0 assez petit il existe au moins un nombre naturel s avec cette proprit, si
on fait une hypothse de coercivit sur J).
On pose alors
k = sr.
Ide intuitive : bien exploiter les possiblits de descendre dans la direction J(u(k) ).
Lalgorithme associ est le suivant :
faire r = 1
tant que (g(2r) < g(r) < g(0) est faux) faire r = r/2
= 2r
tant que (g( + r) < g()) faire = + r
k = .
29

3.3

La mthode des gradients conjugus

Rappels notations :
P
1. Si v1 , v2 , vl IRn on note par L(v1 , v2 , vl ) = { li=1 i vi , 1 , l IR}
lespace vectoriel engendr par les vecteurs v1 , v2 , vl ; cest un sous-espace vectoriel
de IRn .
2. Si a IRn et M IRn alors a + M dsigne lensemble {a + x, x M }.

3.3.1

Le cas quadratique

Dans ce paragraphe on considre J : IRn 7 IR une fonction quadratique

J(u) =

1
< Au , u > < b , u > + c,
2

u IRn

avec A Mn (IR), b IRn , c IR. On suppose que la matrice A est SDP.

Ide de la mthode : Rappellons que la mthode de gradient pas optimal consiste
faire :


u(k+1) = u(k) k J(u(k) ) = min J u(k) J(u(k) )
IR
Ceci est quivalent avec :




u(k+1) u(k) + L J(u(k) ) est llment qui minimise J sur u(k) + L J(u(k) )
Dans la suite on va procder de la manire suivante : On va noter pour tout k IN :


Gk = L J(u(0) ), J(u(1) ), J(u(k) ) Rn
La mthode des gradients conjugus consiste chercher u(k+1) u(k) + Gk tel que
J(u(k+1) ) =

min

J(v)

(3.15)

vu(k) +Gk

(en supposant quun tel minimum existe).

On minimise donc sur un espace plus grand que dans la mthode de gradient pas
optimal. On sattend alors un meilleur minimum. Il reste montrer que cette mthode
est facile implmenter et quelle donne le rsultat attendu.
Comme J est elliptique et que u(k) + Gk est un ensemble ferm et convexe (car cest un
espace affine), alors il existe une solution unique du problme de minimisation (3.15).
En plus, le Thorme 2.17 nous donne
< J(u(k+1) ) , v u(k+1) > 0,

v u(k) + Gk .

Soit maintenant w Gk arbitraire. Remarquons quon a :



u(k+1) + w = u(k) + u(k+1) u(k) + w u(k) + Gk car u(k+1) u(k) Gk .
30

(3.16)

On peut alors prendre v = u(k+1) + w en (3.16) et aussi v = u(k+1) w. On obtient

< J(u(k+1) ) , w > = 0,

w Gk

(cest dire : J(u(k+1) ) est orthogonal sur tous les vecteurs de Gk ). Ceci nous donne
< J(u(k+1) ) , J(u(l) ) > = 0,

l = 0, 1, k.

(3.17)

(rappellons que dans lalgorithme de gradient pas optimal on avait seulement

< J(u(k+1) ) , J(u(k) ) > = 0.)
Consquences :
1. Si les vecteurs J(u(0) ), J(u(1) ), J(u(k) ) sont tous 6= 0 alors ils sont indpendants (cest une consquence immdiate du rsultat bien connu : si des vecteurs nonnuls sont orthogonaux par rapport un produit scalaire, alors ils sont indpendants
(facile montrer)).
2. Lalgorithme sarrte en au plus n itrations, car il existe k {0, 1, n} tel que
J(u(k) ) = 0
(sinon, on aurait n + 1 vecteurs non-nuls indpendants en IRn , ce qui est impossible).
Alors u(k) est la solution rechrche.
La question qui se pose maintenant est : comment calculer u(k+1) partir de u(k) ?
Supposons quon a
J(u(i) ) 6= 0, i = 0, 1, k
(sinon, lalgorithme sarrtait avant davoir calculer u(k+1) ).
Nous avons lexpression suivante :
u(l+1) = u(l) + l

l = 0, 1, k.

(3.18)

avec l Gl que nous crivons sous la forme

l =

l
X

il J(u(i) )

(3.19)

i=0

avec il IR des coefficients trouver. Rappellons que

J(x) = Ax b x IRn .
On utilisera souvent la formule suivante :




J u(l+1) = J u(l) + Al .
(car J(u(l+1) ) = Au(l+1) b = A(u(l) + l ) b = Au(l) b + Al ).
31

(3.20)

Proposition 3.7. On a
1.
l 6= 0,

l = 0, 1, k.

2.
< Al , m > = 0

si 0 m < l k.

Dmonstration. En faisant le produit scalaire de lgalit (3.20) par J u(l)

on obtient

kJ(u(l) )k2 + < Al , J(u(l) ) > = 0.

Comme kJ(u(l) )k2 6= 0 on dduit < Al , J(u(l) ) > 6= 0 donc l 6= 0, ce qui finit la
partie 1.
Pour montrer la partie 2. nous faisons le produit scalaire de (3.20) avec J(u(i) ), i < l.
On obtient
< Al , J(u(i) ) > = 0,

i = 0, 1, l 1,

donc i = 0, 1, m.

En multipliant par im et en sommant pour i de 0 m on obtient lgalit de la partie

2.
Ceci nous amme donner la dfinition suivante :
Dfinition 3.8. On dit que deux vecteurs x, y IRn sont conjugus par rapport une
matrice B Mn (IR) si
< Bx , y > = 0.
Remarque : Si B est une matrice SDP alors lapplication
(x, y) IRn IRn < Bx , y > IR
est un produit scalaire en Rn (rsultat admis !) quon appelle produit scalaire associ la
matrice B. ( noter que le produit scalaire habituel est un fait un produit scalaire associ
la matrice identit In ). Alors la dfinition prcdente nous dit que, dans le cas o B est
SDP, deux vecteur sont conjugus par rapport la matrice B sils sont orthogonaux par
rapport au produit scalaire associ B.
Comme les vecteurs 0 , 1 , k sont non-nuls et orthogonaux par rapport au produit
scalaire associ la matrice A (Proposition 3.7) on dduit immdiatement :
Proposition 3.9. Les vecteurs 0 , 1 , k sont indpendants.
Il est facile de voir quon a


L(0 , 1 , l ) = L J(u(0) ), J(u(1) ), J(u(l) ) ,

l = 0, 1, k

(car linclusion est vidente de (3.19) et en plus les deux espaces ont la mme dimension : l + 1).
On dduit alors :
ll 6= 0, l = 0, 1, k
(3.21)
32



(car sinon, on aurait l L J(u(0) ), J(u(1) ), J(u(l1) ) = L(0 , 1 , l1 ), ce
qui contredirait lindpendance des 0 , , l ).
On peut alors crire
k = k d(k)
avec
d(k) = J(u(k) ) +

k1
X

ki J(u(i) )

(3.22)

i=0

o on a pos

k =

kk

ki

ik /kk

(3.23)

(remarquons que dans (3.22) la somme nexiste pas si k = 0).

Nous avons donc :
u(k+1) = u(k) + k d(k)
avec d(k) donn par (3.22) et (3.23).
Il nous reste calculer les k et d(k) .
Comme < Ak , l > = 0 pour l < k, on dduit que < Ad(k) , l > = 0 ce qui nous donne,
en utilisant aussi (3.20) :
0 = < d(k) , Al > = < d(k) , J(u(l+1) ) J(u(l) ) >

pour 0 l k 1.

A laide de (3.22) cela nous donne

(k)

< J(u ) +

k1
X

kj J(u(j) ) , J(u(l+1) ) J(u(l) ) > = 0 pour 0 l k 1. (3.24)

j=0

En prennant l = k 1 dans cette galit on trouve

kJ(u(k) )k2 kk1 kJ(u(k1) )k2 = 0
ce qui nous donne
kk1 =

kJ(u(k) )k2
.
kJ(u(k1) )k2

En prennant l k 2 en (3.24), on trouve la relation de reccurence

kl+1 kJ(u(l+1) )k2 kl kJ(u(l) )k2 = 0
ce qui donne
kl = kl+1

kJ(u(l+1) )k2
.
kJ(u(l) )k2

33

(3.25)

On en dduit facilement, en utilisant aussi (3.25)

ki =

kJ(u(k) )k2
,
kJ(u(i) )k2

i = 0, 1, k 1.

On obtient alors, laide de (3.22) :

k1
X
kJ(u(k) )k2
d = J(u ) +
J(u(i) ) =
(i) )k2
kJ(u
i=0
"
#
k2
(k1) 2
(k) 2
X
kJ(u
)k
kJ(u
)k
J(u(k1) ) +
J(u(k) ) +
J(u(i) )
(i) )k2
kJ(u(k1) )k2
kJ(u
i=0
(k)

(k)

Ceci nous donne la suite {d(k) } par reccurence sous la forme

(
d(0) = J(u(0) )
d(k) = J(u(k) ) +

kJ(u(k) )k2
kJ(u(k1) )k2

d(k1) .

(3.26)

Il reste dtrminer les k .

Rappellons quon a la relation de reccurence :
u(k+1) = u(k) + k d(k)
et que nous avons


J u(k) + k d(k) J(u(k) + y),

y Gk

ce qui nous donne

J u(k) + k d(k) J(u(k) + d(k) ),

IR

car d(k) Gk . On en dduit que k est un point de minimum sur IR de lapplication

IR J(u(k) + d(k) ) IR.
donc k est un point o la drive de cette application sannule, ce qui donne
< J(u(k) + k d(k) ) , d(k) > = 0
cest dire
< Au(k) + k Ad(k) b , d(k) > = 0.
On obtient alors
k =

< J(u(k) ) , d(k) >

< Ad(k) , d(k) >

(3.27)

Remarque : La Proposition 3.7 nous dit que k 6= 0, ce qui nous donne d(k) 6= 0. Ceci
implique < Ad(k) , d(k) > > 0, car la matrice A est SDP.
Lalgorithme des gradients conjugus (AGC) pour une fonction quadratique avec une
matrice A qui est SDP est alors le suivant :
34

1. pas 1. On pose k = 0, on choisit u(0) IRn et on pose d(0) = J(u(0) ) = Au(0) b.

2. pas 2. Si J(u(k) ) = 0 STOP La solution u est u(k) . Sinon, va au pas 3.
3. pas 3. On pose
< J(u(k) ) , d(k) >
k =
< Ad(k) , d(k) >
u(k+1) = u(k) + k d(k)
k =

kJ(u(k+1) )k2
kJ(u(k) )k2

d(k+1) = J(u(k+1) ) + k d(k)

faire k = k + 1
retour au pas 2.

3.3.2

Cas dune fonction J quelconque

On suppose ici J : IRn 7 IR une fonction elliptique. Dans ce cas lalgorithme des gradients conjugues est le suivant (cest une petite modification de lalgorithme prcdent) :
1. pas 1. On pose k = 0, on choisit u(0) IRn et on pose d(0) = J(u(0) ).
2. pas 2. Si J(u(k) ) = 0 STOP La solution u est u(k) . Sinon, va au pas 3.
3. pas 3. On pose
u(k+1) = u(k) + k d(k)
o k IR est lunique lment qui minimise la fonction
IR J(u(k) + d(k) ) IR
et ensuite
k =

kJ(u(k+1) )k2
kJ(u(k) )k2

d(k+1) = J(u(k+1) ) + k d(k)

faire k = k + 1
retour au pas 2.
Ceci est la variante dite de Fletcher-Reeves.
Il y a aussi la variante dite de Polack-Ribiere avec comme seul changement
k =

< J(u(k+1) ) J(u(k) ) , J(u(k+1) ) >

kJ(u(k) )k2

Cette dernire variante donne des meilleurs rsultats en pratique.

Remarque : Ces deux versions coincident dans le cas dune fonction J quadratique, car
dans ce cas on a
< J(u(k) ) , J(u(k+1) ) > = 0.
35

Chapitre 4
Optimisation avec contraintes
On rappelle quon se donne U IRn o U est un ensemble ferm des contraintes, avec
U 6= et U 6= IRn . On se donne aussi la fonction
J : IRn 7 IR.
On cherche rsoudre le problme de minimisation
min J(u)

(4.1)

uU

(cest dire, on cherche u U tel que

J(u ) J(u),

u U

(4.2)

On va considrer deux cas pour U :

1. U est un pav, cest dire, il est de la forme U = [a1 , b1 ] [a2 , b2 ] [an , bn ]
(avec la convention quon peut avoir ] la place de [ai ou +[ la place
de bi ], donc le pav peut tre de volume infinit).
2. U est de la forme
U = {x IRn , i (x) 0, i = 1, 2, m}

(4.3)

avec m IN et 1 , 2 , m des fonctions de IRn dans IR donnes (on dit dans ce

cas que U est donn par des contraintes ingalits larges).
Remarques :
1. Le premier cas est un cas particulier du deuxime
2. Dans le cas des contraintes ingalits larges, le problme de minimisation associ
est aussi appel problme de programation nonlinaire si au moins une des
fonctions 1 , 2 , m ou J est non affine. Si toutes ces fonctions sont affines, alors
on a un problme de programation linaire (vu en L3).

36

3. Dans la pratique on peut rencontrer des problmes de minimisation avec contraintes

galits, cest dire, des contraintes de la forme
U = {x IRn , i (x) = 0, i = 1, 2, m}
ou des problmes avec des contraintes mlanges (galits et ingalits larges). Dans
ce cas on peut toujours se ramener des problmes avec contraintes ingalits larges,
ceci par deux mthodes :
soit en liminant des contraintes laides des galits
soit en crivant une galit i (x) = 0 comme une double ingalit : i (x) 0 et
i (x) 0 .
Exemple : Considrons lensemble
U = {x = (x1 , x2 , x3 ),

x1 + x2 x3 , 3x1 2x2 = x3 }.

Alors on peut exprimer laide de la dernire galit de U une variable en fonction des
2 autres (par exemple : x3 = 3x1 2x2 ). On remplace ensuite x3 dans lingalit de U :
x1 + x2 3x1 2x2 ce qui donne 2x1 + 3x2 0. On peut alors introduire lensemble 2
variable seulement :
U0 = {x = (x1 , x2 ), 2x1 + 3x2 0}.
Alors minimiser une fonction J(x1 , x2 , x3 ) sur U est quivalent au fait de minimiser sur U0
une fonction J0 de 2 variables dfinie par
J0 (x1 , x2 ) = J(x1 , x2 , 3x1 2x2 ).
Lautre mthode (plus complique) est dcrire U sous la forme quivalentes
U = {x = (x1 , x2 , x3 ),

x1 + x2 x3 , 3x1 2x2 x3 , x3 3x1 2x2 }.

On peut montrer facilement le rsultat suivant :

Proposition 4.1. Soit U donn par (4.3). Si toutes les fonctions 1 , 2 , , m sont
convexes alors U est un ensemble convexe.
Dmonstration. Laisse en exercice.

4.1

Rappel sur les multiplicateurs de Lagrange

Soient J, 1 , 2 , m : IRn 7 IR des fonctions de classe C 1 , avec m IN . On note

= {x IRn , i (x) = 0, i = 1, 2, m}.
O
est une varit de IRn .
On dit que O
est tel que la famille des vecteurs {i (x)}i=1,m forme
Dfinition 4.2.
1. Si x O
n

un systme libre en IR alors on dit que x est un point rgulier de O.

37

 est dite rgulire si tous les points de O

sont rguliers.
2. La varit O
en x est : rang(B) = m o
Remarque : Une condition quivalente de rgularit de O
B est la matrice Jacobienne donne par
Bij =

i
(x), i = 1, m, j = 1, n.
xj

(on a alors ncssairement : m n).

On a le rsultat suivant :
Thorme 4.3. (Admis sans preuve !)
tel que x soit un extremum local de J sur O
(minimum
Soit x un point rgulier de O

local ou maximum local). Alors il existe 1 , 2 , m IR (appells multiplicateurs de

Lagrange) tels que
m
X

J(x ) +
i i (x ) = 0
(4.4)
i=1

Remarque : Le systme (4.4) donne des conditions ncessaires doptimalit (appells

aussi conditions ncessaires doptimalit de premier ordre, car elles font intervenir
des drives une fois uniquement). Ces conditions ne sont pas en gnral suffisantes. Le

systme (4.4) nous donne n quations avec n + m inconnues. Mais le fait que x O

nous donne encore m quations : i (x ) = 0, i = 1, m, ce qui nous fait au total n + m

quations avec n + m inconnues.

4.2

Optimisation sous contraintes dingalits

On se donne de nouveau les fonctions J, 1 , 2 , m : IRn 7 IR de classe C 1 , avec

m IN .
Notons maintenant :
O = {x IRn , i (x) 0, i = 1, 2, m}.
Notations :
On introduit la fonction valeurs vectorielles : IRn 7 IRm donne par
(x) = (1 (x), 2 (x), m (x))T .
Pour un vecteur b = (b1 , bm )T IRm la notation b 0 signifie bi 0, i = 1, m. On
peut donc crire
O = {x IRn , (x) 0}.
On va sintresser au problme de minimisation :
min J(x).
xO

(4.5)

Hypothse : On va supposer que les fonctions i sont de telle manire que O 6= et aussi
que O ne se rduit pas un seul point ou un nombre finit de points (dans quel cas le
problme de minimisation (4.5) est trs banal !)
38

4.2.1

Conditions doptimalit de premier ordre : multiplicateurs

de Karush-Kuhn-Tucker

On donnera des conditions doptimalits similaires au systme (4.4), mais pour des
contraintes ingalits.
Dfinition 4.4.

1. On dit que la contrainte i (u) 0 est active en v O si on a

i (v) = 0.

On introduit alors lensemble

I(v) = {i {1, 2, m}, i (v) = 0}
et la varit (dfinie uniquement si I(v) 6= )

O(v)
= {u IRn ,

i (u) = 0, i I(v)}

(remarquons que v O(v)).

2. On dira que v O est un point rgulier de O si :
- soit I(v) =

- soit v est un point rgulier de la varit O(v).

Le rsultat principal de ce paragraph est le suivant :
Thorme 4.5. Soit x un point rgulier de O. Si x est un point de minimum local de
J sur O alors il existe p1 , p2 , pm [0, +[ (appells multiplicateurs de KarushKuhn-Tucker) tels que :
m
X

J(x ) +
pi i (x ) = 0
(4.6)
i=1

pi i (x )

i = 1, 2, m.

= 0,

(4.7)

Remarque : Ce sont encore des conditions ncessaires doptimalit de premier ordre

appells conditions de Karush-Kuhn-Tucker.
La preuve du Thorme 4.5 fait appel aux rsultats suivants :
Lemme 4.6. Soit v O tel que I(v) 6= et soit w IRn tel que
< j (v) , w > < 0,

j I(v).

Alors w est une direction admissible pour v en O, cest dire, il existe t0 > 0 tel que
v + tw O,

(on a mme plus : v + tw O

t ]0, t0 [.)
39

t [0, t0 ]

Dmonstration. Il faut montrer : j (v + tw) 0, j = 1, 2 , m si t est proche de 0.

Cas 1. Si j 6 I(v).
Alors j (v) < 0 ce qui donne j (v + tw) < 0 si t est proche de 0 (on utilise la continuit
de j ).
Cas 2. Si j I(v).
Alors j (v) = 0 et en utilisant le developpement de Taylor lordre 1 on obtient
j (v + tw) = j (v) + t < j (v) , w > + o(t).

(4.8)

Comme j (v) = 0 et en utilisant lhypothse du lemme, on obtient : j (v + tw) < 0 si

t > 0 est proche de 0. Ceci nous donne le rsultat.
Remarque : On peut affaiblir lhypothse du lemme ci-dessus en prennant : < j (v) , w >
0 si j I(v) et si j est affine (car dans ce cas dans (4.8) on a o(t) = 0).
Le corollaire suivant est une consquence immdiate des lemmes ?? et 2.16 :
Corollaire 4.7. Soit v O tel que I(v) 6= et soit w IRn tel que
< j (v) , w > < 0,

j I(v).

Supposons que v est un minimum local de J sur O. Alors

< J(v) , w > 0.
Lemme 4.8. Soient d1 , d2 , , dl IRn des vecteurs linairement indpendents (donc
forcment l n). Alors la matrice B M(IR) telle que Bij = < di , dj >, i, j = 1, , l
est inversible.
Dmonstration. Soit y = (y1 , y2 , , yl )T IRl telle que B y = 0 cest dire
l
X

< di , dj > yj = 0,

i = 1, 2, , l.

j=1

En multipliant chacune de ces galits par yi et en sommant sur i on obtient

l X
l
X

< yi di , yj dj > = 0

cest dire

i=1 j=1

l
X

yi di k2 = 0.

i=1

Pl
Ceci nous donne
i=1 yi di = 0. Avec lindpendence des vecteurs d1 , d2 , , dl on dduit
y1 = y2 = = yl , donc y = 0.
On a donc montr que By = 0 entrane y = 0, donc B est inversible.

40

Preuve du Thorme 4.5.

Soit x O un point de minimum local de J sur O. Il y a deux situations :
Cas a) Si I(x ) = (aucune contrainte nest active en x ). Alors x appartient
lintrieur de O ce qui implique
J(x ) = 0
et le Thome 4.5 est vraie avec p1 = p2 = = pm = 0.
Cas b) Si I(x ) 6= .
Pour simplifier supposons que I(x ) = {1, 2, , l} avec 1 l m. Cela veut dire :
i (x ) = 0
i (x ) < 0

1il
l+1im

si
si

(avec la convention vidente que la dernire ligne est absente si l = m).

Introduisons les ensembles
) = {x IRn , i (x) = 0 si 1 i l}
O(x
et
V (x ) = {x IRn , i (x) < 0 si l + 1 i m}
(prendre V (x ) = IRn si l = m).
Il est clair que V (x ) est un ouvert et que x V (x ), ce qui nous dit que V (x ) est un
voisinage de x .
) V (x ) O. En plus il existe W IRn avec W voisinage
Dautre part nous avons O(x

) V (x ) O donc
de x tel que x est un point de minimum de J sur O W . Mais O(x
) V (x ) W O W ce qui nous donne que x est un point de minimum de J
O(x
) V (x ) W . Comme V (x ) W est un voisinage de x alors x est un point de
sur O(x
).
minimum local de J sur O(x
On utilise alors le Thorme des multiplicateurs de Lagrange, donc il existe p1 , , pl IR
tels que
l
X

J(x ) +
pk k (x ) = 0.
(4.9)
k=1

Nous posons alors

p1 , p2 ,

, pm

IR tels que

pi = pi
pi = 0

1il
l + 1 i m.

si
si

Alors les galits (4.6) et (4.7) du Thorme 4.5 sont satisfaites (observer quon a pi i (x ) =
0, i = 1, , m).
Pour finir la preuve du Thorme, il reste encore montrer :
pi 0,

i = 1, , l.

41

(4.10)

Nous considrons deux sous-cas :

Cas b1) l = 1 (cest dire : I(x ) = {1}).
Nous avons alors de (4.9) :
J(x ) + p1 1 (x ) = 0.
En faisant le produit scalaire de cette galit par 1 (x ) (remarquer que 1 (x ) 6= 0) on
obtient
p1 k1 (x )k2 = < J(x ) , 1 (x ) > .
Dautre part, du Corollaire 4.7 avec v = x et w = 1 (x ) on dduit
< J(x ) , 1 (x ) > 0
On dduit alors immdiatement
p1 0.
Cas b2) l 2.
On va montrer uniquement
p1 0,

(4.11)

les preuves des autre ingalits tant identiques.

Lide de la preuve est de construire une suite {w(q) }qIN IRn telle que
< w(q) , 1 (x ) > = 1
< w(q) , k (x ) > = 1q

k = 2, , l

(4.12)

(les directions w(q) seront alors admissibles).

Pour cela, on construit w(q) sous la forme
w(q) =

l
X

j j (x )

j=1

avec j IR choisir de sorte que (4.12) soit vraie. Il est clair quil faut alors :
l
X

j < k (x ) , j (x ) > =

j=1

1
1/q

si
si

k=1
k = 2, , l

Ceci est une galit du type B = b o B est la matrice carre de taille l donne par
Bkj =< k (x ) , j (x ) >
est le vecteur inconnu = (1 , , l )T et b est le vecteur dont les lments bk sont
donns par

1
si
k=1
bk =
1/q
si
k = 2, , l
42

Comme les vecteurs 1 (x ), , l (x ) sont indpendents par hypothse, la matrice B

est inversible (voir Lemme 4.8) donc lquation prcdente admet une solution unique.
Donc la suite w(q) avec la proprit (4.12) existe.
Dautre part, lgalit (4.9) nous donne

J(x ) +

l
X

pk k (x ) = 0.

k=1

En multipliant cette galit par w(q) on obtient

< J(x ) , w

(q)

>=

l
X

pk < k (x ) , w(q) >

k=1

ce qui donne laide de (4.12)

l

< J(x ) , w(q) > = p1 +

1X
p .
q k=2 k

(4.13)

Nous avons aussi

< J(x ) , w(q) > 0
comme consquence du Corollaire 4.7 avec w = w(q) . En passant alors la limite q +
en (4.13), on obtient lingalit (4.11), ce qui finit la preuve du Thorme 4.5.
Remarque : Si on considre lensemble
O = {x IRn , i (x) 0, i = 1, , m1 ,

j (x) = 0, j = 1, , m2 }

avec m2 1 alors on peut considrer O comme donn uniquement par des contraintes
ingalits, en crivant
O = {x IRn , i (x) 0, i = 1, , m1 ,

j (x) 0, j = 1, , m2 ,

j (x) 0, j = 1, , m2 }

Il est facile de voir quaucun point x de O nest rgulier, car dune part les deux contraintes
j (x) 0 et j (x) 0 sont actives et dautre part, aucune famille de vecteurs qui
contient la fois j (x) et j (x) ne peut tre indpendente.
Conclusion : Lhypothse de rgularit nest satisfaite pour aucun x O si O comporte
au moins une contrainte galit transforme artificiellement en deux contraintes ingalits.
Exemple : Lensemble
O = {x IR2 , x21 x2 0, x2 x1 4 = 0}
peut scrire sous la forme
O = {x IR2 , x21 x2 0, x2 x1 4 0, x2 + x1 + 4 0}.
43

En introduisant les fonctions : 1 , 2 , 3 : IR2 IR donnes par

1 (x) = x21 x2 , 2 (x) = x2 x1 4, 3 (x) = x2 + x1 + 4
on peut crire O sous la forme standard
O = {x IR2 , i (x) 0, i = 1, 2, 3}.
Il est clair que pour tout x O nous avons {2, 3} I(x). Dautre part, 2 (x) = (1, 1)T
et 3 (x) = (1, 1)T = 2 (x). Donc aucune famille de vecteurs qui inclut 2 (x) et
3 (x) ne peut tre indpendente, donc aucun x O nest rgulier.
Pour rmedier ce genre dinconvenient, il y a deux solutions :
1. Eliminer les contraintes galits en liminant des variables (quand cela est possible)
2. Affaiblir lhypothse de rgularit du Thorme 4.5.
Dans la suite on choisira cette dernire possibilit.
Dfinition 4.9. On dit que les contraintes de O sont qualifis en v O si
a) Soit I(v) =
b) Soit I(v) 6= et il existe w IRn tel quon a i I(v) :
< i (v) , w > 0,
avec en plus
< i (v) , w > < 0 si i est non-affine.
Remarques :
1. Si i est affine pour tout i I(v) alors les contraintes de O sont qualifis en v
(prendre w = 0 dans la partie b) de la Dfinition 4.9). En particulier si les fonctions
i sont affines pour tout i = 1, , m alors les contraintes sont qualifies en tout
point de O.
2. Comme consquence de la Dfinition 4.9 le vecteur w pointe vers lensemble O
(donc t0 > 0 tel que v + tw O, t [0, t0 ] ) (voir Lemme 4.6 et la Remarque
aprs).
Nous avons :
Proposition 4.10. Si un point v O est rgulier alors les contraintes de O sont qualifis
en v. Autrement dit, la condition de qualification de la Dfinition 4.9 est plus faible que
la condition de rgularit de la Dfinition 4.4.
Dmonstration. Nous avons construit dans la preuve du Thorme 4.5 une suite w(q) telle
que < i (v) , w(q) > < 0, i = 1, , l. Ceci prouve le rsultat.
44

On a alors le rsultat suivant, plus forte que le Thorme 4.5 ; ce sera un rsultat admis !
Thorme 4.11. Soit x O tel que les contraintes de O sont qualifis en x . Si x est
un point de minimum local de J sur O alors il existe p1 , p2 , pm [0, +[ (appells
multiplicateurs de Karush-Kuhn-Tucker) tels que :

J(x ) +

m
X

pi i (x ) = 0

(4.14)

i = 1, 2, m.

(4.15)

i=1

pi i (x )

= 0,

Remarque :
lnonc de ce dernier rsultat sobtient partir de lnonc du Thorme 4.5 en remplaant
lhypothse x point rgulier de O par lhypothse plus faible les contraintes de O sont
qualifis en x .
Le rsultat suivant nous donne une condition suffisante pour la qualification en tout
point de O :
Proposition 4.12. Supposons que les fonctions 1 , 2 , , m sont convexes. Supposons
aussi que
- ou bien toutes les fonctions 1 , 2 , , m sont affines
- ou bien il existe y IRn tel que pour tout i = 1, , m on a
i (y) 0
i (y) < 0

si i nest pas affine.

Alors pour tout x O les contraintes de O sont qualifis en x.

Dmonstration. Soit x O. Supposons que I(x) 6= (sinon OK, x est qualifi). Supposons
aussi que toutes les fonctions {i }i=1, ,m ne sont pas affines (sinon OK, x est qualifi,
voir la premire remarque aprs la Dfinition 4.9). Alors il existe y IRn avec la proprit :
i (y) 0, i = 1, , m et
pour tout i = 1, , m tel que i nest pas affine, on a i (y) < 0.
Alors par convexit de i on a
i (y) i (x)+ < i (x) , y x >

i = 1, m

En utilisant lgalit i (x) = 0 pour tout i I(x) on obtient

< i (x) , y x > i (y),

i I(x).

En utilisant les proprits de i (y) on dduit

< i (x) , y x > 0,

i I(x)

et
< i (x) , y x > < 0,

i I(x) si i est non-affine.

Donc la partie b) de la Dfinition 4.9 est satisfaite avec w = yx, ce qui finit la preuve.
45

Exemple 1
O1 = {x IR2 , x2 x21 , x2 x1 = 4}.
Il est clair quon peut crire O1 sous la forme
O1 = {x IR2 , i (x) 0, i = 1, 2, 3}
avec 1 , 2 , 3 : IR2 IR dfinies par
1 (x) = x21 x2 ,

2 (x) = x2 x1 4,

3 (x) = x2 + x1 + 4.

On observe que 1 , 2 et 3 sont convexes, avec en plus 2 et 3 affines. En prennant

y = (0, 4)T nous avons :
1 (y) < 0, 2 (y) = 3 (y) = 0.
Alors les hypothses de la Proposition 4.12 sont satisfaites, donc tous les points de O1 sont
qualifis.
Exemple 2
O2 = {x IR2 , x2 = x21 , x2 x1 4}.
On crit O2 sous la forme
O2 = {x IR2 , i (x) 0, i = 1, 2, 3}
avec
1 (x) = x21 x2 ,

2 (x) = x21 + x2 ,

3 (x) = x2 x1 4.

Comme 2 nest pas convexe, la Proposition 4.12 ne sapplique pas (ceci nimplique pas
automatiquement la non-qualification !) Soit x O2 . Il est clair que {1, 2} I(x). Pour
avoir la qualification, il faudrait quil existe w IR2 tel que
< 1 (x) , w > < 0

et

< 2 (x) , w > < 0

or ceci est impossible car 2 (x) = 1 (x). Donc aucun point de O2 nest qualifi.

4.2.2

Thorie gnrale du point selle

Soit U et P deux ensembles quelconques et lapplication L : U P IR

Dfinition 4.13. On dit que le couple (u , p ) U P est un point selle de L si on a
L(u , p) L(u , p ) L(u, p ),

u U, p P

(Autrement dit : u est un point de minimum de la fonction u U L(u, p ) IR et p

est un point de maximum de la fonction p P L(u , p) IR.)

46

Exemple : Prendre U = P = IR et L(u, p) = u2 p2 . Il est facile de voir que (0, 0) est

un point selle de L.
On introduit les fonctions suivantes :
G : U IR et H : P IR donnes par
G(u) = sup L(u, q)
qP

et respectivement par
H(p) = inf L(v, p).
vU

Remarque : (u , p ) est un point selle de L si et seulement si

G(u ) = L(u , p ) = H(p ).
On a le rsultats suivant :
Proposition 4.14.
sup inf L(u, p) inf sup L(u, p)
pP uU

uU pP

(autrement dit : suppP H(p) inf uU G(u))

Dmonstration. Soit (u, p) U P fix arbitraire. Il est clair quon a
inf L(v, p) L(u, p) sup L(u, q)

vU

qP

ce qui nous donne

H(p) G(u),

(u, p) U P.

En passant au suppremum en p et au infimum en u on obtient le rsultat.

Nous avons :
Thorme 4.15. Si (u , p ) est un point selle de L sur U P alors
sup inf L(u, p) = L(u , p ) = inf sup L(u, p)
pP uU

uU pP

(autrement dit : suppP H(p) = L(u , p ) = inf uU G(u)).

Dmonstration. La dfinition du point selle nous dit
H(p ) = L(u , p ) = G(u )
ce qui nous permet dcrire
sup H(p) L(u , p ) inf G(u).
uU

pP

A laide de la Proposition 4.14 on obtient le rsultat attendu.

47

Exemple : Reprennons lexemple prcdent : L : IR IR IR,

Nous avons
G(u) = sup (u2 p2 ) = u2
pIR
et
H(p) = inf (u2 p2 ) = p2
uIR
On aussi :
inf G(u) = 0, sup H(p) = 0, L(0, 0) = 0
uIR
pIR

L(u, p) = u2 p2 .

(le point (0, 0) tant le point selle de L), ce qui vrifie lgalit du Thorme 4.15.

4.2.3

Applications de la thorie du point selle loptimisation

On utilise ici de nouveau les notations du debut de la Section 4.2, spcifiques aux
problmes doptimisation.
Nous introduisons la fonction L : IRn IRm
+ IR donne par
L(x, p) = J(x) +

m
X

pi i (x) J(x)+ < p , (x) >

i=1

(o on voit p comme un vecteur colonne de composantes p1 , p2 , , pm ). On a le rsultat

suivant :

Thorme 4.16. Si (x , p ) est un point selle de L sur Rn IRm

+ alors x est un point

de minimum de J sur O. En plus (x , p ) satisfait les conditions de Karush-Kuhn-Tucker,
cest dire

Pm
J(x ) + i=1 pi i (x ) = 0
(4.16)

pi i (x ) = 0,
i = 1, , m.

Dmonstration. Nous avons

L(x , p ) L(x , p),

p IRm
+

ce qui donne
m
X
i=1

pi i (x )

m
X

pi i (x ),

p IRm
+.

(4.17)

i=1

En prennant respectivement p = 0 et p = 2p dans lingalit prcdente on obtient

< p , (x ) > = 0.

(4.18)

Maintenant pour un j {1, 2, , m} fix prennons dans (4.17) p = p + ej . On dduit

alors j (x ) 0. Comme ceci est vrai pour tout j, on dduit
x O.
48

(4.19)

Dautre part, on se sert de lingalit

L(x , p ) L(x, p ),

x IRn

cest dire
J(x ) + < p , (x ) > J(x)+ < p , (x) >

x IRn .

(4.20)

En utilisant lgalit (4.18) et le fait que < p , (x) > 0 pour x O, on dduit
J(x ) J(x),

x O.

Ceci nous dit que x est un point de minimum de J sur O.

Dautre part, P
de (4.20) on dduit que x est un point de minimum de la fonction

x IRn J(x)+ m
i=1 pi i (x). Ceci nous donne, en utilisant le Thorme 2.17, la premire
galit de (4.16). Finalement, de (4.18) et (4.19) on a
m
X

pj j (x ) = 0 et

pi i (x ) 0 pour tout i {1, , m}

j=1

ce qui nous donne la deuxime partie de (4.16). Ceci finit la preuve du Thorme.
Remarque : Ce rsultat nous donne une condition suffisante pour avoir un minimum de
J sur O. On verra aussi une reciproque, sous des hypothses supplementaires. On cherchera
alors rsoudre le problme appell le problme dual :
sup

inf n L(u, p)

m
pIR+ uIR

(justifi par le Thorme 4.15) plus simple rsoudre que le problme de minimisation de
J sur O (quon appellera problme primal).

4.2.4

Le cas convexe

On verra ici des rciproques des Thormes 4.5 et 4.16 dans le cas o J et j sont
convexes.
Thorme 4.17. (Rciproque du Thorme 4.5).
Supposons que toutes les fonctions J, 1 , 2 , , m sont convexes. Supposons aussi quil
existe p1 , p2 , , pm [0, +[ et x O tels que les conditions de Karush-Kuhn-Tucker
(4.6) et (4.7) du Thorme 4.5 soient satisfaites. Alors
a) x est un point de minimum de J sur O
b) (x , p ) est un point selle de L
(Rappel : L : IRn IRm
L(x, p) = J(x) + < p , (x) >).
+ IR,

49

Dmonstration. a) Nous avons

J(x ) J(x )

m
X

pi i (y),

y O ( car i (y) 0, pi 0).

i=1

Ensuite de (4.7) et de la convexit de i on dduit

pi i (y) = pi [i (y) i (x )] pi < i (x ) , y x >
On obtient alors des ingalits prcdentes et de (4.6) :
J(x ) J(x )+ < J(x ), y x >,

y O.

En utilisant cette fois-ci la convexit de J nous obtenons

J(x ) J(y),

y O

ce qui finit la preuve de a).

b) Nous avons
L(x , p) = J(x )+ < p , (x ) > J(x )+ < p , (x ) > = L(x , p ),

p IRm
+

car < p , (x ) > 0 et < p , (x ) > = 0.

Dautre part, comme les fonctions J, 1 , , m sont convexes alors lapplication x IRn
L(x, p ) est convexe. Mais lgalit (4.6) nous dit que le gradient de cette application
sannule en x . On dduit alors (voir la remarque aprs Thorme 2.18) que x est un point
de minimum de cette application et ceci finit la preuve.
On finit cette section par les corollaires suivants :
Corollaire 4.18. (Lien entre point selle et conditions de Karush-Kuhn-Tucker)
Supposons que les fonctions J, 1 , , m sont convexes. Alors (x , p ) est point selle de L
si et seulement si x O et les conditions (4.6) et (4.7) sont satisfaites.
Dmonstration. Cest une consquence immdiate des Thormes 4.16 et 4.17 partie b).
Corollaire 4.19. (Rciproque du Thorme 4.16)
Supposons que les fonctions J, 1 , , m sont convexes. Soit x un point de minimum de
J sur O tel que les contraintes de O sont qualifis en x . Alors il existe p IRm
+ tel que

(x , p ) est un point selle de L.
Dmonstration. Cest une consquence immdiate des Thormes 4.11 et 4.17 partie b).

50

4.3

Algorithmes de minimisation avec contraintes

Le but de cette section est de donner des algorithmes numriques pour la rsolution du
problme de minimisation avec contraintes :
min J(u)

(4.21)

uU

avec U IRn un enesemble de contraintes.

On rappelle les deux cas de contraintes que nous considrons dans ce cours :
1. U est un pav, cest dire, il est de la forme U = [a1 , b1 ] [a2 , b2 ] [an , bn ]
(avec la convention quon peut avoir ] la place de [ai ou +[ la place
de bi ], donc le pav peut tre de volume infinit).
2. U est de la forme
U = {x IRn , i (x) 0, i = 1, 2, m}
avec m IN et 1 , 2 , m des fonctions de IRn dans IR donnes (U est donn par
des contraintes ingalits larges).
Dans le premier cas on utilisera des extension naturelles des mthodes de minimisation sur
IRn , vues en Chapitre 3. Dans le deuxime cas on utilisera des mthodes du type dualit.

4.3.1

Mthodes de relaxation

On suppose ici
U = [a1 , b1 ] [a2 , b2 ] [an , bn ] ni=1 [ai , bi ].

(4.22)

Lalgorithme dans ce cas ressemble lalgorithme de relaxation pour minimisation sans

contraintes.
Algorithme :

T

T
(k)
(k)
(k)
(k+1)
(k+1)
(k+1)
On se donne u(k) = u1 , u2 , , un
et on va calculer u(k+1) = u1
, u2
, , un
en n pas successifs. On a :
(k+1)

J(u1
(k+1)

J(u1

(k)

(k)

(k)
, u2 , u(k)
n ) = min J(y, u2 , un )
y[a1 , b1 ]

(k+1)

, u2

(k)

(k+1)

, u3 u(k)
n ) = min J(u1
y[a2 , b2 ]

(k)

, y, u3 u(k)
n )

...
(k+1)
J(u1
,

u(k+1)
)
n

(k+1)

min J(u1

y[an , bn ]

(k+1)

, un1 , y)

Comme dans le cas sans contraintes, on a le thorme de convergence suivant :

Thorme 4.20. Si J : IRn IR est une fonction elliptique et lensemble U est donn
par (4.22) alors la mthode de relaxation pour la minimisation de J sur U est bien dfinie
et converge.
Dmonstration. La preuve du fait que la mthode est bien dfinie se fait exactement comme
dans le Thorme 3.3. La convergence est admise !
51

4.3.2

Mthodes de projection

Rappellons dabord le rsultat fondamental suivant :

Thorme 4.21. (Thorme de projection sur un convexe ferm)
Soit U IRn un ensemble convexe, ferm, non-vide et soit v IRn . Alors il existe un
unique element P v U (on peut le noter pour plus de prcision par PU (v)) tel que
kv PU (v)k = inf kv uk = min kv uk.
uU

uU

Llment PU (v) U sappelle la projection de v sur U en IRn . En plus on a

a) Llment PU (v) U satisfait aussi
< v PU (v) , u PU (v) > 0,

u U

(4.23)

b) Si w U est tel que

< v w , u w > 0,

u U

(4.24)

alors w = PU (v) (donc w = PU (v) est lunique lment de U satisfaisant (4.24).

c) On a
kPU (v1 ) PU (v2 )k kv1 v2 k, v1 , v2 IRn
(la fonction PU naugmente pas les distances). Ceci implique que PU est une fonction lipschitzienne, donc continue.
d) On a
v = PU (v) si et seulement si v U
e) Si U est le sous-espace affine ferm de IRn donn par U = a + U0 avec a IRn et U0
un sous-espace vectoriel ferm de IRn alors lingalit (4.23) devient lgalit
< v PU (v) , u > = 0,

u U0

(cest dire v PU (v) U0 ).

Ide de la preuve
Tout revient minimiser sur U la fonction g : IRn IR dfinie par
g(u) = ku vk2 .
Montrons dabord que g est une fonction elliptique. Pour cela, on utilise les calculs et les
rsultats du Chapitre 2. On peut crire
g(u) = < v u , v u > = < u, u > 2 < u, v > + < v, v > .
ce qui donne
g(u) = 2u 2v
52

2 g(u) = 2In

( donc constante indpendente de u).

Comme 2In est une matrice symmtrique et dfinie positive (matrice SDP) alors g est
elliptique.
Comme U est ferm convexe alors il existe un unique lment P v = PU (v) U tel que
g(PU (v)) g(u), u U cest dire
kv PU (v)k kv uk,

u U.

ce qui donne le rsultat principal du thorme. Nous avons aussi (voir Thorme 2.17) :
< g(PU (v)) , u PU (v) > 0,

uU

ce qui nous donne facilement

< v PU (v) , u PU (v) > 0,

u U.

ce qui prove a). La partie b) est une consquence de lellipticit et de lunicit.

Dautre part, soient v1 , v2 IRn . On a alors
< v1 P v1 , u P v1 > 0,

u U

< v2 P v2 , u P v2 > 0,

u U

En prennant u = P v2 dans la premire ingalit et u = P v1 dans la deuxime et en faisant

la somme, on trouve
< P v2 P v1 , v1 P v1 v2 + P v2 > 0
ce qui donne
kP v2 P v1 k2 < P v2 P v1 , v2 v1 > kP v2 P v1 k kv2 v1 k
(on a utilis lingalit de Cauchy-Schwarz). Ceci nous donne c) par simplification.
La partie d) est vidente.
Pour la partie e), soit U0 un sous-espace vectoriel de IRn , a IRn , U = a + U0 et h U0
arbitraire et fix. On va prendre en (4.23) : u = P v h qui est un lment de U car P v U
et h U0 . Ceci donne
< v Pv , h > 0
do on dduit
< v Pv , h > = 0
ce qui finit la preuve.
Exemple 1.
Si n = 1 et U = [a, b]
tout v IR on a

a
v
PU (v) =

(avec a < b +) alors il est facile de voir que pour

si
si
si

(partie inexistente si a = )

v<a
vU
v>b

(partie inexistente si b = +)
53

On a videment le cas particulier : si U = [0, +[ alors


v
si
v0
PU (v) =
0
si
v<0
On peut aussi noter dans ce cas
PU (v) = v + ,

v IR.

Exemple 2.
Supposons que U est un pav, donc
U = ni=1 [ai , bi ] IRn
avec ai < bi +,

i = 1, , n. Alors v = (v1 , v2 , , vn )T IRn on a

PU (v) = (P1 v1 , P2 v2 , , Pn vn )T

avec Pk vk = la projection de vk en IR sur lintervalle [ak , bk ] (voir TD pour la preuve).

Cas particulier : Si U = [0, , +[n alors PU (v) = (v1+ , v2+ , , vn+ )T .
Remarque : Dans le cas o U est donn par des contraintes ingalit gnrales, alors il
peut tre difficile en pratique de calculer la projection en IRn sur U .
Revenons au problme de minimisation (4.21). On supposera dans la suite que lensemble U des contraintes est convexe et ferme.
Supposons que x U est tel que
J(x ) = min J(x).
xU

Alors
< J(x ) , x x > 0,

xU

(4.25)

qui est quivalente pour tout > 0 lingalit

< J(x ) , x x > 0,

x U.

Ceci donne
< [x J(x )] x , x x > 0,

x U.

En utilisant le Thorme de projection cette dernire ingalit est quivalente lgalit

x = PU (x J(x )).
Alors la solution du problme de minimisation (4.21) est un point fixe de lapplication
g : U 7 O donne par
g(x) = PU (x J(x)).
54

Une ide naturelle pour approcher numriquement ce point fixe est dutiliser une mthode
iterative, qui consiste construire une suite x(k) U par reccurence :
x(k+1) = PU (x(k) J(x(k) )),

k IN

avec > 0 donn. Il est aussi possible de faire varier chaque pas. Donc lalgorithme
gnral sera dans ce cas :
(
x(k+1) = PU (x(k) k J(x(k) )), k IN
(4.26)
x(0) donn U
avec k > 0 donnes. Cest la mthode de gradient avec projection pas variable.
On lappelle mthode de gradient avec projection pas fixe si k est indpendent
de k.
On a le rsultat suivant :
Thorme 4.22. Soit U IRn un ensemble ferm, convexe et non vide et J : IRn 7 IR
une fonction elliptique telle que J soit lipschitzienne
(Donc il existe M > 0 et > 0 tels que x, y IRn on a
< J(x) J(y) , x y > kx yk2
et
kJ(x) J(y)k M kx yk. )
Supposons quil existe des nombres rels a1 et a2 satisfaisant
0 < a1 a2 <

2
M2

tels que
a1 k a2

k IN.

Alors la mthode (4.26) converge et la convergence est gomtrique

(cest dire, il existe C 0 et [0, 1[ tels que
kx(k) x k C k ,

k IN. )

Dmonstration. Par dfinition nous avons

x(k+1) = PU x(k) k J(x(k) )
et aussi
x = PU (x k J(x ))
En faisant la diffrence et en utilisant la Partie c) du Thorme 4.21 (Thorme de projection), on dduit


kx(k+1) x k kx(k) x k J(x(k) ) J(x ) k
55

cest dire
kx(k+1) x k2 kx(k) x k2 +2k kJ(x(k) )J(x )k2 2k < x(k) x , J(x(k) )J(x ) > .
En utilisant les hypothses sur J on dduit
kx(k+1) x k2 (1 2k + M 2 2k )kx(k) x k2 .
La suite de la preuve est exactement comme dans la preuve du Thorme 3.6 ( partir de
lingalit (3.12)).
Remarque : Cette mthode est applicable uniquement si on peut calculer facilement
la projection PU , par exemple si U est un pav en IRn . Pour un ensemble U donn par des
contraintes ingalits larges, il nest pas facile en gnral dutiliser cette mthode.
Exemple : Supposons que J est une fonction quadratique associe une matrice SDP,
donc J : IRn IR est donne par
J(x) =

1
< Ax , x > < b, x > + c
2

avec A Mn (IR) une matrice carre relle et SDP, b IRn , c IR.

Supposons aussi que U = [0, +[n .
Rappellons quon a dans ce cas :
J(x) = Ax b,

x IRn

+
+
PU (x1 , x2 , , xn ) = (x+
1 , x2 , , xn )

Alors (4.26) devient

(k+1)

xi

4.3.3

(k)
= max{xi k Ax(k) b i , 0}, i = 1, , n et k IN.

Mthodes de pnalisation exterieure

On considre toujours le problme de minimisation (4.21).

On introduira une fonction : IRn 7 IR ayant les proprits suivantes :

fonction continue et convexe

(x) 0, x IRn

(x) = 0 si et seulement si x U.

(4.27)

Remarque : Une fonction avec les proprits de (4.27) est appelle fonction de pnalisation extrieure pour U . On introduit ensuite pour tout  > 0 assez petit une
fonction J : IRn 7 IR dfinie par
1
J (x) = J(x) + (x).

56

(4.28)

La fonction J sappelle fonction pnalise de J.

La mthode de pnalisation exterieure du problme (4.21) consiste minimiser sur
IRn la fonction J , avec un  > 0 qui tend vers 0. La partie 1 (x) pnalise lloignement
de x par rapport U .
On rduit donc le problme de minimisation avec contraintes (de J sur U ) un problme
de minimisation sans contraintes (de J sur IRn ). On applique pour la minimisation sans
contraintes de J tout algorithme vu en Chapitre 3.
Le rsultat suivant de convergence justifie cette mthode :
Thorme 4.23. Soit J : IRn 7 IR une fonction continue, coercive sur IRn et strictement
convexe, U IRn un ensemble convexe, ferm et non-vide et : IRn 7 IR une fonction de
pnalisation extrieure de U (donc satisfaisant les hypothses de (4.27)).
Alors pour tout  > 0 il existe un unique lment x IRn vrifiant
J (x ) = minn J (x).
xIR
En plus on a
x x

pour  7 0

o x est lunique point de U satisfaisant

J(x ) J(x),

x U.

Dmonstration. Il est facile de voir que pour tout  > 0 fix, J est une fonction continue,
coercive et strictement convexe sur IRn ; donc il existe un unique point de minimum de J
sur IRn quon va noter par x . Il est facile de voir que
J J

et

J = J sur U.

On dduit alors
J(x ) J (x ) J (x) = J(x),

x U.

(4.29)

Ceci nous dit que la suite J(x ) est borne, ce qui implique que la suite x est borne (car
sinon, il y aurait une sous-suite de x dont la norme tend vers +, ce qui impliquerait,
par coercivit de J, que J(x ) 7 + ; ceci est impossible cause de (4.29)).
Comme x est born en IRn , le Thorme de Bolzano-Weierstrass nous dit quil existe une
sous-suite x0 de x tel que x0 converge vers un lment x de IRn . En passant la limite
0 7 0 en (4.29) on dduit, grce la continuit de J que
J(x ) J(x),

x U.

(4.30)

Pour montrer que x est un point de minimum de J sur U il reste montrer que x U ;
grce la troisime proprit de (4.27) ceci revient montrer que (x ) = 0. En effet nous
avons :
0 (x0 ) = 0 [J0 (x0 ) J(x0 )] 0 [J(x) J(x0 )]
57

pour un x U fix. Par continuit de J nous avons que J(x0 ) converge, donc le term
J(x) J(x0 ) est born. Ceci implique que 0 [J(x) J(x0 )] 0 pour 0 0. On obtient
alors (x0 ) 7 0. Par continuit de on dduit (x ) = 0, cest dire x U .
Comme J est strictement convexe, x est lunique point de minimum de J sur U .
Il nous reste dmontrer que toute la squence x converge vers x . Montrons ce
rsultat par absurd : supposons que x ne converge pas vers x ; ceci implique quil existe
une sous-suite x00 de x et un > 0 tels que
kx00 x k .

(4.31)

En rproduisant pour x00 le mme argument que pour x , on peut extraire une sous-suite
x000 de x00 qui converge vers x (lunicit de x est ici essentielle) ; ceci contredit (4.31) et
finit la preuve du Thorme.
Remarque : Cette mthode est utile sil est facile de construire une fonction avec
les proprits (4.27).
Exemple : On appelle distance dun point x IRn lensemble U , note dist(x, U ) la
quantit donne par
dist(x, U ) = kx PU (x)k.
(rappellons que U est ferm et convexe). On dfinit alors la fonction : IRn 7 IR par
(x) = dist2 (x, U ) = kx PU (x)k2 .
Il est trs facile de montrer toutes les proprits de (4.27) sauf la convexit de . Pour la
convexit de dans un cas particulier de U voir TD.

4.3.4

Mthode dUzawa

La mthode dUzawa est base sur la formulation duale et la recherche des points selle
et elle est bien adapte pour des ensembles de contraintes dfinies par des ingalits larges.
On va considrer ici des ensembles de contraintes comme dans la Section 4.2, cest
dire
U = O = {x IRn , i (x) 0, i = 1, 2, , m}
avec 1 , 2 , , m : IRn 7 IR, m IN . On peut encore crire
U = O = {x IRn , (x) 0}.
Rappellons que nous considrons le problme de minimisation (4.21).
Nous faisons dans cette partie les hypothses suivantes :
1. J est elliptique, donc J est de classe C 1 et il existe > 0 tel que
< J(x) J(y) , x y > kx yk2 ,
58

x, y IRn

2. Pour tout k = 1, , m on a que k est une fonction convexe et de classe C 1 . En

plus est lipschitzienne, donc il existe M > 0 tel que
k(x) (y)k M kx yk,

x, y IRn .

3. Les contraintes de O sont qualifis en tout point x O.

Nous introduisons lapplication L : IRn IRm
+ 7 IR donne par
L(x, p) = J(x) + < p, (x) > = J(x) +

m
X

pk k (x),

x IRn , p IRm
+.

k=1

Grce la convexit de toutes les fonctions k lensemble U est convexe (Proposition

4.1). Comme lensemble U est ferm et convexe et J elliptique, il existe un unique point
de minimum x U de J sur U . Le Corollaire 4.19 nous dit alors quil existe p =

(p1 , p2 , , pm )T IRm
+ tel que (x , p ) est un point selle de L. Du Thorme 4.15 on
dduit alors que
sup inf n L(x, p) = L(x , p ) = inf n sup L(x, p).
m
xIR pIRm
pIR+ xIR
+
Introduisons la fonction H : IRm
+ 7 IR par
H(p) = inf n L(x, p).
xIR
La Proposition 2.12 et les hypothses faites sur J et les k nous disent que pour tout
p IRm
+ fix lapplication
x IRn 7 L(x, p) IR
est elliptique. Alors il existe un unique point de minimum de cette aplication sur IRn , que
nous allons noter xp . Donc xp IRn est tel que
L(
xp , p) L(x, p) x IRn .
On dduit alors que H prend ses valeurs en IR et que
H(p) = minn L(x, p) = L(
xp , p),
xR

p IRm
+.

Le problme dual de (4.21) sera

Trouver p IRm
p ) = sup H(p)
+ tel que H(
m
pIR+

(4.32)

(le problme (4.21) sera appell problme primal).

Remarque : Le problme de maximisation (4.32) peut scrire comme un problme de
minimisation :
H(
p ) = inf m [H(p)].
pIR+
59

Supposons que p est bien une solution du problme de maximisation (4.32). Alors on a
sup inf n L(x, p) = sup H(p) = H(
p ) = L(
x , p )
m
m
pIR+ xIR
pIR+

o on a not x = xp .
Alors le point selle (x , p ) que nous cherchons, se trouve parmi les solutions (
x , p ) provenant de (4.32).
Comme lensemble des contraintes du problme dual (4.32) est un pav (cest lensemble
m
IR+ ) on peut alors utiliser un algorithme de gradient avec projection pas variable :
(k)

p(k+1) = PIRm [pi + k H(p(k) )]

+
ce qui donne, en tenent compte de lexpression de la projection sur IRm
+ :


H (k)
(k)
(k+1)
p
= max pi + k
(p ), 0
i = 1, , m
pi

(4.33)

avec k > 0.
.
Il nous reste calculer H
pi
Nous avons le calcul formelP
suivant, en supposant que lapplication p 7 xp est de classe
xp ) alors
C 1 : comme H(p) = J(
xp ) + m
j=1 pj j (
m

X
H
xp
xp
= < J(
xp ) ,
> +i (
xp ) +
pj < j (
xp ) ,
>
pi
pi
p
i
j=1
P
xp ) = 0 (consquence immdiate du fait que xp est le
Mais comme J(
xp ) + m
j=1 pj j (
point de minimum de la fonction x 7 L(x, p) ) alors il reste
H
= i (
xp ).
pi
Le rsultat prcis avec dmonstration rigoureuse est donn dans le lemme suivant :
Lemme 4.24. La fonction H est de classe C 1 et on a p IRm
+ :
H
(p) = i (
xp ),
pi

i = 1, 2, , m.

m
Dmonstration. Soit p IRm
+ et t IR tel que p + tei IR+ . Le but principal est de
montrer que la limite pour t 7 0 de 1t [H(p + tei ) H(p)] existe et de calculer cette limite.
Etape 1. On montre dabord que lapplication p 7 xp est continue.
0
Soit p 0 fix et p0 0 tel que p0 converge vers p. Les vecteurs xp et xp satisfont
respectivement
m
X
p
J(
x )+
pj j (
xp ) = 0
j=1

60

et
p0

J(
x )+

m
X

p0j j (
xp ) = 0

j=1
0

En faisant la diffrence entre ces deux galits et en faisant le produit scalaire avec xp xp
on trouve
X
0
0
0
0
< J(
xp ) J(
xp ) , xp xp > +
p0j < j (
xp ) j (
xp ) , xp xp >
j

(p0j pj ) < j (
xp ) , xp xp > = 0

On utilise ensuite lingalite dellipticit de J et le fait que les fonctions j sont convexes
et on dduit
X
0
0
k
xp xp k2
(p0j pj ) < j (
xp ) , xp xp >
j

En utilisant lingalit de Cauchy-Schwarz, on trouve

X
0
0
k
xp xp k2
|p0j pj | kj (
xp )k k
xp xp k
j

ce qui nous donne immdiatement

0

xp 7 xp

si p0 7 p.

On a donc la continuit souhaite.

Etape 2. Nous avons dune part
H(p) = L(
xp , p) L(
xp+tei , p)
et dautre part
H(p + tei ) = L(
xp+tei , p + tei ) L(
xp , p + tei ).
Ceci nous donne
X
X
H(p+tei )H(p) L(
xp , p+tei )L(
xp , p) = J(
xp )+
pj j (
xp )+ti (
xp )J(
xp )
pj j (
xp )
j

cest dire
H(p + tei ) H(p) ti (
xp ).

(4.34)

Nous avons aussi

H(p + tei ) H(p) L(
xp+tei , p + tei ) L(
xp+tei , p) = J(
xp+tei )+
X
X
pj j (
xp+tei ) + ti (
xp+tei ) J(
xp+tei )
pj j (
xp+tei )
j

61

cest dire
H(p + tei ) H(p) ti (
xp+tei ).

(4.35)

En divisant (4.34) et (4.35) par t 6= 0 on trouve

i (
xp+tei )

H(p + tei ) H(p)

i (
xp ),
t

si t > 0

et

H(p + tei ) H(p)

i (
xp+tei ), si t < 0.
t
En passant la limite t 7 0 et en utilisant le fait que xp+tei 7 xp (consquence de lEtape
1) on dduit
H(p + tei ) H(p)
i (
xp ) si t 7 0.
t
En utilisant de nouveau le rsultat de lEtape 1 on obtient le rsultat attendu.
i (
xp )

On peut alors remplacer lexpression de

H
pi

dans (4.33) et on trouve

n
o
(k)
(k)
p(k+1) = max pi + k i (
xp ), 0
(k)

i = 1, , m

On va noter dans la suite x(k) = xp . Alors lalgorithme dUzawa est le suivant :

(0)
pas 1. On pose k = 0, on choisit p(0) IRm
= 0) et on choisit
+ (par exemple p
kmax IN assez grand (par exemple kmax = 1000) et  > 0 assez petit (par exemple
 = 106 ).
pas 2. Calculer x(k) IRn qui minimise sur IRn la fonction x IRn J(x) +
Pm (k)
j=1 pj j (x) (appliquer lun des algorithme de minimisation sans contrainte vus en Chapitre 3).
Si (k 1) alors
Si kx(k) x(k1) k  alors x(k) est le point de minimum recherch (lalgorithme a
converg)
Sinon, va au pas 3.
pas 3.
Si (k = kmax ) alors lalgorithme diverge.
Sinon, faire :
n
o
(k+1)
(k)
pi
= max pi + k i (x(k) ), 0
i = 1, , m
ensuite k = k + 1, retour au pas 2.
Nous finissons par le rsultat de convergence suivant :
Thorme 4.25. (convergence de lalgorithme dUzawa)
Soient a1 , a2 IR tels que
2
0 < a1 a2 < 2 .
M
62

Supposons que les facteurs k sont tels que

a1 k a2

k IN.

Alors la suite x(k) gnre par lalgorithme dUzawa converge vers x lunique solution du
problme de minimisation (4.21).
Dmonstration. Il est clair que x(k) et x existent et sont uniques, grce aux hypothses

du dbut du paragraph 4.3.4. On rappelle aussi quil existe p IRm
+ tel que (x , p ) soit
un point selle de L.
Etape 1. Nous montrons les ingalits suivantes :
< J(x(k) ) , x x(k) > +

m
X

(k)

pj [i (x) i (x(k) )] 0,

x IRn

(4.36)

x IRn

(4.37)

j=1

et

< J(x ) , x x > +

m
X

pj [i (x) i (x )] 0,

j=1

Preuve de (4.36) : Dans lingalit

J(z) +

m
X

(k)

pj j (z) J(x(k) ) +

j=1

m
X

(k)

pj j (x(k) ),

z IRn

j=1

prenons z = x(k) + t(x x(k) ) avec x IRn arbitraire et t [0, 1]. Grce la convexit
des j nous avons
j (x(k) + t(x x(k) )) j (x(k) ) t[j (x) j (x(k) ]
ce qui donne avec lingalit prcdente :
J(x

(k)

(k)

(k)

+ t(x x )) J(x ) + t

m
X

(k)

pj [j (x) j (x(k) ] 0,

t ]0, 1].

j=1

En divisant par t et en passant la limite t 7 0 on obtient (4.36).

La preuve de (4.37) est analogue (remplacer p(k) et x(k) par p et x respectivement).
Etape 2. En posant x = x en (4.36) et x = x(k) en (4.37) et en faisant la somme des deux
ingalits, on obtient :

(k)

< J(x ) J(x ) , x

(k)

m
X
(k)
x > +
(pj pj )[i (x(k) ) i (x )] 0

j=1

ce qui donne, en utilisant lhypothse dellipticit de J :

< p(k) p , (x(k) ) (x ) > kx(k) x k2 .
63

(4.38)

Dautre part, nous avons par hypothse

p(k+1) = PIRm p(k) + k (x(k) ).
+

(4.39)

Comme p ralise le minimum sur IR+ de la fonction

p J(x ) < p , (x ) > nous avons
p = PIRm (p + k (x ))
+

(4.40)

En faisant la diffrence entre (4.39) et (4.40) et en utilisant la partie c) du Thorme de

projection, on dduit
kp(k+1) p k kp(k) p + k [(x(k) ) (x )]k
cest dire,
kp(k+1) p k2 kp(k) p k2 + 2k k(x(k) ) (x )k2 + 2k < p(k) p , (x(k) ) (x ) >
En utilisant le fait que est lipschitzienne, on dduit
kp(k+1) p k2 kp(k) p k2 + 2k M 2 kx(k) x k2 + 2k < p(k) p , (x(k) ) (x ) > (4.41)
On obtient ensuite facilement des ingalits (4.38) et (4.41) :
kp(k+1) p k2 kp(k) p k2 + 2k M 2 kx(k) x k2 2k kx(k) x k2
cest dire
kp(k+1) p k2 kp(k) p k2 + (2k M 2 2k )kx(k) x k2

(4.42)

Introduisons la fonction : IR IR donne par

() = 2 M 2 2
 2 
et que
On observe que () > 0, 0, M
2
() min{(a1 ), (a2 )} [a1 , a2 ].
En choisissant alors = min{(a1 ), (a2 )} > 0 on dduit
2k M 2 2k

k IN.

Ceci nous permet de dduire de (4.42) :

kp(k+1) p k2 kp(k) p k2 kx(k) x k2

(4.43)

On obtient alors
kp(k+1) p k2 kp(k) p k2
ce qui nous dit que la suite relle kp(k) p k2 est dcroissante. Comme elle est aussi
positive, elle est convergente, et soit l 0 sa limite. On obtient de (4.43) :

1  (k)
kp p k2 kp(k+1) p k2
kx(k) x k2

Comme le membre de droite de cette ingalit converge vers 0, on dduit que x(k) converge
vers x . Ceci finit la preuve.
FIN
64

Bibliographie
[1] D. Az, J.B. Hiriart-Urruty, Analyse variationnelle et optimisation, Cpadus, 2010
[2] M. Bergounioux, Optimisation et contrle des systmes linaires, Dunod, Paris, 2001.
[3] P. Ciarlet, Introduction lanalyse numrique matricielle et loptimisation, Masson,
Paris, 1982.
[4] P. Ciarlet, B. Miara, J.M. Thomas, Exercices lanalyse numrique matricielle et doptimisation, Masson, Paris, 1987.

65