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 | modifier le code]
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 | modifier le code]
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 | modifier le code]
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 | modifier le code]
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 | modifier le code]
- 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 | modifier le code]
- 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.
