= Threshold formula for the sum of the largest components
{title2=$f_k(x)=\min_t\{kt+\sum_i(x_i-t)_+\}$}
For $1\leq k\leq n$, <linear programming duality> gives
$$
f_k(x)=\min_{t\in\mathbb R,\ s\geq0}\left\{kt+\sum_i s_i:s_i+t\geq x_i\right\}
=\min_{t\in\mathbb R}\left\{kt+\sum_i(x_i-t)_+\right\},
$$
where $(\cdot)_+$ is the <positive part of a real-valued function>. To see equality directly, order the coordinates $x_{[1]}\geq\cdots\geq x_{[n]}$ and choose $x_{[k+1]}\leq t\leq x_{[k]}$ for $k<n$, or $t\leq x_{[n]}$ for $k=n$. The threshold expression then equals the <sum of the largest components>. Introducing the variables $s_i$ turns this <convex> piecewise-linear objective into a <linear program>.
Back to article page
