Optimisation contrainte - Constrained optimization

Dans l' optimisation mathématique , optimisation sous contraintes (dans certains contextes appelés optimisation de contraintes ) est le processus d'optimisation d' une fonction objective par rapport à certaines des variables en présence de contraintes sur ces variables. La fonction objectif est soit une fonction de coût ou fonction de l' énergie , qui doit être réduite au minimum , ou une fonction de récompense ou la fonction utilitaire , qui doit être maximisé . Les contraintes peuvent être soit des contraintes dures , qui définissent des conditions pour les variables qui doivent être satisfaites, soit des contraintes souples , qui ont des valeurs variables qui sont pénalisées dans la fonction objectif si, et en fonction de la mesure dans laquelle, les conditions sur les variables ne sont pas satisfaits.

Relation avec les problèmes de satisfaction de contraintes

Le problème d'optimisation sous contraintes (COP) est une généralisation significative du modèle classique de problème de satisfaction de contraintes (CSP). COP est un CSP qui comprend une fonction objectif à optimiser. De nombreux algorithmes sont utilisés pour gérer la partie optimisation.

Forme générale

Un problème général de minimisation sous contraintes peut s'écrire comme suit :

${\displaystyle {\begin{array}{rcll}\min &~&f(\mathbf {x} )&\\\mathrm {subject~to} &~&g_{i}(\mathbf {x} )=c_{ i}&{\text{for }}i=1,\ldots ,n\quad {\text{Contraintes d'égalité}}\\&~&h_{j}(\mathbf {x} )\geqq d_{j}& {\text{for }}j=1,\ldots ,m\quad {\text{Contraintes d'inégalité}}\end{array}}}$

où et sont des contraintes qui doivent être satisfaites (on les appelle contraintes dures ), et est la fonction objectif qui doit être optimisée sous réserve des contraintes. ${\displaystyle g_{i}(\mathbf {x} )=c_{i}~\mathrm {for~} i=1,\ldots ,n}$${\displaystyle h_{j}(\mathbf {x} )\geq d_{j}~\mathrm {for~} j=1,\ldots ,m}$${\displaystyle f(\mathbf {x} )}$

Dans certains problèmes, souvent appelés problèmes d'optimisation de contraintes , la fonction objectif est en fait la somme des fonctions de coût, dont chacune pénalise la mesure (le cas échéant) dans laquelle une contrainte douce (une contrainte qui est préférée mais pas obligée d'être satisfaite) est violé.

Méthodes de résolution

De nombreux algorithmes d'optimisation sous contraintes peuvent être adaptés au cas non contraint, souvent via l'utilisation d'une méthode de pénalité . Cependant, les étapes de recherche prises par la méthode sans contrainte peuvent être inacceptables pour le problème contraint, conduisant à un manque de convergence. C'est ce qu'on appelle l'effet Maratos.

Contraintes d'égalité

Méthode de substitution

Pour des problèmes très simples, disons une fonction de deux variables soumise à une seule contrainte d'égalité, il est plus pratique d'appliquer la méthode de substitution. L'idée est de substituer la contrainte à la fonction objectif pour créer une fonction composite qui intègre l'effet de la contrainte. Par exemple, supposons que l'objectif est de maximiser le sujet à . La contrainte implique , qui peut être substituée dans la fonction objectif à créer . La condition nécessaire du premier ordre donne , qui peut être résolu pour et, par conséquent, . ${\displaystyle f(x,y)=x\cdot y}$${\style d'affichage x+y=10}$${\style d'affichage y=10-x}$${\style d'affichage p(x)=x(10-x)=10x-x^{2}}$${\displaystyle {\frac {\partial p}{\partial x}}=10-2x=0}$${\style d'affichage x=5}$${\style d'affichage y=10-5=5}$

Multiplicateur de Lagrange

