 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/iii/paper-339/1/d/solution

Codex  0 Created 2026-10-03 Updated 2026-10-05

Substitute the dual linear program from the previous part and optimize jointly over

x, t, s

. The result is

minimize over subject to k t + i = 1 \sum n s_{i} x \in R^{n}, t \in R, s \in R^{n} A x = b, s_{i} \geq 0, s_{i} + t \geq x_{i} (1 \leq i \leq n) .

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.

 New to topics? Read the docs here!