Algorithme à régions de confiance

Algorithme à régions de confiance

Un algorithme à régions de confiance est un algorithme d'optimisation différentiable (l'optimisation dont il est question ici est une branche des mathématiques), destiné à minimiser une fonction réelle définie sur un espace euclidien (par exemple, \mathbb{R}^n, l'espace des n-uplets de nombres réels, muni d'un produit scalaire) ou, plus généralement, sur un espace hilbertien. L'algorithme est itératif et procède donc par améliorations successives. Au point courant, l'algorithme effectue un déplacement qui est obtenu en minimisant un modèle simple de la fonction (par exemple quadratique) sur une région de confiance (généralement une boule dont le rayon est appelé le rayon de confiance du modèle). Le rayon de confiance est ajusté de manière à faire décroître suffisamment la fonction à chaque itération.

Cette approche algorithmique peut être vue comme une technique de globalisation, c'est-à-dire une méthode permettant d'obtenir la convergence des itérés (sous certaines conditions) quel que soit l'itéré initial choisi. Elle s'apparente ainsi aux algorithmes à directions de descente en améliorant légèrement (mais parfois de manière décisive) leurs résultats de convergence. La conception des algorithmes à régions de confiance est cependant plus compliquée que celle des algorithmes à directions de descente, ce qui limite parfois leur application (par exemple aux grands problèmes de moindres-carrés sans possibilité de calcul de la jacobienne des résidus).

Le principe des régions de confiance est très général et s'étend (parfois avec peine) à d'autres problèmes classiques de l'optimisation : optimisation non lisse, optimisation avec contraintes, etc.

Sommaire

Principes de l'algorithme

Soient \mathbb{E} est un espace hilbertien (produit scalaire noté \langle\cdot,\cdot\rangle et norme associée notée \|\cdot\|) et x\in\mathbb{E}\mapsto f(x)\in\mathbb{R} une fonction différentiable. On note f'(x) et \nabla f(x) la dérivée et le gradient de f en x, si bien que

\forall\,d\in\mathbb{E}:\qquad f'(x)\cdot d=\langle\nabla f(x),d\rangle.

Comparaison avec les algorithmes avec recherche linéaire

Comparaison de la recherche linéaire et des régions de confiance
Recherche linéaire Région de confiance
On se donne une direction de descente dk de f en xk On se donne un modèle ψk de f en xk
On adapte le pas αk > 0 le long de dk pour faire décroître f On adapte le rayon de confiance Δk > 0 pour faire décroître f
Le déplacement sk = αkdk est aligné sur dk (recherche linéaire) Le déplacement sk change d'orientation avec Δk (recherche curviligne)
Facile à mettre en œuvre Difficile à mettre en œuvre
Résultats de convergence faibles Résultats de convergence renforcés

Annexes

Articles connexes

Lien externe

Ouvrage de référence

  • (en) A. R. Conn, N. I. M. Gould, Ph. L. Toint (2000). Trust-Region Methods. MPS-SIAM Series on Optimization 1. SIAM and MPS, Philadelphia.

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme à régions de confiance de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Algorithme du gradient — L algorithme du gradient désigne un algorithme d optimisation différentiable. Il est par conséquent destiné à minimiser une fonction réelle différentiable définie sur un espace euclidien (par exemple, , l espace des n uplets de nombres réels,… …   Wikipédia en Français

  • Algorithme à directions de descente — Un algorithme à directions de descente est un algorithme d optimisation différentiable (l optimisation dont il est question ici est une branche des mathématiques), destiné à minimiser une fonction réelle différentiable définie sur un espace… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Méthode de Newton — Isaac Newton En analyse numérique, la méthode de Newton ou méthode de Newton Raphson[1] est, dans son application la plus simple, un algorithme efficace pour trouver numériquement une approximation précise d …   Wikipédia en Français

  • Optimisation non linéaire — En optimisation, vue comme branche des mathématiques, l optimisation non linéaire (en anglais : nonlinear programming – NLP) s occupe principalement des problèmes d optimisation dont les données, i.e., les fonctions et ensembles définissant… …   Wikipédia en Français

  • 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 linéaire — En optimisation non contrainte, la recherche linéaire est une des deux approches itératives classiques permettant de trouver les extremums d une fonction . L autre méthode est celle des régions de confiance. Algorithme i) Mettre le compteur d… …   Wikipédia en Français

  • Global Positioning System — « GPS » redirige ici. Pour les autres significations, voir GPS (homonymie). Un satellite NAVSTAR (Navigation Satellite Timing And Ranging) appartenant à la constellation du GPS …   Wikipédia en Français

  • Variable régionalisée — La VR comme phénomène physique : topographie de la ville de Binche …   Wikipédia en Français

  • Structure secondaire — ██████████3 % Relecture …   Wikipédia en Français

Share the article and excerpts

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