Présentation
RÉSUMÉ
L’optimisation peut se voir appliquer deux méthodes bien différentes, le continu et le discret. L'optimisation continue et non différentiable se situe entre les deux : les méthodes appartiennent au monde continu mais cependant 90 % des problèmes relèvent de l'optimisation discrète, il en est ainsi de la découpe industrielle, des tournées de véhicules, et les problèmes de grande taille. Après avoir introduit la théorie de base et le problème dual, cet article expose les algorithmes d’optimisation convexe avec notamment l’utilisation des méthodes de sous-gradients puis de plans sécants. Pour terminer, une petite digression est faite avec des cas non convexes.
Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.
Lire l’articleAuteur(s)
-
Claude LEMARÉCHAL : Directeur de recherches à l'INRIA (Institut national de recherche en Informatique et en Automatique)
INTRODUCTION
L'optimisation comporte en gros deux mondes, dont les problèmes se ressemblent vus de loin, mais bien différents quant aux méthodes : le continu et le discret. Le présent dossier traite surtout de l'optimisation non différentiable, qui est un peu à cheval entre les deux mondes : les méthodes appartiennent à 100 % au monde continu mais 90 % des problèmes touchent de près ou de loin à l'optimisation discrète.
Parmi ces derniers, citons par exemple : la découpe industrielle, les tournées de véhicules ou d'équipages, le routage de multiflots en télécommunications, etc. Certaines techniques parmi les plus efficaces pour attaquer ces problèmes (génération de colonnes, Branch and Price) font appel à l'optimisation dont il est question ici : continue et non différentiable.
Les problèmes de grande taille appartiennent à la même famille : par leur nombre de variables ou de contraintes, ou encore parce qu'ils comportent plusieurs éléments hétérogènes, ces problèmes nécessitent de faire appel à une technologie spéciale : la décomposition, laquelle conduit généralement à l'optimisation non différentiable. En productique par exemple, on peut disposer d'un grand nombre de moyens de production de différents types, participant tous à la même production : c'est le cas de l'énergie électrique, produite à la fois par des centrales nucléaires, thermiques classiques, et des turbines hydro-électriques ; ces moyens de production sont bien différents les uns des autres.
Les grands types de problèmes sus-mentionnés proviennent des sciences « sociales » ; on en trouve d'autres de nature analogue, provenant de l'automatique (stabilisation), de la statistique (calibrage de matrices de covariance), de la mécanique (problèmes d'impacts), de l'électronique (semi-conducteurs) – liste non exhaustive.
Le texte de ce dossier comporte de nombreuses allusions et références aux mondes de l'optimisation continue et discrète, déjà mentionnés. Le lecteur se reportera utilement aux articles :
Cet article est réservé aux abonnés.
Il vous reste 93 % à découvrir.
Déjà abonné ? Se connecter
DOI (Digital Object Identifier)
Présentation
Introduction, motivationArticle 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.
Cet article est réservé aux abonnés.
Il vous reste 94 % à découvrir.
Déjà abonné ? Se connecter
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.
BIBLIOGRAPHIE
-
(1) - MINOUX (M.) - Optimisation en nombres entiers. - [AF 1 251] Mathématiques pour l'ingénieur, avr. 2008.
-
(2) - LEMARÉCHAL (C.) - Optimisation continue. - [S 7 210] Informatique industrielle, mars 2002.
-
(3) - CESSENAT (M.) - Vocabulaire des mathématiques. - [A 1 205] Mathématiques pour l'ingénieur, fév. 1992.
-
(4) - GILBERT (J.C.) - Optimisation différentiable. - [AF 1 252] Mathématiques pour l'ingénieur, avr. 2008.
Références bibliographiques
BARAHONA (F.), ANBIL (R.) - The volume algorithm : Producing primal solutions with a subgradient method. - Mathematical Programming, 87(3), p. 385-399 (2000).
BIHAIN (A.) - Optimization of upper semidifferentiable functions. - Journal of Optimization Theory and Applications, 44, p. 545-568 (1984).
BOYD (S.), VANDENBERGHE (L.) - Convex Optimization. - Cambridge University Press (2004).
CAMERINI (P.M.), FRATTA (L.), MAFFIOLI (F.) - On improving relaxation methods by modified gradient techniques. - Mathematical Programming Study, 3, p. 26-34 (1975).
CHENEY (E.), GOLDSTEIN (A.) - Newton's method for convex programming and Tchebycheff approximations. - Numerische Mathematik, 1, p. 253-268 (1959).
CLARKE (F.) - Generalized gradients and applications. - Transactions of the AMS, 205, p. 247-262 (1975).
CONEJO (A.J.), CASTILLO (E.), MÍGUEZ (R.), GARCÍA-BERTRAND (R.) - Decomposition Techniques in Mathematical Programming. Engineering and Science Applications. - Springer Verlag (2006).
DANSKIN (J.M.) - The theory of max-min with applications. - SIAM Journal on Applied Mathematics, 14(4), p. 641-655 (1966).
DESAULNIERS (G.), DESROSIERS (J.), SOLOMON (M.), eds - Column Generation, - Springer Verlag (2005).
GOFFIN (J.-L.), HAURIE (A.), VIAL (J.-Ph.) - Decomposition and nondifferentiable optimization with the projective algorithm. - Management Science, 38(2), p. 284-302 (1992).
GOFFIN (J.-L.), VIAL (J.-Ph.) - Convex nondifferentiable optimization : a survey focused on the analytic center cutting plane method. - Optimization Methods and Software, 17(5), p. 805-867 (2002).
HIRIART-URRUTY (J.-B.), LEMARÉCHAL (C.) - Convex Analysis and Minimization Algorithms. - Springer Verlag, Heidelberg, Deux volumes (1993).
HIRIART-URRUTY (J.-B.), LEMARÉCHAL (C.) - Fundamentals of Convex Analysis. - Springer Verlag, Heidelberg (2001).
KELLEY (J.E.) - The...
Cet article est réservé aux abonnés.
Il vous reste 95 % à découvrir.
Déjà abonné ? Se connecter
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.
![Écoutez notre podcast Cogitons Sciences : Intégrer l’IA dans votre entreprise, pour un usage utile et raisonné [L’IA s’invite dans nos métiers #2]](https://www.techniques-ingenieur.fr/actualite/wp-content/uploads/2024/01/CS-IA-ep2.png)
