POLYNOMES POLAIRES ET GRADIENT CONJUGUE

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 .

Table des matiéres

1 OPTIMISATION SANS CONTRAINTES
1.1 Notions de base
1.2 Schémas général des algorithmes d’optimisation sans contraintes
1.2.1 Exemples de choix de directions de descente
1.2.2 Exemple de choix de pas k
1.3 Conditions d’optimalité des problémes d’optimisation sans contraintes
1.3.1 Condition nécessaire d’optimalité du premier ordre
1.3.2 Conditions nécessaires d’optimalité du second ordre
1.3.3 Conditions su¢ santes d’optimalité du second ordre
1.4 Les modes de convergence
2 OPTIMISATION DANS <. RECHERCHES LINEAIRES EXACTES
2.1 Recherche linéaire
2.2 Objectifs à atteindre
2.3 Choix optimal du pas k
2.4 Optimisation dans < . Recherches Linéaires Exactes
2.4.1 L’intervalle d’incertitude
2.4.2 Schémas général des recherches linéaires exactes utilisant les intervalles d’incertitude
2.4.3 La méthode progressive-retrogressive ou Forward-Backward Algorithm
2.4.4 Deux méthodes d’optimisation unidimensionnelle sans dérivées
2.5 Avantages et Inconvénients des recherches linéaires exactes
3 OPTIMISATION DANS <. RECHERCHES LINEAIRES INEXACTES
3.1 Introduction et rappels
3.1.1 Le schéma des recherches linéaires inexactes
3.2 La régle d’Armijo
3.3 La régle de Goldstein et Price
3.4 La régle de Wolfe
3.5 La régle de Wolfe fort
3.6 La régle de Wolfe relaxée
4 GRADIENT CONJUGUE. CAS QUADRATIQUE
4.1 Optimisation quadratique sans contraintes
4.1.1 Definition et théorémes fondamentaux
4.1.2 Calcul du pas obtenu par une recherche linéaire exacte
4.2 Méthode des directions conjuguées
4.2.1 Définitions et propriétés générales
4.2.2 L’Algorithme des directions conjuguées
4.3 Méthode du gradient conjugué. Cas quadratique
4.3.1 Introduction
4.3.2 Algorithme du gradient conjugué. Cas quadratique
4.3.3 Propriétés du gradient conjugué quadratique
4.3.4 Convergence de l’Algorithme du gradient conjugué quadratique
5 GRADIENT CONJUGUE NON QUADRATIQUE
5.1 Introduction et di§érentes formes du gradient conjugué
6 SYNTHESE DES RESULTATS DE CONVERGENCES DES METHODES DU GRADIENT CONJUGUE NON QUADRATIQUE
6.1 Hypothéses C1 et C2 et théoréme de Zoutendijk
6.2 RÙle joué par la direction de recherche initiale
6.2.1 Méthode de Dai-Yuan généralisée
6.3 Les méthodes o˘ gTk+1yk figure dans le numérateur de k
6.3.1 Méthode de Liu et Storey LS
6.4 Méthodes hybrides et familles paramétriques du gradient conjugué
7 LA NOUVELLE METHODE CGBBB
7.1 Intrducton
7.2 Algorithme de méthode CGBBB
7.3 Propriété de la descente
7.4 Convergence globale de l’Algorithme CGBBB
7.5 Résultats numériques et comparaisons
8 PROGRAMMES EN FORTRAN
8.1 Programme en fortran 77 d’Armijo
8.2 Programme en fortran 77 de Goldschtien
8.3 Programme en fortran 77 de Wolfe
8.4 Programme en fortran 90 de la méthode du gradient conjugé