submodulaire

Submodulaire is a term used in mathematics, particularly in the field of discrete optimization and game theory, to describe a certain type of function. A function f defined on a set of subsets of a ground set is called submodular if it satisfies a property of diminishing returns.

More formally, let X be a ground set, and let 2^X be the power set of X, meaning the set of all possible subsets of X. A function f: 2^X -> R (where R is the set of real numbers) is submodular if for any two subsets A and B of X, the following inequality holds: f(A U B) + f(A ∩ B) <= f(A) + f(B). This inequality captures the idea that the marginal gain of adding an element to a larger set is less than or equal to the marginal gain of adding it to a smaller set.

This property has significant implications. For instance, submodular functions are often associated with problems that exhibit a structure where adding more resources or features yields progressively smaller improvements. This makes them amenable to efficient algorithms, particularly for minimization problems. Many combinatorial optimization problems, such as the set cover problem or facility location problems, can be formulated using submodular functions.

In machine learning, submodular functions are used in tasks like feature selection, summarization, and active learning, where the goal is to select a diverse and informative subset of items. The concept also extends to continuous functions, but the most common usage refers to set functions.