Pénalisation (optimisation)

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.

Principes modifier

Définition modifier

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

$(P_{X})\qquad \inf _{x\in X}\,f(x),$

où $X$ est une partie d'un ensemble $\mathbb {E}$ et $f:\mathbb {E} \to {\bar {\mathbb {R} }}:x\mapsto f(x)$ est une fonction définie sur $\mathbb {E}$ pouvant prendre des valeurs infinies. La pénalisation (sous entendu de la contrainte $x\in X$ ) est une technique qui remplace le problème $(P_{X})$ par un ou des problèmes sans contrainte de la forme

$(P_{r})\qquad \inf _{x\in \mathbb {E} }\,f_{r}(x),$

où $f_{r}$ est la fonction définie en $x\in \mathbb {E}$ par

f_{r}(x)=f(x)+r\,p(x).

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

$p:x\in \mathbb {E} \mapsto p(x)$

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 $(P_{X})$ et $(P_{r})$ 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.

Exemples modifier

Fonction indicatrice modifier

Si l'on est familier avec les fonctions pouvant prendre la valeur $+\infty$ , on comprendra aisément qu'une fonction de pénalisation naturelle pour $(P_{X})$ est la fonction indicatrice de $X$ :

$p_{0}\equiv {\mathcal {I}}_{X}:\mathbb {E} \to \mathbb {R} \cup \{+\infty \}:x\mapsto {\mathcal {I}}_{X}(x)=\left\{{\begin{array}{lll}0&{\mbox{si}}&x\in X\\+\infty &{\mbox{si}}&x\notin X.\end{array}}\right.$

Dans cette pénalisation, le facteur $r>0$ ne joue aucun rôle (il multiplie zéro ou l'infini). Par ailleurs, les problèmes $(P_{X})$ et $(P_{r})$ 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 ( $X\neq \mathbb {E}$ ) et sans ( $X=\mathbb {E}$ ) 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 $f_{r}$ dans le voisinage de cet itéré ( $f_{r}$ y est égale à $+\infty$ ) 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ù $\mathbb {E} =\mathbb {R} ^{n}$ et l'ensemble $X$ est défini par une contrainte de positivité :

$X:=\{x\in \mathbb {R} ^{n}:x\geqslant 0\}$

est l'orthant positif de $\mathbb {R} ^{n}$ . La pénalisation logarithmique consiste à prendre comme fonction de pénalisation :

$p_{1}(x):=-\sum _{i=1}^{n}\log x_{i}.$

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 auto-concordante (en).

Pénalisation de contraintes d'égalité modifier

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

$X:=\{x\in \mathbb {E} :c(x)=0\},$

où $c:\mathbb {E} \to \mathbb {F}$ est une fonction à valeurs dans un espace normé $\mathbb {F}$ , dont la norme est notée $\|\cdot \|$ . Les deux fonctions $p_{2}$ et $p_{3}$ , définies ci-dessous par leurs valeurs en $x\in \mathbb {E}$ , sont des fonctions de pénalisation que l'on rencontre souvent :

$p_{2}(x):=\|c(x)\|\qquad {\mbox{et}}\qquad p_{3}(x):={\frac {1}{2}}\,\|c(x)\|^{2}.$

La fonction $p_{3}$ est mieux adaptée à un espace de Hilbert $\mathbb {F}$ ; 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 $X$ est défini par des contraintes d'inégalité

$X:=\{x\in \mathbb {E} :c(x)\leqslant 0\},$

où $c:\mathbb {E} \to \mathbb {R} ^{m}$ ( $m$ entier) et l'inégalité se lit composante par composante : $c_{1}(x)\leqslant 0$ , ..., $c_{m}(x)\leqslant 0$ . Les deux fonctions $p_{4}$ et $p_{5}$ , définies ci-dessous par leurs valeurs en $x\in \mathbb {E}$ , sont des fonctions de pénalisation que l'on utilise souvent :

$p_{4}(x):=\|c(x)^{+}\|\qquad {\mbox{et}}\qquad p_{5}(x):={\frac {1}{2}}\,\|c(x)^{+}\|_{2}^{2},$

où $\|\cdot \|$ est une norme arbitraire sur $\mathbb {R} ^{m}$ , $\|\cdot \|_{2}$ est la norme euclidienne de $\mathbb {R} ^{m}$ et $v^{+}$ est pour $v\in \mathbb {R} ^{m}$ le vecteur de $\mathbb {R} ^{m}$ dont la composante $i$ est $\max(0,v_{i})$ . Comme ci-dessus, la pénalisation $p_{4}$ donne lieu à une pénalisation exacte, tandis que $p_{5}$ correspond à une pénalisation inexacte extérieure. Cette dernière porte le nom de pénalisation quadratique.

Pénalisation de contraintes générales modifier

Plus généralement, supposons que $G$ soit un ensemble convexe d'un espace normé $\mathbb {F}$ et que $c:\mathbb {E} \to \mathbb {F}$ soit une fonction. On considère ici le cas où l'ensemble $X$ est défini par

$X:=\{x\in \mathbb {E} :c(x)\in G\}.$

On retrouve les exemples précédents lorsque $G=\{0\}$ et $G$ est l'orthant négatif $G=\{y\in \mathbb {R} ^{m}:y\leqslant 0\}$ . Les généralisations à ce cadre des fonctions de pénalisation $p_{2}$ ou $p_{4}$ , d'une part, et $p_{3}$ ou $p_{5}$ , d'autre part, sont les fonctions suivantes

$p_{6}(x):=\operatorname {dist} (c(x),G)\qquad {\mbox{et}}\qquad p_{7}(x):={\frac {1}{2}}\,{\Bigl [}\operatorname {dist} (c(x),G){\Bigr ]}^{2},$

où $\operatorname {dist} (y,G)$ est la distance de $y\in \mathbb {F}$ à l'ensemble $G$ . Ici aussi, la pénalisation $p_{6}$ donne lieu à une pénalisation exacte, tandis que $p_{7}$ correspond à une pénalisation inexacte extérieure.

Pénalisations exacte et inexacte modifier

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 $(P_{X})$ et $(P_{r})$ définis ci-dessus. Une définition pourrait être la suivante.

Pénalisation exacte — On dit que la pénalisation réalisée dans $(P_{r})$ est exacte si les solutions de $(P_{X})$ sont solutions de $(P_{r})$ . 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 $(P_{X})$ et de $(P_{r})$ 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 $r$ pour que la propriété d'exactitude soit vraie. Il arrive aussi que les solutions de $(P_{r})$ soient solutions de $(P_{X})$ , mais cette propriété est plus rare, à moins que l'on ne sélectionne parmi les solutions de $(P_{r})$ , celles qui sont admissibles pour $(P_{X})$ , c'est-à-dire qui sont dans l'ensemble admissible $X$ .

Lorsque la pénalisation est exacte, le lien entre les problèmes d'optimisation $(P_{X})$ et $(P_{r})$ est clair : ces problèmes ont des solutions en commun. Dès lors, si l'on veut résoudre le problème avec contrainte $(P_{X})$ , il suffit parfois de résoudre le problème sans contrainte $(P_{r})$ . 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 $p_{2}$ , $p_{4}$ et $p_{6}$ 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 $(P_{X})$ et $(P_{r})$ 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 $r$ 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 $(P_{r})$ pour plusieurs valeurs de $r$ repose sur les raisons suivantes :

il ne suffit pas de donner à $r$ sa valeur limite; si $r=0$ , il n'y a plus de terme de pénalisation dans $f_{r}$ , si bien que l'on ne tient plus compte des contraintes ; si $r=+\infty$ , $f_{r}$ n'est pas bien définie ;
il ne suffit pas de prendre un unique paramètre de pénalisation $r$ 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 $(P_{X})$ acceptable ;
lorsque le paramètre de pénalisation est proche de sa valeur limite, le problème $(P_{r})$ 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 $(P_{r})$ , à 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 $(P_{X})$ sans trop s'écarter du chemin défini par les minimiseurs des problèmes $(P_{r})$ (méthode de suivi de chemin).

Pénalisations extérieure et intérieure modifier

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

Dans une pénalisation extérieure, la fonction de pénalisation $p$ est nulle sur, et uniquement sur, l'ensemble admissible $X$ . À l'extérieur de cet ensemble, $p$ prend des valeurs strictement positives. Comme on cherche à minimiser $f_{r}:=f+r\,p$ , cette pénalisation force le minimiseur à se rapprocher de l'ensemble admissible, d'autant plus que le facteur de pénalisation $r$ est grand. Dans cette approche, la fonction $p$ pénalise donc la violation des contraintes, d'autant plus que son argument est éloigné de l'ensemble admissible $X$ ; 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 $f_{r}$ sont en général extérieurs à l'ensemble admissible $X$ et on fait tendre $r$ vers $+\infty$ pour trouver une solution de $(P_{X})$ à partir de celles de $(P_{r})$ . Les fonctions $p_{3}$ , $p_{5}$ et $p_{7}$ données en exemples ci-dessus sont des fonctions de pénalisation extérieure.

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

Propriété de monotonie modifier

Pénalisations inexactes modifier

Pénalisation extérieure modifier

Pénalisation intérieure modifier

Pénalisation exacte modifier

Pénalisation du lagrangien modifier

Lagrangien ordinaire modifier

Lagrangien augmenté modifier

Annexes modifier

Note modifier

↑ (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 connexe modifier

Méthodes de points intérieurs

Lien externe modifier

J. Ch. Gilbert, Éléments d'Optimisation Différentiable — Théorie et Algorithmes, syllabus de cours à l'ENSTA ParisTech, Paris.

Références modifier

(en) D. P. Bertsekas (1995), Nonlinear Programming. Athena Scientific. (ISBN 978-1-886529-14-4).
(en) J. F. Bonnans, J. Ch. Gilbert, C. Lemaréchal, C. Sagastizábal (2006), Numerical Optimization - Theoretical and Numerical Aspects [détail des éditions].
(en) J. Nocedal, S. J. Wright (2006), Numerical Optimization, Springer. (ISBN 978-0-387-30303-1).

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

[1]