De nombreux algorithmes d’optimisation sans contrainte peuvent être adaptés au cas contraint, souvent via l’utilisation d’une méthode de pénalité. Cependant, les étapes de recherche effectuées par la méthode sans contrainte peuvent être inacceptables pour le problème contraint, ce qui entraîne un manque de convergence. C’est ce qu’on appelle l’effet Maratos.
Contraintes d’égalitéEdit
Méthode de substitutionEdit
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 dans la fonction objectif pour créer une fonction composite qui incorpore l’effet de la contrainte. Par exemple, supposons que l’objectif est de maximiser f ( x , y ) = x ⋅ y {\displaystyle f(x,y)=x\cdot y}.
sous réserve que x + y = 10 {\displaystyle x+y=10}
. La contrainte implique y = 10 – x {\displaystyle y=10-x}
, qui peut être substitué dans la fonction objectif pour créer p ( x ) = x ( 10 – x ) = 10 x – x 2 {\displaystyle p(x)=x(10-x)=10x-x^{2}}
. La condition nécessaire de premier ordre donne ∂ p ∂ x = 10 – 2 x = 0 {\displaystyle {\frac {\partial p}{\partial x}}=10-2x=0}.
, qui peut être résolu pour x = 5 {\displaystyle x=5}
et, par conséquent, y = 10 – 5 = 5 {\displaystyle y=10-5=5}
.
Multiplicateur de LagrangeEdit
Si le problème contraint ne comporte 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 initial de variables plus le nombre initial 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 les premières peuvent être substituées hors de la fonction objectif, laissant un problème sans contrainte dans un plus petit nombre de variables.
Contraintes d’inégalitéEdit
Avec des contraintes d’inégalité, le problème peut être caractérisé en termes de conditions d’optimalité géométrique, de conditions de Fritz John et de conditions de Karush-Kuhn-Tucker, sous lesquelles des problèmes simples peuvent être solvables.
Programmation linéaireEdit
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 ce n’est pas garanti, ou par des méthodes de points intérieurs qui sont garanties de fonctionner en temps polynomial.
Programmation non linéaireEdit
Si la fonction objectif ou certaines des contraintes sont non linéaires, et certaines contraintes sont des inégalités, alors le problème est un problème de programmation non linéaire.
Programmation quadratiqueEdit
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. Il peut encore être résolu en temps polynomial par la méthode ellipsoïde si la fonction objectif est convexe ; sinon, le problème peut être NP hard.
Conditions KKTEdit
En admettant des contraintes d’inégalité, l’approche KKT de la programmation non linéaire généralise la méthode des multiplicateurs de Lagrange. Elle peut être appliquée sous différentiabilité et convexité.
Branch and boundEdit
L’optimisation par contraintes peut être résolue par des algorithmes de branch-and-bound. Ce sont des algorithmes de backtracking stockant le coût de la meilleure solution trouvée pendant 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 revient en 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 faire marche arrière à partir d’une solution partielle, une partie de la recherche est sautée. Plus le coût estimé est faible, meilleur est l’algorithme, car un coût estimé faible a plus de chances d’être inférieur au meilleur coût de solution trouvé jusqu’à présent.
En revanche, ce coût estimé ne peut pas être inférieur au coût effectif que l’on peut obtenir en étendant la solution, car sinon l’algorithme pourrait faire marche arrière alors qu’il existe une solution meilleure que la meilleure trouvée jusqu’à présent. Par conséquent, l’algorithme nécessite une borne supérieure sur le coût qui peut être obtenu en étendant une solution partielle, et cette borne 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. Elle implémente de manière inhérente les contraintes rectangulaires.
Fonctions de délimitation de premier choixEdit
Une façon d’évaluer cette limite supérieure pour une solution partielle est de considérer chaque contrainte molle séparément. Pour chaque contrainte molle, on suppose la valeur maximale possible pour toute affectation aux variables non affectées. La somme de ces valeurs est une limite supérieure car les contraintes molles ne peuvent pas prendre une valeur supérieure. Elle est exacte car les valeurs maximales des contraintes molles peuvent dériver de différentes évaluations : une contrainte molle peut être maximale pour x = a {\displaystyle x=a}.
alors qu’une autre contrainte est maximale pour x = b {\displaystyle x=b}
.
Recherche de poupées russesEdit
Cette méthode exécute un algorithme de branchement et de liaison sur n {\displaystyle n}.
problèmes, où n {\displaystyle n}
est le nombre de variables. Chacun de ces problèmes est le sous-problème obtenu en abandonnant une séquence de variables x 1 , … , x i {\displaystyle x_{1},\ldots ,x_{i}}.
du problème original, ainsi que les contraintes qui les contiennent. Après le problème sur les variables x i + 1 , … , x n {\displaystyle x_{i+1},\ldots ,x_{n}}
est résolu, son coût optimal peut être utilisé comme limite supérieure lors de la résolution des autres problèmes,
En particulier, l’estimation du coût d’une solution ayant x i + 1 , … , x n {\displaystyle x_{i+1},\ldots ,x_{n}}
comme variables non assigné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 les variables non assignées, sauf que ce dernier problème a déjà été résolu. Plus précisément, le coût des contraintes molles contenant à la fois des variables assignées et non assignées est estimé comme ci-dessus (ou en utilisant une autre méthode arbitraire) ; le coût des contraintes molles contenant uniquement des variables non assignées est au contraire estimé en utilisant la solution optimale du problème correspondant, qui est déjà connue à ce stade.
Il existe une similitude entre la méthode de recherche de poupées russes et la programmation dynamique. Comme la programmation dynamique, la recherche de poupées russes résout des sous-problèmes afin de résoudre le problème entier. Mais, alors que la Programmation Dynamique combine directement les résultats obtenus sur les sous-problèmes pour obtenir le résultat du problème entier, la Recherche de Poupées Russes ne les utilise que comme bornes pendant sa recherche.
Élimination de seauxModification
L’algorithme d’élimination de seaux peut être adapté à l’optimisation des contraintes. Une variable donnée peut en effet être supprimée du problème en remplaçant toutes les contraintes molles la contenant par une nouvelle contrainte molle. Le coût de cette nouvelle contrainte est calculé en supposant une valeur maximale pour chaque valeur de la variable supprimée. Formellement, si x {\displaystyle x}
est la variable à supprimer, C 1 , … , C n {\displaystyle C_{1},\ldots ,C_{n}}
sont les contraintes molles qui la contiennent, et y 1 , … , y m {\displaystyle y_{1},\ldots ,y_{m}}
sont leurs variables sauf x {\displaystyle x}
, la nouvelle contrainte molle est définie par : C ( y 1 = a 1 , … , y n = a n ) = max a ∑ i C i ( x = a , y 1 = a 1 , … , y n = a n ) . {\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 par seau 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 a le plus haut dans l’ordre. L’élimination des seaux se fait de la dernière variable à la première. Pour chaque variable, toutes les contraintes du seau sont remplacées comme ci-dessus pour éliminer la variable. La contrainte résultante est ensuite placée dans le seau approprié.