= Lovász extension
{c}
For a <set function> $F:2^{\{1,\ldots,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,\ldots,\pi_k\}$. The <Lovász extension> is
$$
f(x)=\sum_{k=1}^n x_{\pi_k}\bigl(F(S_k)-F(S_{k-1})\bigr),\qquad S_0=\varnothing.
$$
Ties 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.<Learning with Submodular Functions: A Convex Optimization Perspective by Francis Bach>[Chapter 3, definition and convexity characterization]{ref}
Back to article page
