Fonction sous-modulaire
En optimisation combinatoire, les fonctions sous-modulaires sont des fonctions d'ensemble particulières.
Soient E un ensemble et f une fonction qui à tout sous-ensemble X de E associe un réel f(X), on dit que f est sous-modulaire si l'inégalité suivante est vérifiée pour tous sous-ensembles X et Y de E
Les fonctions sous-modulaires peuvent être vues comme l'analogue discret des fonctions convexes[1].
Définition modifier
Soient E un ensemble et f une fonction qui à tout sous-ensemble X de E associe un réel f(X), on dit que f est sous-modulaire si l'inégalité suivante est vérifiée pour tous sous-ensembles X et Y de E
Une définition équivalente est que pour tout avec et tout on a : . Cette définition est parfois appelée loi des rendements décroissants, notamment dans l'application à l'économie[2].
Exemples modifier
Des exemples de fonctions sous-modulaires sont les fonctions de rang des matroïdes, ou en théorie des graphes la fonction qui associe à tout sous-ensemble de sommets d'un graphe la cardinalité de sa coupe[3]. On trouve aussi des exemples en théorie de l'information, comme l'entropie de Shannon, ou dans la théorie des probabilités.
Aspects algorithmiques modifier
Le résultat important en algorithmique à propos des fonctions sous-modulaires est le suivant :
- On peut minimiser une fonction sous-modulaire en temps (fortement) polynomial[3].
Un cas particulier est le calcul de la coupe minimum d'un graphe.
A contrario, la maximisation d'une fonction sous-modulaire définit un problème de décision NP-complet, mais sa résolution via un algorithme glouton fournit un algorithme d'approximation[4]. Le problème de couverture maximale est un exemple de telle maximisation.
Utilisations modifier
Ce type de fonction apparait en apprentissage automatique. Par exemple, en sélection de caractéristique, étant donné des données de grande dimension, on cherche à trouver un petit ensemble de variables qui soit les plus pertinentes, et cette pertinence peut parfois être représentée par une fonction sous-modulaire.
Bibliographie modifier
- Alexander Schrijver, « A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time », J. Comb. Theory, Ser. B, vol. 80, no 2, , p. 346-355
Notes et références modifier
- László Lovász, « Submodular functions and convexity », Mathematical Programming The State of the Art, , p. 235-257 (lire en ligne)
- Andreas Krause et Daniel Golovin, « Submodular Function Maximization », sur École polytechnique fédérale de Zurich, .
- Alexander Schrijver, « A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time », J. Comb. Theory, Ser. B, vol. 80, no 2, , p. 346-355
- George L Nemhauser, Laurence A Wolsey et Marshall L Fisher, « An analysis of approximations for maximizing submodular set functions—I », Mathematical Programming, vol. 14, no 1, , p. 265-294.
