OPTIMISATION & CONTRÔLE

Carte mentale

Élargissez votre recherche dans Universalis

La théorie abstraite

Le cadre général

On se donne un ensemble X et une fonction f : X → R ∪ {+ ∞}. L'introduction de la valeur + ∞ est ici essentielle, tant pour des raisons de commodité théorique que de nécessité pratique, comme on le verra. Un problème d'optimisation (P) consiste à chercher le ou les points qui réalisent le minimum de f sur X :

Un tel point sera appelé solution optimale, ou tout simplement solution du problème (P). On appelle souvent X le domaine permis, et ses éléments les points admissibles. La fonction f est le coût, ou le critère. Le problème (P) lui-même sera noté :

Sans conditions supplémentaires, on ne peut affirmer l'existence d'une solution optimale. Par contre, on peut toujours affirmer l'existence de suites minimisantes, c'est-à-dire de suites (xn) dans X telles que :

Le second membre est soit + ∞ (si X ne rencontre pas l'ensemble des points où f est finie), soit fini, soit − ∞ (on dit alors que f n'est pas bornée inférieurement). On l'appelle souvent la valeur du problème (P). Dire que est solution optimale signifie précisément que :

Les suites minimisantes sont un instrument très important dans la théorie comme dans la pratique. C'est en établissant la convergence de certaines suites minimisantes qu'on montre l'existence de solutions optimales, et c'est en construisant ces suites minimisantes par des algorithmes appropriés qu'on résout numériquement les problèmes d'optimisation.

Un autre moyen d'étude important consiste à plonger le problème (P) dans une famille de problèmes d'optimisation dépendant d'un paramètre y variant dans un espace Y. Typiquement, on introduira une fonction ϕ(yx) : X × Y → ∪ {+ ∞}, telle que ϕ(ȳx) = (x), et à chaque ∈ Y on associera le problème d'optimisation :

et sa valeur :

Les problèmes (Py) apparaissent alors comme des perturbations du problème (P), que l'on retrouve en faisant y = ȳ. Le comportement de la fonction valeur V : Y → R ∪ {± ∞} au voisinage de y = ȳ apporte alors des renseignements extrêmement précieux sur le problème (P) lui-même.

Nous passons maintenant à une étude plus détaillée des problèmes qui se posent. Ils sont de trois types :

– existence de solutions optimales ;

– caractérisation de celles-ci ;

– approximation numérique.

La résolution complète d'un problème d'optimisation passe par ces trois phases, dans l'ordre chronologique en général, bien qu'elles soient intimement liées.

Existence de solutions optimales

La seule méthode connue consiste à se ramener au théorème qui affirme que toute fonction semi-continue inférieurement sur un compact atteint son minimum. Rappelons que f : X → R ∪ {+ ∞} est dite semi-continue inférieurement (s.c.i.) si son épigraphe :

est une partie fermée de X × R. Ainsi, toute fonction continue est semi-continue inférieurement.

En dimension finie, il n'y a pratiquement jamais de difficulté. La fonction f sera en général continue, et l'ensemble X compact pour peu qu'il soit fermé et borné. S'il n'est pas borné, on peut souvent se ramener à un compact en remplaçant X par Xm = X ∩ {x | f (x) ≤ m}, où m est choisi convenablement : il revient au même de minimiser f sur X ou sur Xm. Bref, la réponse, positive ou négative, peut être obtenue d'un coup d'œil.

En dimension infinie, par contre, il en est tout autrement. La difficulté est que, pour rendre X compact, il faudra avoir recours à des topologies tellement faibles qu'elles ne laisseront plus à f aucune chance d'être continue. La convexité seule peut sauver la situation, et encore, dans certains espaces seulement.

Théorème. Soit E un espace de Banach réflexif, muni de la topologie de la norme, X ⊂ E une partie convexe fermée et f : E → R ∪ {+ ∞} une fonction convexe semi-continue inférieurement. Si X est bornée, ou si f (x) → + ∞ quand ∥x∥ → ∞, alors (P) possède une solution optimale au moins.

Les espaces Lp sont réflexifs pour 1 < < ∞, les espaces L1, L et Cr ne le sont pas. Ce théorème paraît technique, mais l'expérience montre que les hypothèses mathématiques – réflexivité, convexité – traduisent des obstructions réelles. Nous aurons l'occasion d'y revenir (problème de Plateau, théorie de la relaxation).

Conditions nécessaires d'optimalité

