Recherche linéaire (optimisation)

Voici un exemple d'algorithme qui utilise la recherche linéaire à l'étape 3:

i) Mettre le compteur d'itération à 0, ${\displaystyle k=0}$, et fixer une valeur initiale, ${\displaystyle \mathbf {x} _{0}}$ comme minimum.

ii) Calculer une direction de descente ${\displaystyle \mathbf {p} _{k}}$.

iii) Choisir ${\displaystyle \alpha _{k}}$, comme la valeur ${\displaystyle \alpha \in \mathbb {R} }$, telle que ${\displaystyle \phi (\alpha )=f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})}$ atteigne son minimum.

iv) Mettre à jour ${\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}}$, ${\displaystyle k=k+1}$.

Si ${\displaystyle \|\nabla f(\mathbf {x} _{k})\|\leq }$tolerance, STOP.

Sinon, retourner au ii).

Dans l'étape iii) on peut minimiser exactement ${\displaystyle \phi }$, en résolvant ${\displaystyle \phi '(\alpha _{k})=0}$, ou bien minimiser faiblement, en n'imposant qu'une décroissance suffisante de ${\displaystyle \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.

• Algorithme à directions de descente

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

• Portail de l'analyse