Ensemble actif

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 :

$g_{1}(x)\geq 0,\dots ,g_{k}(x)\geq 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)\geq 0$

est dite 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'ensemble actif (ou active set) au point $x$ est l'ensemble des contraintes $g_{i}(x)$ actives au point courant.

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

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Active set » (voir la liste des auteurs).