Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
Télécharger au format pdf ou txt
Vous êtes sur la page 1/ 8
Optimisation
Maher Moakher Ecole Polytechnique de Tunisie
Janvier, 2023 Méthodes Numériques Plan 1 Algorithmes de descente : Principes généraux 2 Exemples de méthodes à directions de descente - Algorithme du gradient - Algorithme du gradient conjugué - Algorithme de Newton - Algorithme de quasi-Newton 3 La recherche linéaire - Règle de Cauchy - Règle d’Armijo - Règle de Wolfe 4 Convergence des méthodes à directions de descente 5 Algorithme de Newton pour des systèmes non linéaires Problèmes sans contraintes On s’intéresse au problème d’optimisation sans contrainte :
min f (x), (P)
x∈Rn
où f : Rn → R est supposée régulière. Soit ∥ · ∥ la norme associée à un
produit scalaire ⟨·, ·⟩ sur Rn . Définition On dit que d est une direction de descente de f en x ∈ Rn si
∇f (x) · d < 0.
Si d est une direction de descente, alors
f (x + αd) < f (x),
pour tout α > 0 suffisamment petit.
Méthodes de descente
Les méthodes à directions de descente permettent de minimiser une
fonction en construisant une suite de vecteurs (xk )k≥1 approchant une solution x∗ de (P) par la récurrence :
xk+1 = xk + αk dk , k ≥ 1,
où αk > 0 est appelé le pas et dk la direction de descente de f en xk .
Pour passer de l’itéré xk à l’itéré xk+1 , l’algorithme effectue deux étapes :
Calcul d’une direction de descente dk ∈ Rn ; Calcul du pas de déplacement αk > 0 suivant cette direction (c’est la recherche linéaire). Algorithme du gradient On suppose que f est différentiable et on note gk = ∇f (xk ).
La direction du (moins le) gradient (ou de la plus profonde descente) est
une direction de descente si xk n’est pas un point stationnaire :
∇f (xk ) · (−gk ) = ⟨gk , −gk ⟩ = −∥gk ∥2 < 0.
Algorithme (du gradient)
1 Initialisation : x0 ∈ Rn donné. 2 Pour k ≥ 0 : dk = −gk , αk = arg minα∈R f (xk + αdk ), xk+1 = xk + αk dk . Si ∥gk ∥ ≤ ϵ, arrêt de l’algorithme. Algorithme du gradient conjugué Algorithme (du gradient conjugué) 1 Si ∥gk ∥ ≤ ϵ, arrêt de l’algorithme 2 Sinon, ( −g1 si k = 1, dk = −gk + βk dk−1 si k ≥ 2,
Le scalaire βk ∈ R peut prendre différentes valeurs.
La direction du gradient conjugué dk est une direction de descente en un un point non stationnaire : ∇f (xk ) · dk = ⟨gk , dk ⟩ = −∥gk ∥2 < 0, lorsque αk−1 est choisi de manière à minimiser f le long de la direction dk−1 , donc ⟨gk , dk−1 ⟩ = ⟨∇f (xk−1 + αk−1 dk−1 ), dk−1 ⟩ = 0. Algorithme de Newton
On suppose que f est deux fois différentiable et que la matrice hessienne
∇2 f (xk ), k ≥ 1, est inversible. Algorithme (de Newton) 1 Si ∥gk ∥ ≤ ϵ, arrêt de l’algorithme 2 Sinon, dk = −[∇2 f (xk )]−1 gk
Au voisinage d’un minimum local strict x∗ , si la condition suffisante du
second ordre ∇2 f (x) > 0 est vérifiée, alors :
∇f (xk ) · dk = −⟨gk , [∇2 f (xk )]−1 gk ⟩
= −([∇2 f (xk )]−1 gk )T ∇2 f (xk ) · ([∇2 f (xk )]−1 gk ) < 0. Algorithme de quasi-Newton Algorithme (de quasi-Newton) 1 Si ∥gk ∥ ≤ ϵ, arrêt de l’algorithme 2 Sinon, dk = −Mk−1 gk où Mk est une matrice d’ordre n symétrique générée par une formule de récurrence.
En général, Mk est définie positive. Dans ce cas, dk est une direction de
descente puisque, si on pose vk = Mk−1 gk ̸= 0, on a : ∇f (xk ) · dk = −⟨gk , Mk−1 gk ⟩ = −⟨Mk vk , vk ⟩ < 0. Formule BFGS (Broyden-Fletcher-Goldfarb-Shanno) yk yTk Mk sk sT Mk M0 = I, Mk+1 = Mk + T − T k sk yk sk Mk sk avec sk = xk+1 − xk et yk = ∇f (xk+1 ) − ∇f (xk ).
