OPTIMISATION & CONTRÔLE

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 x̄ qui réalisent le minimum de f sur X :

Un tel point x̄ 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 (x_n) 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 x̄ 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 ϕ(y, x) : X × Y → R ∪ {+ ∞}, telle que ϕ(ȳ, x) = f (x), et à chaque y ∈ Y on associera le problème d'optimisation :

et sa valeur :

Les problèmes (P_y) 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 X_m = X ∩ {x | f (x) ≤ m}, où m est choisi convenablement : il revient au même de minimiser f sur X ou sur X_m. 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 x̄ au moins.

Les espaces L^p sont réflexifs pour 1 < p < ∞, les espaces L¹, L^∞ et C^r 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 C², pour toute solution optimale x̄, on aura f′(x̄) = 0 (condition du premier ordre) et f″(x̄) 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

Afficher les 2 médias de l'article