Content deleted Content added
Mathreader17 (talk | contribs) Add citation to budget-additive function |
Mathreader17 (talk | contribs) |
||
Line 40:
== Continuous extensions ==
===
For a submodular function <math>f:2^{\Omega}\rightarrow \mathbb{R}</math> with <math>|\Omega|=n</math>, we can associate each <math>S\subseteq \Omega</math> with a binary vector <math>x^{S}\in \{0, 1\}^{n}</math> such that <math>x_{i}^{S}=1</math> when <math>i\in S</math>, and <math>x_{i}^{S}=0</math> otherwise. In this sense, the submodular function can be seen as a function defined on <math>\{0, 1\}^{n}</math>. We can then define the continuous [[Restriction_(mathematics)#Extension_of_a_function|extension]] of <math>f</math> to be any continuous function <math>F:\mathbb{R}^{n}\rightarrow \mathbb{R}</math> such that it matches the value of the submodular function on <math>x\in \{0, 1\}^{n}</math>, i.e. <math>F(x^{S})=f(S)</math>. Some commonly used continuous extensions are as follows.
===
==== Lovász extension ====
This extension is named after mathematician [[László Lovász]].<ref name="L" /> Consider any vector <math>\mathbf{x}=\{x_1,x_2,\dots,x_n\}</math> such that each <math>0\leq x_i\leq 1</math>. Then the Lovász extension is defined as <math>f^L(\mathbf{x})=\mathbb{E}(f(\{i|x_i\geq \lambda\}))</math> where the expectation is over <math>\lambda</math> chosen from the [[uniform distribution (continuous)|uniform distribution]] on the interval <math>[0,1]</math>. The Lovász extension is a convex function if and only if <math>f</math> is a submodular function.
==== Multilinear extension ====
Consider any vector <math>\mathbf{x}=\{x_1,x_2,\ldots,x_n\}</math> such that each <math>0\leq x_i\leq 1</math>. Then the multilinear extension is defined as <math>F(\mathbf{x})=\sum_{S\subseteq \Omega} f(S) \prod_{i\in S} x_i \prod_{i\notin S} (1-x_i)</math>.
==== Convex closure ====
Consider any vector <math>\mathbf{x}=\{x_1,x_2,\dots,x_n\}</math> such that each <math>0\leq x_i\leq 1</math>. Then the convex closure is defined as <math>f^-(\mathbf{x})=\min\left(\sum_S \alpha_S f(S):\sum_S \alpha_S 1_S=\mathbf{x},\sum_S \alpha_S=1,\alpha_S\geq 0\right)</math>. The convex closure of any set function is convex over <math>[0,1]^n</math>. It can be shown that <math>f^L(\mathbf{x})=f^-(\mathbf{x})</math> for submodular functions.
==== Concave closure ====
Consider any vector <math>\mathbf{x}=\{x_1,x_2,\dots,x_n\}</math> such that each <math>0\leq x_i\leq 1</math>. Then the concave closure is defined as <math>f^+(\mathbf{x})=\max\left(\sum_S \alpha_S f(S):\sum_S \alpha_S 1_S=\mathbf{x},\sum_S \alpha_S=1,\alpha_S\geq 0\right)</math>.
| |||