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, ${\displaystyle \mathbb {R} ^{n}}$, l'espace des ${\displaystyle 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, mais à rester assez petit pour que le modèle simple reste acceptablement valable.

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.

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

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 ${\displaystyle d_{k}}$ de ${\displaystyle f}$ en ${\displaystyle x_{k}}$	On se donne un modèle ${\displaystyle \psi _{k}}$ de ${\displaystyle f}$ en ${\displaystyle x_{k}}$
On adapte le pas ${\displaystyle \alpha _{k}>0}$ le long de ${\displaystyle d_{k}}$ pour faire décroître ${\displaystyle f}$	On adapte le rayon de confiance ${\displaystyle \Delta _{k}>0}$ pour faire décroître ${\displaystyle f}$
Le déplacement ${\displaystyle s_{k}=\alpha _{k}d_{k}}$ est aligné sur ${\displaystyle d_{k}}$ (recherche linéaire)	Le déplacement ${\displaystyle s_{k}}$ change d'orientation avec ${\displaystyle \Delta _{k}}$ (recherche curviligne)
Facile à mettre en œuvre	Difficile à mettre en œuvre
Résultats de convergence faibles	Résultats de convergence renforcés

• Algorithme du gradient conjugué
• Algorithme à directions de descente

• J. Ch. Gilbert, Éléments d'Optimisation Différentiable — Théorie et Algorithmes, syllabus de cours à l'ENSTA ParisTech, Paris.

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

v · m Optimisation: théorie et algorithmes
Non linéaire	Méthode du nombre d'or Recherche linéaire Méthode de Nelder-Mead Critères de Wolfe Méthode de Broyden-Fletcher-Goldfarb-Shanno Algorithme à régions de confiance Pénalisation Algorithme du gradient Algorithme du gradient stochastique Méthode de Newton Algorithme de Gauss-Newton Algorithme de Levenberg-Marquardt Algorithme du lagrangien augmenté
Convexe	Optimisation complètement positive Optimisation copositive Optimisation SDP Méthode des plans sécants Algorithme de Frank-Wolfe Méthode de l'ellipsoïde Linéaire Optimisation conique Algorithme du simplexe Méthodes de points intérieurs Décomposition de Benders Génération de colonnes Quadratique Optimisation quadratique successive
Combinatoire	Algorithme d'approximation Programmation dynamique Algorithme glouton Optimisation linéaire en nombres entiers
Métaheuristique	Algorithme évolutionniste Algorithme génétique Essaims Forêts aléatoires Boosting
Liste

• Portail des mathématiques