Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 46:
=== 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 ===
Line 54 ⟶ 58:
=== 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>. === Concave closure ===
| |||