micro2 optimisation 2014+corrige .pdf



Nom original: micro2 optimisation 2014+corrige.pdf

Ce document au format PDF 1.3 a été généré par / pdfTeX-1.0b-pdfcrypt, et a été envoyé sur fichier-pdf.fr le 01/04/2016 à 21:15, depuis l'adresse IP 105.104.x.x. La présente page de téléchargement du fichier a été vue 1144 fois.
Taille du document: 98 Ko (6 pages).
Confidentialité: fichier public
Auteur vérifié


Aperçu du document


CORRIGE MICRO2 MASTER OPTIMISATION
Exercice 1 (6points)
1.1 (3points)Montrez que (Wolfe forte) implique (Wolfe)
1.2 (3points) Montrez que (Wolfe relaxée) implique (Wolfe forte)
Corrigé Exercice 1 (6points)
1.1 (3points)
k véri…e les condition de Wolfe forte si les deux conditions suivantes sont
véri…eés :
'k (

k)

j'0k (

k )j

0
k 'k (0);

'k (0) +
'0k (0);

0<

0<

<

<1;

1
2

(Wolfeforte1)
(Wolfeforte2)

>

Si k véri…e (wolfeforte1) et (wolfeforte2), alors k véri…e (wolfe1) et
(wolfe2) .
(wolfeforte1) et (wolfe1) sont les mêmes propositions. Reste à monter
que
(wolf ef orte2) =) (wolf e2)
En e¤et. Supposons que

k

véri…e (Wolfeforte2). Alors on a

'0k (0)

'0k (

'0k (0)

k)

Par conséquent on a
'0k (
Ceci implique que

k

'0k (0)

k)

véri…e (Wolfe2)

1.2 (3points)
k véri…e la règle de Wolfe relaxée si
f (xk +
1r

T

où 0 <

f (xk )dk
<

1

k dk )

f (xk ) +

rf (xk +

< 1 et

2

kr

T
k dk ) dk

T

f (xk )dk
2r

T

f (xk )dk

(Wolfe-relax e1)
(Wolfe-relax e2)

> 0:

Les conditions de Wolfe relaxée impliquent les conditions de Wolfe fortes.
En e¤et (Wolfe relaxée1) et (Wolfeforte1) sont les mêmes. Reste à montre
1

que (Wolfe-relaxée2) implique (Wolfe-forte2). En e¤et prenons dans (Wolferelaxée2) le cas particulier: 1 = 2 = , on obtient
1r

T

f (xk )dk

T
rT f (xk + k dk )dk
2 r f (xk )dk
) rT f (xk )dk rT f (xk + k dk )dk
rT f (xk )dk
rT f (xk + k dk )dk
rT f (xk )dk
)

Exercice 2(6points)
a) 2points) Quels sont les hypothèses du théorème de Zoudentijk
b) (1point) Quel est le résultat du théorème de Zoudentijk
c)(3points) Quelle hypothèse faut il rajouter aux hypothèses du théorème
de Zoudentijk pour avoir
lim krf (xk )k = 0

k!1

Justi…ez votre réponse
Corrigé Exercice 2(6points)
a) 2points)
Hypothèses du théorème de Zoudentijk
f : Rn ! R, bornée inférieurement, di¤érentiable, dont le gradient est
continu au sens de Lipshitz, c’est à dire qu’il existe M > 0 tel que
krf (x)

rf (y)k

M kx

yk : 8x; y 2 Rn

Soit un algorithme itératif qui génère une suite fxk gk2N dans Rn dé…nie par
x0 2 Rn quelconque et les itérations
xk+1 = xk +

k dk ;

k = 0; 1; 2; :::

avec dk direction de descente (c’est à dire rf (xk )T dk < 0) et
conditions de (Wolfe1) et (Wolfe2).
b) (1point) Résultat du théoréme de Zoudentijk
1
X
k=0

cos2 ( k ) krf (xk )k2 < +1

c) (3points)
2

k

véri…ant les

L’hypothèse su¢ sante qu’on rajoute est la suivante:
9 > 0 : cos( k )


k

: 8k 2 N

(c-bis)

est l’angle dé…ni par
cos( k ) =

rf (xk )T dk
krf (xk )k kdk k

Avec cette hypothèse et les hypothèses du théorème de Zoudentijk, on a:
lim krf (xk )k = 0:

k!1

Justi…catif
D’après le théorème de Zoutendijk, on a
1
X
k=0

cos2 ( k ) krf (xk )k2 < +1

Ceci implique
lim cos2 ( k ) krf (xk )k2 = 0:

k!1

Notons
uk = cos2 ( k ); vk = krf (xk )k2 ; wk = uk vk

(d)

Alors (b) et (c-bis) impliquent
uk

2

> 0; vk > 0;

lim wk = 0

k!1

(e)

(d) implique
vk =

1
wk
uk

(f)

(e) et (f) donnent
0

1

vk

2

wk

lim wk = 0 et (g) impliquent

k!1

lim krf (xk )k = 0:

