Supermodular function: Difference between revisions

Revision as of 21:29, 12 December 2024

Latest revision as of 01:51, 24 May 2025

(4 intermediate revisions by 3 users not shown)

Line 2:

In mathematics, a '''supermodular function''' is a function on a [[Lattice (order)|lattice]] that, informally, has the property of being characterized by "increasing differences." Seen from the point of [[Set function|set functions]], this can also be viewed as a relationship of "increasing returns", where adding more elements to a subset increases its valuation. In [[economics]], supermodular functions are often used as a formal expression of complementarity in preferences among goods. Supermodular functions are studied and have applications in [[game theory]], [[economics]], [[Lattice (order)|lattice theory]], [[combinatorial optimization]], and [[machine learning]].

=== Definition ===

Let <math>(X, \preceq)</math> be a [[Lattice (order)|lattice]]. A real-valued function <math>f: X \rightarrow \mathbb{R}</math> is called '''supermodular''' if

<math>f(x \vee y) + f(x \wedge y) \geq f(x) + f(y)</math>

for all <math>x, y \in X</math> .<ref>{{Cite book |title=Supermodularity and complementarity |date=1998 |publisher=Princeton University Press |isbn=978-0-691-03244-3 |editor-last=Topkis |editor-first=Donald M. |series=Frontiers of economic research |___location=Princeton, N.J}}</ref>.

If the inequality is strict, then <math>f</math> is '''strictly supermodular''' on <math>X</math>. If <math>-f</math> is (strictly) supermodular then ''f'' is called ('''strictly) submodular'''. A function that is both submodular and supermodular is called '''modular'''. This corresponds to the inequality being changed to an equality.

Line 39:

=== Definition ===

Let <math>S</math> be a finite set. A set function <math>f: 2^S \to \mathbb{R}</math> is '''supermodular''' if it satifies the following (equivalent) conditions:<ref>{{Citation |last=McCormick |first=S. Thomas |title=Discrete Optimization |chapter=Submodular Function Minimization |date=2005 |workseries=Handbooks in Operations Research and Management Science |volume=12 |pages=321–391 |chapter-url=https://linkinghub.elsevier.com/retrieve/pii/S0927050705120076 |access-date=2024-12-12 |publisher=Elsevier |language=en |doi=10.1016/s0927-0507(05)12007-6. |isbn=978-0-444-51507-0}}</ref>:

# <math> f(A)+f(B) \leq f(A \cap B) + f(A \cup B) </math> for all <math> A, B \subseteq S </math>.

# <math> f(A \cup \{v\}) - f(A) \geqleq f(B \cup \{v\}) - f(B) </math> for all <math> A \subset B \subset V </math>, where <math> v \notin B </math>.

A set function <math>f</math> is submodular if <math>-f</math> is supermodular, and modular if it is both supermodular and submodular.

Line 52:

== Optimization Techniques ==

There are specialized techniques for optimizing submodular functions. Theory and enumeration algorithms for finding local and global maxima (minima) of submodular (supermodular) functions can be found in "Maximization of submodular functions: Theory and enumeration algorithms", B. Goldengorin.<ref>{{Cite journal |last=Goldengorin |first=Boris |date=2009-10-01 |title=Maximization of submodular functions: Theory and enumeration algorithms |url=https://www.sciencedirect.com/science/article/pii/S0377221708007418 |journal=European Journal of Operational Research |language=en |volume=198 |issue=1 |pages=102–112 |doi=10.1016/j.ejor.2008.08.022 |issn=0377-2217|url-access=subscription }}</ref>

==See also==