Définition d’un problème d’optimisation

Un cadre très général

Dans cet ouvrage, nous nous intéresserons à l’étude et à la résolution des problèmes qui s’énoncent de la manière suivante :« Trouver x∗ ∈ X tel que, pour tout x ∈ X, on ait f(x∗) 6 f(x) ». Dans cet énoncé, X est un ensemble et f est une application définie sur X à valeurs dans la droite achevée R := R ∪ {−∞, +∞}. Il s’agit donc de trouver un point x∗ de l’ensemble X qui donne à f sa plus petite valeur sur X. C’est ce que l’on appelle un problème d’optimisation. On notera également ce problème comme suit : (PX )  inf f(x) x ∈ X ou encore inf x∈X f(x) ou inf {f(x) : x ∈ X}. L’optimisation est la discipline qui étudie ces problèmes. Elle traite des questions d’existence et d’unicité de solution de ce problème, de l’établissement de ses conditions d’optimalité, de sa dualisation, etc. Par ailleurs, une grande partie de cette discipline, et de cet ouvrage, est consacrée aux méthodes numériques qui ont été conçues pour résoudre les problèmes d’optimisation. 

Vocabulaire

 L’optimisation a son propre vocabulaire, dont nous allons dévoiler maintenant les premières bribes. On dit que X est l’ensemble admissible du problème et un point de X est dit admissible. Ces deux notions sont surtout pertinentes lorsque X est une partie d’un autre ensemble E (souvent un espace vectoriel réel), si bien que tout point de E n’est pas nécessairement admissible. Lorsque X est non vide, on dit que le problème est réalisable. La fonction f est appelée critère, fonction coût ou fonction objectif du problème. On appelle valeur optimale de (PX ) la borne inférieure val(PX) := inf{f(x) : x ∈ X} des valeurs prises par f sur X. On dit que le problème (PX) est borné si sa valeur optimale ne vaut pas −∞. Dans le cas contraire, on dit qu’il n’est pas borné ou qu’il est non borné. On a alors inf x∈X f(x) = −∞, ce qui se produit s’il existe une suite {xk} ⊆ X (éventuellement stationnaire, c’est-àdire avec tous les xk égaux pour k grand) telle que f(xk) → −∞. Par ailleurs inf x∈X f(x) = +∞, si f(x) = +∞ pour tout x ∈ X. Il en sera donc ainsi si X = ∅ (l’ensemble vide). On a donc inf x∈∅ f(x) = +∞ et sup x∈∅ f(x) = −∞. (1.1) Ayant défini un problème d’optimisation, il faut maintenant préciser ce qu’en est une solution. On dit qu’un point x∗ est une solution ou un minimum ou encore un minimiseur du problème (PX ) si x∗ ∈ X et ∀x ∈ X, f(x∗) 6 f(x).Il faut donc deux conditions : que x∗ soit admissible et qu’il donne à f une valeur qui n’excède pas (strictement) celle donnée à f par tout autre point admissible. On dit aussi qu’un tel x∗ est solution/minimum/minimiseur global de (PX ) pour distinguer cette notion des autres qui vont suivre. On note indifféremment par Sol(PX) ou arg min x∈X f(x) l’ensemble des solutions de (PX). 

Remarque 1.1 

Lorsque le problème (PX ) a une solution, on écrit min x∈X f(x), donc avec l’opérateur ‘min’ plutôt que ‘inf’. Lorsque X est inclus dans un espace topologique E, on peut définir la notion plus faible de minimum local de (PX). Il s’agit d’un point x∗ tel qu’il existe un voisinage V de x∗ dans E tel que x∗ ∈ X et ∀x ∈ X ∩ V, f(x∗) 6 f(x). Une solution globale est aussi une solution locale (on prend V = E). On parlera de solution ou de minimum global ou local strict si f(x∗) < f(x), pour tout x ∈ X \ {x∗} ou pour tout x ∈ (X ∩ V ) \ {x∗}, respectivement. Il est important de pouvoir prendre en compte des problèmes d’optimisation dans lesquels le critère f peut prendre des valeurs infinies, −∞ ou +∞, parce que ces fonctions sont parfois générées par des procédures qui ne leur assurent pas nécessairement que des valeurs finies (c’est le cas de la dualité au chapitre 14, par exemple). Le domaine effectif (ou simplement domaine) de f est l’ensemble des points de X où elle ne prend pas la valeur +∞ (mais elle peut y prendre la valeur −∞, pour une raison qui sera vue au chapitre 3 sur les fonctions convexes). On le note dom f := {x ∈ X : f(x) < +∞}. Il est clair que les problèmes inf x∈X f(x) et inf x∈dom f f(x) (1.3) ont les mêmes valeurs optimales et les mêmes solutions. Si dom f = ∅, les valeurs optimales sont +∞ (à gauche parce que f(x) = +∞ pour tout x ∈ X, à droite parce que dom f = ∅ et que l’on a adopté la convention (1.1) qui s’avère donc essentielle ici) ; si dom f 6= ∅, alors on ne modifie pas le problème de gauche en excluant de son ensemble admissible les points où f prend la valeur +∞, comme on le fait à droite. L’équivalence entre les problèmes de (1.3) sera souvent utilisée. 

