Active set

En optimisation mathématique, un problème est défini en utilisant une fonction objectif à minimiser ou maximiser, et un ensemble de contraintes :

$g_1(x)\ge 0, \dots, g_k(x)\ge 0$

qui définissent l'espace de solutions admissibles qui est l'ensemble des x à tester afin de trouver la solution optimale. Soit un point x admissible, une contrainte

$g_i(x) \ge 0$

est dite active active au point x si g_i(x) = 0 et inactive au point x si g_i(x) > 0. Par conséquent, les contraintes d'égalité sont toujours actives. L'active set au point x est l'ensemble des contraintes g_i(x) actives au point courant (Nocedal & Wright 2006, pg 308).

L'active set 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 de programmation linéaire, l'active set 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'active set nous 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 Multiplicateur 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