Bibliographie & annexes
Présentation
En anglais
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’articleABSTRACT
Problems of differentiable optimization arise when one tries to determine the optimal value of a finite number of parameters, optimality referring to the minimality of a given criteria. This article describes the principal algorithms for the resolution of these problems by précising their motivation. these resolution problems arise in numerous sectors of engineering as well as in science and economy. They are sometimes posed in infinite dimension; in that case, one tries to determine an optimal function. The current numerical methods of optimization stem from ever multiplying advances that enrich another.
Auteur(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
L'inégalité
On note
Pour indiquer qu'une matrice carrée M est symétrique semi-définie positive (resp. définie positive), on note
L'ensemble des matrices symétriques d'ordre n est noté
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 :
L'expertise technique et scientifique de référence
DOI (Digital Object Identifier)
Cet article fait partie de l’offre
Mathématiques
(166 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Présentation
Optimisation sans contrainte
En anglais
1. Outils théoriques, concepts algorithmiques
1.1 Problème à résoudre
De manière assez formelle, un problème d'optimisation se pose lorsque l'on cherche un point d'un ensemble X en lequel une fonction f définie sur cet ensemble prend une valeur minimale. Nous l'écrirons de la manière suivante :
( 1 )
La fonction f est appelée critère ou fonction-coût du problème. L'ensemble X est appelé l'ensemble admissible du problème (surtout s'il fait partie d'un ensemble plus grand) et un point de X est dit admissible. Une solution de (PX ) est un point
tel que
pour tout x ∊ X. On parle aussi de minimum global, par opposition à un minimum local
qui ne vérifie
que pour des x ∊ X voisins de
(pour que cette notion de voisinage ait un sens, il faut que X soit un espace topologique). On dit que ces minima sont stricts si on a l'inégalité stricte f (
) < f (x ) pour des x ∊ X (éventuellement voisins de x *) et différents de
.
La formulation...
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Mathématiques
(166 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Outils théoriques, concepts algorithmiques
DANS NOS BASES DOCUMENTAIRES
-
Méthodes de Krylov pour la résolution des systèmes linéaires.
-
Méthodes numériques de base. Algèbre numérique.
BIBLIOGRAPHIE
-
(1) - BEN-TAL (A.), NEMIROVSKI (A.) - Lectures on Modern Convex Optimization – Analysis, Algorithms, and Engineering Applications. - MPS/SIAM Series on Optimization, 2, SIAM (2001).
-
(2) - BERTSEKAS (D.P.) - Nonlinear Programming (seconde édition). - Athena Scientific (1999).
-
(3) - BONNANS (J.F.), GILBERT (J.Ch.), LEMARÉCHAL (C.), SAGASTIZÁBAL (C.) - Numerical Optimization – Theoretical and Practical Aspects (seconde édition). - Universitext. Springer Verlag, Berlin (2006).
-
(4) - BONNANS (J.F.), SHAPIRO (A.) - Perturbation Analysis of Optimization Problems. - Springer Verlag, New York (2000).
-
(5) - CONN (A.R.), GOULD (N.), TOINT (P.L.) - Trust-Region Methods. - MPS/SIAM Series on Optimization, 1, SIAM and MPS, Philadelphia (2000).
-
(6) - DENNIS (J.E.), SCHNABEL (R.B.) - Numerical Methods for Unconstrained Optimization...
ANNEXES
###
(liste non exhaustive)
Codes de différentiation et d'optimisation
ADIC (C) http://www-new.mcs.anl.gov/adic/
ADIFOR (Fortran 77) http://www-unix.mcs.anl.gov/autodiff/ADIFOR/
ADOL-C (C++) http://www.math.tu-dresden.de/~adol-c/
AXIOM http://www.axiom-developer.org/index.html
DONLP2 (SQP) ftp://ftp.mathematik.tu-darmstadt.de/pub/department/ software/opti/DONLP2
FAIPA (PI)
FSQP (SQP admissible) http://www.aemdesign.com/
IPOPT (PI) https://projects.coin-or.org/Ipopt
KNITRO (PI) http://www.ziena.com/
LANCELOT (lagrangien augmenté) http://www.numerical.rl.ac.uk/lancelot/blurb.html
LBFGSB (
-BFGS) http://www.ece.northwestern.edu/~nocedal/lbfgsb.html
LBFGS (
-BFGS) http://www.ece.northwestern.edu/~nocedal/lbfgs.html
LOQO (PI) http://www.princeton.edu/~rvdb/loqo/LOQO.html
MACSYMA http://maxima.sourceforge.net/...
L'expertise technique et scientifique de référence
Cet article fait partie de l’offre
Mathématiques
(166 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
