= Solution
Substitute the <dual linear program> from the previous part and optimize jointly over $x,t,s$. The result is
$$
\boxed{
\begin{aligned}
\operatorname{minimize}\quad&kt+\sum_{i=1}^n s_i\\
\text{over}\quad&x\in\mathbb R^n,\ t\in\mathbb R,\ s\in\mathbb R^n\\
\text{subject to}\quad&Ax=b,\\
&s_i\geq0,\quad s_i+t\geq x_i\quad(1\leq i\leq n).
\end{aligned}}
$$
The 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.
Back to article page
