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

${\displaystyle f(X\cap Y)+f(X\cup Y)\leq f(X)+f(Y).}$

Les fonctions sous-modulaires peuvent être vues comme l'analogue discret des fonctions convexes^[1].

Définition

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

${\displaystyle f(X\cap Y)+f(X\cup Y)\leq f(X)+f(Y).}$

Une définition équivalente est que pour tout ${\displaystyle X,Y\subseteq E}$ avec ${\displaystyle X\subseteq Y}$ et tout ${\displaystyle x\in E\backslash Y}$ on a : ${\displaystyle f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)}$. Cette définition est parfois appelée loi des rendements décroissants, notamment dans l'application à l'économie^[2].

Exemples

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

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

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

• Alexander Schrijver, « A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time », J. Comb. Theory, Ser. B, vol. 80, n^o 2,‎ 2000, p. 346-355

Notes et références

1. László Lovász, « Submodular functions and convexity », Mathematical Programming The State of the Art,‎ 1983, p. 235-257 (lire en ligne)
2. Andreas Krause et Daniel Golovin, « Submodular Function Maximization », sur École polytechnique fédérale de Zurich, 2012.
3. Alexander Schrijver, « A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time », J. Comb. Theory, Ser. B, vol. 80, n^o 2,‎ 2000, p. 346-355
4. George L Nemhauser, Laurence A Wolsey et Marshall L Fisher, « An analysis of approximations for maximizing submodular set functions—I », Mathematical Programming, vol. 14, n^o 1,‎ 1978, p. 265-294.