micro2 optimisation 2014+corrige .pdf


À propos / Télécharger Aperçu
Nom original: micro2 optimisation 2014+corrige.pdf

Ce document au format PDF 1.3 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 1164 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)




Sur le même sujet..





Ce fichier a été mis en ligne par un utilisateur du site. Identifiant unique du document: 00413913.
⚠️  Signaler un contenu illicite
Pour plus d'informations sur notre politique de lutte contre la diffusion illicite de contenus protégés par droit d'auteur, consultez notre page dédiée.