Présentation

Article

1 - INTRODUCTION, MOTIVATION

2 - THÉORIE DE BASE

  • 2.1 - Un minimum d'analyse convexe
  • 2.2 - Relation avec le primal

3 - ALGORITHMES D'OPTIMISATION CONVEXE

4 - PROBLÈMES VOISINS

Article de référence | Réf : AF1253 v1

Introduction, motivation
Optimisation et convexité

Auteur(s) : Claude LEMARÉCHAL

Date de publication : 10 avr. 2008

Pour explorer cet article
Télécharger l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !

Sommaire

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’article

ABSTRACT

Two very different methods can be applied to optimization: the continuous and discrete methods. The continuous and non differentiable are half way between the two: the methods belong to the continuous world and yet 90% of problems falls within discrete optimization; this is the case for industrial cutting, vehicle routing and large size problems. After having introduced the basic theory and the dual problem, this article presents the algorithms of convex optimization with notably the use of subgradient and secant plane method. It concludes by a small digression on non-convex cases.

Auteur(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 :

  • « Optimisation continue » [S 7 210] ;

  • « Optimisation en nombres entiers » [AF 1 251] ;

  • « Optimisation différentiable » [AF 1 252].

Cet article est réservé aux abonnés.
Il vous reste 93% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

DOI (Digital Object Identifier)

https://doi.org/10.51257/a-v1-af1253


Cet article fait partie de l’offre

Mathématiques

(202 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

ABONNEZ-VOUS

Lecture en cours
Présentation

1. Introduction, motivation

Le problème-type traité dans ce dossier est l'optimisation d'une fonction dont les dérivées présentent des singularités. Nous notons ce problème :

(la raison de notre notation q (u ) au lieu de l'habituel f (x ) viendra au § 1.2.1).

On peut aussi rencontrer des contraintes  ; la nature du problème ne change pas : minimiser q c'est satisfaire la contrainte , où q * est la valeur minimale. Pour ces problèmes, les outils de base ne proviennent pas du calcul différentiel mais de l'analyse convexe.

L'exemple le plus naïf avec n ≥ 1 est la fonction q (u ) ≥ | u | (qui est convexe) : sa dérivée existe partout sauf en 0 – un « détail » qui ne peut être ignoré puisque 0 est justement le minimum de q.

Dans la grande majorité des cas, la non-différentiabilité vient de l'intervention de l'opérateur max dans le calcul de q. Schématiquement, on doit minimiser une fonction de la forme :

( 1 )

L est une fonction régulière. Noter de ce point de vue que la valeur absolue ci-dessus peut se mettre sous forme d'un max de plusieurs façons : les égalités

( 2 )

sont...

Cet article est réservé aux abonnés.
Il vous reste 92% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Mathématiques

(202 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

ABONNEZ-VOUS

Lecture en cours
Introduction, motivation
Sommaire
Sommaire

1 Bibliographie

###

HAUT DE PAGE

2 Annexe

À lire également dans nos bases

MINOUX (M.) - Optimisation en nombres entiers. - [AF 1 251] Mathématiques pour l'ingénieur, avr. 2008.

LEMARÉCHAL (C.) - Optimisation continue. - [S 7 210] Informatique industrielle, mars 2002.

CESSENAT (M.) - Vocabulaire des mathématiques. - [A 1 205] Mathématiques pour l'ingénieur, fév. 1992.

GILBERT (J.C.) - Optimisation différentiable. - [AF 1 252] Mathématiques pour l'ingénieur, avr. 2008.

HAUT DE PAGE

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...

Cet article est réservé aux abonnés.
Il vous reste 94% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Mathématiques

(202 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

ABONNEZ-VOUS