Threshold formula for the sum of the largest components ($f_k(x)={\min }_t\{kt+{\sum }_i(x_i-t{)}_{+}\}$)

For $1\le k\le n$, linear programming duality giveswhere $(\cdot {)}_{+}$ is the positive part of a real-valued function. To see equality directly, order the coordinates $x_{[1]}\ge \cdots \ge x_{[n]}$ and choose $x_{[k+1]}\le t\le x_{[k]}$ for $k<n$, or $t\le 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.