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
modifierDéfinition
modifierConsidérons le problème d'optimisation avec contrainte suivant
où 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
où 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.
Exemples
modifierFonction indicatrice
modifierSi 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é
modifierConsidé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 auto-concordante (en).
Pénalisation de contraintes d'égalité
modifierConsidérons maintenant le cas où l'ensemble est défini par une contrainte d'égalité
où 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é
modifierConsidérons à présent le cas où l'ensemble est défini par des contraintes d'inégalité
où ( 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 :
où 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érales
modifierPlus 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
où 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 inexacte
modifierLa 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érieure
modifierUne 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 monotonie
modifierPénalisations inexactes
modifierPénalisation extérieure
modifierPénalisation intérieure
modifierPénalisation exacte
modifierPénalisation du lagrangien
modifierLagrangien ordinaire
modifierLagrangien augmenté
modifierAnnexes
modifierNote
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
modifierLien 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).