Recherche lineaire

Recherche linéaire

En optimisation non contrainte, la recherche linéaire est une des deux approches itératives classiques permettant de trouver les extrema $\mathbf{x}^*$ d'une fonction $f:\mathbb R^n\to\mathbb R$. L'autre méthode est celle des régions de confiance.

Algorithme

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 α_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)\|\leq$tolerance, STOP.

Sinon, retourner au ii).

Dans l'étape iii) on peut minimiser exactement φ, en résolvant φ'(α_k) = 0, ou bien minimiser faiblement, en n'imposant qu'une décroissance suffisante de φ. 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 minima locaux.

Références

• 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.

Ce document provient de « Recherche lin%C3%A9aire ».