Un ensemble actif est un ensemble de contraintes en optimisation mathématique, en un point donné. Il permet notamment de déterminer quelles contraintes influencent le résultat final.
Définition
En optimisation mathématique, un problème est défini en utilisant une fonction objectif à minimiser ou maximiser, et un ensemble de contraintes :
qui définissent l'espace de solutions admissibles qui est l'ensemble des x à tester afin de trouver la solution optimale. Soit un point admissible, une contrainte
est dite active au point si et inactive au point si Par conséquent, les contraintes d'égalité sont toujours actives. L'ensemble actif (ou active set) au point est l'ensemble des contraintes actives au point courant[1].
L'ensemble actif est particulièrement important en optimisation car il permet de déterminer quelles contraintes influencent le résultat final. Par exemple, en résolvant un problème d'optimisation linéaire, l'ensemble actif fournit les hyperplans qui se croisent au point formant la solution. En optimisation quadratique, comme la solution n'est pas obligatoirement sur l'un des bords du polygone formant la frontière du domaine admissible, une estimation de l'ensemble actif permet d'avoir un sous-ensemble d'inégalités à regarder pour chercher la solution, ce qui réduit la complexité de la recherche.
En général, un algorithme active set a la structure suivante :
- Trouver un point de départ admissible
- répéter jusqu'à « optimisation suffisante » (en observant par exemple les conditions KKT)
- résoudre le problème d'égalité défini par l'active set (approximativement)
- calculer les multiplicateurs de Lagrange de l'active set
- enlever un sous-ensemble de contraintes correspondant aux multiplicateurs de Lagrange négatifs (cela indique en effet que la fonction objectif peut encore être optimisée en rendant inactives les contraintes correspondantes), on enlève les contraintes par ordre du multiplicateur le plus négatif.
- fin répéter
Notes et références