Technique de relaxation (optimisation)

Un problème de nombres entiers où les points rouges représentent des solutions admissibles peut être assoupli avec, par exemple, la zone rouge ou la zone bleue (où tous les points dans les zones sont des solutions admissibles).

En mathématiques, une technique de relaxation est une méthode d'optimisation qui consiste en la résolution d'un problème d'optimisation $A$ difficile par le biais de problèmes d'optimisations $B_{1},\dots ,B_{m}$ plus approchables numériquement, mais dont les solutions ne fournissent pas immédiatement de garantie concernant la résolution ou non du problème initial $A$.

Généralement, les techniques de relaxation consistent à remplacer des contraintes strictes du problème $A$ en des contrainte moins strictes dans un problème $B$ similaire. On peut citer par exemple :

• la relaxation continue, qui consiste à interpréter de manière continue un problème d’optimisation portant sur des variables à valeurs discrètes,
• la relaxation lagrangienne, qui consiste à supprimer des contraintes en les intégrant dans la fonction objectif (en pénalisant le non respect de ces dernières).

Trouver une solution au problème d'optimisation relaxé $B$ ne garantit alors pas immédiatement qu'il existe une solution au problème initial $A$, mais les solutions trouvées permettent au moins de s'approcher d'une solution admissible. C'est d'une certaine manière l'opposé d'une approche par ajout de conservatisme.

Les techniques de relaxation sont largement utilisées dans les méthodes de séparation et évaluation.

Il ne faut pas confondre les techniques de relaxation avec les méthodes itératives de relaxation, comme la méthode de surrelaxation successive, qui servent notamment à résoudre des systèmes d'équations linéaires.

Voir aussi

• Relaxation continue
• Relaxation lagrangienne
• Surrelaxation successive
• Conservatisme