Dans le cas le plus simple, où X = E est un espace de Banach et f : E → R une fonction de classe C2, pour toute solution optimale , on aura f′() = 0 (condition du premier ordre) et f″() semi-définie positive (condition du second ordre).

Sauf cas spéciaux (condition de Legendre en calcul des variations, problèmes de sensit [...]

1  2  3  4  5
pour nos abonnés,
l’article se compose de 8 pages

Médias de l’article

Problème de Dirichlet : solution

Problème de Dirichlet : solution
Crédits : Encyclopædia Universalis France

dessin

Convexifiée

Convexifiée
Crédits : Encyclopædia Universalis France

graphique

Afficher les 2 médias de l'article


Écrit par :

  • : professeur de mathématiques à l'université de Paris-IX-Dauphine (Centre de recherche de mathématiques de la décision). président honoraire à l'Université Paris-Dauphine

Classification

Autres références

«  OPTIMISATION & CONTRÔLE  » est également traité dans :

AUTOMATISATION

  • Écrit par 
  • Jean VAN DEN BROEK D'OBRENAN
  •  • 11 887 mots
  •  • 12 médias

Dans le chapitre « La classification par un réseau de neurones »  : […] Supposons que l'on désire classer des « formes » en deux catégories (A ou B) en fonction de certaines caractéristiques de ces formes, on peut définir une fonction ϕ qui prend la valeur + 1 pour toutes les formes de la classe A et — 1 pour toutes les formes de la classe B. On peut démontrer que cette approximation constitue une probabilité d'appartenance de la forme inconnue à la classe A. Les cla […] Lire la suite

CONVEXITÉ - Ensembles convexes

  • Écrit par 
  • Victor KLEE
  •  • 4 797 mots
  •  • 7 médias

Dans le chapitre « Points extrémaux »  : […] Les fonctions convexes et concaves présentent des propriétés très utiles dans les problèmes d' optimisation. Par exemple, soit f une fonction convexe définie dans un domaine convexe D d'un espace vectoriel topologique localement convexe E ; alors tout minimum local de f dans D est un minimum global , c'est-à-dire que si un point x 0 de D possède un voisinage U tel que f  ( x ) ≥  f ( x 0 ) pour t […] Lire la suite

FONCTIONS REPRÉSENTATION & APPROXIMATION DES

  • Écrit par 
  • Jean-Louis OVAERT, 
  • Jean-Luc VERLEY
  •  • 19 540 mots
  •  • 6 médias

Dans le chapitre « Optimisation de l'approximation »  : […] Avec les notations du chapitre précédent, nous allons étudier les deux problèmes suivants : a ) l'unicité de l'élément ϕ n de E n optimisant l'approximation de f par les éléments de E n  ; il est alors intéressant de construire des méthodes explicites de calcul de ϕ n  ; b ) la distance δ n ( f  ) tend-elle vers 0 si n tend vers + ∞ ? Si oui, déterminer la vitesse de convergence en fonction d […] Lire la suite

NUMÉRIQUE ANALYSE

  • Écrit par 
  • Jean-Louis OVAERT, 
  • Jean-Luc VERLEY
  •  • 6 645 mots

Dans le chapitre « Cadre théorique »  : […] Soit f une fonction continue sur [α, β]. Pour obtenir des valeurs approchées de : on effectue une subdivision à pas constants de [α, β] et, sur chaque intervalle [ a ,  b ] ainsi déterminé, on effectue une interpolation de f par une fonction polynomiale de degré ≤  p où p est un entier donné. On introduit donc un système interpolateur S = {α 0 , α 1 , ..., α p } de points de [ a ,  b ] et le […] Lire la suite

RÉSEAUX DE NEURONES

  • Écrit par 
  • Gérard DREYFUS
  •  • 5 124 mots
  •  • 7 médias

Dans le chapitre « L'apprentissage des réseaux de neurones formels »  : […] L'apprentissage, pour les réseaux de neurones formels, consiste à calculer les paramètres de telle manière que les sorties du réseau de neurones soient, pour les exemples utilisés lors de l'apprentissage, aussi proches que possible des sorties « désirées », qui peuvent être le code de la classe à laquelle appartient la forme que l'on veut classer, la valeur de la fonction que l'on veut approcher o […] Lire la suite

Voir aussi

Pour citer l’article

Ivar EKELAND, « OPTIMISATION & CONTRÔLE », Encyclopædia Universalis [en ligne], consulté le 24 mai 2022. URL : https://www.universalis.fr/encyclopedie/optimisation-et-controle/