Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 42 / 1 / c

Introduce a free scalar $t$. The epigraph reformulation is the linear programFor each fixed $x$, the smallest feasible $t$ equals the maximum of the affine expressions, so the reformulation preserves the optimum.

Associate nonnegative multipliers $y_i$ with these inequalities. Its optimization Lagrangian isBecause $x$ and $t$ are unrestricted, the infimum is finite precisely when the coefficients of both vanish. Therefore the Lagrangian dual problem isA feasible dual vector is a convex combination of the slopes whose mean slope is zero. It gives a constant lower bound on the maximum of the affine functions. The primal is always feasible, by taking $x=0$ and sufficiently large $t$. If it has a finite optimum, linear programming duality gives attainment and equality with this dual; otherwise the dual is infeasible and the primal is unbounded below.