Recherche linéaire

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En optimisation mathématique, la recherche linéaire est l'une des deux approches classiques permettant de forcer la convergence des algorithmes de calcul d'un minimum x_* d'une fonction f:\R^n\to\R, lorsque le premier itéré est éloigné d'un tel minimum. L'autre méthode est celle des régions de confiance.

Algorithme[modifier | modifier le code]

i) Mettre le compteur d'itération à 0 k=0, et fixer une valeur initiale, \mathbf{x}_0 comme minimum.
ii) Calculer une direction de descente \mathbf{p}_k.
iii) Choisir \alpha_k afin de minimiser \phi(\alpha)=f(\mathbf{x}_k+\alpha\mathbf{p}_k) en fonction de la variable \alpha\in\mathbb R.
iv) Mettre à jour \mathbf{x}_{k+1}=\mathbf{x}_k+\alpha_k\mathbf{p}_k, k=k+1.
Si \|\nabla f(\mathbf{x}_k)\|\leqtolerance, STOP.
Sinon, retourner au ii).

Dans l'étape iii) on peut minimiser exactement \phi, en résolvant \phi'(\alpha_k)=0, ou bien minimiser faiblement, en n'imposant qu'une décroissance suffisante de \phi. Cette dernière approche peut être réalisée en utilisant les critères de Wolfe.

Comme les autres méthodes d'optimisation, la recherche linéaire peut être couplée avec le recuit simulé afin d'éviter les minimums locaux.

Annexes[modifier | modifier le code]

Article connexe[modifier | modifier le code]

Références[modifier | modifier le code]

  • N. I. M. Gould and S. Leyffer, An introduction to algorithms for nonlinear optimization. In J. F. Blowey, A. W. Craig, and T. Shardlow, Frontiers in Numerical Analysis, pages 109-197. Springer Verlag, Berlin, 2003.