Présentation
RÉSUMÉ
Les problèmes d’optimisation différenciable se posent lorsque l’on cherche à déterminer la valeur optimale d’un nombre fini de paramètres, l’optimalité signifiant la minimalité d’un critère donné. Cet article décrit les principaux algorithmes de résolution de ces problèmes, en précisant leur motivation. Ces problèmes de résolution se présentent dans de nombreux domaines de l’ingénieur, mais aussi en science et en économie. Ils se posent parfois en dimension infinie, on cherche alors à déterminer une fonction optimale. Les méthodes numériques actuelles de l’optimisation sont la résultante d‘avancées qui ne cessent de se multiplier et de s’enrichir mutuellement.
Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.
Lire l’articleAuteur(s)
-
Jean Charles GILBERT : Directeur de recherche à l'INRIA (Institut national de recherche en informatique et en automatique)
INTRODUCTION
Cette synthèse raisonnée décrit les principaux algorithmes de résolution des problèmes d'optimisation différentiable et en donne leur motivation. Ces problèmes se posent lorsque l'on cherche à déterminer la valeur optimale d'un nombre fini de paramètres. L'optimalité signifie ici la minimalité d'un critère donné. La différentiabilité supposée des fonctions qui définissent le problème écarte d'emblée de notre propos l'optimisation combinatoire (les paramètres à optimiser ne prennent que des valeurs entières ou discrètes, voir le dossier « Optimisation en nombres entiers » [AF 1 251]) et l'optimisation non lisse (les fonctions ont des irrégularités, voir le dossier « Optimisation et convexité » [AF 1 253]).
Les problèmes d'optimisation se présentent dans de nombreux domaines de l'ingénieur, ainsi qu'en science et en économie, souvent après avoir conduit à leur terme les étapes de simulation. Il arrive souvent que ces problèmes se posent en dimension infinie, c'est-à-dire que l'on cherche une fonction optimale plutôt qu'un nombre fini de paramètres optimaux. Il faut alors passer par une phase de discrétisation (en espace, en temps) pour retrouver le cadre qui est le nôtre et se ramener ainsi à un problème qui peut être résolu sur ordinateur. La transcription directe des problèmes de commande optimale suit une telle procédure de discrétisation. D'autres exemples sont décrits dans le dossier « Optimisation continue » [S 7 210].
Les méthodes numériques de l'optimisation ont principalement été développées après la seconde guerre mondiale, en parallèle avec l'amélioration des ordinateurs, et n'ont cessé depuis de s'enrichir. En optimisation non linéaire, on peut ainsi distinguer plusieurs vagues : méthodes de pénalisation, méthode du lagrangien augmenté (1958), méthodes de quasi-Newton (1959), méthodes newtoniennes ou SQP (1976), algorithmes de points intérieurs (1984). Une vague n'efface pas la précédente mais permet d'apporter de meilleures réponses à certaines classes de problèmes, comme ce fut le cas pour les méthodes de points intérieurs en optimisation semi-définie positive (SDP). Une attention particulière est portée aux algorithmes pouvant traiter les problèmes de grande taille, ceux qui se présentent dans les applications.
La norme euclidienne (ou ) est notée || · ||2 .
L'inégalité (resp. u < v ) entre deux vecteurs v et w signifie que (resp. vi < wi ) pour tout indice i.
On note et l'image et le noyau d'une matrice M.
Pour indiquer qu'une matrice carrée M est symétrique semi-définie positive (resp. définie positive), on note (resp. ).
L'ensemble des matrices symétriques d'ordre n est noté et .
Une fonction f est dite de classe C m,α si elle est m fois différentiable et si sa dérivée m-ième vérifie pour une constante C et pour tout x et y :
Cet article est réservé aux abonnés.
Il vous reste 94 % à découvrir.
Déjà abonné ? Se connecter
DOI (Digital Object Identifier)
Présentation
Optimisation avec contraintes d'égalité et d'inégalitéArticle inclus dans l'offre
"Mathématiques"
(170 articles)
Actualisée et enrichie d’articles validés par nos comités scientifiques.
Quiz, médias, tableaux, formules, vidéos, etc.
Opérationnels et didactiques, pour garantir l'acquisition des compétences transverses.
Un ensemble de services exclusifs en complément des ressources.
2. Optimisation sans contrainte
Dans ce paragraphe, nous nous intéressons à la minimisation d'une fonction
sur
tout entier (donc avec n variables non soumises à des contraintes), ce que nous écrivons :
La fonction est supposée régulière (c'est-à-dire, différentiable). Son gradient et son hessien en un itéré xk sont respectivement notés :
Ceux-ci sont supposés calculés pour le produit scalaire euclidien, si bien que leurs composantes sont respectivement les dérivées partielles premières et secondes de f en xk . Nous exposons les techniques de base de l'optimisation numérique, techniques qui sont aussi utilisées en optimisation avec contraintes.
2.1 Techniques de globalisation
Les deux techniques que nous décrivons ci-après sont utilisées pour forcer la convergence des itérés, même si le premier d'entre eux est éloigné d'une solution. La recherche linéaire (§ 2.1.1...
Cet article est réservé aux abonnés.
Il vous reste 93 % à découvrir.
Déjà abonné ? Se connecter
Optimisation sans contrainte
Article inclus dans l'offre
"Mathématiques"
(170 articles)
Actualisée et enrichie d’articles validés par nos comités scientifiques.
Quiz, médias, tableaux, formules, vidéos, etc.
Opérationnels et didactiques, pour garantir l'acquisition des compétences transverses.
Un ensemble de services exclusifs en complément des ressources.