Si le problème contraint n'a que des contraintes d'égalité, la méthode des multiplicateurs de Lagrange peut être utilisée pour le convertir en un problème sans contrainte dont le nombre de variables est le nombre original de variables plus le nombre original de contraintes d'égalité. Alternativement, si les contraintes sont toutes des contraintes d'égalité et sont toutes linéaires, elles peuvent être résolues pour certaines des variables en fonction des autres, et la première peut être remplacée par la fonction objectif, laissant un problème sans contrainte dans un plus petit nombre de variables.

Contraintes d'inégalité

Avec des contraintes d'inégalité, le problème peut être caractérisé en termes de conditions d' optimalité géométrique , conditions de Fritz John et conditions de Karush-Kuhn-Tucker , sous lesquelles des problèmes simples peuvent être résolus.

Programmation linéaire

Si la fonction objectif et toutes les contraintes dures sont linéaires et que certaines contraintes dures sont des inégalités, alors le problème est un problème de programmation linéaire . Cela peut être résolu par la méthode du simplexe , qui fonctionne généralement en temps polynomial dans la taille du problème mais n'est pas garanti, ou par des méthodes de points intérieurs qui sont garanties pour fonctionner en temps polynomial.

Programmation non linéaire

Si la fonction objectif ou certaines des contraintes sont non linéaires et que certaines contraintes sont des inégalités, alors le problème est un problème de programmation non linéaire .

Programmation quadratique

Si toutes les contraintes dures sont linéaires et certaines sont des inégalités, mais que la fonction objectif est quadratique, le problème est un problème de programmation quadratique . C'est un type de programmation non linéaire. Elle peut encore être résolue en temps polynomial par la méthode de l' ellipsoïde si la fonction objectif est convexe ; sinon, le problème peut être NP dur .

Conditions KKT

Autorisant les contraintes d'inégalité, l' approche KKT de la programmation non linéaire généralise la méthode des multiplicateurs de Lagrange. Il peut être appliqué sous la différentiabilité et la convexité.

Branché et lié

L'optimisation des contraintes peut être résolue par des algorithmes de branchement et de liaison . Ce sont des algorithmes de backtracking stockant le coût de la meilleure solution trouvée lors de l'exécution et l'utilisant pour éviter une partie de la recherche. Plus précisément, chaque fois que l'algorithme rencontre une solution partielle qui ne peut pas être étendue pour former une solution de meilleur coût que le meilleur coût stocké, l'algorithme fait marche arrière, au lieu d'essayer d'étendre cette solution.

En supposant que le coût doit être minimisé, l'efficacité de ces algorithmes dépend de la façon dont le coût qui peut être obtenu en étendant une solution partielle est évalué. En effet, si l'algorithme peut revenir en arrière à partir d'une solution partielle, une partie de la recherche est ignorée. Plus le coût estimé est bas, meilleur est l'algorithme, car un coût estimé inférieur est plus susceptible d'être inférieur au meilleur coût de solution trouvé jusqu'à présent.

D'autre part, ce coût estimé ne peut pas être inférieur au coût effectif qui peut être obtenu en étendant la solution, car sinon l'algorithme pourrait revenir en arrière alors qu'une solution meilleure que la meilleure trouvée à ce jour existe. En conséquence, l'algorithme nécessite une limite supérieure sur le coût qui peut être obtenu en étendant une solution partielle, et cette limite supérieure doit être aussi petite que possible.

Une variante de cette approche appelée méthode de Hansen utilise des méthodes d'intervalle . Il implémente intrinsèquement des contraintes rectangulaires.

Fonctions de délimitation de premier choix

Une façon d'évaluer cette borne supérieure pour une solution partielle consiste à considérer chaque contrainte souple séparément. Pour chaque contrainte souple, la valeur maximale possible pour toute affectation aux variables non affectées est supposée. La somme de ces valeurs est une limite supérieure car les contraintes souples ne peuvent pas prendre une valeur plus élevée. Elle est exacte car les valeurs maximales des contraintes souples peuvent dériver de différentes évaluations : une contrainte souple peut être maximale pour tandis qu'une autre contrainte est maximale pour . ${\style d'affichage x=a}$${\style d'affichage x=b}$