k!1

3

(g)

Exercice 3 (8points)
3.1(4points) Enoncez sans démonstrations tous les résultats de convergence de la méthode du gradient conjugué Fletcher Reeves FR
3.2 (4points) Expliquez pourquoi la méthode gradient conjugué Polak
Ribière Poliak: PRP est plus performante numériquement que la méthode
gradient conjugué Fletcher Reeves FR
Corrigé Exercice 3 (8points)
3.1(4points)
Théorème 1(1.5points)
Notons gk = rf (xk ): Supposons que L’hypothèse Condition C1 soit
satisfaite. Considérons une méthode du type (4.12), (4.13), avec k = Fk R =
kgk k2
et le pas k satisfaisant à la règle de (Wolfe-forte1) et (Wolfe-forte2)
kg
k2
k 1



2 0; 12 : Alors on a

dTk gk
kgk k2

1
1

2
1

1

; k = 1; :::

Corollaire 1 (1point)
Notons gk = rf (xk ): Sous les mêmes hypothèses et conditions du Théorème
4.4 précédent, on a pour tout k
1; dk est une direction de descente su¤isante i.e., il existe une constante C > 0 telle que
C kgk k2

gkT dk

Théorème 2 (1.5 points)
Notons gk = rf (xk ): Supposons que les hypothèses: Condition C1 et
Condition C2 soient satisfaites. Considérons une méthode du type (4.12),
2
(4.13) avec k = Fk R = kgkgk k k2 et le pas k satisfaisant à la règle de (Wolfek 1

forte1) et (Wolfe-forte2) où 2 0; 12 : Alors cette méthode est globalement
convergente, dans le sens suivant:
lim inf kgk k = 0

k!1

3.2(4points)
Explication pourquoi la méthode PRP est plus performante
numériquement que la méthode FR
4

Notons
a donc

l’angle que fait la direction dk avec la direction

k

rf (xk )T dk
krf (xk )k kdk k

cos( k ) =

rf (xk ): On
(4.2)

Pour la méthode Fletcher Reeves, AlBaali ([ 1 ]) a démontré la relation
suivante:
1
rf (xk )T dk
2
1
; k = 1; :::
(4.3)
2
1
1
krf (xk )k
Ceci implique

1 2 krf (xk )k
1
kdk k

1

cos( k )

1

krf (xk )k
kdk k

(4.4)

D’après la dernière inégalité, cos( k ) ' 0 si et seulement si krf (xk )k est
négligeable devant kdk k ; i.e.,
krf (xk )k

kdk k

Supposons maintenant qu’à une itération k, on ait cos( k ) ' 0: Puisque
la direction dk est presque orthogonale à rf (xk+1 ) il est probable que
xk+1 ' xk

(4.5)

rf (xk+1 ) ' rf (xk )

(4.6)

et par conséquent
Puisque

FR
k

=

krf (xk+1 )k
krf (xk )k2

dk+1 =
et puisque krf (xk )k

2

: Donc

rf (xk+1 ) +

FR
k

' 1: Par conséquent

FR
k dk

'

rf (xk+1 ) + dk

(4.7)

kdk k ; on aura
dk+1 ' dk

(4.8)

Ceci implique
kxk+2

xk+1 k ' kxk+1

xk k si le pas est petit

(4.9)

Ce phenomème peut se repeter indé…niment et l’algorithme progresse très
lentement ou ne progresse plus.
5

Pour éviter celà il faut redémarrer l’algorithme en posant = 0:
b) Pour la méthode Polak Ribière Poliak, Supposons qu’à une itération
k, on ait rf (xk+1 ) ' rf (xk ): Puisque
P RP
k

=

rf (xk+1 )(rf (xk+1 ) rf (xk ))
'0
krf (xk )k2

(4.10)

Par conséquent
dk+1 =

P RP
dk
k

rf (xk+1 ) +

'

rf (xk+1 )

(4.11)

et l’algorithme démarre automatiquent en utilisant la méthode du gradient.
En d’autres termes, lorsque ça va mal, la méthode PRP s’auto soigne.

6


Aperçu du document micro2 optimisation 2014+corrige.pdf - page 1/6

Aperçu du document micro2 optimisation 2014+corrige.pdf - page 2/6

Aperçu du document micro2 optimisation 2014+corrige.pdf - page 3/6

Aperçu du document micro2 optimisation 2014+corrige.pdf - page 4/6

Aperçu du document micro2 optimisation 2014+corrige.pdf - page 5/6

Aperçu du document micro2 optimisation 2014+corrige.pdf - page 6/6




Télécharger le fichier (PDF)


Télécharger
Formats alternatifs: ZIP




Documents similaires


micro2 optimisation 2014 corrige
controle1 analyse 2016 avec corrige
professeur benzine rachid cours optimisation sans contraintes tome1
theoreme d arzela ascoli
innovation project 4th june 2018   tazi bouardi hamza
gradient conjugue cas quadratique et non quadratique

Sur le même sujet..




🚀  Page générée en 0.097s