Recherche linéaire

Recherche linéaire

En optimisation non contrainte, la recherche linéaire est une des deux approches itératives classiques permettant de trouver les extremums \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)\|\leqtolerance, 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 minimums 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.

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Recherche linéaire de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • 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 d une fonction . L autre méthode est celle des régions de confiance. Algorithme i) Mettre… …   Wikipédia en Français

  • Recherche des plus proches voisins — Le problème de la recherche des plus proches voisins (ou des k plus proches voisins) est très courant en algorithmique et de nombreux auteurs ont proposé des algorithmes efficaces pour le résoudre rapidement. Soient : un espace E de… …   Wikipédia en Français

  • Recherche operationnelle — Recherche opérationnelle La recherche opérationnelle (aussi appelée aide à la décision) peut être définie comme l ensemble des méthodes et techniques rationnelles d analyse et de synthèse des phénomènes d organisation utilisables pour élaborer de …   Wikipédia en Français

  • Recherche-développement — Recherche et développement Pour les articles homonymes, voir Recherche (homonymie). La recherche et développement (notée R D) est une catégorie statistique, économique et comptable englobant l ensemble des activités entreprises « de façon… …   Wikipédia en Français

  • Recherche & Développement — Recherche et développement Pour les articles homonymes, voir Recherche (homonymie). La recherche et développement (notée R D) est une catégorie statistique, économique et comptable englobant l ensemble des activités entreprises « de façon… …   Wikipédia en Français

  • Recherche et Développement — Pour les articles homonymes, voir Recherche (homonymie). La recherche et développement (notée R D) est une catégorie statistique, économique et comptable englobant l ensemble des activités entreprises « de façon systématique en vue… …   Wikipédia en Français

  • Recherche et developpement — Recherche et développement Pour les articles homonymes, voir Recherche (homonymie). La recherche et développement (notée R D) est une catégorie statistique, économique et comptable englobant l ensemble des activités entreprises « de façon… …   Wikipédia en Français

  • linéaire — [ lineɛr ] adj. et n. m. • XVe; lat. linearis, de linea → ligne 1 ♦ Qui a rapport aux lignes, se traduit par des lignes. Mesure linéaire : mesure de longueur. Dessin linéaire, où le trait seul est utilisé (cf. Au trait). Perspective linéaire… …   Encyclopédie Universelle

  • RECHERCHE SCIENTIFIQUE — La recherche scientifique correspond à un besoin de l’homme, celui de connaître et de comprendre le monde et la société dans lesquels il vit. Ce besoin n’a pas a priori de justification économique ou politique; il constitue, en quelque sorte, la… …   Encyclopédie Universelle

  • Recherche documentaire — Recherche d information Abrégée en RI ou IR (Information Retrieval en anglais), la recherche d information est la science qui consiste à rechercher l information dans des documents les documents eux mêmes ou les métadonnées qui décrivent les… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”