Pénalisation (optimisation)

technique permettant d'analyser et de résoudre analytiquement ou numériquement des problèmes d'optimisation avec contraintes

En optimisation mathématique, la pénalisation est une technique permettant d'analyser et de résoudre analytiquement ou numériquement des problèmes d'optimisation avec contraintes. Elle consiste à transformer le problème avec contraintes en un problème (cas de la pénalisation exacte) ou des problèmes (cas de la pénalisation inexacte) d'optimisation sans contrainte ; le sens précis de cette phrase apparaîtra plus loin.

C'est un outil à la fois théorique et algorithmique.

  • En théorie, on peut l'utiliser pour démontrer l'existence de solution des problèmes d'optimisation avec contraintes, en étudier les propriétés, établir des conditions d'optimalité, etc.
  • En algorithmique, cette approche permet de résoudre des problèmes avec contraintes en n'utilisant que des méthodes de l'optimisation sans contrainte ; cependant, à moins que l'on ne spécifie l'algorithme de manière raffinée (comme dans les algorithmes de points intérieurs en optimisation linéaire, quadratique et semi-définie positive — qui peuvent être interprétés comme des algorithmes de pénalisation), c'est un peu la «méthode du pauvre», permettant d'obtenir des résultats peu précis mais avec peu d'effort.

PrincipesModifier

DéfinitionModifier

Considérons le problème d'optimisation avec contrainte suivant

 

  est une partie d'un ensemble   et   est une fonction définie sur   pouvant prendre des valeurs infinies. La pénalisation (sous entendu de la contrainte  ) est une technique qui remplace le problème   par un ou des problèmes sans contrainte de la forme

 

  est la fonction définie en   par

 

Dans cette expression,   est en général un réel positif à ajuster, appelé facteur de pénalisation, et

 

est une fonction à spécifier, appelée fonction de pénalisation.

À ce niveau de généralité, rien ne permet de dire que les problèmes   et   ont un lien entre eux ; cela dépend de la fonction de pénalisation et du facteur de pénalisation. De manière à rendre l'approche plus concrète, donnons quelques exemples.

ExemplesModifier

Fonction indicatriceModifier

Si l'on est familier avec les fonctions pouvant prendre la valeur  , on comprendra aisément qu'une fonction de pénalisation naturelle pour   est la fonction indicatrice de   :

 

Dans cette pénalisation, le facteur   ne joue aucun rôle (il multiplie zéro ou l'infini). Par ailleurs, les problèmes   et   sont alors équivalents, dans le sens où ils ont les mêmes solutions et les mêmes valeurs optimales. On l'utilise souvent dans certains développements théoriques pour prendre en compte simultanément les problèmes avec ( ) et sans ( ) contraintes. Numériquement, cette pénalisation n'est guère utile, car si l'itéré courant est en dehors de l'adhérence de l'ensemble admissible, l'examen de   dans le voisinage de cet itéré (  y est égale à  ) n'apportera pas d'information sur la direction à prendre pour trouver un point admissible.

Pénalisation de contraintes de positivitéModifier

Considérons d'abord le cas où   et l'ensemble   est défini par une contrainte de positivité :

 

est l'orthant positif de  . La pénalisation logarithmique consiste à prendre comme fonction de pénalisation :

 

Cette pénalisation a été introduite par l'économiste Ragnar Frisch en 1955[1]. Il s'agit d'une pénalisation inexacte intérieure. Elle peut se généraliser, dans un sens bien précis (et compliqué), à des ensembles convexes (presque) arbitraires, via la notion de fonction autoconcordante.

Pénalisation de contraintes d'égalitéModifier

Considérons maintenant le cas où l'ensemble   est défini par une contrainte d'égalité

 

  est une fonction à valeurs dans un espace normé  , dont la norme est notée  . Les deux fonctions   et  , définies ci-dessous par leurs valeurs en  , sont des fonctions de pénalisation que l'on rencontre souvent :

 

La fonction   est mieux adaptée à un espace de Hilbert   ; elle porte le nom de pénalisation quadratique. Ces deux fonctions de pénalisation conduisent à des propriétés très différentes : la première donne lieu à une pénalisation exacte, la seconde à une pénalisation inexacte extérieure.

Pénalisation de contraintes d'inégalitéModifier

Considérons à présent le cas où l'ensemble   est défini par des contraintes d'inégalité

 

  (  entier) et l'inégalité se lit composante par composante :  , ...,  . Les deux fonctions   et  , définies ci-dessous par leurs valeurs en  , sont des fonctions de pénalisation que l'on utilise souvent :

 

  est une norme arbitraire sur  ,   est la norme euclidienne de   et   est pour   le vecteur de   dont la composante   est  . Comme ci-dessus, la pénalisation   donne lieu à une pénalisation exacte, tandis que   correspond à une pénalisation inexacte extérieure. Cette dernière porte le nom de pénalisation quadratique.

Pénalisation de contraintes généralesModifier

Plus généralement, supposons que   soit un ensemble convexe d'un espace normé   et que   soit une fonction. On considère ici le cas où l'ensemble   est défini par

 

On retrouve les exemples précédents lorsque   et   est l'orthant négatif  . Les généralisations à ce cadre des fonctions de pénalisation   ou  , d'une part, et   ou  , d'autre part, sont les fonctions suivantes

 

  est la distance de   à l'ensemble  . Ici aussi, la pénalisation   donne lieu à une pénalisation exacte, tandis que   correspond à une pénalisation inexacte extérieure.

Pénalisations exacte et inexacteModifier

La notion de pénalisation exacte est très utile, bien qu'elle ne soit pas très précise ; plutôt, elle requiert des précisions supplémentaires dans les résultats qui la mentionne. Le concept est attaché au lien que l'on désire établir entre les problèmes   et   définis ci-dessus. Une définition pourrait être la suivante.

Pénalisation exacte — On dit que la pénalisation réalisée dans   est exacte si les solutions de   sont solutions de  . On dit que la pénalisation est inexacte dans le cas contraire.

Cette définition ne dit pas ce que l'on entend par solution : est-ce un minimum global, local, un point-stationnaire ? Aussi, faut-il que cette correspondance ait lieu entre toutes les solutions de   et de   ou pour une seule d'entre elles ? Les résultats qui affirment qu'une pénalisation est exacte précisent les réponses à ces questions. Ils précisent aussi les valeurs que doit prendre le facteur de pénalisation   pour que la propriété d'exactitude soit vraie. Il arrive aussi que les solutions de   soient solutions de  , mais cette propriété est plus rare, à moins que l'on ne sélectionne parmi les solutions de  , celles qui sont admissibles pour  , c'est-à-dire qui sont dans l'ensemble admissible  .

Lorsque la pénalisation est exacte, le lien entre les problèmes d'optimisation   et   est clair : ces problèmes ont des solutions en commun. Dès lors, si l'on veut résoudre le problème avec contrainte  , il suffit parfois de résoudre le problème sans contrainte  . Cette propriété remarquable est contrebalancée par le fait qu'une fonction de pénalisation exacte est souvent non-différentiable (c'est le cas des fonctions de pénalisation  ,   et   données en exemples ci-dessus) ou contient des paramètres qui ne sont pas facilement calculables (comme un multiplicateur optimal dans le lagrangien augmenté).

