POLYNOMES POLAIRES ET GRADIENT CONJUGUE
OPTIMISATION DANS <. RECHERCHES LINEAIRES EXACTES
Notre problème consiste à minimiser une fonction f : R n ! R. On s’intéresse à la classe des méthodes à directions de descente, ou on ne peut pas garantir la convergence vers un minimum, m’me local. C’est pourquoi, ces algorithmes sont couplés à une recherche linéaire. Ainsi, on retrouve dans l’algorithme la propriété de convergence globale vers un minimum local. On suppose connaÓtre la direction de descente dk au point xk:
Recherche linéaire
Faire de la recherche linéaire veut dire déterminer un pas k le long d’une direction de descente dk; autrement dit résoudre le problème d’optimisation unidimensionnel : min2R f(xk +dk) (2.1) Notre intér’t pour la recherche linéaire ne vient pas seulement du fait que dans les applications on rencontre, naturellement, des problèmes unidimensionnels, mais plutÙt du fait que la recherche linéaire est un composant fondamental de toutes les méthodes traditionnelles d’optimisation multidimensionnelle. D’habitude, nous avons le schéma suivant d’une méthode de minimisation sans contraintes multidimensionnelle : En regardant le comportement local de l’objectif f sur l’itération courante xk, la méthode choisit la ìdirection du mouvementîdk (qui, normalement, est une direction de 13 descente de l’objectif : r T f(x):d < 0) et exécute un pas dans cette direction : xk 7.
Deux méthodes díoptimisation unidimensionnelle sans dérivées
La méthode de dichotomie. La méthode de dichotomie est simple. Elle se base sur le théorème1. Le choix des points k et k se fait de la faÁon suivante : Choix des points k et k On Öxe » > 0 au démarrage, assez petit. A líitération k, k est le milieu de [ak; bk] moins « : k est le milieu de [ak; bk] plus « : En díautres termes k = ak + bk 2 .
1 OPTIMISATION SANS CONTRAINTES |
