Cours 10 : Optimisation non lineaire

multidimensionnelle sans contraintes

Christophe Gonzales

LIP6 Universite Paris 6, France

 Plan du cours

Optimisation dune fonction differentiable a` n variables

1
methode du gradient
2
methode du gradient conjugue (la semaine prochaine)

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 2/14

Fonction differentiable
f : C 7 R : fonction definie
dans un convexe ouvert C de Rn :

x1
...

f :x = xj 7 f (x) = f (x1 , ..., xj , ..., xn )

...
xn

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 3/14

Fonction differentiable
f : C 7 R : fonction definie
dans un convexe ouvert C de Rn :

x1
...

f :x = xj 7 f (x) = f (x1 , ..., xj , ..., xn )

...
xn

fonction differentiable
f (x)

f est differentiable en x C si deriv
ees partielles ,
xj
j = 1, ..., n et admet pour approximation du 1er ordre la forme

lineaire
quelles definissent :
n
X f (x)
f (x + h) = [f (x1 + h1 , . . . , xn + hn )] = f (x) + .hj + o(khk)
xj
j=1

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 3/14
 Gradient (1/3)

Definition du gradient

f (x)
x1
...


f (x)
~ ~

f (x) : gradient de f en x = le vecteur f (x) =
xj


...


f (x)
xn

~ (x)T .h + o(khk)
= f (x + h) = f (x) + f
`
= La variation de f est du 2eme ~ (x)T .h = 0
ordre lorsque f
n o
~ (x) 6= 0 = y : f (y ) = f (x) + f
f ~ (x)T . [y x] = lhyper-
plan tangent en x a` lhypersurface de niveau {z : f (z) = f (x)}

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 4/14
 Gradient (1/3)

Definition du gradient

f (x)
x1
...


f (x)
~ ~

f (x) : gradient de f en x = le vecteur f (x) =
xj


...


f (x)
xn

~ (x)T .h + o(khk)
= f (x + h) = f (x) + f
`
= La variation de f est du 2eme ~ (x)T .h = 0
ordre lorsque f
n o
~ (x) 6= 0 = y : f (y ) = f (x) + f
f ~ (x)T . [y x] = lhyper-
plan tangent en x a` lhypersurface de niveau {z : f (z) = f (x)}

~ (x)
normale de lhyperplan = f

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 4/14
 Gradient (2/3)

~ (x)
normale de lhyperplan = f

~ (x)) = f (x) + f
f (x + f ~ (x)T .f
~ (x)
2
~
= f (x) + f (x)

> f (x) pour > 0

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 5/14
 Gradient (2/3)

~ (x)
normale de lhyperplan = f

~ (x)) = f (x) + f
f (x + f ~ (x)T .f
~ (x)
2
~
= f (x) + f (x)

> f (x) pour > 0

du cot
= normale dirigee e des points ou` f prend des valeurs
ees
plus elev quen x

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 5/14
 Gradient (2/3)

~ (x)
normale de lhyperplan = f

