Duality in Chebychev approximation I got messed up with this problem and can't find any clue to solve this. Hope some one here can help me.


Let $A$ be an $m \times n$ matrix an let $b$ be a vector in $R^{m}$. We consider the problem of minimizing $||Ax - b||_{\infty}$ over all $x \in R^{n}$. Here $||.||_\infty$ is the vector norm defined by $||y||_\infty = max_{i}|y_{i}|$. Let $v$ be the value of the optimal cost.
    Let $p$ be any vector in $R^{m}$ that satisfies $\sum_{i=1}^{m}|p_{i}| = 1 $ and $p^{T}A = 0$. Show that $p^{T}b \le v$. Here $x,p,b$ is column vectors.


I really appreciate if some one can help me. Thanks
 A: Duality in Chebychev approximation
Consider the problem of minimizing $\| Ax−b \|_\infty$ over all $x \in R^n$. It is equivalent to the following LP:
$$
\begin{array}{ll}
\operatorname{minimize} & t \\
\text {subject to } & -t \mathbf{1} \preceq A x-b \preceq t \mathbf{1}, \; t \geq 0
\end{array}
$$
with variables $x \in \mathrm{R}^n, t \in \mathrm{R}$. Where $\mathbf{1}$ denotes a vector with all components equal to one. To derive the dual problem, introduce Lagrange multipliers $\lambda , \mu \geq 0$ and we obtain the Lagragian:
$$
L(x, t, \lambda, \mu) = t + \lambda^T(-t \mathbf{1} - Ax + b) + \mu^T (Ax - b - t \mathbf{1})
$$
Thus the dual function is:
$$
g(\lambda, \mu) = \inf_{t \geq 0, \, x} L(x, t, \lambda, \mu) = \inf_{t \geq 0, \, x} (1 - \lambda^T \mathbf{1} - \mu^T \mathbf{1})\,t + (-A^T \lambda + A^T \mu)^T x + b^T(\lambda - \mu)
$$
Hence, we obtain the dual problem:
$$
\begin{array}{ll}
\operatorname{maximize} & b^T (\lambda - \mu) \\
\text {subject to } & (\lambda + \mu)^T\mathbf{1} \leq 1 \\
  & A^T (-\lambda + \mu) = 0
\end{array}
$$
Let $y = \lambda - \mu$, since $\lambda, \mu \geq 0$, we have $|y| = \lambda + \mu$. $\;\;$ ($\lambda, \mu$ can not be both positive due to complementary slackness.)
The problem above turns into:
$$
\begin{array}{ll}
\operatorname{maximize} & b^T y \\
\text {subject to } & \sum_{i} |y_i| \leq 1 \\
  & A^T y = 0
\end{array}
$$
Here we notice that the dual of minimizing an infinite norm is also a LP with 1-norm constraint.
