Optimisation, méthodes de gradient et méthode des moindres carrés

´paration a
` l’Agre
´gation de Mathe
´matiques
Pre
TP : Optimisation, m´
ethodes de gradient et m´
ethode des moindres carr´
es
´thode du gradient a
` pas constant
1. Me
1.1. Programmer la m´ethode de gradient `a pas constant. L’appliquer `a la fonction J(x) = x2 + sin(x)
d´efinie sur R.
1.2. L’appliquer ´egalement aux fonctions J(x, y) = (x − 1)2 + 10(y − 1)2 et J(x, y) = (x − 1)2 +
10(x2 − y)2 (appel´ee ”Banane de Rosenbrock”) d´efinies sur R2 .
1.3. L’appliquer enfin au probl`eme du r´eseau t´el´ephonique, c’est-`a-dire trouver le minimum de la
fonction J : R2 → R, d´efinie par
N
X
J(x) =
|x − Ai |,
i=1
2
o`
u Ai , 1 ≤ i ≤ N sont des points donn´es de R . Prendre, par exemple, N = 4.
`me des moindres carre
´s
2. Proble
2.1. Soient n points (xi , yi ), 1 ≤ i ≤ n. Faire un programme qui trouve la droite y = ax+b minimisant
n
X
|yi − (axi + b)|2 , en utilisant la d´ecomposition QR de Scilab. Prendre un exemple et tracer sur un
i=1
graphique les points et la droite.
2.2. Mˆeme chose avec une fonction quadratique.
2.3. Programmer la d´ecomposition QR d’une matrice A ∈ GLn (R) `a l’aide du proc´ed´e de GramSchmidt.
2.4. Comment faire si on ajoute au probl`eme de la question 2.1. une contrainte de type y0 = ax0 + b ?
´mentaires
3. Exercices supple
3.1. Appliquer la m´ethode de gradient associ´ee `a la condition d’Armijo (cf TD optimisation) pour
la r´esolution du probl`eme suivant (cf texte Public 2009).
Soit V : R → R d´efinie par
1
2
V (r) = 12 − 6 ,
r
r
on cherche `
a minimiser la fonction
X
J(X1 , · · · , XN ) =
V (||Xi − Xj ||)
i<j
d´efinie sur R3N , qui donne la r´epartition de N atomes formant une mol´ecule d’´energie minimale.
On appliquera la m´ethode de gradient avec N = 3 et N = 4 en partant d’une donn´ee initiale
al´eatoire dans [0, 1]3N . Pour trouver le pas de descente `a chaque ´etape, on fera d´ecroˆıtre ρ comme une
suite g´eom´etrique jusque’`
a ce que la condition d’Armijo
J(uk+1 ) < J(uk ) − βρk ||∇J(uk )||22 ,
(0)
avec β = 10−4 soit satisfaite. On initiera la suite g´eom´etrique `a ρk =
1
et on prendra une
||∇J(uk )||2
raison ´egale `
a 0.3.
3.2. Trouver analytiquement le minimum cherch´e dans les cas N = 3 et N = 4.
4. Optimisation sous contraintes
Voir le texte Public 2012 sur l’optimisation et la chimie. Penser `a utiliser, si cela si prˆete, la m´ethode
de Newton pour r´esoudre un syst`eme non lin´eraire. Par exemple, pour minimiser la fonction J : Rn → R
dans le cas de contraintes d’´egalit´e
G(x) = (g1 (x), · · · , gp (x)) = 0,
1
2
on r´esout le syst`eme form´e par les ´equations v´erifi´ees par les multiplicateurs de Lagrange, coupl´ees aux
contraintes, c’est-`
a-dire le syst`eme :

p
X


∗
∇J(x ) +
λi ∇gi (x∗ ) = 0
i=1


G(x∗ ) = 0
´fe
´rences
5. Re
Ciarlet, Introduction `
a l’analyse num´erique matricielle et `
a l’optimisation, Dunod.
Lascaux-Th´eodor, Analyse num´erique matricielle appliqu´ee `
a l’art de l’ing´enieur. Tome 1., Dunod.

Download Report