Restrictions 

In our opinion, the main fact, which should be known to any person dealing with optimization methods, is that in general optimization problems are unsolvable. This statement, which is usually missing in standard optimization courses, is very important for an understanding of optimization theory and its development in the past and in the future. Y. Nesterov . Présenté comme ci-dessus, le problème (PX ) peut être très général, mais les méthodes théoriques et algorithmiques étudiées dans ce manuel ne seront efficaces que sur un petit sous-ensemble de ces problèmes, qui contient toutefois beaucoup de ceux qui se posent en pratique, mais en écarte aussi beaucoup d’autres. Les restrictions présentes dans (PX ) ou que nous nous imposerons, faute de pouvoir tout faire, sont les suivantes. L’ensemble d’arrivée de f est un espace vectoriel de dimension un, ce qui veut dire que l’on ne cherche à minimiser qu’un seul critère. Lorsque l’espace d’arrivée est de dimension supérieure, on parle d’optimisation multicritère. Nous n’aborderons pas ces problèmes dans cet ouvrage, bien qu’il soit fait allusion à la notion d’optimalité au sens de Pareto à l’exercice 3.14. Même si cela n’apparaît pas dans la formulation générale de (PX ), on éliminera également de nos préoccupations une autre classe importante de problèmes, ceux pour lesquels les variables sont entières : X est une partie de N n. Ces problèmes d’optimisation en nombres entiers ou combinatoire sont d’une autre nature que ceux qui peuvent être résolus par les algorithmes que nous étudierons (pour une introduction à ces problèmes, voir par exemple [476]). Ces derniers auront besoin d’une certaine régularité des données. Il faudra une topologie sur X et un critère f au moins continu, si possible différentiable (éventuellement dans un sens généralisé). Cette restriction à des classes de fonctions particulières permet aussi d’échapper au verdict étonnant et fâcheux, selon lequel tous les algorithmes sont équivalents, si on moyenne leur performance sur l’ensemble des fonctions [627 ; 1997], affirmation qui doit d’ailleurs être nuancée [26 ; 2007]. Dans le même ordre d’idée, les algorithmes que nous étudierons ne seront efficaces que pour trouver des minima locaux. Trouver un minimum global d’une fonction qui a beaucoup de minima locaux s’apparente en effet souvent à un problème combinatoire (par exemple lorsque l’ensemble des minima locaux est discret), lequel a été éliminé de nos préoccupations ci-dessus. Les algorithmes locaux, c’est-à-dire ceux trouvant des minima locaux, sont toutefois utiles, car ils sont souvent très efficaces et sont d’ailleurs parfois utilisés dans certaine méthode d’optimisation globale. On peut en fait souvent montrer que plus les fonctions à minimiser sont régulières et plus rapide sera la convergence locale des itérés générés par un algorithme sachant utiliser cette régularité de manière idoine. Quand il sera question d’algorithmes, nous travaillerons toujours en dimension finie, c’est-à-dire que l’ensemble admissible X sera une partie d’un espace vectoriel de dimension finie sur R (par exemple, l’espace vectoriel R n des n-uplets x1, . . . , xn) ou l’espace vectoriel S n des matrices réelles d’ordre n symétriques). Les composantes de x peuvent alors être vues comme des paramètres servant à rendre optimal un système. En pratique, les problèmes de dimension infinie se rencontrent fréquemment, par exemple lorsqu’il s’agit de déterminer une trajectoire optimale ou une forme optimale. Il s’agit alors de déterminer une fonction plutôt qu’un vecteur. Lorsqu’on veut résoudre ces problèmes, il est nécessaire de passer par une phase de discrétisation qui, en utilisant une technique adéquate, construit un problème approché en dimension finie qui pourra être résolu sur ordinateur par les algorithmes vus dans cet ouvrage.