~ (x)) = f (x) + f
f (x + f ~ (x)T .f
~ (x)
2
~
= f (x) + f (x)

> f (x) pour > 0

du cot
= normale dirigee e des points ou` f prend des valeurs
ees
plus elev quen x

~ (x) = direction interessante

on cherche min f = = f

~ (x) = direction de lanti-gradient

= f

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 5/14
 Gradient (3/3)

x2
~ (x)
f

~ (x)
f

xb
f (x) = constante

x1

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 6/14
 Minima et points stationnaires

minimum (global ou absolu) de f en xb : x C = f (x) f (xb)

minimum local de f en xb : un voisinage V de xb tel que
x V = f (x) f (xb)
voisinage V de xb dans C = un sous-ensemble de C
contenant une boule ouverte {y : ky xk < }
~ (xb) = 0
xb = point stationnaire de f si f

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 7/14
 Minima et points stationnaires

minimum (global ou absolu) de f en xb : x C = f (x) f (xb)

minimum local de f en xb : un voisinage V de xb tel que
x V = f (x) f (xb)
voisinage V de xb dans C = un sous-ensemble de C
contenant une boule ouverte {y : ky xk < }
~ (xb) = 0
xb = point stationnaire de f si f

Lemme

f differentiable
minimum local de f en xb = xb = point stationnaire
de plus, si f convexe :
xb = point stationnaire = xb = minimum local

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 7/14
 Direction de lanti-gradient (1/2)

La methode du gradient sappuie sur :

Proposition
La direction de lanti-gradient est la direction de plus grande
pente :
f (x) f (x + h)
max lim0
~
{h:khk=kf (x)k} khk

~ (x).
est atteint pour h = f

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 8/14
 Direction de lanti-gradient (2/2)

Demonstration de la proposition :

~ (x)T .h + o( khk) = pour khk =
f (x) f (x + h) = f ~ (x)
f :
 
~ (x)T .h + o
f ~ (x)
f
f (x) f (x + h)
=
khk ~
f (x)

~ (x)T .h o()
f
= +
~
f (x)

f (x) f (x + h) ~ (x)T .h
f
= lim0 =
khk ~
f (x)

 
~ (x).h est maximum sous khk =
ou` f ~ (x)
f ~ (x)
pour h = f

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 9/14

Pas de la methode du gradient

variations de f lorsque lon part de x dans la direction de

lanti-gradient = celles de la fonction dune seule variable 0 :
~ (x))
: 7 () = f (x f

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 10/14

Pas de la methode du gradient

variations de f lorsque lon part de x dans la direction de

lanti-gradient = celles de la fonction dune seule variable 0 :
~ (x))
: 7 () = f (x f
n
X f
Or 0 () = ~ (x)).f
(x f ~ j (x) = f
~ (x f
~ (x)).f
~ (x)
xj
j=1
2
~ (x)T .f
en particulier : 0 (0) = f ~ (x) = ~ (x)
f <0

= strictement decroissante au voisinage de = 0

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 10/14

Pas de la methode du gradient

variations de f lorsque lon part de x dans la direction de

lanti-gradient = celles de la fonction dune seule variable 0 :
~ (x))
: 7 () = f (x f
n
X f
Or 0 () = ~ (x)).f
(x f ~ j (x) = f
~ (x f
~ (x)).f
~ (x)
xj
j=1
2
~ (x)T .f
en particulier : 0 (0) = f ~ (x) = ~ (x)
f <0

= strictement decroissante au voisinage de = 0

tant que 0 () > 0, on continue a` se deplacer

en :
et on sarrete
xe = x ~ (x), ou`
ef e est la plus petite valeur de solution de
0 () = 0 (si elle existe)

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 10/14

Methode du gradient (1/2)

Methode du gradient Cauchy (1847), Curry (1944)
partir dun point initial x 0
on rep ` le pas x xe prec
ete edent
: x k x k+1 = (x
g k)

`
criteres possibles :
darrets
 
n
 f k 
1 maxi=1  (x ) < 
xi

~ k
f (x ) < 
2

 k+1 
3 f (x ) f (x k ) < 

`
Les 3 criteres indiquent que f est proche detre
darret
stationnaire

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 11/14

Methode du gradient (2/2)

x1
X2 ~ (x 1 )
f

~ (x 1 )
f

xb

f (x) = constante

X1

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 12/14

Methode du gradient (2/2)

x1
X2 ~ (x 1 )
f

~ (x 1 )
f

xb
x2

f (x) = constante

X1

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 12/14

Methode du gradient (2/2)

x1
X2 ~ (x 1 )
f

~ (x 1 )
f

xb
x2
~ (x 2 )
f

f (x) = constante

X1

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 12/14

Methode du gradient (2/2)

x1
X2 ~ (x 1 )
f

~ (x 1 )
f

xb
~ (x 3 )
f x2
~ 2
x 3 f (x )

f (x) = constante

X1

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 12/14

Point faible de la methode du gradient (1/2)

0 () ~ (xe)T .f
e = f ~ (x) = 0

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 13/14

Point faible de la methode du gradient (1/2)

0 () ~ (xe)T .f
e = f ~ (x) = 0

= les gradients en x et xe sont orthogonaux

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 13/14

Point faible de la methode du gradient (1/2)

0 () ~ (xe)T .f
e = f ~ (x) = 0

= les gradients en x et xe sont orthogonaux

= a` chaque pas on prend une direction orthogonale a` la

edente
direction prec

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 13/14

Point faible de la methode du gradient (1/2)

0 () ~ (xe)T .f
e = f ~ (x) = 0

= les gradients en x et xe sont orthogonaux

= a` chaque pas on prend une direction orthogonale a` la

edente
direction prec

cheminement de la methode du gradient : en zigzag

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 13/14

Point faible de la methode du gradient (2/2)

= pour eviter erer
les zigzags et accel la convergence,
on peut avoir recours a` lun des proced es
suivants :

diminuer le pas : ne pas aller jusquen xe.

Polyak (66) : effectuer
des pas pred
P etermines en imposant
une suite k telle que k 0 et k k = +

= (x k ) tend vers xb

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 14/14

Point faible de la methode du gradient (2/2)

= pour eviter erer
les zigzags et accel la convergence,
on peut avoir recours a` lun des proced es
suivants :

diminuer le pas : ne pas aller jusquen xe.

Polyak (66) : effectuer
des pas pred
P etermines en imposant
une suite k telle que k 0 et k k = +

= (x k ) tend vers xb

utiliser dautres directions que lanti-gradient :

Forsythe (1968), Luenberger (1973) :

toutes les m iterations, au lieu de partir dans la direction de
lanti-gradient en x k , couper en partant dans la direction
= x k x km

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 14/14

Point faible de la methode du gradient (2/2)

= pour eviter erer
les zigzags et accel la convergence,
on peut avoir recours a` lun des proced es
suivants :

diminuer le pas : ne pas aller jusquen xe.

Polyak (66) : effectuer
des pas pred
P etermines en imposant
une suite k telle que k 0 et k k = +

= (x k ) tend vers xb

utiliser dautres directions que lanti-gradient :

Forsythe (1968), Luenberger (1973) :

toutes les m iterations, au lieu de partir dans la direction de
lanti-gradient en x k , couper en partant dans la direction
= x k x km

utiliser des directions conjuguees

Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 14/14