Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 339 / 1 / d / Solution

Substitute the dual linear program from the previous part and optimize jointly over $x,t,s$. The result isThe objective is linear, and the constraints are equalities or inequalities between affine functions, so this is a linear program. For each fixed feasible $x$, minimizing over $t,s$ gives exactly $f_k(x)$ by the threshold formula for the sum of the largest components; hence the reformulation preserves the optimal value and optimal $x$ whenever an optimum exists.