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
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.