Lorsque la pénalisation est inexacte, le lien entre les problèmes d'optimisation   et   n'est pas nécessairement absent. Si la pénalisation est bien construite, le lien s'obtient asymptotiquement, en faisant tendre le paramètre de pénalisation   vers une valeur limite, zéro ou l'infini. Numériquement, la résolution d'un problème d'optimisation par pénalisation inexacte se fera par la résolution d'une suite de problèmes d'optimisation sans contrainte, en faisant tendre le paramètre de pénalisation vers sa limite. La nécessité de résoudre des problèmes d'optimisation   pour plusieurs valeurs de   repose sur les raisons suivantes :

  • il ne suffit pas de donner à   sa valeur limite; si  , il n'y a plus de terme de pénalisation dans  , si bien que l'on ne tient plus compte des contraintes ; si  ,   n'est pas bien définie ;
  • il ne suffit pas de prendre un unique paramètre de pénalisation   proche de sa valeur limite (proche de zéro ou très grand), car on ne peut pas dire a priori, si cela conduira à une solution approchée de   acceptable ;
  • lorsque le paramètre de pénalisation est proche de sa valeur limite, le problème   est en général mal conditionné, si bien qu'il est numériquement difficile d'obtenir de la précision sur les minimiseurs de  , à moins que le point de départ du processus de minimisation soit déjà proche d'un tel minimiseur ; il est donc judicieux de se rapprocher d'une solution de   sans trop s'écarter du chemin défini par les minimiseurs des problèmes   (méthode de suivi de chemin).

Pénalisations extérieure et intérieureModifier

Une pénalisation inexacte peut être extérieure ou intérieure.

Dans une pénalisation extérieure, la fonction de pénalisation   est nulle sur, et uniquement sur, l'ensemble admissible  . À l'extérieur de cet ensemble,   prend des valeurs strictement positives. Comme on cherche à minimiser  , cette pénalisation force le minimiseur à se rapprocher de l'ensemble admissible, d'autant plus que le facteur de pénalisation   est grand. Dans cette approche, la fonction   pénalise donc la violation des contraintes, d'autant plus que son argument est éloigné de l'ensemble admissible   ; lorsque cet ensemble est défini par des contraintes fonctionnelles, cet éloignement est mesuré par la valeur de ces contraintes fonctionnelles. Dans cette technique de pénalisation, les minimiseurs de   sont en général extérieurs à l'ensemble admissible   et on fait tendre   vers   pour trouver une solution de   à partir de celles de  . Les fonctions  ,   et   données en exemples ci-dessus sont des fonctions de pénalisation extérieure.

Dans une pénalisation intérieure, ...

Propriété de monotonieModifier

Pénalisations inexactesModifier

Pénalisation extérieureModifier

Pénalisation intérieureModifier

Pénalisation exacteModifier

Pénalisation du lagrangienModifier

Lagrangien ordinaireModifier

Lagrangien augmentéModifier

AnnexesModifier

NoteModifier

  1. (en) R. Frisch (1955, mai). The logarithmic potential method for convex programming with particular application to the dynamics of planning for national development. Memorandum, Institut d’Économie, Université d’Oslo, Oslo, Norvège.

Article connexeModifier

Lien externeModifier

RéférencesModifier