0

The dual to the program that defines $y^{}$ is $$\max {c x-f(0) t: A x-t b \leq d,(x, t) \geq 0}$$ Let $\left(x^{}, t^{}\right)$ be the optimal solution this program. By the duality theorem $$c x^{}-f(0) t^{}=d y^{}$$

Let $x^{0}$ be an optimal solution to $(\mathrm{P})$. Choose $\epsilon \leq 1 / t^{}$, when $t^{}=0$, take $\epsilon$ to be any positive number. Consider
$$x=(1-t \epsilon) x^{0}+\epsilon x^{}$$ Since $x \geq 0$ and $A x \leq b+\epsilon d$ it follows that $x$ is a feasible solution to the program that defines $f(\epsilon)$. Hence, \begin{aligned} f(\epsilon) \geq c x &=(1-t \epsilon) c x^{0}+\epsilon c x^{} \ &=(1-t \epsilon) f(0)+\epsilon\left(d y^{}-f(0) t^{}\right)=f(0)+\epsilon d y^{*} \end{aligned}

ECNM10085/ECNM11072 COURSE NOTES ：

\begin{aligned} &\min \left[\max {i} \sum{j=1}^{n}\left(a_{i j} y_{j}\right)\right] \ &\sum_{j=1}^{n} y_{j}=1, \quad y_{j} \geq 0 \end{aligned}
This is not a linear program but can be transformed into one (which we call LPC)
$\min R \quad$ (the mini-max value)
\begin{aligned} &\text { s.t. } \sum_{j=1}^{n}\left(a_{i j} y_{j}\right) \leq R, \ &\sum_{j=1}^{n} y_{j}=1, \quad y_{j} \geq 0 . \end{aligned}