Recherche de poupées russes

Cette méthode exécute un algorithme de branchement et de limite sur les problèmes, où est le nombre de variables. Chacun de ces problèmes est le sous-problème obtenu en supprimant une séquence de variables du problème d'origine, ainsi que les contraintes les contenant. Une fois le problème sur les variables résolu, son coût optimal peut être utilisé comme borne supérieure tout en résolvant les autres problèmes, ${\style d'affichage n}$${\style d'affichage n}$${\displaystyle x_{1},\ldots ,x_{i}}$${\displaystyle x_{i+1},\ldots ,x_{n}}$

En particulier, l'estimation du coût d'une solution ayant comme variables non affectées est ajoutée au coût qui dérive des variables évaluées. Pratiquement, cela correspond à ignorer les variables évaluées et à résoudre le problème sur celles non affectées, sauf que ce dernier problème a déjà été résolu. Plus précisément, le coût des contraintes souples contenant à la fois des variables affectées et non affectées est estimé comme ci-dessus (ou en utilisant une autre méthode arbitraire) ; le coût des contraintes souples contenant uniquement des variables non affectées est plutôt estimé en utilisant la solution optimale du problème correspondant, qui est déjà connue à ce stade. ${\displaystyle x_{i+1},\ldots ,x_{n}}$

Il existe une similitude entre la méthode Russian Doll Search et la programmation dynamique . Comme la programmation dynamique, Russian Doll Search résout les sous-problèmes afin de résoudre l'ensemble du problème. Mais, alors que la programmation dynamique combine directement les résultats obtenus sur les sous-problèmes pour obtenir le résultat de l'ensemble du problème, Russian Doll Search ne les utilise que comme limites lors de sa recherche.

Élimination du seau

L' algorithme d' élimination du bucket peut être adapté pour l'optimisation des contraintes. Une variable donnée peut en effet être supprimée du problème en remplaçant toutes les contraintes souples la contenant par une nouvelle contrainte souple. Le coût de cette nouvelle contrainte est calculé en supposant une valeur maximale pour chaque valeur de la variable supprimée. Formellement, si est la variable à supprimer, sont les contraintes souples la contenant, et leurs variables sauf , la nouvelle contrainte souple est définie par : ${\style d'affichage x}$${\displaystyle C_{1},\ldots ,C_{n}}$${\displaystyle y_{1},\ldots ,y_{m}}$${\style d'affichage x}$

${\displaystyle C(y_{1}=a_{1},\ldots ,y_{n}=a_{n})=\max _{a}\sum _{i}C_{i}(x=a, y_{1}=a_{1},\ldots ,y_{n}=a_{n}).}$

L'élimination des compartiments fonctionne avec un ordre (arbitraire) des variables. A chaque variable est associé un seau de contraintes ; le seau d'une variable contient toutes les contraintes ayant la variable la plus élevée dans l'ordre. L'élimination des buckets procède de la dernière variable à la première. Pour chaque variable, toutes les contraintes du bucket sont remplacées comme ci-dessus pour supprimer la variable. La contrainte résultante est ensuite placée dans le bucket approprié.

Voir également

• moindres carrés contraints
• Optimisation des contraintes distribuées
• Problème de satisfaction de contraintes (CSP)
• Programmation par contraintes
• Programmation en nombres entiers
• Méthode de pénalité
• Supériorisation

Les références

Lectures complémentaires

• Bertsekas, Dimitri P. (1982). Optimisation sous contraintes et méthodes du multiplicateur de Lagrange . New York : Presse académique. ISBN 0-12-093480-9.
• Dechter, Rina (2003). Traitement des contraintes . Morgan Kaufmann. ISBN 1-55860-890-7.