Lovász extension

For a set function $F:2^{\{1,\dots ,n\}}\to \mathbb{R}$ with $F(\varnothing )=0$, sort the coordinates of $x\in {\mathbb{R}}^n$ as $x_{{\pi }_1}\ge \cdots \ge x_{{\pi }_n}$, and put $S_k=\{{\pi }_1,\dots ,{\pi }_k\}$. The Lovász extension isTies do not affect the result, because equal-coordinate terms telescope. At an indicator vector $1_S$ it gives $f(1_S)=F(S)$, so it extends a discrete objective to a piecewise linear function on a vector space.

For $F(S)=1$ when $S\ne \varnothing$ and zero otherwise, $f(x)={\max }_i{x}_i$. More generally, the extension is a convex function exactly when $F$ is a submodular set function. This equivalence is what makes the construction useful: a diminishing-returns condition on subsets becomes a geometric property on real vectors.^[ref]