Optimisation progressive

L'optimisation graduéeest uned'optimisation globalequi tente de résoudre un problème d'optimisation difficile en résolvant initialement un problème fortement simplifié, puis en transformant progressivement ce problème (tout en l'optimisant) jusqu'à ce qu'il soit équivalent au problème d'optimisation difficile.

L'optimisation graduée est une amélioration de l'algorithme de recherche locale qui permet d'éviter de se focaliser sur des optima locaux. Elle décompose un problème d'optimisation complexe en une séquence de sous-problèmes, le premier étant convexe (ou quasi-convexe). La solution de chaque sous-problème fournit un bon point de départ pour le suivant, et le dernier sous-problème est le problème d'optimisation complexe que l'algorithme cherche à résoudre. L'optimisation graduée donne souvent de meilleurs résultats que l'algorithme de recherche locale. De plus, sous certaines conditions, elle permet de trouver une solution optimale au dernier sous-problème de la séquence. Ces conditions sont :

• Le premier problème d'optimisation de la séquence peut être résolu étant donné le point de départ initial.
• La région localement convexe autour de l'optimum global de chaque problème de la séquence inclut le point qui correspond à l'optimum global du problème précédent dans la séquence.

On peut démontrer par récurrence que si ces conditions sont réunies, un algorithme de recherche locale convergera vers l'optimum global du problème complexe. Malheureusement, il est souvent difficile de trouver une suite de problèmes d'optimisation qui remplisse ces conditions. L'optimisation progressive donne souvent de bons résultats, même lorsqu'il est impossible de prouver que la suite de problèmes satisfait strictement à toutes ces conditions.

L'optimisation graduée est couramment utilisée en traitement d'images pour localiser des objets au sein d'une image plus grande. Ce problème peut être rendu plus convexe par floutage des images. Ainsi, la recherche d'objets s'effectue en commençant par l'image la plus floue, puis en poursuivant la recherche à partir de ce point dans une image moins floue, et ainsi de suite jusqu'à ce que l'objet soit localisé avec précision dans l'image originale nette. Le choix approprié de l'opérateur de floutage dépend de la transformation géométrique reliant l'objet d'une image à l'autre.

L'optimisation graduée peut être utilisée dans l'apprentissage de variétés. L'algorithme de sculpture de variétés, par exemple, utilise l'optimisation graduée pour rechercher un plongement de variété permettant une réduction non linéaire de la dimensionnalité . Il réduit progressivement la variance des dimensions supplémentaires au sein d'un ensemble de données tout en optimisant les dimensions restantes. Il a également été utilisé pour calculer les conditions de fractionnement des tumeurs , pour le suivi d'objets en vision par ordinateur et à d'autres fins.

Une analyse approfondie de la méthode et de ses applications peut être trouvée dans

Le recuit simulé est étroitement lié à l'optimisation progressive. Au lieu de lisser la fonction optimisée, il perturbe aléatoirement la solution courante par une variation décroissante, ce qui peut produire un effet similaire. Cependant, comme le recuit simulé repose sur un échantillonnage aléatoire pour identifier les améliorations, sa complexité de calcul est exponentielle par rapport au nombre de dimensions optimisées. À l'inverse, l'optimisation progressive lisse la fonction optimisée, permettant ainsi l'utilisation de techniques d'optimisation locale efficaces dans un espace de grande dimension (telles que les techniques basées sur le gradient, l'algorithme de la plus grande pente, etc.).

Plus d articles de Worldlex Wiki

Revenez a l index pour explorer davantage de pages sur l histoire, la science, la culture, la geographie et la societe en francais.