Fonctions Non Linéaires
Fonctions Non Linéaires
Fonctions Non Linéaires
Christophe Gonzales
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)
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)
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)
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 (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
Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 7/14
Minima et points stationnaires
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
Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 10/14
Pas de la methode du gradient
Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 10/14
Pas de la methode du gradient
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
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
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
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 :
= (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 :
= (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 :
= (x k ) tend vers xb
utiliser des directions conjuguees
Cours 10 : Optimisation non lineaire multidimensionnelle sans contraintes 14/14